Iteration-complexity of first-order augmented Lagrangian methods for convex conic programming
share
In this paper we consider a class of convex conic programming. In particular, we propose an inexact augmented Lagrangian (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 computing an ϵ-KKT solution is at most O(ϵ^-7/4). We also propose a modified I-AL method and show that it has an improved iteration-complexity O(ϵ^-1ϵ^-1), which is so far the lowest complexity bound among all first-order I-AL type of methods for computing an ϵ-KKT solution. Our complexity analysis of the I-AL methods is mainly based on an analysis on inexact proximal point algorithm (PPA) and the link between the I-AL methods and inexact PPA. It is substantially different from the 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. Compared to the mostly related I-AL methods Lan16, our modified I-AL method is more practically efficient and also applicable to a broader class of problems.
READ FULL TEXT