On the complexity of an augmented Lagrangian method for nonconvex optimization.

In this paper we study the worst-case complexity of an inexact augmented Lagrangian method for nonconvex constrained problems. Assuming that the penalty parameters are bounded we prove a complexity bound of |$\mathcal{O}(|\log (\epsilon)|)$| outer iterations for the referred algorithm to generate an |$\epsilon$| -approximate KKT point for |$\epsilon \in (0,1)$|⁠. When the penalty parameters are unbounded we prove an outer iteration complexity bound of |$\mathcal{O}(\epsilon ^{-2/(\alpha -1)})$|⁠ , 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 ^{-2})$| and |$\mathcal{O}(\epsilon ^{- (\frac{2(2+\alpha)}{\alpha -1}+2)})$|⁠ , respectively, when appropriate first-order methods (⁠|$p=1$|⁠) are used to approximately solve the unconstrained subproblems at each iteration. In the case of problems having only linear equality constraints the latter bounds are improved to |$\mathcal{O}(|\log (\epsilon)|^{2}\epsilon ^{-(p+1)/p})$| and |$\mathcal{O}(\epsilon ^{-(\frac{4}{\alpha -1}+\frac{p+1}{p})})$|⁠ , respectively, when appropriate |$p$| -order methods (⁠|$p\geq 2$|⁠) are used as inner solvers. [ABSTRACT FROM AUTHOR]