Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization

Understand

First-order methods have been studied for nonlinear constrained optimization within the framework of the augmented Lagrangian method (ALM) or penalty method.

• We propose an improved inexact ALM (iALM) and conduct a unified analysis for nonconvex problems with either affine equality or nonconvex constraints.
• Under certain regularity conditions (that are also assumed by existing works), we show an $\tilde{O}(\varepsilon^{-\frac{5}{2}})$ complexity result for a problem with a nonconvex objective and affine equality constraints and an $\tilde{O}(\varepsilon^{-3})$ complexity result for a problem with a nonconvex objective and nonconvex constraints, where the complexity is measured by the number of first-order oracles to yield an $\varepsilon$-KKT solution.
• Both results are the best known.