The augmented Lagrangian function and the corresponding augmented Lagrangian method are constructed for solving a class of minimax optimization problems with equality constraints. We prove that, under the linear independence constraint qualification and the second-order sufficiency optimality condition for the lower level problem and the second-order sufficiency optimality condition for the minimax problem, for a given multiplier vector μ, the rate of convergence of the augmented Lagrangian method is linear with respect to ||μ - μ*|| and the ratio constant is proportional to 1/c when the ratio ||μ - μ*/c is small enough, where c is the penalty parameter that exceeds a threshold c* > 0 and μ* is the multiplier corresponding to a local minimizer. Moreover, we prove that the sequence of multiplier vectors generated by the augmented Lagrangian method has at least Q-linear convergence if the sequence of penalty parameters {ck} is bounded and the convergence rate is superlinear if {ck} is increasing to infinity. Finally, we use a direct way to establish the rate of convergence of the augmented Lagrangian method for the minimax problem with a quadratic objective function and linear equality constraints.
Yu-Hong Dai, Li-Wei Zhang
. The Rate of Convergence of Augmented Lagrangian Method for Minimax Optimization Problems with Equality Constraints[J]. Journal of the Operations Research Society of China, 2024
, 12(2)
: 265
-297
.
DOI: 10.1007/s40305-022-00439-z
[1] Hestenes, M.R.:Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303-320(1969)
[2] Powell, M.J.D.:A method for nonlinear constraints in minimization problems. In:Fletcher, R.(ed.) Optimization, pp. 283-298. Academic Press, New York (1969)
[3] Rockafellar, R.T.:A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Program. 5, 354-373(1973)
[4] Rockafellar, R.T.:The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl. 12, 555-562(1973)
[5] Rockafellar, R.T.:Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1, 97-116(1976)
[6] Rockafellar, R.T.:Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877-898(1976)
[7] Bertsekas, D.P.:Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982)
[8] Conn, A.R., Gould, N.I.M., Toint, P.L.:A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds. SIAM J. Numer. Anal. 28, 545-572(1991)
[9] Contesse-Becker, L.:Extended convergence results for the method of multipliers for non-strictly binding inequality constraints. J. Optim. Theory Appl. 79, 273-310(1993)
[10] Ito, K., Kunisch, K.:The augmented Lagrangian method for equality and inequality constraints in Hilbert spaces. Math. Program. 46, 341-360(1990)
[11] Sun, D.F., Sun, J., Zhang, L.W.:The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming. Math. Program. 114, 349-391(2008)
[12] Zhang, J., Wang, M., Hong, M., Zhang, S.:Primal-dual first-order methods for affinely constrained multi-block saddle point problems. arXiv:2109.14212v2[math.OC] 8 Oct (2021)
[13] Tsaknakis, I., Hong, M., Zhang, S.:Minimax problems with coupled linear constraints:computational complexity, duality and solution methods. arXiv:2110.11210v1[math.OC] 21 Oct (2021)
[14] Goktas, D., Greenwald, A.:Convex-concave min-max Stackelberg games. arXiv:2110.05192v2[cs.GT] 10 Nov (2021)
[15] Dai, Y.H., Zhang, L.W.:Optimality conditions for constrained minimax optimization. CSIAM Trans. Appl. Math. 1(2), 296-315(2020)
[16] Jin, C., Netrapalli, P., Jordan, M.I.:What is local optimality in nonconvex-nonconcave minimax optimization?arXiv:1902.00618v2[cs.LG] 3 Jun (2019)
[17] Debreu, G.:Definite and semidefinite quadratic forms. Econometrica 20, 295-300(1952)
[18] Puntanen, S., Styan, G.P.H.:Historical introduction:Issai Schur and the early development of the Schur complement. In:Zhang, F.Z.(ed.) The Schur Complement and its Application, pp. 1-16. Springer (2005)
[19] Wang, G.R., Wei, Y.M., Qiao, S.Z.:Generalized Inverses:Theory and Computations. Science Press, Springer, Beijing (2018)
