Oct 31, 2026J/K move · Enter open · S save
H. Zhang, M. Zhang, Z. Xu, Y. -H. Dai
Department of Mathematics, Shanghai University, Shanghai 200444, People’s Republic of China · LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China · Newtouch Center for Mathematics of Shanghai University, Shanghai 200444, People’s Republic of China+2
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
O(ε−7/2) complete first-order oracle evaluations in the strongly concave setting and
O(ε−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.