# Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2017.

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

- [Training OOD Detectors in their Natural Habitats](https://mlsanity.com/paper/2202.03299/) (2022)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (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)
- [First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/2204.03132/) (2022)
- [Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes](https://mlsanity.com/paper/2306.07001/) (2023)
- [Federated Learning with Convex Global and Local Constraints](https://mlsanity.com/paper/2310.10117/) (2023)
- [A Retention-Centric Framework for Continual Learning with Guaranteed Model Developmental Safety](https://mlsanity.com/paper/2410.03955/) (2024)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Adaptive UAV-Assisted Hierarchical Federated Learning: Optimizing Energy, Latency, and Resilience for Dynamic Smart IoT](https://mlsanity.com/paper/2503.06145/) (2025)
- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)
- [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)
- [First-order methods for stochastic and finite-sum convex optimization with deterministic constraints](https://mlsanity.com/paper/2506.20630/) (2025)
- [Distributed optimization: designed for federated learning](https://mlsanity.com/paper/2508.08606/) (2025)
- [Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints](https://mlsanity.com/paper/2212.11143/) (2022)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)
- [A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints](https://mlsanity.com/paper/2405.01984/) (2024)
- [A proximal augmented Lagrangian method for nonconvex optimization with equality and inequality constraints](https://mlsanity.com/paper/2509.02894/) (2025)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)

## Abstract (arXiv)

Augmented Lagrangian method (ALM) has been popularly used for solving constrained optimization problems. Practically, subproblems for updating primal variables in the framework of ALM usually can only be solved inexactly. The convergence and local convergence speed of ALM have been extensively studied. However, the global convergence rate of inexact ALM is still open for problems with nonlinear inequality constraints. In this paper, we work on general convex programs with both equality and inequality constraints. For these problems, we establish the global convergence rate of inexact ALM and estimate its iteration complexity in terms of the number of gradient evaluations to produce a solution with a specified accuracy. We first establish an ergodic convergence rate result of inexact ALM that uses constant penalty parameters or geometrically increasing penalty parameters. Based on the convergence rate result, we apply Nesterov's optimal first-order method on each primal subproblem and estimate the iteration complexity of the inexact ALM. We show that if the objective is convex, then O(varepsilon-1) gradient evaluations are sufficient to guarantee an varepsilon-optimal solution in terms of both primal objective and feasibility violation. If the objective is strongly convex, the result can be improved to O(varepsilon^-frac12|logvarepsilon|). Finally, by relating to the inexact proximal point algorithm, we establish a nonergodic convergence rate result of inexact ALM that uses geometrically increasing penalty parameters. We show that the nonergodic iteration complexity result is in the same order as that for the ergodic result. Numerical experiments on quadratically constrained quadratic programming are conducted to compare the performance of the inexact ALM with different settings.