Sensitivity Analysis of the Maximal Value Function with Applications in Nonconvex Minimax Programs

References

• [1] Andreani R, Haeser G, Schuverdt ML, Silva PJ (2012) A relaxed constant positive linear dependence constraint qualification and applications. Math. Programming 135(1–2):255–273.Crossref, Google Scholar
• [2] Bertsekas DP, Ozdaglar AE (2002) Pseudonormality and a Lagrange multiplier theory for constrained optimization. J. Optim. Theory Appl. 114(2):287–343.Crossref, Google Scholar
• [3] Bonnans JF, Shapiro A (2013) Perturbation Analysis of Optimization Problems (Springer Science & Business Media, New York).Google Scholar
• [4] Clarke FH (1990) Optimization and Nonsmooth Analysis (SIAM, Philadelphia).Crossref, Google Scholar
• [5] Dai YH, Zhang L (2020) Optimality conditions for constrained minimax optimization. CSIAM Trans. Appl. Math. 1(2):296–315.Crossref, Google Scholar
• [6] Dempe S, Dutta J (2012) Is bilevel programming a special case of a mathematical program with complementarity constraints? Math. Programming 131(1–2):37–48.Crossref, Google Scholar
• [7] Fiacco AV, Ishizuka Y (1990) Sensitivity and stability analysis for nonlinear programming. Ann. Oper. Res. 27(1):215–235.Crossref, Google Scholar
• [8] Fiacco AV, Kyparisis J (1986) Convexity and concavity properties of the optimal value function in parametric nonlinear programming. J. Optim. Theory Appl. 48(1):95–126.Crossref, Google Scholar
• [9] Gauvin J (1979) The generalized gradient of a marginal function in mathematical programming. Math. Oper. Res. 4(4):458–463.Link, Google Scholar
• [10] Gauvin J, Dubeau F (1982) Differential properties of the marginal function in mathematical programming. Guignard M, ed. Optimality and Stability in Mathematical Programming, Mathematical Programming Studies, vol. 19 (Springer, Berlin), 101–119.Crossref, Google Scholar
• [11] Gfrerer H, Mordukhovich BS (2017) Robinson stability of parametric constraint systems via variational analysis. SIAM J. Optim. 27(1):438–465.Crossref, Google Scholar
• [12] Gfrerer H, Ye JJ (2017) New constraint qualifications for mathematical programs with equilibrium constraints via variational analysis. SIAM J. Optim. 27(2):842–865.Crossref, Google Scholar
• [13] Giorgi G, Jiménez B, Novo V (2016) Approximate Karush–Kuhn–Tucker condition in multiobjective optimization. J. Optim. Theory Appl. 171(1):70–89.Crossref, Google Scholar
• [14] Goodfellow I, Pouget-Abadie J, Mirza M, Xu B, Warde-Farley D, Ozair S, Courville A, Bengio Y (2014) Generative adversarial nets. Ghahramani Z, Welling M, Cortes C, Lawrence N, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems 27 (NIPS 2014) (NeurIPS, San Diego), 2672–2680.Google Scholar
• [15] Guo L, Lin GH, Ye JJ (2012) Stability analysis for parametric mathematical programs with geometric constraints and its applications. SIAM J. Optim. 22(3):1151–1176.Crossref, Google Scholar
• [16] Guo L, Lin GH, Ye JJ, Zhang J (2014) Sensitivity analysis of the value function for parametric mathematical programs with equilibrium constraints. SIAM J. Optim. 24(3):1206–1237.Crossref, Google Scholar
• [17] Henrion R, Jourani A, Outrata J (2002) On the calmness of a class of multifunctions. SIAM J. Optim. 13(2):603–618.Crossref, Google Scholar
• [18] Intriligator MD (2002) Mathematical Optimization and Economic Theory (SIAM, Philadelphia).Crossref, Google Scholar
• [19] Janin R (1984) Directional Derivative of the Marginal Function in Nonlinear Programming (Springer, Berlin).Crossref, Google Scholar
• [20] Jiang J, Chen X (2022) Optimality conditions for nonsmooth nonconvex-nonconcave min-max problems and generative adversarial networks. Preprint, submitted March 21, https://arxiv.org/abs/2203.10914.Google Scholar
• [21] Jin C, Netrapalli P, Jordan M (2020) What is local optimality in nonconvex-nonconcave minimax optimization? Daumé H, Singh A, eds. Internat. Conf. Machine Learn. (PMLR, New York), 4880–4889.Google Scholar
• [22] Lin T, Jin C, Jordan MI (2020) Near-optimal algorithms for minimax optimization. Abernethy J, Agarwal S, eds. Conf. Learn. Theory (PMLR, New York), 2738–2779.Google Scholar
• [23] Lin T, Jin C, Jordan M (2020) On gradient descent ascent for nonconvex-concave minimax problems. Daumé H, Singh A, eds. Internat. Conf. Machine Learn. (PMLR, New York), 6083–6093.Google Scholar
• [24] Lu S, Tsaknakis I, Hong M, Chen Y (2020) Hybrid block successive approximation for one-sided non-convex min-max problems: Algorithms and applications. IEEE Trans. Signal Processing 68:3676–3691.Crossref, Google Scholar
• [25] Lucet Y, Ye JJ (2001) Sensitivity analysis of the value function for optimization problems with variational inequality constraints. SIAM J. Control Optim. 40(3):699–723.Crossref, Google Scholar
• [26] Lucet Y, Ye JJ (2002) Erratum: Sensitivity analysis of the value function for optimization problems with variational inequality constraints. SIAM J. Control Optim. 41(4):1315–1319.Crossref, Google Scholar
• [27] Mehlitz P, Minchenko LI (2022) R-regularity of set-valued mappings under the relaxed constant positive linear dependence constraint qualification with applications to parametric and bilevel optimization. Set-Valued Variational Anal. 30(1):179–205.Crossref, Google Scholar
• [28] Minchenko L, Stakhovski S (2011) Parametric nonlinear programming problems under the relaxed constant rank condition. SIAM J. Optim. 21(1):314–332.Crossref, Google Scholar
• [29] Mordukhovich BS (2006) Variational Analysis and Generalized Differentiation I: Basic Theory, vol. 331 (Springer, Berlin).Crossref, Google Scholar
• [30] Mordukhovich BS, Nam NM, Yen ND (2009) Subgradients of marginal functions in parametric mathematical programming. Math. Programming 116(1–2):369–396.Crossref, Google Scholar
• [31] Ostrovskii DM, Lowy A, Razaviyayn M (2021) Efficient search of first-order Nash equilibria in nonconvex-concave smooth min-max problems. SIAM J. Optim. 31(4):2508–2538.Crossref, Google Scholar
• [32] Ozdaglar AE, Bertsekas DP (2004) The relation between pseudonormality and quasiregularity in constrained optimization. Optim. Methods Software 19(5):493–506.Crossref, Google Scholar
• [33] Rafique H, Liu M, Lin Q, Yang T (2022) Weakly-convex–concave min–max optimization: Provable algorithms and applications in machine learning. Optim. Methods Software 37(3):1087–1121.Crossref, Google Scholar
• [34] Robinson SM (1976) Stability theory for systems of inequalities. Part II. Differentiable nonlinear systems. SIAM J. Numerical Anal. 13(4):497–513.Crossref, Google Scholar
• [35] Robinson SM (1982) Generalized equations and their solutions. Part II. Applications to nonlinear programming. Guignard M, ed. Optimality and Stability in Mathematical Programming, Mathematical Programming Studies, vol. 19 (Springer, Berlin), 200–221.Crossref, Google Scholar
• [36] Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [37] Rockafellar RT, Wets RJB (1998) Variational Analysis (Springer Science & Business Media, New York).Crossref, Google Scholar
• [38] Scheel H, Scholtes S (2000) Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25(1):1–22.Link, Google Scholar
• [39] Sion M (1958) On general minimax theorems. Pacific J. Math. 8:171–176.Crossref, Google Scholar
• [40] Stein O (2003) Bi-Level Strategies in Semi-Infinite Programming (Springer Science & Business Media, New York).Crossref, Google Scholar
• [41] Thibault L (1991) On subdifferentials of optimal value functions. SIAM J. Control Optim. 29(5):1019–1036.Crossref, Google Scholar
• [42] Von Neumann J (1928) Zur theorie der gesellschaftsspiele. Math. Ann. 100(1):295–320.Crossref, Google Scholar
• [43] Von Neumann J, Morgenstern O (1947) Theory of Games and Economic Behavior (Princeton University Press, Princeton, NJ).Google Scholar
• [44] Wolfe P (1961) A duality theorem for non-linear programming. Quart. Appl. Math. 19(3):239–244.Crossref, Google Scholar
• [45] Yang J, Kiyavash N, He N (2020) Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems. Adv. Neural Inform. Processing Systems 33 (NeurIPS 2020), 1153–1165.Google Scholar
• [46] Ye JJ (1998) New uniform parametric error bounds. J. Optim. Theory Appl. 98:197–219.Crossref, Google Scholar
• [47] Ye JJ (2005) Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. J. Math. Anal. Appl. 307(1):350–369.Crossref, Google Scholar
• [48] Ye JJ, Wu SY (2008) First order optimality conditions for generalized semi-infinite programming problems. J. Optim. Theory Appl. 137:419–434.Crossref, Google Scholar
• [49] Ye JJ, Zhang J (2013) Enhanced Karush–Kuhn–Tucker condition and weaker constraint qualifications. Math. Programming 139(1–2):353–381.Crossref, Google Scholar
• [50] Ye JJ, Zhou J (2018) Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems. Math. Programming 171:361–395.Crossref, Google Scholar
• [51] Ye JJ, Zhu D (1995) Optimality conditions for bilevel programming problems. Optimization 33(1):9–27.Crossref, Google Scholar
• [52] Ye JJ, Zhu D, Zhu QJ (1997) Exact penalization and necessary optimality conditions for generalized bilevel programming problems. SIAM J. Optim. 7(2):481–507.Crossref, Google Scholar