ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints
Authors: H. Zhang, M. Zhang, Z. Xu, Y. -H. Dai
Organizations: 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 · State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China · School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China
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.
Figures & tables
Method
Setting
Constraints
Loops
Complexity
Criterion
MGD [ 35 ]
SC–SC
Linear ineq.
Multi
O(ε−2log(1/ε))
ε -stationarity
PGmsAD [ 7 ]
C–C *
Linear eq.
Multi
O(ε−2log(1/ε))
ε -KKT
FAL [ 21 ]
NC–SC
Nonlinear ineq.
Multi
O(ε−7/2log(1/ε))
ε -KKT
ALDER
NC–SC
Nonlinear ineq.
Single
O(ε−7/2)
ε -KKT
FAL [ 20 ]
NC–C
Nonlinear ineq.
Multi
O(ε−4log(1/ε))
ε -KKT
ALDER
NC–C
Nonlinear ineq.
Single
O(ε−4)
ε -KKT
Table 1: Complexity comparison for minimax problems with coupled constraints.
Figure 1: KKT residual versus solver CPU time for problem ( 67 ).
Figure 2: KKT residual versus solver CPU time for problem ( 68 ).
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · Sauder School of Business, University of British Columbia, Vancouver, BC, Canada.