A one-phase interior point method for nonconvex optimization
arXiv:1801.03072
Abstract
The work of Wachter and Biegler suggests that infeasible-start interior point methods (IPMs) developed for linear programming cannot be adapted to nonlinear optimization without significant modification, i.e., using a two-phase or penalty method. We propose an IPM that, by careful initialization and updates of the slack variables, is guaranteed to find a first-order certificate of local infeasibility, local optimality or unboundedness of the (shifted) feasible region. Our proposed algorithm differs from other IPM methods for nonconvex programming because we reduce primal feasibility at the same rate as the barrier parameter. This gives an algorithm with more robust convergence properties and closely resembles successful algorithms from linear programming. We implement the algorithm and compare with IPOPT on a subset of CUTEst problems. Our algorithm requires a similar median number of iterations, but fails on only 9% of the problems compared with 16% for IPOPT. Experiments on infeasible variants of the CUTEst problems indicate superior performance for detecting infeasibility. The code for our implementation can be found at https://github.com/ohinder/OnePhase .
fixed typo in sign of dual multiplier in KKT system
References in corpus (2)
Cited by in corpus (4)
- A primal-dual interior-point relaxation method with global and rapidly local convergence for nonlinear programs
- On the behavior of Lagrange multipliers in convex and non-convex infeasible interior point methods
- Worst-case iteration bounds for log barrier methods on problems with nonconvex constraints
- Primal-Dual Interior-Point Methods for Domain-Driven Formulations