Weak sharp minima revisited. II: Application to linear regularity and error bounds. (English) Zbl 1124.90349

Summary: The notion of weak sharp minima is 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. It has been studied extensively by several authors. This paper is the second of a series on this subject where the basic results on weak sharp minima in Part I [Control Cybern. 31, No. 3, 439–469 (2002; Zbl 1105.90356)] are applied to a number of important problems in convex programming.
In Part II we study 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. We obtain both new results and reproduce several existing results from a fresh perspective.


90C31 Sensitivity, stability, parametric optimization
49J52 Nonsmooth analysis


Zbl 1105.90356
Full Text: DOI


[1] Aubin, J.-P., Ekeland, I.: Applied Nonlinear Analysis. Wiley–Interscience, (1984) · Zbl 0641.47066
[2] Auslender, A., Crouzeix, J.-P.: Global regularity theorem. Math. Oper. Res. 13, 243–253 (1988) · Zbl 0655.90059
[3] Barbu, V., Precupanu, Th.: Convexity and Optimization in Banach Spaces. D. Reidel Publishing Co., (1986) · Zbl 0594.49001
[4] Bauschke, H.: Projection algorithms and monotone operators. Ph.D. Thesis, Simon Fraser University, Dept. of Math., Burnaby, British Columbia, V5A 1S6, Canada, (1996)
[5] Bauschke, H., Borwein, J., Li, W.: Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization. Math. Prog. 86, 135–160 (1999) · Zbl 0998.90088
[6] Borwein, J., Lewis, A.: Convex Analysis and Nonlinear Optimization. Theory and Examples. CMS Books in Mathematics. Springer-Verlag, New York, (2000) · Zbl 0953.90001
[7] Brøndsted, R., Rockafellar, R.T.: On the subdifferentiability of convex functions. Proc. Am. Math. Soc. 16, 605–611 (1965) · Zbl 0141.11801
[8] Burke, J.V., Deng, S.: Weak sharp minima revisited, part i: Basic theory. Control and Cybernetics 31, 439–469 (2002) · Zbl 1105.90356
[9] Burke, J.V., Ferris, M.C.: Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31, 1340–1359 (1993) · Zbl 0791.90040
[10] Burke, J.V., Tseng, P.: A unified analysis of Hoffman’s bound via Fenchel duality. SIAM J. Optim. 6, 265–282 (1996) · Zbl 0849.90093
[11] Clarke, F.H.: Optimization and Nonsmooth Analysis. Classics in Applied Mathematics. Reprinted by SIAM, (1990) · Zbl 0696.49002
[12] Deng, S.: Global error bounds for convex inequality systems in Banach spaces. SIAM J. Control Optim. 36, 1240–1249 (1998) · Zbl 0909.90250
[13] Diestel, J.: Sequences and Series in Banach Spaces. Springer, (1984) · Zbl 0542.46007
[14] Ekeland, I., Temam, R.: Convex Analysis and Variational Problems. North Holland, (1976) · Zbl 0322.90046
[15] Ferris, M.C.: Weak sharp minima and penalty functions in mathematical programming. Tech. Report 779, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1988)
[16] Göpfert, A., Riahi, H., Tammer, C., Zalinescu, C.: Variational Methods in Partially Ordered Spaces. CMS Books in Mathematics. Springer, (2003) · Zbl 1140.90007
[17] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I, volume 306 of Grundlehren der Mathematischen Wissenschaften. Springer–Verlag, (1993)
[18] Hoffman, A.J.: On approximate solutions to systems of linear inequalities. J. Res. Nat. Bur. Standards 49, 263–265 (1952)
[19] Jameson, G.J.O.: The duality of pairs of wedges. Proc. London Math. Soc. 24, 531–547 (1972) · Zbl 0233.46009
[20] Klatte, D.: Hoffman’s error bound for systems of convex inequalities. In: Fiacco A.V., (eds.), Mathematical Programming with Data Perturbations. Marcel Dekker Publ., Moscow, (1998) · Zbl 0911.90315
[21] Klatte, D., Li, W.: Asymptotic constraint qualifications and global error bounds for convex inequalities. Math. Prog. 84, 137–160 (1999) · Zbl 1050.90557
[22] Lewis, A.S., Pang, J.-S.: Error bounds for convex inequality systems. In: J.P. Crouzeix, J.-E. Martinez-Legaz, Volle, M., (eds.), Proceedings of the Fifth International Symposium on Generalized Convexity held in Luminy June 17-21, 1996, Dordrecht, (1998). Kluwer Academic Publishers, pp. 75–101 · Zbl 0953.90048
[23] Li, C., Ng, K.F.: Constraint qualification, the strong CHIP, and best approximation with convex constraints in Banach spaces. SIAM J. Optim. 14, 757–772 (2004) · Zbl 1079.90103
[24] Li, W.: Abadie’s constraint qualification, metric regularity, and error bounds for differentiable convex inequalities. SIAM J. Optim. 7, 966–978 (1997) · Zbl 0891.90132
[25] Luo, X.D., Luo, Z.Q.: Extension of hoffman’s error bound to polynomial systems. SIAM J. Optim. 4, 383–392 (1994) · Zbl 0821.90113
[26] Ng, K.F., Yang, W.H.: Regularities and their relations to error bounds. Math. Prog. Ser. A 99, 521–538 (2004) · Zbl 1077.90050
[27] Ng, K.F., Zheng, X.Y.: Characterizations of error bounds for convex multifunctions on Banach spaces. Math. Oper. Res. 29, 45–63 (2004) · Zbl 1082.90114
[28] Pang, J.S.: Error bounds in mathematical programming. Math. Prog. 79, 299–332 (1997) · Zbl 0887.90165
[29] 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)
[30] Robinson, S.M.: An application of error bounds for convex programming in a linear space. SIAM J. Control 13, 271–273 (1975) · Zbl 0297.90072
[31] Rockafellar, R.T.: Level sets and continuity of conjugate convex functions. Trans. Am. Math. Soc. 123, 46–63 (1966) · Zbl 0145.15802
[32] Rockafellar, R.T.: Convex Analysis. Princeton University Press, (1970) · Zbl 0193.18401
[33] Rockafellar, R.T.: Conjugate Duality and Optimization. SIAM, (1974) · Zbl 0296.90036
[34] Rockafellar, R.T.: Integral functionals, normal integrands and measurable selections. In: Nonlinear Operators in the Calculus of Variations, number 543 in Lecture Notes in Mathematics, Springer-Verlag, (1976), pp. 157–207
[35] Volle, M.: Sous-différentiel d’une enveloppe supérieure de fonctions convexes. C. R. Acad. Sci. Paris, I Math 317, 845–849 (1993) · Zbl 0792.46029
[36] Yosida, K.: Functional Analysis. Springer-Verlag, (1980) · Zbl 0435.46002
[37] Zalinescu, C.: Weak sharp minima, well-behaving functions and global error bounds for convex inequalities in Banach spaces. In: V. Bulatov, V. Baturin (eds.), Proceedings of the 12th Baikal International Conference on Optimization Methods and their Applications, Irkutsk,. Institute of System Dynamics and Control Theory of SB RAS, pp. 272–284 (2001)
[38] Zalinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, (2002)
[39] Zheng, X.Y., Ng, K.F.: Error moduli for conic convex systems on Banach spaces. Math. Oper. Res. 29, 231–228 (2004) · Zbl 1082.90120
[40] Zheng, X.Y., Ng, K.F.: Metric regularity and constraint qualifications for convex inequalities on banach spaces. SIAM J. Optim. 14, 757–772 (2004) · Zbl 1079.90103
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.