Abstract
The notion of weak sharp minima unifies a number of important ideas in optimization. Part I of this work provides the foundation for the theory of weak sharp minima in the infinite-dimensional setting. Part II discusses applications of these results to linear regularity and error bounds for nondifferentiable convex inequalities. This work applies the results of Part I to error bounds for differentiable convex inclusions. A number of standard constraint qualifications for such inclusions are also examined.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abadie J.: On the Kuhn–Tucker Theorem. In: Abadie J. (ed) Nonlinear Programming, pp. 21–36. North Holland (1967)
Aubin J.-P. and Ekeland I. (1984). Applied Nonlinear Analysis. Wiley–Interscience, New York
Auslender A. and Crouzeix J.-P. (1988). Global regularity theorem. Math. Oper. Res. 13: 243–253
Auslender A. and Teboulle M. (2003). Asymptotic Cones and Functions in Optimization and Variational Inequalities. Springer, Heidelberg
Bauschke, H.: Projection algorithms and monotone operators. Ph.D. Thesis, Simon Fraser University, Department of Mathematics, Burnaby, British Columbia, V5A 1S6, Canada (1996)
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
Borwein J. and Lewis A. (2000). Convex Analysis and Nonlinear Optimization, Theory and Examples CMS Books in Mathematics. Springer, New York
Burke J.V. (1991). An exact penalization viewpoint of constrained optimization. SIAM J. Control Optim. 29: 968–998
Burke J.V. (1991). Calmness and exact penalization. SIAM J. Control Optim. 29: 493–497
Burke J.V. and Deng S. (2002). Weak sharp minima revisited, part I: Basic theory. Control Cybernetics 31: 439–469
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
Burke J.V. and Ferris M.C. (1993). Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31: 1340–1359
Burke J.V. and Ferris M.C. (1995). A Gauss–Newton method for convex composite optimization. Math. Prog. 71: 179–194
Burke J.V. and Moré J.J. (1988). On the identification of active constraints. SIAM J. Numer. Anal. 25: 1197–1211
Burke J.V. and Tseng P. (1996). A unified analysis of Hoffman’s bound via Fenchel duality. SIAM J. Optim. 6: 265–282
Clarke F.H. (1976). A new approach to Lagrange multipliers. Math. Oper. Res. 2: 165–174
Deng S. (1998). Global error bounds for convex inequality systems in Banach spaces. SIAM J. Control Optim. 36: 1240–1249
Dontchev A.L. and Rockafellar R.T. (2004). Regularity and conditioning of solution mappings in variational analysis. Set-Valued Anal. 12: 79–109
Ekeland, I., Temam, R.: Convex analysis and variational problems. North Holland (1976)
Ferris, M.C.: Weak sharp minima and penalty functions in mathematical programming. Tech. Report 779, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin (1988)
Henrion R and Jourani A. (2002). Subdifferential conditions for calmness of convex constraints. SIAM J. Optim. 13: 520–534
Henrion R. and Outrata J. (2001). A subdifferential criterion for calmness of multifunctions. J. Math. Anal. Appl. 258: 110–130
Henrion R. and Outrata J. (2005). Calmness of constraint systems with applications. Math. Prog. Ser. B. 104: 437–464
Hiriart-Urruty J.-B. and Lemaréchal C. (1993). Convex Analysis and Minimization Algorithms I, volume 306 of Grundlehren der Mathematischen Wissenschaften. Springer, Heidelberg
Hoffman A.J. (1952). On approximate solutions to systems of linear inequalities. J. Res. Nat. Bur. Stand. 49: 263–265
Jourani A. (2000). Hoffman’s error bounds, local controllability and sensitivity analysis. SIAM J. Control Optim. 38: 947–970
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
Klatte D. and Li W. (1999). Asymptotic constraint qualifications and global error bounds for convex inequalities. Math. Prog. 84: 137–160
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
Li W. (1997). Abadie’s constraint qualification, metric regularity and error bounds for differentiable convex inequalities. SIAM J. Optim. 7: 966–978
Luo X.D. and Luo Z.Q. (1994). Extension of hoffman’s error bound to polynomial systems. SIAM J. Optim. 4: 383–392
Maguregui, J.: Regular multivalued functions and algorithmic applications. Ph.D. Thesis, University of Wisconsin at Madison, Madison, WI (1977)
Ng K.F. and Yang W.H. (2004). Regularities and their relations to error bounds. Math. Prog. Ser. A 99: 521–538
Ngai H.V. and Thera M. (2005). Error bounds for convex differentiable inequality systems in Banach spaces. Math. Program. Ser. B 104: 465–482
Pang J.-S. (1997). Error bounds in mathematical programming. Math. Prog. 79: 299–333
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)
Robinson S.M. (1972). Normed convex processes. Trans. Amer. Math. Soc. 174: 127–140
Robinson S.M. (1975). An application of error bounds for convex programming in a linear space. SIAM J. Control 13: 271–273
Robinson S.M. (1976). Regularity and stability for convex multivalued functions. Math. Oper. Res. 1: 130–143
Rockafellar R.T. (1970). Convex Analysis. Princeton University Press, Princeton
Rockafellar R.T. (1974). Conjugate Duality and Optimization. SIAM, Philadelphia
Rockafellar R.T. and Wets R.J.-B. (1998). Variational Analysis. Springer, Heidelberg
Ursescu C. (1975). Multifunctions with closed convex graph. Czech. Math. J. 25: 438–441
Yosida K. (1980). Functional Analysis. Springer, Heidelberg
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)
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
Zheng X.Y. and Ng K.F. (2004). Error moduli for conic convex systems on Banach spaces. Math. Oper. Res. 29: 213–228
Author information
Authors and Affiliations
Corresponding author
Additional information
We dedicate this paper to Professor A. Auslender on the occasion of his 65th birthday. We, and the optimization community at large, have greatly profited from the deep insight and intuition Professor Auslender has brought to the subject over his many years of his service.
J. V. Burke’s research was supported in part by the National Science Foundation Grant No. DMS-0505712.
Rights and permissions
About this article
Cite this article
Burke, J.V., Deng, S. Weak sharp minima revisited, Part III: error bounds for differentiable convex inclusions. Math. Program. 116, 37–56 (2009). https://doi.org/10.1007/s10107-007-0130-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-007-0130-8
Keywords
- Weak sharp minima
- Convex inclusion
- Affine convex inclusion
- Constraint qualification
- Error bounds
- Calmness