On the behavior of Lagrange multipliers in convex and nonconvex infeasible interior point methods

• 成果类型: Article
• 署名作者: Haeser, Gabriel; Hinder, Oliver; Ye, Yinyu
• 署名单位: Universidade de Sao Paulo; Stanford University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01454-4
• 发表日期: 2021
• 页码: 257-288
• 关键词: constraint qualification; homogeneous algorithm; optimality condition; GLOBAL CONVERGENCE; implementation; optimization

摘要

We analyze sequences generated by interior point methods (IPMs) in convex and nonconvex settings. We prove that moving the primal feasibility at the same rate as the barrier parameter mu ensures the Lagrange multiplier sequence remains bounded, provided the limit point of the primal sequence has a Lagrange multiplier. This result does not require constraint qualifications. We also guarantee the IPM finds a solution satisfying strict complementarity if one exists. On the other hand, if the primal feasibility is reduced too slowly, then the algorithm converges to a point of minimal complementarity; if the primal feasibility is reduced too quickly and the set of Lagrange multipliers is unbounded, then the norm of the Lagrange multiplier tends to infinity. Our theory has important implications for the design of IPMs. Specifically, we show that IPOPT, an algorithm that does not carefully control primal feasibility has practical issues with the dual multipliers values growing to unnecessarily large values. Conversely, the one-phase IPM of Hinder and Ye (A one-phase interior point method for nonconvex optimization, 2018. arXiv:1801.03072), an algorithm that controls primal feasibility as our theory suggests, has no such issue.