Complete characterization of openness, metric regularity, and Lipschitzian properties of multifunctions

Mordukhovich, Boris

doi:10.1090/S0002-9947-1993-1156300-4

Complete characterization of openness, metric regularity, and Lipschitzian properties of multifunctions
HTML articles powered by AMS MathViewer

by Boris Mordukhovich PDF

Trans. Amer. Math. Soc. 340 (1993), 1-35 Request permission

Abstract:

We consider some basic properties of nonsmooth and set-valued mappings (multifunctions) connected with open and inverse mapping principles, distance estimates to the level sets (metric regularity), and a locally Lipschitzian behavior. These properties have many important applications to various problems in nonlinear analysis, optimization, control theory, etc., especially for studying sensitivity and stability questions with respect to perturbations of initial data and parameters. We establish interrelations between these properties and prove effective criteria for their fulfillment stated in terms of robust generalized derivatives for multifunctions and nonsmooth mappings. The results obtained provide complete characterizations of the properties under consideration in a general setting of closed-graph multifunctions in finite dimensions. They ensure new information even in the classical cases of smooth single-valued mappings as well as multifunctions with convex graphs.

References

Jean-Pierre Aubin, Lipschitz behavior of solutions to convex minimization problems, Math. Oper. Res. 9 (1984), no. 1, 87–111. MR 736641, DOI 10.1287/moor.9.1.87
Jean-Pierre Aubin and Ivar Ekeland, Applied nonlinear analysis, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1984. A Wiley-Interscience Publication. MR 749753
Jean-Pierre Aubin and Hélène Frankowska, Set-valued analysis, Systems & Control: Foundations & Applications, vol. 2, Birkhäuser Boston, Inc., Boston, MA, 1990. MR 1048347
J. M. Borwein, Stability and regular points of inequality systems, J. Optim. Theory Appl. 48 (1986), no. 1, 9–52. MR 825383, DOI 10.1007/BF00938588
J. M. Borwein and D. M. Zhuang, Verifiable necessary and sufficient conditions for openness and regularity of set-valued and single-valued maps, J. Math. Anal. Appl. 134 (1988), no. 2, 441–459. MR 961349, DOI 10.1016/0022-247X(88)90034-0
James V. Burke, An exact penalization viewpoint of constrained optimization, SIAM J. Control Optim. 29 (1991), no. 4, 968–998. MR 1111671, DOI 10.1137/0329054
Frank H. Clarke, Generalized gradients and applications, Trans. Amer. Math. Soc. 205 (1975), 247–262. MR 367131, DOI 10.1090/S0002-9947-1975-0367131-6
Frank H. Clarke, Optimization and nonsmooth analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1983. A Wiley-Interscience Publication. MR 709590
Frank H. Clarke, Methods of dynamic and nonsmooth optimization, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 57, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. MR 1085948, DOI 10.1137/1.9781611970142
Roberto Cominetti, Metric regularity, tangent sets, and second-order optimality conditions, Appl. Math. Optim. 21 (1990), no. 3, 265–287. MR 1036588, DOI 10.1007/BF01445166
A. V. Dmitruk, A. A. Milyutin, and N. P. Osmolovskiĭ, Ljusternik’s theorem and the theory of the extremum, Uspekhi Mat. Nauk 35 (1980), no. 6(216), 11–46, 215 (Russian). MR 601755
Asen L. Dontchev and William W. Hager, Lipschitzian stability in nonlinear control and optimization, SIAM J. Control Optim. 31 (1993), no. 3, 569–603. MR 1214755, DOI 10.1137/0331026
I. Ekeland, On the variational principle, J. Math. Anal. Appl. 47 (1974), 324–353. MR 346619, DOI 10.1016/0022-247X(74)90025-0
Anthony V. Fiacco, Introduction to sensitivity and stability analysis in nonlinear programming, Mathematics in Science and Engineering, vol. 165, Academic Press, Inc., Orlando, FL, 1983. MR 721641
Halina Frankowska, An open mapping principle for set-valued maps, J. Math. Anal. Appl. 127 (1987), no. 1, 172–180. MR 904219, DOI 10.1016/0022-247X(87)90149-1
Hélène Frankowska, Some inverse mapping theorems, Ann. Inst. H. Poincaré C Anal. Non Linéaire 7 (1990), no. 3, 183–234 (English, with French summary). MR 1065873, DOI 10.1016/S0294-1449(16)30300-6
Lawrence M. Graves, Some mapping theorems, Duke Math. J. 17 (1950), 111–114. MR 35398
Hubert Halkin, Interior mapping theorem with set-valued derivatives, J. Analyse Math. 30 (1976), 200–207. MR 486353, DOI 10.1007/BF02786714
J.-B. Hiriart-Urruty, A short proof of the variational principle for approximate solutions of a minimization problem, Amer. Math. Monthly 90 (1983), no. 3, 206–207. MR 691372, DOI 10.2307/2975554
Alexander D. Ioffe, Regular points of Lipschitz functions, Trans. Amer. Math. Soc. 251 (1979), 61–69. MR 531969, DOI 10.1090/S0002-9947-1979-0531969-6
A. D. Ioffe, Nonsmooth analysis: differential calculus of nondifferentiable mappings, Trans. Amer. Math. Soc. 266 (1981), no. 1, 1–56. MR 613784, DOI 10.1090/S0002-9947-1981-0613784-7
A. D. Ioffe, Approximate subdifferentials and applications. I. The finite-dimensional theory, Trans. Amer. Math. Soc. 281 (1984), no. 1, 389–416. MR 719677, DOI 10.1090/S0002-9947-1984-0719677-1
A. D. Ioffe, On the local surjection property, Nonlinear Anal. 11 (1987), no. 5, 565–592. MR 886649, DOI 10.1016/0362-546X(87)90073-3
A. D. Ioffe, Approximate subdifferentials and applications. III. The metric theory, Mathematika 36 (1989), no. 1, 1–38. MR 1014198, DOI 10.1112/S0025579300013541
A. D. Ioffe and V. M. Tihomirov, Theorie der Extremalaufgaben, VEB Deutscher Verlag der Wissenschaften, Berlin, 1979 (German). Translated from the Russian by Bernd Luderer. MR 527119
A. Jourani and L. Thibault, Approximate subdifferential and metric regularity: the finite-dimensional case, Math. Programming 47 (1990), no. 2, (Ser. A), 203–218. MR 1059393, DOI 10.1007/BF01580860
Alan J. King and R. Tyrrell Rockafellar, Sensitivity analysis for nonsmooth generalized equations, Math. Programming 55 (1992), no. 2, Ser. A, 193–212. MR 1167597, DOI 10.1007/BF01581199
A. Ya. Kruger, Properties of generalized differentials, Sibirsk. Mat. Zh. 26 (1985), no. 6, 54–66, 189 (Russian). MR 816504
A. Ya. Kruger, A covering theorem for set-valued mappings, Optimization 19 (1988), no. 6, 763–780. MR 967038, DOI 10.1080/02331938808843391

