Iteration complexity of first-order augmented Lagrangian methods for convex conic programming

Abstract

In this paper we consider a class of convex conic programming. In particular, we first propose an inexact augmented Lagrangian (I-AL) method that resembles the classical I-AL method for solving this problem, in which the augmented Lagrangian subproblems are solved approximately by a variant of Nesterov's optimal first-order method. We show that the total number of first-order iterations of the proposed I-AL method for finding an $\epsilon$-KKT solution is at most $\mathcal{O}({\epsilon }^{-7/4})$. We then propose an adaptively regularized I-AL method and show that it achieves a first-order iteration complexity $\mathcal{O}({\epsilon }^{-1}\log {\epsilon }^{-1})$, which significantly improves existing complexity bounds achieved by first-order I-AL methods for finding an $\epsilon$-KKT solution. Our complexity analysis of the I-AL methods is based on a sharp analysis of inexact proximal point algorithm (PPA) and the connection between the I-AL methods and inexact PPA. It is vastly different from existing complexity analyses of the first-order I-AL methods in the literature, which typically regard the I-AL methods as an inexact dual gradient method.

accepted by SIAM Journal on Optimization

References in corpus (1)

• An Augmented Lagrangian Method for Conic Convex Programming

Cited by in corpus (7)

• Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems
• Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization
• Augmented Lagrangian based first-order methods for convex-constrained programs with weakly-convex objective
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• Algorithms for Difference-of-Convex (DC) Programs Based on Difference-of-Moreau-Envelopes Smoothing
• An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems
• An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems