# On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2019.

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

- [A first-order augmented Lagrangian method for constrained minimax optimization](https://mlsanity.com/paper/2301.02060/) (2023)
- [A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees](https://mlsanity.com/paper/2301.03139/) (2023)
- [Federated Learning with Convex Global and Local Constraints](https://mlsanity.com/paper/2310.10117/) (2023)
- [Lasry-Lions Envelopes and Nonconvex Optimization: A Homotopy Approach](https://mlsanity.com/paper/2103.08533/) (2021)
- [A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization](https://mlsanity.com/paper/2301.04204/) (2023)
- [Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2404.09438/) (2024)
- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)
- [First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods](https://mlsanity.com/paper/2307.07605/) (2023)
- [A proximal augmented Lagrangian method for nonconvex optimization with equality and inequality constraints](https://mlsanity.com/paper/2509.02894/) (2025)
- [A first-order method for nonconvex-strongly-concave constrained minimax optimization](https://mlsanity.com/paper/2512.22909/) (2025)

## Abstract (arXiv)

In this paper we study the worst-case complexity of an inexact Augmented Lagrangian method for nonconvex constrained problems. Assuming that the penalty parameters are bounded, we prove a complexity bound of O(|log(ε)|) outer iterations for the referred algorithm to generate an ε-approximate KKT point, for ε∈ (0,1). When the penalty parameters are unbounded, we prove an outer iteration complexity bound of Oleft(ε-2/(α-1)right), where α>1 controls the rate of increase of the penalty parameters. For linearly constrained problems, these bounds yield to evaluation complexity bounds of O(|log(ε)|2ε-2) and Oleft(ε^-left(frac2(2+α)α-1+2right)right), respectively, when appropriate first-order methods (p=1) are used to approximately solve the unconstrained subproblems at each iteration. In the case of problems having only linear equality constraints, the latter bounds are improved to O(|log(ε)|2ε-(p+1)/p) and Oleft(ε^-left(frac4α-1+fracp+1pright)right), respectively, when appropriate p-order methods (p≥ 2) are used as inner solvers.