ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints
Abstract
ALDER, a single-loop augmented-Lagrangian damped extragradient method, is proposed for smooth nonconvex--concave minimax problems with nonlinear coupled inequality constraints. Within an augmented-Lagrangian framework, ALDER combines prediction--correction steps for the primal variables with explicit projected-and-relaxed multiplier updates in a single loop. The penalty parameter is fixed throughout each run, eliminating inner-loop subproblem solves and iterative penalty updates. We establish uniform boundedness of the relaxed multiplier sequence and, under an extended Mangasarian--Fromovitz constraint qualification, boundedness of the projected output multiplier. Building on these bounds, we show that ALDER finds an ε-KKT point within 𝒪(ε−7/2) complete first-order oracle evaluations in the strongly concave setting and 𝒪(ε−4) in the concave setting. These bounds improve upon the best known complexity bounds for multi-loop algorithms for this problem class, achieved by FAL, by removing a log(1/ε) factor, while retaining a single-loop update structure.
Related
- Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity
- An Adaptive Augmented Lagrangian Method for Deterministic and Stochastic Nonconvex Optimization
- Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
- A Smoothed Augmented Lagrangian Method for Mathematical Programs with Vertical Complementarity Constraints
- Augmented Lagrangian methods with telescopic subproblems for MPCCs and cardinality constraints with general constraints: constraint-preserving swaps and B-stationarity
BibTeX
@misc{zhang2026alder,
title = {{ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints}},
author = {H. Zhang and M. Zhang and Z. Xu and Y. -H. Dai},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00691},
eprint = {2611.00691},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00691},
}
RIS
TY - UNPB
TI - ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints
AU - H. Zhang
AU - M. Zhang
AU - Z. Xu
AU - Y. -H. Dai
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00691
UR - https://arxiv.org/abs/2611.00691
AB - ALDER, a single-loop augmented-Lagrangian damped extragradient method, is proposed for smooth nonconvex--concave minimax problems with nonlinear coupled inequality constraints. Within an augmented-Lagrangian framework, ALDER combines prediction--correction steps for the primal variables with explicit projected-and-relaxed multiplier updates in a single loop. The penalty parameter is fixed throughout each run, eliminating inner-loop subproblem solves and iterative penalty updates. We establish uniform boundedness of the relaxed multiplier sequence and, under an extended Mangasarian--Fromovitz constraint qualification, boundedness of the projected output multiplier. Building on these bounds, we show that ALDER finds an ε-KKT point within 𝒪(ε^−7/2) complete first-order oracle evaluations in the strongly concave setting and 𝒪(ε^−4) in the concave setting. These bounds improve upon the best known complexity bounds for multi-loop algorithms for this problem class, achieved by FAL, by removing a log(1/ε) factor, while retaining a single-loop update structure.
ER -