Generalized normals and derivatives, and necessary conditions for extrema in nondifferentiable programming

Generalizes normals and derivatives, and necessary conditions for extrema in nondifferentiable programming

A. Ja. Kruger and B. Š. Morduhovič, Extremal points and the Euler equation in nonsmooth optimization problems, Dokl. Akad. Nauk BSSR 24 (1980), no. 8, 684–687, 763 (Russian, with English summary). MR 587714
Bernd Kummer, An implicit-function theorem for $C^{0,1}$-equations and parametric $C^{1,1}$-optimization, J. Math. Anal. Appl. 158 (1991), no. 1, 35–46. MR 1113397, DOI 10.1016/0022-247X(91)90264-Z

Conditional extrema of functionals

41

George J. Minty, Monotone (nonlinear) operators in Hilbert space, Duke Math. J. 29 (1962), 341–346. MR 169064
B. Sh. Mordukhovich, Maximum principle in the problem of time optimal response with nonsmooth constraints, Prikl. Mat. Meh. 40 (1976), no. 6, 1014–1023 (Russian); English transl., J. Appl. Math. Mech. 40 (1976), no. 6, 960–969 (1977). MR 0487669, DOI 10.1016/0021-8928(76)90136-2

Metric approximations and necessary optimality conditions for general classes of nonsmooth extremal problems

22

B. Sh. Mordukhovich, Nonsmooth analysis with nonconvex generalized differentials and conjugate mappings, Dokl. Akad. Nauk BSSR 28 (1984), no. 11, 976–979 (Russian, with English summary). MR 771737
B. Sh. Mordukhovich, Metody approksimatsiĭ v zadachakh optimizatsii i upravleniya, “Nauka”, Moscow, 1988 (Russian). MR 945143
Boris S. Mordukhovich, Sensitivity analysis in nonsmooth optimization, Theoretical aspects of industrial design (Wright-Patterson Air Force Base, OH, 1990) SIAM, Philadelphia, PA, 1992, pp. 32–46. MR 1157413
B. S. Mordukhovich, On variational analysis of differential inclusions, Optimization and nonlinear analysis (Haifa, 1990) Pitman Res. Notes Math. Ser., vol. 244, Longman Sci. Tech., Harlow, 1992, pp. 199–213. MR 1184644
Boris Mordukhovich, Lipschitzian stability of constraint systems and generalized equations, Nonlinear Anal. 22 (1994), no. 2, 173–206. MR 1258955, DOI 10.1016/0362-546X(94)90033-7
Boris S. Mordukhovich, Generalized differential calculus for nonsmooth and set-valued mappings, J. Math. Anal. Appl. 183 (1994), no. 1, 250–288. MR 1273445, DOI 10.1006/jmaa.1994.1144

