Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-20T07:15:05.994Z Has data issue: false hasContentIssue false
  • English
  • Français

METRIC REGULARITY—A SURVEY PART II. APPLICATIONS

Part of: Topological linear spaces and related structures Maps and general types of spaces defined by maps Optimality conditions Existence theories Nonlinear operators and their properties Calculus on manifolds; nonlinear operators

Published online by Cambridge University Press:  08 July 2016

A. D. IOFFE
A. D. IOFFE*
Affiliation:
Department of Mathematics, Technion, Haifa 32000, Israel email [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Metric regularity theory lies in the very heart of variational analysis, a relatively new discipline whose appearance was, to a large extent, determined by the needs of modern optimization theory in which such phenomena as nondifferentiability and set-valued mappings naturally appear. The roots of the theory go back to such fundamental results of the classical analysis as the implicit function theorem, Sard theorem and some others. The paper offers a survey of the state of the art of some principal parts of the theory along with a variety of its applications in analysis and optimization.

Keywords

set-valued mappingregularitytransversalityimplicit functionLipschitz stabilitySard theorem

MSC classification

Primary: 49J53: Set-valued and variational analysis
Secondary: 54C60: Set-valued maps 58C06: Set valued and function-space valued mappings 47H04: Set-valued operators 49K40: Sensitivity, stability, well-posedness 46A30: Open mapping and closed graph theorems; completeness (including $B$-, $B_r$-completeness) 90C31: Sensitivity, stability, parametric optimization
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 101 , Issue 3 , December 2016 , pp. 376 - 417
Copyright
© 2016 Australian Mathematical Publishing Association Inc. 

References

Aragon Artacho, F. J. and Geoffroy, M. H., ‘Characterization of metric regularity of subdifferential’, J. Convex Anal. 15 (2008), 365–380.Google Scholar
Aragon Artacho, F. J. and Geoffroy, M. H., ‘Metric subregularity of convex subdifferential in Banach sopaces’, J. Nonlinear Convex Anal. 15 (2014), 35–47.Google Scholar
Arutyunov, A., Avakov, E., Gelman, B., Dmitruk, A. and Obukhovski, V., ‘Locally covering maps in metric spaces and coincidence points’, J. Fixed Point Theory Appl. 5 (2009), 106–127.Google Scholar
Aubin, J.-P. and Cellina, A., Differential Inclusions (Springer, Berlin, 1984).CrossRefGoogle Scholar
Aubin, J. P. and Frankowska, H., Set-Valued Analysis (Birkhäuser, Boston, 1990).Google Scholar
Avakov, E. R., Magaril-Il’yaev, G. G. and Tikhomirov, V. M., ‘Lagrange’s principle in extremal problems with constraints’, Russian Math. Surveys 68(3) (2013), 401–434.CrossRefGoogle Scholar
Azé, D. and Corvellec, J.-N., ‘On the sensitivity analysis of Hoffmann’s constant for systems of linear inequalities’, SIAM J. Optim. 12 (2002), 913–927.CrossRefGoogle Scholar
Azé, D. and Corvellec, J.-N., ‘Characterization of error bounds for lower semicontinuous functions on metric spaces’, ESAIM Control Optim. Calc. Var. 10 (2004), 409–425.CrossRefGoogle Scholar
Azé, D., Corvellec, J.-N. and Lucchetti, R., ‘Variational pairs and application to stability in nonsmooth analysis’, Nonlinear Anal. 49 (2002), 643–670.CrossRefGoogle Scholar
Barbet, L., Dambrine, M., Daniilidis, A. and Rifford, L., ‘Sard theorems for Lipschitz functions and applications in optimization’, Israel J. Math., to appear.Google Scholar
Bauschke, H. and Borwein, J. M., ‘On projection algorithms for solving convex feasibility problems’, SIAM Rev. 38 (1996), 367–426.CrossRefGoogle Scholar
Bochnak, J., Coste, M. and Roy, M.-F., Real Algebraic Geometry (Springer, 1998).CrossRefGoogle Scholar
Bolte, J., Daniilidis, A. and Lewis, A. S., ‘The Morse–Sard theorem for non-differentiable subanalytic functions’, J. Math. Anal. Appl. 321 (2006), 729–740.CrossRefGoogle Scholar
Borwein, J. M., ‘Adjoint process duality’, Math. Oper. Res 8 (1983), 403–434.CrossRefGoogle Scholar
Borwein, J. M., ‘Norm duality for convex processes and applications’, J. Optim. Theory Appl. 48 (1986), 53–64.CrossRefGoogle Scholar
Borwein, J. M. and Lewis, A. S., Convex Analysis and Nonlinear Optimization, 2nd edn. (Springer, 2006).CrossRefGoogle Scholar
Bregman, L. M., ‘The method of successive projections for finding a common point of convex sets’, Dokl. Akad. Nauk 6 (1965), 688–692.Google Scholar
Cánovas, M. J., Lopez, M. A., Mordukhovich, M. S. and Parra, J., ‘Variational analysis in linear semi-infinite and infinite programming 1: stability of linear inequality system of feasible solutions’, SIAM J. Optim. 20 (2009), 1504–1526.CrossRefGoogle Scholar
Cibulka, R. and Fabian, M., ‘A note on Robinson–Ursescu and Lyusternik–Graves theorems’, Math. Program. B 139 (2013), 89–101.CrossRefGoogle Scholar
Cibulka, R., Fabian, M. and Ioffe, A. D., ‘On primal regularity estimates for single-valued mappings’, J. Fixed Point Theory Appl. 17 (2015), 187–208.CrossRefGoogle Scholar
Clarke, F. H., ‘A new approach to Lagrange multipliers’, Math. Oper. Res. 1 (1976), 165–174.CrossRefGoogle Scholar
Clarke, F. H., ‘On the inverse function theorem’, Pacific J. Math. 64 (1976), 97–102.CrossRefGoogle Scholar
Clarke, F. H., ‘Necessary conditions for a general control problem’, in: Calculus of Variations and Control Theory (ed. Russel, D. L.) (Academic Press, 1976), 257–279.Google Scholar
Clarke, F. H., Optimization and Nonsmooth Analysis (Wiley-Interscience, New York, 1983).Google Scholar
Clarke, F. H., Necessary Conditions in Dynamic Optimization, Memoirs of the American Mathematical Society, 816 (AMS, Providence, RI, 2005).Google Scholar
Coste, M., ‘An introduction to $o$ -minimal geometry’, Inst. Rech. Math., Univ. de Rennes, 1999 (http://name.math.univ-rennes1.fr/michel.coste/polyens/OMIN.pdf).Google Scholar
Coulibali, A. and Crouzeix, J.-P., ‘Conditions numbers and error bounds in convex programming’, Math. Program. B 116 (2009), 79–113.CrossRefGoogle Scholar
Dmitruk, A. V., Milyutin, A. A. and Osmolovskii, N. P., ‘Ljusternik’s theorem and the theory of extrema’, Russian Math. Surveys 35(6) (1980), 11–51.CrossRefGoogle Scholar
Dontchev, A. L., ‘Characterizations of Lipschitz stability in optimization’, in: Recent Developments in Well-Posed Variational Problems (eds. Lucchetti, R. and Revalski, J.) (Kluwer, 1995), 95–115.CrossRefGoogle Scholar
Dontchev, A. L. and Frankowska, H., ‘Lyusternik–Graves theorem and fixed points’, Proc. Amer. Math. Soc. 139 (2011), 521–534.CrossRefGoogle Scholar
Dontchev, A. L. and Frankowska, H., ‘Lyusternik–Graves theorem and fixed points 2’, J. Convex Anal. 19 (2012), 955–974.Google Scholar
Dontchev, A. L. and Rockafellar, R. T., ‘Characterizations of strong regularity for variational inequalities over polyhedral convex sets’, SIAM J. Optim. 6 (1996), 1087–1105.CrossRefGoogle Scholar
Dontchev, A. L. and Rockafellar, R. T., Implicit Functions and Solution Mappings, 2nd edn. (Springer, 2014).CrossRefGoogle Scholar
Drusvyatsky, D. and Ioffe, A. D., ‘Quadratic growth and critical point stability of semi-algebraic functions’, Math. Program. A 153 (2015), 635–653.CrossRefGoogle Scholar
Drusvyatsky, D., Ioffe, A. D. and Lewis, A. S., ‘Alternating projections and coupling slope’, Found. Comput. Math. 18 (2015), 1637–1651.Google Scholar
Drusvyatsky, D. and Lewis, A. S., ‘Semi-algebraic functions have small subdifferentials’, Math. Program. B 140 (2013), 5–29.CrossRefGoogle Scholar
Drusvyatsky, D. and Lewis, A. S., ‘Tilt stability, uniform quadratic growth and strong metric regularity of the subdifferential’, SIAM J. Optim. 23 (2013), 256–267.CrossRefGoogle Scholar
Dubovitslii, A. Y. and Milyutin, A. A., ‘Zadachi na ekstremum pri nalichii ogranichenij’, Zh. Vychisl. Mat. Mat. Fiz. 5(3) (1965), 395–453; (in Russian; English translation: ‘Problems for extremum under constraints’, USSR Comput. Math. Math. Phys. 5 (1965)).Google Scholar
Eaves, B. C. and Rothblum, U. G., ‘Relationships of properties of piecewise affine maps over ordered fields’, Linear Algebra Appl. 132 (1990), 1–63.CrossRefGoogle Scholar
Facchinei, F. and Pang, J. S., Finite-Dimensional Variational Inequalities and Complementarity Problems (Springer, New York, 2003).Google Scholar
Filippov, A. F., ‘Classical solutions of differential inclusions with multivalued right-hand sides’, SIAM J. Control Optim. 5 (1967), 609–621.CrossRefGoogle Scholar
Gamkrelidze, R. V., Foundations of Optimal Control (TGU, Tbilisi, 1977), (in Russian).Google Scholar
Ginsburg, B. and Ioffe, A. D., ‘Maximum principle for general semilinear optimal control problems’, in: Nonsmooth Analysis and Geometric Methods in Optimal Control (eds. Mordukhovich, B. and Sussmann, H.) (Springer, 1995), 81–110.Google Scholar
Gubin, L. G., Polyak, B. T. and Raik, E. V., ‘The method of projections for finding a common point of convex sets’, Comput. Math. Math. Phys. 7 (1967), 1–24.CrossRefGoogle Scholar
Hoffman, A. J., ‘On approximate solutions of systems of linear inequalities’, J. Res. Nat. Bureau Standards e49 (1952), 263–265.CrossRefGoogle Scholar
Hörmander, L., ‘Sur la fonction d’appui des ensembles convexes dans un espace localement convex’, Ark. Mat. 3 (1955), 181–186.CrossRefGoogle Scholar
Ioffe, A. D., ‘Necessary and sufficient conditions for a local minimum. Reduction theorem and first order conditions’, SIAM J. Control Optim. 17 (1979), part 1, 245–251, part 2, 261–265.Google Scholar
Ioffe, A. D., ‘Non-smooth analysis: differential calculus of non-differentiable mappings’, Trans. Amer. Math. Soc. 255 (1981), 1–55.CrossRefGoogle Scholar
Ioffe, A. D., ‘Approximate subdifferentials and applications 1. The finite dimensional theory’, Trans. Amer. Math. Soc. 28 (1984), 389–416.Google Scholar
Ioffe, A. D., ‘On the local surjection property’, Nonlinear Anal. 11 (1987), 565–592.CrossRefGoogle Scholar
Ioffe, A. D., ‘Approximate subdifferentials and applications 3. The metric theory’, Mathematika 36 (1989), 1–38.CrossRefGoogle Scholar
Ioffe, A. D., ‘Directional compactness, scalarization and nonsmooth semi-Fredholm mappings’, Nonlinear Anal. 29 (1997), 201–219.CrossRefGoogle Scholar
Ioffe, A. D., ‘Metric regularity and subdifferential calculus’, Uspekhi Mat. Nauk 55(3) (2000), 103–162; (in Russian), English translation: Russian Math. Surveys 55 (2000), 501–558.Google Scholar
Ioffe, A. D., ‘Critical values of set-valued mappings with stratifiable graphs. Extensions of Sard and Smale–Sard theorems’, Proc. Amer. Math. Soc. 136 (2008), 3111–3119.CrossRefGoogle Scholar
Ioffe, A. D., ‘Regularity on fixed sets’, SIAM J. Optim. 21 (2011), 1345–1370.CrossRefGoogle Scholar
Ioffe, A. D., ‘Variational analysis and mathematical economics 2. Nonsmooth regular economies’, Adv. Math. Econ. 14 (2011), 17–38.CrossRefGoogle Scholar
Ioffe, A. D., ‘Convexity and variational analysis’, in: Computational and Analytical Mathematics (eds. Bailey, D., Bauschke, H., Garvan, F., Thera, M., Vanderwerff, J. and Wolkovicz, H.) (Springer, 2013), 397–428.Google Scholar
Ioffe, A. D., ‘Metric regularity, fixed points and some associated problems of variational analysis’, J. Fixed Point Theory Appl. 15 (2014), 67–99.CrossRefGoogle Scholar
Ioffe, A. D., ‘Metric regularity—a survey. Part 1. Theory’, J. Aust. Math. Soc., in press.Google Scholar
Ioffe, A. D., ‘On necessary conditions for minimum’, Fundam. Prikl. Mat. 19 (2014), 121–152.Google Scholar
Ioffe, A. D., ‘On variational inequalities over polyhedral sets’, Math. Program. (submitted)arXiv:1508.06607v1.Google Scholar
Ioffe, A. D. and Penot, J.-P., ‘Subdifferentials of performance functions and calculus of coderivatives of set-valued mappings’, Serdica Math. J. 22 (1996), 359–384.Google Scholar
Ioffe, A. D. and Sekiguchi, Y., ‘Regularity estimates for convex multifunctions’, Math. Program. B 117 (2009), 255–270.CrossRefGoogle Scholar
Ioffe, A. D. and Tihomirov, V. M., Theory of Extremal Problems (Nauka, Moscow, 1974), (in Russian); English translation: North-Holland, 1979.Google Scholar
Jourani, A. and Thibault, L., ‘Metric regularity and subdifferential calculus in Banach spaces’, Set-Valued Anal. 3 (1995), 87–100.CrossRefGoogle Scholar
Jourani, A. and Thibault, L., ‘Verifiable conditions for openness and metric regularity in Banach spaces’, Trans. Amer. Math. Soc. 347 (1995), 1255–1268.CrossRefGoogle Scholar
Klatte, D. and Kummer, B., Nonsmooth Equations in Optimization (Kluwer, New York, 2002).Google Scholar
Klatte, D. and Kummer, B., ‘Optimization methods and stability of inclusions in Banach spaces’, Math. Program. B 117 (2009), 305–330.CrossRefGoogle Scholar
Klatte, D. and Li, W., ‘Asymptotic constraint qualifications and global error bounds for convex inequalities’, Math. Program. 84 (1999), 137–160.CrossRefGoogle Scholar
Kruger, A. Y., ‘Generalized differentials of nonsmooth functions, mimeographed notes’, 1332–81 (Belorussian State University, 1981), 64 pages (in Russian).Google Scholar
Kruger, A. Y., ‘Generalized differentials of nonsmooth functions and necessary conditions for an extremum’, Sib. Math. J. 26 (1985), 370–379.CrossRefGoogle Scholar
Levitin, E. S., Milyutin, A. A. and Osmolovskii, N. P., ‘On conditions for a local minimum in problems with constraints’, in: Mathematical Economics and Functional Analysis (ed. Mityagin, B. S.) (Nauka, Moscow, 1974), (in Russian).Google Scholar
Lewis, A. S., ‘Ill-conditioned convex processes and conic linear systems’, Math. Oper. Res. 24 (1999), 829–834.CrossRefGoogle Scholar
Lewis, A. S., ‘Ill-conditioned inclusions’, Set-Valued Anal. 9 (2001), 375–381.CrossRefGoogle Scholar
Lewis, A. S., Luke, D. R. and Malick, J., ‘Local linear convergence for alternating and averaged nonconvex projections’, Found. Comput. Math. 9 (2009), 485–513.CrossRefGoogle Scholar
Lewis, A. S. and Pang, J. S., ‘Error bounds for convex inequality systems’, in: Generalized Convexity, Generalized Monotonicity: Recent Results (eds. Crouzeix, J. P., Martinez-Legas, J. E. and Volle, M.) (Kluwer, 1998), 75–110.CrossRefGoogle Scholar
Loewen, P. D., ‘Limits of Fréchet normals in nonsmooth analysis’, in: Optimization and Nonlinear Analysis (eds. Ioffe, A., Markus, M. and Reich, S.) (Longman, New York, 1992).Google Scholar
Mordukhovich, B. S., Approximation Methods in Problems of Optimization and Control (Nauka, Moscow, 1988), (in Russian).Google Scholar
Mordukhovich, B. S., Variational Analysis and Generalized Differentiation, vol. 1, 2 (Springer, 2006).Google Scholar
Mordukhovich, B. S., Peña, J. F. and Roschina, V., ‘Applying metric regularity to compute a condition measure of a smoothing algorithm for matrix games’, SIAM J. Optim. 20 (2010), 3490–3511.CrossRefGoogle Scholar
Ng, K. F. and Yang, W. H., ‘Error bounds for some convex functions and distance composite functions’, SIAM J. Optim. 15 (2005), 1042–1056.CrossRefGoogle Scholar
Páles, Z., ‘Inverse and implicit function theorems for nonsmooth maps in Banach spaces’, J. Math. Anal. Appl. 209 (1997), 202–220.CrossRefGoogle Scholar
Páles, Z. and Zeidan, V., ‘Infinite dimensional Clarke generalized Jacobian’, J. Convex Anal. 14 (2007), 433–454.Google Scholar
Páles, Z. and Zeidan, V., ‘Generalized Jacobian for functions with infinite dimensional range and domain’, Set-Valued Anal. 15 (2007), 331–375.CrossRefGoogle Scholar
Poliquin, R. and Rockafellar, R. T., ‘Tilt stability of a local minimum’, SIAM J. Optim. 8 (1998), 287–299.CrossRefGoogle Scholar
Robinson, S. M., ‘Normed convex processes’, Trans. Amer. Math. Soc. 174 (1972), 127–140.CrossRefGoogle Scholar
Robinson, S. M., ‘Stability theory for system of inequalities. Part 1: Linear systems’, SIAM J. Numer. Anal. 12 (1975), 754–769.CrossRefGoogle Scholar
Robinson, S. M., ‘Stability theory for system of inequalities. Part II: Differentiable nonlinear systems’, SIAM J. Numer. Anal. 13 (1976), 497–513.CrossRefGoogle Scholar
Robinson, S. M., ‘Regularity and stability for convex multivalued functions’, Math. Oper. Res. 1 (1976), 130–143.CrossRefGoogle Scholar
Robinson, S. M., ‘First order conditions for general nonlinear optimization’, SIAM J. Appl. Math. 30 (1976), 597–608.CrossRefGoogle Scholar
Robinson, S. M., ‘Generalized equations and their solutions. Part 1: Basic theory’, Math. Program. Study 10 (1979), 128–141.CrossRefGoogle Scholar
Robinson, S. M., ‘Strongly regular generalized equations’, Math. Oper. Res. 5 (1980), 43–62.CrossRefGoogle Scholar
Robinson, S. M., ‘An implicit function theorem for a class of nonsmooth functions’, Math. Oper. Res. 16 (1991), 292–309.CrossRefGoogle Scholar
Robinson, S. M., ‘Normal maps induced by linear transformations’, Math. Oper. Res. 17 (1992), 691–714.CrossRefGoogle Scholar
Rockafellar, R. T., Monotone Processes of Convex and Concave Type, Memoirs of the American Mathematical Society, 77 (AMS, Providence, RI, 1967).Google Scholar
Rockafellar, R. T., Convex Analysis (Princeton University Press, Princeton, NJ, 1970).CrossRefGoogle Scholar
Rockafellar, R. T. and Wets, R. J. B., Variational Analysis (Springer, 1998).CrossRefGoogle Scholar
Song, W., ‘Calmness and error bounds for convex constraint systems’, SIAM J. Optim. 17 (2006), 353–371.CrossRefGoogle Scholar
Tikhomirov, V. M., Fundamental Principles of the Theory of Extremal Problems (John Wiley & Sons, 1982).Google Scholar
Ursescu, C., ‘Multifunctions with closed convex graphs’, Czechoslovak Math. J. 25 (1975), 438–411.CrossRefGoogle Scholar
Vinter, R. B., Optimal Control (Birkhäuser, Boston, 2000).Google Scholar
Vinter, R. B., ‘The role of metric regularity in state constrained optimal control’, in: Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference Seville, Spain (2005), 262–265.Google Scholar
von Neumann, J., ‘Functional operators 2. The geometry of orthogonal spaces’, Ann. Math. Stud. 22 (1950), Princeton.Google Scholar
Warga, J., ‘Controllability and necessary conditions in unilateral problems without differentiability assumptions’, SIAM J. Conrol Optim. 14 (1976), 546–573.CrossRefGoogle Scholar
Warga, J., ‘Derivate containers, inverse functions and controllability’, in: Calculus of Variations and Optimal Control (ed. Russel, D. L.) (Academic, New York, 1976), 13–46.Google Scholar
Yomdin, Y. and Comte, G., Tame Geometry with Applications to Smooth Analysis, Springer LNM Series, 1834 (2004).CrossRefGoogle Scholar
Yorke, J. A., ‘The maximum principle and controllability of nonlinear equations’, SIAM J. Control Optim. 10 (1972), 334–338.CrossRefGoogle Scholar
Zalinescu, C., Convex Analysis in General Vector Spaces (World Scientific, New Jersey, 2002).CrossRefGoogle Scholar
Zheng, X. Y. and Ng, K. F., ‘Metric regularity and constraint qualifications for convex inequalities in Banach spaces’, SIAM J. Optim. 14 (2004), 757–772.CrossRefGoogle Scholar