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 O(|log(ε)|) outer iterations for the referred algorithm to generate an ε-approximate KKT point, for ε∈ (0,1). When the penalty parameters are unbounded, we prove an outer iteration complexity bound of Oleft(ε-2/(α-1)right), where α>1 controls the rate of increase of the penalty parameters. For linearly constrained problems, these bounds yield to evaluation complexity bounds of O(|log(ε)|2ε-2) and Oleft(ε^-left(frac2(2+α)α-1+2right)right), 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 O(|log(ε)|2ε-(p+1)/p) and Oleft(ε^-left(frac4α-1+fracp+1pright)right), respectively, when appropriate p-order methods (p≥ 2) are used as inner solvers.