# An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints

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

## Key facts

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

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

- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/2207.05650/) (2022)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees](https://mlsanity.com/paper/2409.09906/) (2024)
- [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)
- [Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints](https://mlsanity.com/paper/2504.15243/) (2025)
- [Approximating Optimal Transport via Low-rank and Sparse Factorization](https://mlsanity.com/paper/2111.06546/) (2021)
- [Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching](https://mlsanity.com/paper/2312.11801/) (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)
- [Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Data](https://mlsanity.com/paper/2209.15097/) (2022)
- [A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization](https://mlsanity.com/paper/2301.04204/) (2023)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2404.09438/) (2024)
- [Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points](https://mlsanity.com/paper/2112.13269/) (2021)
- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)
- [Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecture](https://mlsanity.com/paper/2501.16322/) (2025)
- [Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions](https://mlsanity.com/paper/2502.19764/) (2025)
- [Motion Planning with Model-Based Diffusion via Constraint Optimization and Adaptive Scheduling](https://mlsanity.com/paper/2607.14455/) (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)
- [A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints](https://mlsanity.com/paper/2405.01984/) (2024)
- [PEEL the Layers and Find Yourself: Revisiting Inference-time Data Leakage for Residual Neural Networks](https://mlsanity.com/paper/2504.06410/) (2025)
- [Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2504.09409/) (2025)
- [A proximal augmented Lagrangian method for nonconvex optimization with equality and inequality constraints](https://mlsanity.com/paper/2509.02894/) (2025)
- [Single-Snapshot Gridless 2D-DoA Estimation for UCAs: A Joint Optimization Approach](https://mlsanity.com/paper/2510.17818/) (2025)
- [A first-order method for nonconvex-strongly-concave constrained minimax optimization](https://mlsanity.com/paper/2512.22909/) (2025)
- [Local Constrained Bayesian Optimization](https://mlsanity.com/paper/2603.07965/) (2026)

## Abstract (arXiv)

We propose a practical inexact augmented Lagrangian method (iALM) for nonconvex problems with nonlinear constraints. We characterize the total computational complexity of our method subject to a verifiable geometric condition, which is closely related to the Polyak-Lojasiewicz and Mangasarian-Fromowitz conditions. In particular, when a first-order solver is used for the inner iterates, we prove that iALM finds a first-order stationary point with tildeO(1/ε4) calls to the first-order oracle. If, in addition, the problem is smooth and a second-order solver is used for the inner iterates, iALM finds a second-order stationary point with tildeO(1/ε5) calls to the second-order oracle, which matches the known theoretical complexity result in the literature. We also provide strong numerical evidence on large-scale machine learning problems, including the Burer-Monteiro factorization of semidefinite programs, and a novel nonconvex relaxation of the standard basis pursuit template. For these examples, we also show how to verify our geometric condition.