In this talk we consider a class of convex conic programming. We propose an inexact augmented Lagrangian (I-AL) method for this problem, where the subproblems are solved approximately by a variant of Nesterov’s optimal first-order method. We show that the I-AL method is equivalent with the proximal point algorithm (PPA) applied to the monotone operator associated with the Lagrangian dual function. Based on this fact, we establish a bound on the total number of first-order iterations for computing an approximate Karush-Kuhn-Tucker (KKT) point to the problem. We also propose a variant of I-AL, which corresponds to applying PPA to the monotone operator associated with the ordinary Lagrangian function, and show that it has better complexity bound than the original I-AL. In contrast to existing works on I-AL methods, our algorithms are practically applicable to a broader class of problems, and our analysis also provides sharper complexity bounds.

This is joint work with Zirui Zhou (Simon Fraser University).