Fonctionelles convexes

Jean-Paul Penot, Metric regularity, openness and Lipschitzian behavior of multifunctions, Nonlinear Anal. 13 (1989), no. 6, 629–643. MR 998509, DOI 10.1016/0362-546X(89)90083-7
B. H. Pourciau, Analysis and optimization of Lipschitz continuous mappings, J. Optim. Theory Appl. 22 (1977), no. 3, 311–351. MR 454813, DOI 10.1007/BF00932859
Stephen M. Robinson, Regularity and stability for convex multivalued functions, Math. Oper. Res. 1 (1976), no. 2, 130–143. MR 430181, DOI 10.1287/moor.1.2.130
Stephen M. Robinson, Stability theory for systems of inequalities. II. Differentiable nonlinear systems, SIAM J. Numer. Anal. 13 (1976), no. 4, 497–513. MR 410522, DOI 10.1137/0713043
Stephen M. Robinson, Generalized equations and their solutions. I. Basic theory, Math. Programming Stud. 10 (1979), 128–141. Point-to-set maps and mathematical programming. MR 527064, DOI 10.1007/bfb0120850
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
Ralph T. Rockafellar, The theory of subgradients and its applications to problems of optimization, R & E, vol. 1, Heldermann Verlag, Berlin, 1981. Convex and nonconvex functions. MR 623763

Proximal subgradients, marginal functions, and augmented Lagrangians in nonconvex optimization

6

R. T. Rockafellar, Extensions of subgradient calculus with applications to optimization, Nonlinear Anal. 9 (1985), no. 7, 665–698. MR 796082, DOI 10.1016/0362-546X(85)90012-4
R. Tyrrell Rockafellar, Lipschitzian properties of multifunctions, Nonlinear Anal. 9 (1985), no. 8, 867–885. MR 799890, DOI 10.1016/0362-546X(85)90024-0
R. T. Rockafellar, Maximal monotone relations and the second derivatives of nonsmooth functions, Ann. Inst. H. Poincaré Anal. Non Linéaire 2 (1985), no. 3, 167–184 (English, with French summary). MR 797269
R. T. Rockafellar, Proto-differentiability of set-valued mappings and its applications in optimization, Ann. Inst. H. Poincaré C Anal. Non Linéaire 6 (1989), no. suppl., 449–482. Analyse non linéaire (Perpignan, 1987). MR 1019126, DOI 10.1016/S0294-1449(17)30034-3
R. T. Rockafellar, Dualization of subgradient conditions for optimality, Nonlinear Anal. 20 (1993), no. 6, 627–646. MR 1214732, DOI 10.1016/0362-546X(93)90024-M
A. Shapiro and J. F. Bonnans, Sensitivity analysis of parametrized programs under cone constraints, SIAM J. Control Optim. 30 (1992), no. 6, 1409–1422. MR 1185630, DOI 10.1137/0330075
Lionel Thibault, Subdifferentials of compactly Lipschitzian vector-valued functions, Ann. Mat. Pura Appl. (4) 125 (1980), 157–192. MR 605208, DOI 10.1007/BF01789411
Lionel Thibault, On subdifferentials of optimal value functions, SIAM J. Control Optim. 29 (1991), no. 5, 1019–1036. MR 1110085, DOI 10.1137/0329056
Jay S. Treiman, Clarke’s gradients and epsilon-subgradients in Banach spaces, Trans. Amer. Math. Soc. 294 (1986), no. 1, 65–78. MR 819935, DOI 10.1090/S0002-9947-1986-0819935-8
Corneliu Ursescu, Multifunctions with convex closed graph, Czechoslovak Math. J. 25(100) (1975), no. 3, 438–441. MR 388032
J. Warga, Fat homeomorphisms and unbounded derivate containers, J. Math. Anal. Appl. 81 (1981), no. 2, 545–560. MR 622836, DOI 10.1016/0022-247X(81)90081-0