# Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2019.

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

- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold](https://mlsanity.com/paper/2303.09261/) (2023)
- [A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/2207.05650/) (2022)
- [A first-order augmented Lagrangian method for constrained minimax optimization](https://mlsanity.com/paper/2301.02060/) (2023)
- [Landing with the Score: Riemannian Optimization through Denoising](https://mlsanity.com/paper/2509.23357/) (2025)
- [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)
- [A Retention-Centric Framework for Continual Learning with Guaranteed Model Developmental Safety](https://mlsanity.com/paper/2410.03955/) (2024)
- [A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees](https://mlsanity.com/paper/2207.05697/) (2022)
- [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)
- [Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity](https://mlsanity.com/paper/2607.08954/) (2026)
- [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)
- [Outlier Detection Using Generative Models with Theoretical Performance Guarantees](https://mlsanity.com/paper/2310.09999/) (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)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)
- [MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization](https://mlsanity.com/paper/2605.29635/) (2026)

## Abstract (arXiv)

We analyze worst-case complexity of a Proximal augmented Lagrangian (Proximal AL) framework for nonconvex optimization with nonlinear equality constraints. When an approximate first-order (second-order) optimal point is obtained in the subproblem, an ε first-order (second-order) optimal point for the original problem can be guaranteed within O(1/ ε2 - η) outer iterations (where η is a user-defined parameter with η∈[0,2] for the first-order result and η ∈ [1,2] for the second-order result) when the proximal term coefficient β and penalty parameter ρ satisfy β = O(εη) and ρ = Omega (1/εη), respectively. We also investigate the total iteration complexity and operation complexity when a Newton-conjugate-gradient algorithm is used to solve the subproblems. Finally, we discuss an adaptive scheme for determining a value of the parameter ρ that satisfies the requirements of the analysis.