Characterizing the Rate of Convergence of the Augmented Lagrange Method for Nonlinear Programming

Abstract

The rate of convergence of the augmented Lagrangian method for solving nonlinear programming is studied under the Jacobian uniqueness conditions. It is demonstrated that, for a given multiplier vector $(\mu, \lambda)$, the rate of convergence of the augmented Lagrangian method is linear with respect to $\| (\mu, \lambda) - (\mu^{*}, \lambda^{*}) \|$ and the ratio constant is proportional to $1/c$ when the ratio $\| (\mu, \lambda)-(\mu^{*}, \lambda^{*}) \| /c$ is small enough, where $c$ is the penalty parameter that exceeds a threshold $c^{*} > 0$ and $(\mu^{*}, \lambda^{*})$ is the multiplier corresponding to a local minimum point. Importantly, the ratio constant of the $Q$-linear convergence of the sequence of multiplier vectors is estimated by the second-order derivative of the value function of the nonlinear optimization problem. This characterization gives an explicit expression for the rate constant of the $Q$-linear convergence of the sequence of multiplier vectors.