publication . Preprint . 2018

A one-phase interior point method for nonconvex optimization

Hinder, Oliver; Ye, Yinyu;
Open Access English
  • Published: 09 Jan 2018
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 rob...
Subjects
free text keywords: Mathematics - Optimization and Control
Download from
42 references, page 1 of 3

[1] P. R. Amestoy, I. S. Du , and J.-Y. L'Excellent. Mumps multifrontal massively parallel solver version 2.0. 1998.

[2] E. D. Andersen and Y. Ye. A computational study of the homogeneous algorithm for large-scale convex optimization. Computational Optimization and Applications, 10(3):243{269, 1998.

[3] E. D. Andersen and Y. Ye. On a homogeneous algorithm for the monotone complementarity problem. Mathematical Programming, 84(2):375{399, 1999.

[4] H. Y. Benson, D. F. Shanno, and R. J. Vanderbei. Interior-point methods for nonconvex nonlinear programming: jamming and numerical testing. Mathematical programming, 99(1):35{48, 2004.

[5] J. R. Bunch and B. N. Parlett. Direct methods for solving symmetric inde nite systems of linear equations. SIAM Journal on Numerical Analysis, 8(4):639{655, 1971. [OpenAIRE]

[6] R. H. Byrd, J. Nocedal, and R. A. Waltz. Knitro: An integrated package for nonlinear optimization. In Large-scale nonlinear optimization, pages 35{59. Springer, 2006.

[7] L. Chen and D. Goldfarb. Interior-point l2-penalty methods for nonlinear programming with strong global convergence properties. Mathematical Programming, 108(1):1{36, 2006.

[8] F. E. Curtis. A penalty-interior-point algorithm for nonlinear constrained optimization. Mathematical Programming Computation, 4(2):181{209, 2012.

[9] E. D. Dolan and J. J. More. Benchmarking optimization software with performance pro les. Mathematical programming, 91(2):201{213, 2002.

[10] M. Doyle. A barrier algorithm for large nonlinear optimization problems. PhD thesis, Stanford, 2003.

[11] A. V. Fiacco and G. P. McCormick. Nonlinear programming: sequential unconstrained minimization techniques. SIAM, 1990.

[12] R. Fletcher and S. Ley er. Nonlinear programming without a penalty function. Mathematical programming, 91(2):239{269, 2002.

[13] M. Gertz, J. Nocedal, and A. Sartenar. A starting point strategy for nonlinear interior methods. Applied mathematics letters, 17(8):945{952, 2004.

[14] P. E. Gill, M. A. Saunders, and J. R. Shinnerl. On the stability of cholesky factorization for symmetric quaside nite systems. SIAM Journal on Matrix Analysis and Applications, 17(1):35{46, 1996.

[15] P. E. Gill, M. A. Saunders, and E. Wong. On the performance of SQP methods for nonlinear optimization. In Modeling and Optimization: Theory and Applications, pages 95{123. Springer, 2015.

42 references, page 1 of 3
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 rob...
Subjects
free text keywords: Mathematics - Optimization and Control
Download from
42 references, page 1 of 3

[1] P. R. Amestoy, I. S. Du , and J.-Y. L'Excellent. Mumps multifrontal massively parallel solver version 2.0. 1998.

[2] E. D. Andersen and Y. Ye. A computational study of the homogeneous algorithm for large-scale convex optimization. Computational Optimization and Applications, 10(3):243{269, 1998.

[3] E. D. Andersen and Y. Ye. On a homogeneous algorithm for the monotone complementarity problem. Mathematical Programming, 84(2):375{399, 1999.

[4] H. Y. Benson, D. F. Shanno, and R. J. Vanderbei. Interior-point methods for nonconvex nonlinear programming: jamming and numerical testing. Mathematical programming, 99(1):35{48, 2004.

[5] J. R. Bunch and B. N. Parlett. Direct methods for solving symmetric inde nite systems of linear equations. SIAM Journal on Numerical Analysis, 8(4):639{655, 1971. [OpenAIRE]

[6] R. H. Byrd, J. Nocedal, and R. A. Waltz. Knitro: An integrated package for nonlinear optimization. In Large-scale nonlinear optimization, pages 35{59. Springer, 2006.

[7] L. Chen and D. Goldfarb. Interior-point l2-penalty methods for nonlinear programming with strong global convergence properties. Mathematical Programming, 108(1):1{36, 2006.

[8] F. E. Curtis. A penalty-interior-point algorithm for nonlinear constrained optimization. Mathematical Programming Computation, 4(2):181{209, 2012.

[9] E. D. Dolan and J. J. More. Benchmarking optimization software with performance pro les. Mathematical programming, 91(2):201{213, 2002.

[10] M. Doyle. A barrier algorithm for large nonlinear optimization problems. PhD thesis, Stanford, 2003.

[11] A. V. Fiacco and G. P. McCormick. Nonlinear programming: sequential unconstrained minimization techniques. SIAM, 1990.

[12] R. Fletcher and S. Ley er. Nonlinear programming without a penalty function. Mathematical programming, 91(2):239{269, 2002.

[13] M. Gertz, J. Nocedal, and A. Sartenar. A starting point strategy for nonlinear interior methods. Applied mathematics letters, 17(8):945{952, 2004.

[14] P. E. Gill, M. A. Saunders, and J. R. Shinnerl. On the stability of cholesky factorization for symmetric quaside nite systems. SIAM Journal on Matrix Analysis and Applications, 17(1):35{46, 1996.

[15] P. E. Gill, M. A. Saunders, and E. Wong. On the performance of SQP methods for nonlinear optimization. In Modeling and Optimization: Theory and Applications, pages 95{123. Springer, 2015.

42 references, page 1 of 3
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue