Augmented Lagrangian based first-order methods for convex and nonconvex programs: nonergodic convergence and iteration complexity.

摘要: 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 convex problems with functional constraints. It is straightforward generalization that by [Rockafellar'73, MathProg], which studied only inequality By result, show complexity the AL-based solving strongly problem, has composite structured objective and smooth To achieve $\epsilon$-KKT point, method needs $O(\epsilon^{-\frac{1}{2}}|\log\epsilon|)$ proximal gradient steps. This differs from existing lower bound $|\log\epsilon|$ thus nearly optimal. Then apply to problem $O(\epsilon^{-1}|\log\epsilon|)$ We further design novel non-convex constraint functions. The new follows framework point (PP) method. On approximately PP subproblems, it mixes inexact AL (iALM) quadratic penalty method, while latter always fed estimated multipliers iALM. We $O(\epsilon^{-\frac{5}{2}}|\log\epsilon|)$ proposed point. best known result. Theoretically, hybrid iteration-complexity requirement than its counterpart uses iALM solve numerically, can perform significantly better pure-penalty-based Numerical experiments are conducted on quadratically constrained programs nonconvex linearly programs. numerical results demonstrate efficiency over ones.