On the cost of solving augmented Lagrangian subproblems

• 成果类型: Article
• 署名作者: Fernandez, Damian; Solodov, Mikhail
• 署名单位: Consejo Nacional de Investigaciones Cientificas y Tecnicas (CONICET); National University of Cordoba; National University of Cordoba
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01384-1
• 发表日期: 2020
• 页码: 37-55
• 关键词: local convergence; multipliers; STABILITY

摘要

At each iteration of the augmented Lagrangian algorithm, a nonlinear subproblem is being solved. The number of inner iterations (of some/any method) needed to obtain a solution of the subproblem, or even a suitable approximate stationary point, is in principle unknown. In this paper we show that to compute an approximate stationary point sufficient to guarantee local superlinear convergence of the augmented Lagrangian iterations, it is enough to solve two quadratic programming problems (or two linear systems in the equality-constrained case). In other words, two inner Newtonian iterations are sufficient. To the best of our knowledge, such results are not available even under the strongest assumptions (of second-order sufficiency, strict complementarity, and the linear independence constraint qualification). Our analysis is performed under second-order sufficiency only, which is the weakest assumption for obtaining local convergence and rate of convergence of outer iterations of the augmented Lagrangian algorithm. The structure of the quadratic problems in question is related to the stabilized sequential quadratic programming and to second-order corrections.