Preprint A677/2010
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.