×

An augmented Lagrangian method for optimization problems with structured geometric constraints. (English) Zbl 1518.90060

Summary: This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality constraints) as well as optimization problems over sets of matrices which have to satisfy additional rank constraints. The key idea behind our method is to keep these complicated constraints explicitly in the constraints and to penalize only the remaining constraints by an augmented Lagrangian function. The resulting subproblems are then solved with the aid of a problem-tailored nonmonotone projected gradient method. The corresponding convergence theory allows for an inexact solution of these subproblems. Nevertheless, the overall algorithm computes so-called Mordukhovich-stationary points of the original problem under a mild asymptotic regularity condition, which is generally weaker than most of the respective available problem-tailored constraint qualifications. Extensive numerical experiments addressing complementarity- and cardinality-constrained optimization problems as well as a semidefinite reformulation of MAXCUT problems visualize the power of our approach.

MSC:

90C22 Semidefinite programming
90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K10 Numerical optimization and variational techniques

Software:

CPLEX; ALGENCAN
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Achtziger, W.; Kanzow, C., Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications, Math. Program. Series A, 114, 1, 69-99 (2008) · Zbl 1151.90046
[2] Andreani, R.; Birgin, EG; Martínez, JM; Schuverdt, ML, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18, 4, 1286-1309 (2008) · Zbl 1151.49027
[3] Andreani, R., Gómez, W., Haeser, G., Mito, L.M., Ramos, A.: On optimality conditions for nonlinear conic programming. Math. Oper. Res. (2021). doi:10.1287/moor.2021.1203 · Zbl 1502.90191
[4] Andreani, R.; Haeser, G.; Schuverdt, ML; Silva, PJS, A relaxed constant positive linear dependence constraint qualification and applications, Math. Program., 135, 1, 255-273 (2012) · Zbl 1262.90162
[5] Andreani, R.; Haeser, G.; Secchin, LD; Silva, PJS, New sequential optimality conditions for mathematical programs with complementarity constraints and algorithmic consequences, SIAM J. Optim., 29, 4, 3201-3230 (2019) · Zbl 1427.90258
[6] Andreani, R.; Haeser, G.; Viana, DS, Optimality conditions and global convergence for nonlinear semidefinite programming, Math. Program., 180, 1, 203-235 (2020) · Zbl 1434.90121
[7] Andreani, R.; Martínez, JM; Ramos, A.; Silva, PJS, A cone-continuity constraint qualification and algorithmic consequences, SIAM J. Optim., 26, 1, 96-110 (2016) · Zbl 1329.90162
[8] Andreani, R.; Martínez, JM; Ramos, A.; Silva, PJS, Strict constraint qualifications and sequential optimality conditions for constrained optimization, Math. Oper. Res., 43, 3, 693-717 (2018) · Zbl 1516.90091
[9] Andreani, R.; Secchin, LD; Silva, P., Convergence properties of a second order augmented Lagrangian method for mathematical programs with complementarity constraints, SIAM J. Optim., 28, 3, 2574-2600 (2018) · Zbl 1406.90114
[10] Barzilai, J.; Borwein, JM, Two-point step size gradient methods, IMA J. Numer. Anal., 8, 1, 141-148 (1988) · Zbl 0638.65055
[11] Bauschke, HH; Combettes, PL, Convex Analysis and Monotone Operator Theory in Hilbert Spaces (2011), New York: Springer, New York · Zbl 1218.47001
[12] Bauschke, HH; Luke, DR; Phan, HM; Wang, X., Restricted normal cones and sparsity optimization with affine constraints, Found. Comput. Math., 14, 63-83 (2013) · Zbl 1298.49047
[13] Beck, A.; Eldar, YC, Sparsity constrained nonlinear optimization: optimality conditions and algorithms, SIAM J. Optim., 23, 3, 1480-1509 (2013) · Zbl 1295.90051
[14] Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM, Philadelphia (2001). doi:10.1137/1.9780898718829 · Zbl 0986.90032
[15] Benko, M.; Červinka, M.; Hoheisel, T., Sufficient conditions for metric subregularity of constraint systems with applications to disjunctive and ortho-disjunctive programs, Set-Valued Variat. Anal., 30, 1143-177 (2022) · Zbl 1484.49025
[16] Benko, M.; Gfrerer, H., New verifiable stationarity concepts for a class of mathematical programs with disjunctive constraints, Optimization, 67, 1, 1-23 (2018) · Zbl 1398.90169
[17] Bertsekas, DP, Constrained Optimization and Lagrange Multiplier Methods (1982), New York: Academic Press, New York · Zbl 0572.90067
[18] Birgin, EG; Martínez, JM, Practical Augmented Lagrangian Methods for Constrained Optimization (2014), Philadelphia: SIAM, Philadelphia · Zbl 1339.90312
[19] Birgin, EG; Martínez, JM; Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10, 4, 1196-1211 (2000) · Zbl 1047.90077
[20] Börgens, E.; Kanzow, C.; Mehlitz, P.; Wachsmuth, G., New constraint qualifications for optimization problems in Banach spaces based on asymptotic KKT conditions, SIAM J. Optim., 30, 4, 2956-2982 (2020) · Zbl 1453.90182
[21] Burdakov, OP; Kanzow, C.; Schwartz, A., Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method, SIAM J. Optim., 26, 1, 397-425 (2016) · Zbl 1332.90220
[22] Candès, EJ; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 717 (2009) · Zbl 1219.90124
[23] Červinka, M.; Kanzow, C.; Schwartz, A., Constraint qualifications and optimality conditions for optimization problems with cardinality constraints, Math. Program., 160, 1, 353-377 (2016) · Zbl 1356.90146
[24] Chen, JS, SOC Functions and their Applications (2019), Singapure: Springer, Singapure · Zbl 1423.90002
[25] Chen, X.; Guo, L.; Lu, Z.; Ye, JJ, An augmented Lagrangian method for non-Lipschitz nonconvex programming, SIAM J. Numer. Anal., 55, 1, 168-193 (2017) · Zbl 1421.90119
[26] Chen, X.; Lu, Z.; Pong, TK, Penalty methods for a class of non-Lipschitz optimization problems, SIAM J. Optim., 26, 3, 1465-1492 (2016) · Zbl 1342.90181
[27] Chieu, NH; Lee, GM, A relaxed constant positive linear dependence constraint qualification for mathematical programs with equilibrium constraints, J. Optim. Theory Appl., 158, 1, 11-32 (2013) · Zbl 1272.90085
[28] Dennis, JE Jr; Schnabel, RB, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1996), Philadelphia: SIAM, Philadelphia · Zbl 0847.65038
[29] Flegel, ML; Kanzow, C.; Outrata, JV, Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints, Set-Valued Anal., 15, 2, 139-162 (2007) · Zbl 1149.90143
[30] Frangioni, A.; Gentile, C., SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Oper. Res. Lett., 35, 2, 181-185 (2007) · Zbl 1149.90379
[31] Goemans, MX; Williamson, DP, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 6, 1115-1145 (1995) · Zbl 0885.68088
[32] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM J. Numer. Anal., 23, 4, 707-716 (1986) · Zbl 0616.65067
[33] Guo, L.; Deng, Z., A new augmented Lagrangian method for MPCCs - theoretical and numerical comparison with existing augmented Lagrangian methods, Math. Oper. Res., 47, 2, 1229-1246 (2022) · Zbl 1489.90197
[34] Guo, L.; Lin, GH, Notes on some constraint qualifications for mathematical programs with equilibrium constraints, J. Optim. Theory Appl., 156, 600-616 (2013) · Zbl 1280.90115
[35] Guo, L.; Ye, JJ, Necessary optimality conditions and exact penalization for non-Lipschitz nonlinear programs, Math. Program., 168, 571-598 (2018) · Zbl 1401.90169
[36] Harder, F.; Mehlitz, P.; Wachsmuth, G., Reformulation of the M-stationarity conditions as a system of discontinuous equations and its solution by a semismooth Newton method, SIAM J. Optim., 31, 2, 1459-1488 (2021) · Zbl 1467.49024
[37] Harder, F.; Wachsmuth, G., The limiting normal cone of a complementarity set in Sobolev spaces, Optimization, 67, 10, 1579-1603 (2018) · Zbl 1407.49010
[38] Henrion, R.; Jourani, A.; Outrata, JV, On the calmness of a class of multifunctions, SIAM J. Optim., 13, 2, 603-618 (2002) · Zbl 1028.49018
[39] Hoheisel, T.; Kanzow, C.; Schwartz, A., Theoretical and numerical comparison of relaxation schemes for mathematical programs with complementarity constraints, Math. Program., 137, 257-288 (2013) · Zbl 1262.65065
[40] Hosseini, S., Luke, D.R., Uschmajew, A.: Tangent and normal cones for low-rank matrices. In: S. Hosseini, B.S. Mordukhovich, A. Uschmajew (eds.) Nonsmooth Optimization and Its Applications, pp. 45-53. Springer, Cham (2019). doi:10.1007/978-3-030-11370-4_3 · Zbl 1417.15050
[41] IBM ILOG CPLEX V12.1: User’s Manual for CPLEX. International Business Machines Corporation (2009)
[42] Izmailov, AF; Solodov, MV; Uskov, EI, Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints, SIAM J. Optim., 22, 4, 1579-1606 (2012) · Zbl 1274.90385
[43] Jia, X., Kanzow, C., Mehlitz, P., Wachsmuth, G.: An augmented Lagrangian method for optimization problems with structured geometric constraints. Tech. rep., preprint arXiv (2021). arXiv:2105.08317
[44] Kanzow, C.; Mehlitz, P.; Steck, D., Relaxation schemes for mathematical programmes with switching constraints, Optim. Methods. Softw., 36, 1223-1258 (2019) · Zbl 1489.65086
[45] Kanzow, C.; Raharja, AB; Schwartz, A., An augmented Lagrangian method for cardinality-constrained optimization problems, J. Optim. Theory Appl., 189, 793-813 (2021) · Zbl 1475.90103
[46] Kanzow, C.; Raharja, AB; Schwartz, A., Sequential optimality conditions for cardinality-constrained optimization problems with applications, Comput. Optim. Appl., 80, 1, 185-211 (2021) · Zbl 1482.90211
[47] Kanzow, C.; Schwartz, A., The price of inexactness: convergence properties of relaxation methods for mathematical programs with equilibrium constraints revisited, Math. Oper. Res., 40, 2, 253-275 (2015) · Zbl 1344.90058
[48] Kanzow, C.; Steck, D., An example comparing the standard and safeguarded augmented Lagrangian methods, Oper. Res. Lett., 45, 6, 598-603 (2017) · Zbl 1409.90186
[49] Lemon, A.; So, AMC; Ye, Y., Low-rank semidefinite programming: theory and applications, Foundations and Trends in Optimization, 2, 1-2, 1-156 (2016)
[50] Liang, YC; Ye, JJ, Optimality conditions and exact penalty for mathematical programs with switching constraints, J. Optim. Theory Appl., 190, 1-31 (2021) · Zbl 07383046
[51] Luke, DR, Prox-regularity of rank constraint sets and implications for algorithms, J. Math. Imaging Vision, 47, 231-238 (2013) · Zbl 1311.90142
[52] Luo, ZQ; Pang, JS; Ralph, D., Mathematical Programs with Equilibrium Constraints (1996), Cambridge: Cambridge University Press, Cambridge
[53] Markovsky, I., Low Rank Approximation: Algorithms, Implementation. Applications. Communications and Control Engineering (2012), London: Springer, London
[54] Mehlitz, P.: Asymptotic stationarity and regularity for nonsmooth optimization problems. J. Nonsmooth Anal. Optim. 1, 6575 (2020). doi:10.46298/jnsao-2020-6575 · Zbl 1480.90230
[55] Mehlitz, P., A comparison of solution approaches for the numerical treatment of or-constrained optimization problems, Comput. Optim. Appl., 76, 1, 233-275 (2020) · Zbl 1461.65175
[56] Mehlitz, P., On the linear independence constraint qualification in disjunctive programming, Optimization, 69, 10, 2241-2277 (2020) · Zbl 1528.90258
[57] Mehlitz, P., Stationarity conditions and constraint qualifications for mathematical programs with switching constraints, Math. Program., 181, 1, 149-186 (2020) · Zbl 1480.90230
[58] Mehlitz, P.; Wachsmuth, G., The limiting normal cone to pointwise defined sets in Lebesgue spaces, Set-Valued Var. Anal., 26, 3, 449-467 (2018) · Zbl 1401.49018
[59] Mordukhovich, BS, Variational Analysis and Applications (2018), Cham: Springer, Cham · Zbl 1402.49003
[60] Outrata, JV; Kočvara, M.; Zowe, J., Nonsmooth Approach to Optimization Problems with Equilibrium Constraints (1998), Dordrecht: Kluwer Academic, Dordrecht · Zbl 0947.90093
[61] Ramos, A., Mathematical programs with equilibrium constraints: a sequential optimality condition, new constraint qualifications and algorithmic consequences, Optim. Methods. Softw., 36, 1, 45-81 (2021) · Zbl 1527.90250
[62] Raydan, M., The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim., 7, 1, 26-33 (1997) · Zbl 0898.90119
[63] Robinson, S.M.: Some continuity properties of polyhedral multifunctions. In: H. König, B. Korte, K. Ritter (eds.) Mathematical Programming at Oberwolfach, pp. 206-214. Springer, Berlin (1981). doi:10.1007/bfb0120929 · Zbl 0449.90090
[64] Rockafellar, RT; Wets, RJB, Variational Analysis (2009), Berlin: Springer Science & Business Media, Berlin · Zbl 0888.49001
[65] Scholtes, S., Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim., 11, 4, 918-936 (2001) · Zbl 1010.90086
[66] Wright, SJ; Nowak, RD; Figueiredo, MAT, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57, 7, 2479-2493 (2009) · Zbl 1391.94442
[67] Xu, M.; Ye, JJ, Relaxed constant positive linear dependence constraint qualification and its application to bilevel programs, J. Global Optim., 78, 181-205 (2020) · Zbl 1447.49031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.