×

Weak sharp minima revisited. III: Error bounds for differentiable convex inclusions. (English) Zbl 1163.90016

The term weak sharp minima is coined by Ferris in the late 1980’s to describe an extension of the notion of sharp minima to include the possibility of a non-unique solution set. It unifies a number of important ideas in optimization and many authors have studied this notion extensively. The notion of weak sharp minima is also an important tool in the analysis of the perturbation behavior of certain classes of optimization problems as well as in the convergence analysis of algorithms designed to solve these problems. This is the third paper in this series. Part I of this work [Control Cybern. 31, No. 3, 439–469 (2002; Zbl 1105.90356)] provides the foundation for the theory of weak sharp minima. The basic results on weak sharp minima in Part I are applied to a number of important problems in convex programming. In Part II [Math. Program. 104, No. 2–3 (B), 235–261 (2005; Zbl 1124.90349)], the applications to the linear regularity and bounded linear regularity of a finite collection of convex sets as well as global error bounds in convex programming are studied. In Part III, the authors continue their study of weak sharp minima by focusing on applications to error bounds for differentiable convex inclusions. A number of standard constraint qualifications for such inclusions are also examined.

MSC:

90C25 Convex programming
90C31 Sensitivity, stability, parametric optimization
49J52 Nonsmooth analysis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abadie J.: On the Kuhn–Tucker Theorem. In: Abadie J. (ed) Nonlinear Programming, pp. 21–36. North Holland (1967) · Zbl 0183.22803
[2] Aubin J.-P. and Ekeland I. (1984). Applied Nonlinear Analysis. Wiley–Interscience, New York · Zbl 0641.47066
[3] Auslender A. and Crouzeix J.-P. (1988). Global regularity theorem. Math. Oper. Res. 13: 243–253 · Zbl 0655.90059 · doi:10.1287/moor.13.2.243
[4] Auslender A. and Teboulle M. (2003). Asymptotic Cones and Functions in Optimization and Variational Inequalities. Springer, Heidelberg · Zbl 1017.49001
[5] Bauschke, H.: Projection algorithms and monotone operators. Ph.D. Thesis, Simon Fraser University, Department of Mathematics, Burnaby, British Columbia, V5A 1S6, Canada (1996)
[6] Bauschke H., Borwein J. and Li W. (1999). Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization. Math. Prog. 86: 135–160 · Zbl 0998.90088 · doi:10.1007/s101070050083
[7] Borwein J. and Lewis A. (2000). Convex Analysis and Nonlinear Optimization, Theory and Examples CMS Books in Mathematics. Springer, New York
[8] Burke J.V. (1991). An exact penalization viewpoint of constrained optimization. SIAM J. Control Optim. 29: 968–998 · Zbl 0737.90060 · doi:10.1137/0329054
[9] Burke J.V. (1991). Calmness and exact penalization. SIAM J. Control Optim. 29: 493–497 · Zbl 0734.90090 · doi:10.1137/0329027
[10] Burke J.V. and Deng S. (2002). Weak sharp minima revisited, part I: Basic theory. Control Cybernetics 31: 439–469 · Zbl 1105.90356
[11] Burke J.V. and Deng S. (2005). Weak sharp minima revisited, part II: Application to linear regularity and error bounds. Math. Program. Ser. B 104: 235–261 · Zbl 1124.90349 · doi:10.1007/s10107-005-0615-2
[12] Burke J.V. and Ferris M.C. (1993). Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31: 1340–1359 · Zbl 0791.90040 · doi:10.1137/0331063
[13] Burke J.V. and Ferris M.C. (1995). A Gauss–Newton method for convex composite optimization. Math. Prog. 71: 179–194 · Zbl 0846.90083
[14] Burke J.V. and Moré J.J. (1988). On the identification of active constraints. SIAM J. Numer. Anal. 25: 1197–1211 · Zbl 0662.65052 · doi:10.1137/0725068
[15] Burke J.V. and Tseng P. (1996). A unified analysis of Hoffman’s bound via Fenchel duality. SIAM J. Optim. 6: 265–282 · Zbl 0849.90093 · doi:10.1137/0806015
[16] Clarke F.H. (1976). A new approach to Lagrange multipliers. Math. Oper. Res. 2: 165–174 · Zbl 0404.90100 · doi:10.1287/moor.1.2.165
[17] Deng S. (1998). Global error bounds for convex inequality systems in Banach spaces. SIAM J. Control Optim. 36: 1240–1249 · Zbl 0909.90250 · doi:10.1137/S0363012995293645
[18] Dontchev A.L. and Rockafellar R.T. (2004). Regularity and conditioning of solution mappings in variational analysis. Set-Valued Anal. 12: 79–109 · Zbl 1046.49021 · doi:10.1023/B:SVAN.0000023394.19482.30
[19] Ekeland, I., Temam, R.: Convex analysis and variational problems. North Holland (1976) · Zbl 0322.90046
[20] Ferris, M.C.: Weak sharp minima and penalty functions in mathematical programming. Tech. Report 779, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin (1988)
[21] Henrion R and Jourani A. (2002). Subdifferential conditions for calmness of convex constraints. SIAM J. Optim. 13: 520–534 · Zbl 1028.49017 · doi:10.1137/S1052623401386071
[22] Henrion R. and Outrata J. (2001). A subdifferential criterion for calmness of multifunctions. J. Math. Anal. Appl. 258: 110–130 · Zbl 0983.49010 · doi:10.1006/jmaa.2000.7363
[23] Henrion R. and Outrata J. (2005). Calmness of constraint systems with applications. Math. Prog. Ser. B. 104: 437–464 · Zbl 1093.90058 · doi:10.1007/s10107-005-0623-2
[24] Hiriart-Urruty J.-B. and Lemaréchal C. (1993). Convex Analysis and Minimization Algorithms I, volume 306 of Grundlehren der Mathematischen Wissenschaften. Springer, Heidelberg
[25] Hoffman A.J. (1952). On approximate solutions to systems of linear inequalities. J. Res. Nat. Bur. Stand. 49: 263–265
[26] Jourani A. (2000). Hoffman’s error bounds, local controllability and sensitivity analysis. SIAM J. Control Optim. 38: 947–970 · Zbl 0945.46023 · doi:10.1137/S0363012998339216
[27] Klatte D. (1997). Hoffman’s error bound for systems of convex inequalities. In: Fiacco, A.V. (eds) Mathematical Programming with Data Perturbations, pp 185–199. Marcel Dekker Publ., Moscow · Zbl 0911.90315
[28] Klatte D. and Li W. (1999). Asymptotic constraint qualifications and global error bounds for convex inequalities. Math. Prog. 84: 137–160 · Zbl 1050.90557
[29] Lewis A.S. and Pang J.-S. (1998). Error bounds for convex inequality systems. In: Crouzeix, J.P., Martinez- Legaz, J.-E. and Volle, M. (eds) Proceedings of the Fifth International Symposium on Generalized Convexity held in Luminy June 17-21, 1996, pp 75–101. Kluwer Academic Publishers, Dordrecht · Zbl 0953.90048
[30] Li W. (1997). Abadie’s constraint qualification, metric regularity and error bounds for differentiable convex inequalities. SIAM J. Optim. 7: 966–978 · Zbl 0891.90132 · doi:10.1137/S1052623495287927
[31] Luo X.D. and Luo Z.Q. (1994). Extension of hoffman’s error bound to polynomial systems. SIAM J. Optim. 4: 383–392 · Zbl 0821.90113 · doi:10.1137/0804021
[32] Maguregui, J.: Regular multivalued functions and algorithmic applications. Ph.D. Thesis, University of Wisconsin at Madison, Madison, WI (1977)
[33] Ng K.F. and Yang W.H. (2004). Regularities and their relations to error bounds. Math. Prog. Ser. A 99: 521–538 · Zbl 1077.90050 · doi:10.1007/s10107-003-0464-9
[34] Ngai H.V. and Thera M. (2005). Error bounds for convex differentiable inequality systems in Banach spaces. Math. Program. Ser. B 104: 465–482 · Zbl 1089.49028 · doi:10.1007/s10107-005-0624-1
[35] Pang J.-S. (1997). Error bounds in mathematical programming. Math. Prog. 79: 299–333 · Zbl 0887.90165
[36] Polyak, B.T.: Sharp minima. In: Proceedings of the IIASA Workshop on Generalized Lagrangians and Their Applications: Laxenburg, Austria. Institute of Control Sciences Lecture Notes, Moscow (1979)
[37] Robinson S.M. (1972). Normed convex processes. Trans. Amer. Math. Soc. 174: 127–140 · Zbl 0264.47018 · doi:10.1090/S0002-9947-1972-0313769-9
[38] Robinson S.M. (1975). An application of error bounds for convex programming in a linear space. SIAM J. Control 13: 271–273 · Zbl 0297.90072 · doi:10.1137/0313015
[39] Robinson S.M. (1976). Regularity and stability for convex multivalued functions. Math. Oper. Res. 1: 130–143 · Zbl 0418.52005 · doi:10.1287/moor.1.2.130
[40] Rockafellar R.T. (1970). Convex Analysis. Princeton University Press, Princeton · Zbl 0193.18401
[41] Rockafellar R.T. (1974). Conjugate Duality and Optimization. SIAM, Philadelphia · Zbl 0296.90036
[42] Rockafellar R.T. and Wets R.J.-B. (1998). Variational Analysis. Springer, Heidelberg · Zbl 0888.49001
[43] Ursescu C. (1975). Multifunctions with closed convex graph. Czech. Math. J. 25: 438–441 · Zbl 0318.46006
[44] Yosida K. (1980). Functional Analysis. Springer, Heidelberg · Zbl 0435.46002
[45] Zălinescu, C.: Weak sharp minima, well-behaving functions and global error bounds for convex inequalities in Banach spaces. In: Bulatov, V., Baturin, V. (ed.) Proceedings of the 12th Baikal International Conference on Optimization Methods and their Applications, pp. 272–284, Institute of System Dynamics and Control Theory of SB RAS, Irkutsk (2001)
[46] Zheng X.Y. and Ng K.F. (2004). Metric regularity and constraint qualifications for convex inequalities on Banach spaces. SIAM J. Optim. 14: 757–772 · Zbl 1079.90103 · doi:10.1137/S1052623403423102
[47] Zheng X.Y. and Ng K.F. (2004). Error moduli for conic convex systems on Banach spaces. Math. Oper. Res. 29: 213–228 · Zbl 1082.90120 · doi:10.1287/moor.1030.0088
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.