An algorithmic framework for MINLP with separable non-convexity

Global optimization algorithms, e.g., spatial branch-and-bound approaches like those implemented in codes such as BARON and COUENNE, have had substantial success in tackling complicated, but generally small scale, non-convex MINLPs (i.e., mixed-integer nonlinear programs having non-convex continuous relaxations). Because they are aimed at a rather general class of problems, the possibility remains that larger instances … Read more

A Matrix-free Algorithm for Equality Constrained Optimization Problems with Rank-deficient Jacobians

We present a line search algorithm for large-scale constrained optimization that is robust and efficient even for problems with (nearly) rank-deficient Jacobian matrices. The method is matrix-free (i.e., it does not require explicit storage or factorizations of derivative matrices), allows for inexact step computations, and is applicable for nonconvex problems. The main components of the … Read more

On the Implementation of an Interior-Point Filter Line-Search Algorithm for Large-Scale Nonlinear Programming

We present a primal-dual interior-point algorithm with a filter line-search method for nonlinear programming. Local and global convergence properties of this method were analyzed in previous work. Here we provide a comprehensive description of the algorithm, including the feasibility restoration phase for the filter method, second-order corrections, and inertia correction of the KKT matrix. Heuristics … Read more

SIAG/Opt Views-and-News Vol 14 No 1

SIAM’s SIAG/Opt Newsletter special issue on Large Scale Nonconvex Optimization. Guest editors Sven Leyffer and Jorge Nocedal, with contributions by Gould, Sachs, Biegler, Waechter, Leyffer, Bussieck and Pruessner. Citation SIAG/Opt Views-and-News, Volume 14 Number 1, April 2003. Article Download View SIAG/Opt Views-and-News Vol 14 No 1

A Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties.

An exact-penalty-function-based scheme—inspired from an old idea due to Mayne and Polak (Math. Prog., vol.~11, 1976, pp.~67–80)—is proposed for extending to general smooth constrained optimization problems any given feasible interior-point method for inequality constrained problems. It is shown that the primal-dual interior-point framework allows for a simpler penalty parameter update rule than that discussed and … Read more

Global and Local Convergence of Line Search Filter Methods for Nonlinear Programming

Line search methods for nonlinear programming using Fletcher and Leyffer’s filter method, which replaces the traditional merit function, are proposed and their global and local convergence properties are analyzed. Previous theoretical work on filter methods has considered trust region algorithms and only the question of global convergence. The presented framework is applied to barrier interior … Read more

Failure of Global Convergence for a Class of Interior Point Methods for Nonlinear Programming

Using a simple analytical example, we demonstrate that a class of interior point methods for general nonlinear programming, including some current methods, is not globally convergent. It is shown that those algorithms do produce limit points that are neither feasible nor stationary points of some measure of the constraint violation, when applied to a well-posed … Read more