Directional quasi-/pseudo-normality as sufficient conditions for metric subregularity. (English) Zbl 1428.49017
Summary: In this paper we study sufficient conditions for metric subregularity of a set-valued map which is the sum of a single-valued continuous map and a locally closed subset. First we derive a sufficient condition for metric subregularity which is weaker than the so-called first-order sufficient condition for metric subregularity (FOSCMS) by adding an extra sequential condition. Then we introduce directional versions of quasi-normality and pseudo-normality which are stronger than the new weak sufficient condition for metric subregularity but weaker than classical quasi-normality and pseudo-normality. Moreover we introduce a nonsmooth version of the second-order sufficient condition for metric subregularity and show that it is a sufficient condition for the new sufficient condition for metric subregularity to hold. An example is used to illustrate that directional pseudo-normality can be weaker than FOSCMS. For the class of set-valued maps where the single-valued mapping is affine and the abstract set is the union of finitely many convex polyhedral sets, we show that pseudo-normality and hence directional pseudo-normality holds automatically at each point of the graph. Finally we apply our results to complementarity and Karush-Kuhn-Tucker systems.
MSC:
| 49J53 | Set-valued and variational analysis |
| 49J52 | Nonsmooth analysis |
| 90C30 | Nonlinear programming |
| 90C31 | Sensitivity, stability, parametric optimization |
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
Keywords:
directional limiting normal cones; metric subregularity; calmness; error bounds; directional pseudo-normality; directional quasi-normality; complementarity systemsReferences:
| [1] | J.-P. Aubin, Lipschitz behavior of solutions to convex minimization problems, Math. Oper. Res., 9 (1984), pp. 87-111, https://doi.org/10.1287/moor.9.1.87. · Zbl 0539.90085 |
| [2] | M. Benko, H. Gfrerer, and J. V. Outrata, Calculus for directional limiting normal cones and subdifferentials, Set-Valued Var. Anal., (2018), pp. 1-33, https://doi.org/10.1007/s1122 8-018-0492-5. |
| [3] | J. Burke, Calmness and exact penalization, SIAM J. Control. Optim., 29 (1991), pp. 493-497, https://doi.org/10.1137/0329027. · Zbl 0734.90090 |
| [4] | A. Dontchev and R. Rockafellar, Regularity and conditioning of solution mappings in variational analysis, Set-Valued Anal., 12 (2004), pp. 79-109, https://doi.org/10.1023/B:SVAN.0000023394.19482.30. · Zbl 1046.49021 |
| [5] | A. L. Dontchev and R. T. Rockafellar, Implicit Functions and Solution Mappings, Springer, New York, 2009, https://doi.org/10.1007/978-0-387-87821-8. · Zbl 1178.26001 |
| [6] | M. J. Fabian, R. Henrion, A. Y. Kruger, and J. V. Outrata, Error bounds: Necessary and sufficient conditions, Set-Valued Var. Anal., 18 (2010), pp. 121-149, https://doi.org/10.1007/s11228-010-0133-0. · Zbl 1192.49018 |
| [7] | F. Facchinei, A. Fischer, and M. Herrich, An LP-Newton method: Nonsmooth equations, KKT systems, and nonisolated solutions, Math. Program., 146 (2014), pp. 1-36, https://doi.org/10.1007/s10107-013-0676-6. · Zbl 1317.90276 |
| [8] | F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. I, Springer Ser. Oper. Res. Financ. Eng., Springer, New York, 2003. · Zbl 1062.90002 |
| [9] | A. Fischer, Local behavior of an iterative framework for generalized equations with nonisolated solutions, Math. Program., 94 (2002), pp. 91-124, https://doi.org/10.1007/s10107-002-0364-4. · Zbl 1023.90067 |
| [10] | H. Gfrerer, On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs, Set-Valued Var. Anal., 21 (2013), pp. 151-176, https://doi.org/10.1007/s11228-012-0220-5. · Zbl 1321.49031 |
| [11] | H. Gfrerer, On directional metric subregularity and second-order optimality conditions for a class of nonsmooth mathematical programs, SIAM J. Optim., 23 (2013), pp. 632-665, https://doi.org/10.1137/120891216. · Zbl 1275.49027 |
| [12] | H. Gfrerer, On metric pseudo-(sub) regularity of multifunctions and optimality conditions for degenerated mathematical programs, Set-Valued Var. Anal., 22 (2014), pp. 79-115, https://doi.org/10.1007/s11228-013-0266-z. · Zbl 1297.49023 |
| [13] | H. Gfrerer, Optimality conditions for disjunctive programs based on generalized differentiation with application to mathematical programs with equilibrium constraints, SIAM J. Optim., 24 (2014), pp. 898-931, https://doi.org/10.1137/130914449. · Zbl 1298.49021 |
| [14] | H. Gfrerer and D. Klatte, Lipschitz and Hölder stability of optimization problems and generalized equations, Math. Program., 158 (2016), pp. 35-75, https://doi.org/10.1007/s10107-015-0914-1. · Zbl 1345.49030 |
| [15] | H. Gfrerer and J. J. Ye, New constraint qualifications for mathematical programs with equilibrium constraints via variational analysis, SIAM J. Optim., 27 (2017), pp. 842-865, https://doi.org/10.1137/16M1088752. · Zbl 1368.49015 |
| [16] | I. Ginchev and B. S. Mordukhovich, On directionally dependent subdifferentials, C. R. Bulg. Acad. Sci., 64 (2011), pp. 497-508. · Zbl 1289.49021 |
| [17] | L. Guo, J. J. Ye, and J. Zhang, Mathematical programs with geometric constraints in Banach spaces: Enhanced optimality, exact penalty, and sensitivity, SIAM J. Optim., 23 (2013), pp. 2295-2319, https://doi.org/10.1137/130910956. · Zbl 1342.90144 |
| [18] | W. W. Hager and S. M. Gowda, Stability in the presence of degeneracy and error estimation, Math. Program., 85 (1999), pp. 181-192, https://doi.org/10.1007/s101070050051. · Zbl 0956.90049 |
| [19] | R. Henrion and A. Jourani, Subdifferential conditions for calmness of convex constraints, SIAM J. Optim., 13 (2002), pp. 520-534, https://doi.org/10.1137/S1052623401386071. · Zbl 1028.49017 |
| [20] | R. Henrion, A. Jourani, and J. V. Outrata, On the calmness of a class of multifunctions, SIAM J. Optim., 13 (2002), pp. 603-618, https://doi.org/10.1137/S1052623401395553. · Zbl 1028.49018 |
| [21] | R. Henrion and J. Outrata, A subdifferential condition for calmness of multifunctions, J. Math. Anal. Appl., 258 (2001), pp. 110-130, https://doi.org/10.1006/jmaa.2000.7363. · Zbl 0983.49010 |
| [22] | R. Henrion and J. V. Outrata, Calmness of constraint systems with applications, Math. Program., 104 (2005), pp. 437-464, https://doi.org/10.1007/s10107-005-0623-2. · Zbl 1093.90058 |
| [23] | A. D. Ioffe, Necessary and sufficient conditions for a local minimum. 1: A reduction theorem and first order conditions, SIAM J. Control Optim., 17 (1979), pp. 245-250, https://doi.org/10.1137/0317019. · Zbl 0417.49027 |
| [24] | A. D. Ioffe, Regular points of Lipschitz functions, Trans. Amer. Math. Soc., 251 (1979), pp. 61-69, https://doi.org/10.2307/1998683. · Zbl 0427.58008 |
| [25] | A. D. Ioffe, Metric regularity and subdifferential calclulus, Russian Math. Surveys, 55 (2000), pp. 501-558, https://doi.org/10.1070/RM2000v055n03ABEH000292. · Zbl 0979.49017 |
| [26] | A. D. Ioffe and J. V. Outrata, On metric and calmness qualification conditions in subdifferential calculus, Set-valued Anal., 16 (2008), pp. 199-227, https://doi.org/10.1007/s11228-008-0076-x. · Zbl 1156.49013 |
| [27] | A. F. Izmailov, On the analytical and numerical stability of critical Lagrange multipliers, Comput. Math. Math. Phys., 45 (2005), pp. 966-982. · Zbl 1087.70011 |
| [28] | A. F. Izmailov and M. V. Solodov, Stabilized SQP revisited, Math. Program., 133 (2012), pp. 93-120, https://doi.org/10.1007/s10107-010-0413-3. · Zbl 1245.90145 |
| [29] | C. Kanzow and A. Schwartz, Mathematical programs with equilibrium constraints: Enhanced Fritz John-conditions, new constraint qualifications, and improved exact penalty results, SIAM J. Optim., 20 (2010), pp. 2730-2753, https://doi.org/10.1137/090774975. · Zbl 1208.49016 |
| [30] | D. Klatte, A note on quantitative stability results in nonlinear optimization, in Proceedings of the 19. Jahrestagung Mathematische Optimierung, Seminarbericht 90, Humboldt-Universität Berlin, Sektion Mathematik, 1987, pp. 77-86. · Zbl 0636.90082 |
| [31] | D. Klatte and B. Kummer, Constrained minima and Lipschitzian penalties in metric spaces, SIAM J. Optim., 13 (2002), pp. 619-633, https://doi.org/10.1137/S105262340139625X. · Zbl 1042.49020 |
| [32] | D. Klatte and B. Kummer, Optimization methods and stability of inclusions in Banach spaces, Math. program., 117 (2009), pp. 305-330, https://doi.org/10.1007/s10107-007-0174-9. · Zbl 1158.49007 |
| [33] | W. Li, Abadie’s constraint qualification, metric regularity, and error bounds for differentiable convex inequalities, SIAM J. Optim., 7 (1997), pp. 966-978, https://doi.org/10.1137/S1052623495287927. · Zbl 0891.90132 |
| [34] | L. Minchenko and A. Tarakanov, On error bounds for quasinormal programs, J. Optim. Theory Appl., 148 (2011), pp. 571-579. · Zbl 1229.90204 |
| [35] | B. S. Mordukhovich, Variational Analysis and Generalized Differentiation I: Basic Theory, Grundlehren Math. Wiss. 330, Springer, Berlin, 2006, https://doi.org/10.1007/3-540-31247-1. |
| [36] | B. S. Mordukhovich and M. E. Sarabi, Critical multipliers in variational systems via second-order generalized differentiation, Math. Program., 169 (2018), pp. 605-648, https://doi.org/10.1007/s10107-017-1155-2. · Zbl 1407.90314 |
| [37] | H. V. Ngai and P. N. Tinh, Metric subregularity of multifunctions: First and second order infinitesimal characterizations, Math. Oper. Res., 40 (2015), pp. 703-724, https://doi.org/10.1287/moor.2014.0691. · Zbl 1323.47054 |
| [38] | M. Nikolova, Minimizers of cost-functions involving nonsmooth data-fidelity terms. Application to the processing of outliers, SIAM J. Numer. Anal., 40 (2002), pp. 965-994, https://doi.org/10.1137/S0036142901389165. · Zbl 1018.49025 |
| [39] | J.-P. Penôt, Error bounds, calmness and their applications in nonsmooth analysis, in Nonlinear Analysis and Optimization II: Optimization, Contemp. Math. 514, A. Leizarowitz, B. S. Mordukhovich, I. Shafrir, and A. J. Zaslavski, eds., American Mathematical Society, Providence, RI, 2010, pp. 225-247, https://doi.org/10.1090/conm/514/10110. |
| [40] | T. T. Pham and R. J. deFigueiredo, Maximum likelihood estimation of a class of non-Gaussian densities with application to \(I_p\) deconvolution, IEEE Trans. Acoust. Speech Signal Process., 37 (1989), pp. 73-82, https://doi.org/10.1109/29.17502. · Zbl 0677.93075 |
| [41] | J. R. Rice and J. S. White, Norms for smoothing and estimation, SIAM Rev., 6 (1964), pp. 243-256, https://doi.org/10.1137/1006061. · Zbl 0121.34102 |
| [42] | S. M. Robinson, Stability theory for systems of inequalities. Part I: Linear systems, SIAM J. Numer. Anal., 12 (1975), pp. 754-769, https://doi.org/10.1137/0712056. · Zbl 0317.90035 |
| [43] | S. M. Robinson, Stability theory for systems of inequalities. Part II: Differentiable nonlinear systems, SIAM J. Numer. Anal., 13 (1976), pp. 497-513, https://doi.org/10.1137/0713043. · Zbl 0347.90050 |
| [44] | S. M. Robinson, Some continuity properties of polyhedral multifunctions, Mathematical Programming at Oberwolfach, Math. Program. Stud. 14, Springer, Berlin, 1981, pp. 206-214, https://doi.org/10.1007/BFb0120929. · Zbl 0449.90090 |
| [45] | S. M. Robinson, Generalized equations and their solutions, part II: Applications to nonlinear programming, in Optimality and Stability in Mathematical Programming, Math. Program. Stud. 19, Springer, Berlin, 1982, pp. 200-221, https://doi.org/10.1007/BFb0120989. · Zbl 0495.90077 |
| [46] | R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Grundlehren Math. Wiss. 317, Springer, Berlin, 1998, https://doi.org/10.1007/978-3-642-02431-3. · Zbl 0888.49001 |
| [47] | S. Scholtes and M. Stöhr, How stringent is the linear independence assumption for mathematical programs with complementarity constraints?, Math. Oper. Res., 26 (2001), pp. 851-863, https://doi.org/10.1287/moor.26.4.851.10007. · Zbl 1082.90580 |
| [48] | M. Studniarski and D. E. Ward, Weak sharp minima: Characterizations and sufficient conditions, SIAM J. Control Optim., 38 (1999), pp. 219-236, https://doi.org/10.1137/S0363012996301269. · Zbl 0946.49011 |
| [49] | X. Wang, J. Ye, X. Yuan, S. Zeng, and J. Zhang, Perturbation Techniques for Convergence Analysis of Proximal Gradient Method and Other First-Order Algorithms Via Variational Analysis, preprint, https://arxiv.org/abs/1810.10051, 2018. |
| [50] | Z. Wu and J. Y. Jane, On error bounds for lower semicontinuous functions, Math. Program., 92 (2002), pp. 301-314, https://doi.org/10.1007/s101070100278. · Zbl 1041.90053 |
| [51] | Z. Wu and J. J. Ye, Sufficient conditions for error bounds, SIAM J. Optim., 12 (2001), pp. 421-435, https://doi.org/10.1137/S1052623400371557. · Zbl 1042.49023 |
| [52] | Z. Wu and J. J. Ye, First-order and second-order conditions for error bounds, SIAM J. Optim., 14 (2003), pp. 621-645, https://doi.org/10.1137/S1052623402412982. · Zbl 1061.49017 |
| [53] | J. J. Ye, Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints, SIAM J. Optim., 10 (2000), pp. 943-962, https://doi.org/10.1137/S105262349834847X. · Zbl 1005.49019 |
| [54] | J. J. Ye, Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints, J. Math. Anal. Appl., 307 (2005), pp. 350-369, https://doi.org/10.1016/j.jmaa.2004.10.032. · Zbl 1112.90062 |
| [55] | J. J. Ye and X. Y. Ye, Necessary optimality conditions for optimization problems with variational inequality constraints, Math. Oper. Res., 22 (1997), pp. 977-997, https://doi.org/10.1287/moor.22.4.977. · Zbl 1088.90042 |
| [56] | J. J. Ye and J. Zhang, Enhanced Karush-Kuhn-Tucker condition and weaker constraint qualifications, Math. Program., 139 (2013), pp. 353-381, https://doi.org/10.1007/s10107-013-0667-7. · Zbl 1285.90078 |
| [57] | J. J. Ye and J. Zhang, Enhanced Karush-Kuhn-Tucker conditions for mathematical programs with equilibrium constraints, J. Optim. Theory Appl., 163 (2014), pp. 777-794, https://doi.org/10.1007/s10957-013-0493-3. · Zbl 1320.90086 |
| [58] | J. J. Ye and J. Zhou, Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems, Math. Program., 171 (2018), pp. 361-395, https://doi.org/10.1007/s10107-017-1193-9. · Zbl 1400.49019 |
| [59] | X. Y. Zheng and K. F. Ng, Metric subregularity and constraint qualifications for nonconvex generalized equations in Banach spaces, SIAM J. Optim., 20 (2010), pp. 2119-2136, https://doi.org/10.1137/090772174. · Zbl 1229.90220 |
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.
