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

Autor(es)

Haeser, Gabriel ^{[1, 2]} ; Hinder, Oliver ^[2] ; Ye, Yinyu ^[2]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Math & Stat, Dept Appl Math, Sao Paulo, SP - Brazil

^[2] Stanford Univ, Dept Management Sci & Engn, Stanford, CA 94305 - USA

• Tipo de documento: Artigo Científico
• Fonte: MATHEMATICAL PROGRAMMING; v. 186, n. 1-2, p. 257-288, MAR 2021.
• Citações Web of Science: 0

Resumo

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. (AU)

• Processo FAPESP: 16/02092-8 - Informação de segunda-ordem em otimização não linear
• Beneficiário: Gabriel Haeser
• Modalidade de apoio: Bolsas no Exterior - Pesquisa
• Processo FAPESP: 13/05475-7 - Métodos computacionais de otimização
• Beneficiário: Sandra Augusta Santos
• Modalidade de apoio: Auxílio à Pesquisa - Temático