Local convergence of exact and inexact augmented Lagrangian methods under the second-order sufficient optimality condition

Mikhail Solodov | Fernández, Damián

Keywords: Augmented Lagrangian; method of multipliers

We establish local convergence and rate of convergence of the classical augmented Lagrangian algorithm under the sole assumption that the dual starting point is close to a multiplier satisfying the second-order sufficient optimality condition. In particular, no constraint qualifications of any kind are needed. Previous literature on the subject required, in addition, the linear independence constraint qualification and either the strict complementarity assumption or a stronger version of the second-order sufficient condition. That said, the classical results allow the initial multiplier estimate to be far from the optimal one, at the expense of proportionally increasing the threshold value for the penalty parameters. Although our primary goal is to avoid constraint qualifications, if the stronger assumptions are introduced then starting points far from the optimal multiplier are allowed within our analysis as well. Using only the second-order sufficient optimality condition, for penalty parameters large enough we prove primal-dual $Q$-linear convergence rate, which becomes superlinear if the parameters are allowed to go to infinity. Both exact and inexact solutions of subproblems are considered. In the exact case, we further show that the primal convergence rate is of the same $Q$-order as the primal-dual rate. Previous assertions for the primal sequence all had to do with the the weaker $R$-rate of convergence and required the stronger assumptions cited above. Finally, we show that under our assumptions one of the popular rules of controlling the penalty parameters ensures their boundedness.

Anexos:

• r2.pdf