On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization

Geovani N. Grapiglia, Ya-xiang Yuan

Published 2019-06-13Version 1

In this paper we study the worst-case complexity of an inexact Augmented Lagrangian method for nonconvex inequality-constrained problems. Assuming that the penalty parameters are bounded, we prove a complexity bound of $\mathcal{O}(|\log(\epsilon)|)$ iterations for the referred algorithm generate an $\epsilon$-approximate KKT point, for $\epsilon\in (0,1)$. When the penalty parameters are unbounded, we prove an iteration complexity bound of $\mathcal{O}\left(\epsilon^{-2/(\alpha-1)}\right)$, where $\alpha>1$ controls the rate of increase of the penalty parameters. For linearly constrained problems, these bounds yield to evaluation complexity bounds of $\mathcal{O}(|\log(\epsilon)|^{2}\epsilon^{-(p+1)/p})$ and $\mathcal{O}\left(\epsilon^{-\left(\frac{4}{\alpha-1}+\frac{p+1}{p}\right)}\right)$, respectively, when suitable $p$-order methods ($p\geq 2$) are used to approximately solve the unconstrained subproblems at each iteration of our Augmented Lagrangian scheme.