Iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian function

Understand

This paper establishes the iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian (IAIPAL) method for solving linearly-constrained smooth nonconvex composite optimization problems that is based on the classical augmented Lagrangian (AL) function.

• More specifically, each IAIPAL iteration consists of inexactly solving a proximal AL subproblem by an accelerated composite gradient (ACG) method followed by a classical Lagrange multiplier update.
• Under the assumption that the domain of the composite function is bounded and the problem has a Slater point, it is shown that IAIPAL generates an approximate stationary solution in ${\cal O}(\varepsilon^{-5/2}\log^2 \varepsilon^{-1})$ ACG iterations where $\varepsilon>0$ is a tolerance for both stationarity and feasibility.
• Moreover, the above bound is derived without assuming that the initial point is feasible.