Augmented Lagrangian based first-order methods for convex and nonconvex programs: nonergodic convergence and iteration complexity
share
First-order methods (FOMs) have been widely used for large-scale problems. In this paper, we first establish a nonergodic convergence rate result of an augmented Lagrangian (AL) based FOM for convex problems with functional constraints. It is a straightforward generalization of that by [Rockafellar'73, MathProg], which studied problems with only inequality constraints. By this result, we show a complexity result of the AL-based FOM for solving a strongly convex problem, which has a composite structured objective and smooth constraints. To achieve an ϵ-KKT point, the method needs O(ϵ^-1/2|logϵ|) proximal gradient steps. This result differs from an existing lower bound by |logϵ| and thus is nearly optimal. Then we apply the result to a convex problem and establish an O(ϵ^-1|logϵ|) complexity result of the AL-based FOM for convex problems. We further design a novel AL-based FOM for problems with non-convex objective and convex constraint functions. The new method follows the framework of the proximal point (PP) method. On approximately solving PP subproblems, it mixes the inexact AL method (iALM) and the quadratic penalty method, while the latter is always fed with estimated multipliers by the iALM. We show a complexity result of O(ϵ^-5/2|logϵ|) for the proposed method to achieve an ϵ-KKT point. This is the best known result. Theoretically, the hybrid method has lower iteration-complexity requirement than its counterpart that only uses iALM to solve PP subproblems, and numerically, it can perform significantly better than a pure-penalty-based method. Numerical experiments are conducted on convex quadratically constrained quadratic programs and nonconvex linearly constrained quadratic programs. The numerical results demonstrate the efficiency of the proposed methods over existing ones.
READ FULL TEXT