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

arXiv: https://arxiv.org/abs/1803.09941 · HTML: https://mlsanity.com/paper/1803.09941/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2018.

## Built on by (most cited first, 7 of 7)

- [Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient](https://mlsanity.com/paper/2206.01209/) (2022)
- [Federated Learning with Convex Global and Local Constraints](https://mlsanity.com/paper/2310.10117/) (2023)
- [Solving bilevel optimization via sequential minimax optimization](https://mlsanity.com/paper/2511.07398/) (2025)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity](https://mlsanity.com/paper/2206.00973/) (2022)
- [First-order methods for stochastic and finite-sum convex optimization with deterministic constraints](https://mlsanity.com/paper/2506.20630/) (2025)
- [A proximal augmented Lagrangian method for nonconvex optimization with equality and inequality constraints](https://mlsanity.com/paper/2509.02894/) (2025)

## Abstract (arXiv)

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.