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

2018/03/27 by Zhaosong Lu, Lu, Zhaosong, Zirui Zhou +1 · 3 citations
Engineering · Mathematics · Computer Science · #Sparse and Compressive Sensing Techniques #Advanced Optimization Algorithms Research #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1803.09941

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 ε-KKT solution is at most O(ε^-7/4). We then propose an adaptively regularized I-AL method and show that it achieves a first-order iteration complexity O(ε^-1logε^-1), which significantly improves existing complexity bounds achieved by first-order I-AL methods for finding an ε-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.

Citations

• Multiplier and gradient methods
• First-order methods of smooth convex optimization with inexact oracle
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Smooth minimization of non-smooth functions

Cited by

• Solving bilevel optimization via sequential minimax optimization
• Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems
• A proximal augmented Lagrangian method for nonconvex optimization with equality and inequality constraints

Related

• Complexity of first order inexact Lagrangian and penalty methods for conic convex programming
• An Augmented Lagrangian Method for Conic Convex Programming
• Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
• Iteration complexity analysis of dual first order methods for conic convex programming
• Inexact Augmented Lagrangian Methods for Conic Programs: Quadratic Growth and Linear Convergence