Nonlinear Optimization

A branch-and-bound algorithm for the computation of optimal point mappings of parametric optimization problems

Categories Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

We propose a novel branch‑and‑bound algorithm that constructs rigorous outer approximations of the optimal point mapping for parametric optimization problems with guaranteed feasibility and optimality tolerances. The method uses the improvement‑function reformulation to define discarding and inclusion tests on sub-boxes, constructing a rigorous outer approximation. Under the same regularity conditions that ensure exactness of this … Read more

A sufficient convergence condition for generalized Benders decomposition with general dual functions

Categories (Mixed) Integer Linear Programming, Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , ,

We revisit the framework of generalized Benders decomposition over a compact but non-finite master domain. We show by counterexample that strong general dual functions alone may fail to guarantee convergence. We then define a condition of uniform local strongness and prove that strong general dual functions satisfying this condition guarantee finite \(\epsilon\)-termination. Finally, we show … Read more

A Computational Toolbox for Linear Optimization with Joint Affine Chance Constraints

Categories Constrained Nonlinear Optimization, Linear Programming, Optimization Software Benchmark Tags , , , ,

We present a Julia computational toolbox for linear optimization problems with joint affine chance constraints under elliptically symmetric uncertainty. The toolbox combines a spherical–radial oracle for estimating the joint probability and its gradient with three structured optimization methods: Proximal, Feasible, and Penalty. The oracle supports several elliptically symmetric distributions and is integrated with these methods … Read more

New adaptive proximal gradient algorithms for solving multiobjective composite optimization problems

Categories Nonlinear Optimization, Nonsmooth Optimization, Robust Optimization Tags , , , ,

In this paper, we propose new adaptive proximal gradient algorithms to solve multiobjective optimization problems, where each objective function is the sum of a differentiable function and a proper, closed, convex function. Utilizing the local behavior of the differentiable terms we propose new adaptive ways to select stepsizes used in proximal gradient scheme. In particular, … Read more

Solution of Binary-Constrained Quadratic-Defined Optimization Problems by a Progressive Integer Programming Method

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , , ,

Extending a classic result of Giannessi and Tomasin [\textit{Lecture Notes in Comput. Sci. 3}, Springer, 1973, pp. 437–449], this paper shows that a binary-constrained quadratic-defined optimization problem can be formulated as a binary-constrained linear program with linear complementarity constraints (Bi-LPCC). The term “quadratic-defined problems” encompasses many problems that are defined by quadratic functions in the … Read more

Two-stage approach for the predispatch problem with uncertain demand using splitting variables in interior-point methods

Categories Applications - Science and Engineering, Quadratic Programming, Stochastic Programming Tags , , ,

The stochastic predispatch optimal power flow problem aims to minimize generation costs and transmission losses subject to network constraints under demand uncertainty. We formulate it as a two-stage stochastic quadratic optimization problem with fixed recourse, in which hydroelectric generation constitutes the here-and-now decision, while thermal generation and transmission flows are recourse decisions. Using a splitting-variable … Read more

The best approximation tuple: an extension of the Cheney-Goldstein algorithm and results to the multiple sets case

Categories Convex Optimization, Global Optimization, Nonlinear Optimization Tags , , , , , ,

We extend the algorithm and several results published in the celebrated 1959 paper of Cheney and Goldstein about the best approximation pair (BAP) problem in two separate directions. One is, for the first time, the ability to consider more than two sets, a task which has been in the mind of researchers for many years … Read more

Integer quadratic programming in fixed dimension is polynomial-time solvable

Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Quadratic Programming Tags , ,

We give a deterministic polynomial-time algorithm for integer quadratic programming in every fixed dimension: it minimizes an arbitrary rational quadratic exactly over the integer points of a rational polyhedron, or certifies infeasibility or integer unboundedness. The core is a sign test that decides whether \(d^{\mathsf{T}}Qd\ge 0\) for every integer point \(d\) of a bounded symmetric … Read more

Unshackling Column Generation for Linearized Unconstrained Binary Quadratic Programs

Categories Integer Programming, Linear Programming, Nonlinear Optimization Tags , , ,

When linearizing binary quadratic programs, the most usual way is to replace bilinear products with additional variables constrained to take on consistent values in any feasible solution. In this setting, column generation is a principally desirable solution technique, for instance because the number of such additional linearization variables may be large while many of them … Read more

A Proximal Approach for Nonsmooth Composite-Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , ,

We propose a proximal-type algorithm for nonsmooth and nonconvex optimization problems with composite constraints. The constraint is defined by the composition of a locally upper-\(C^2\) outer function with a locally Lipschitz continuous inner mapping. The method is based on an improvement function that balances objective decrease and constraint satisfaction, and on a surrogate model obtained … Read more