  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. The same-order complexity results have been
achieved by penalty methods. However, two different analysis techniques are
used to obtain the results, and more importantly, the penalty methods generally
perform significantly worse than iALM in practice. Our improved iALM and
analysis close the gap between theory and practice. Numerical experiments on
nonconvex problems with affine equality or nonconvex constraints are provided
to demonstrate the effectiveness of our proposed method.
