The radius of metric regularity

Dontchev, A.; Lewis, A.; Rockafellar, R.

doi:10.1090/S0002-9947-02-03088-X

The radius of metric regularity
HTML articles powered by AMS MathViewer

by A. L. Dontchev, A. S. Lewis and R. T. Rockafellar PDF

Trans. Amer. Math. Soc. 355 (2003), 493-517 Request permission

Abstract:

Metric regularity is a central concept in variational analysis for the study of solution mappings associated with “generalized equations”, including variational inequalities and parameterized constraint systems. Here it is employed to characterize the distance to irregularity or infeasibility with respect to perturbations of the system structure. Generalizations of the Eckart-Young theorem in numerical analysis are obtained in particular.

References

J. M. Borwein, Norm duality for convex processes and applications, J. Optim. Theory Appl. 48 (1986), no. 1, 53–64. MR 825384, DOI 10.1007/BF00938589
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
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
James Weldon Demmel, On condition numbers and the distance to the nearest ill-posed problem, Numer. Math. 51 (1987), no. 3, 251–289. MR 895087, DOI 10.1007/BF01400115
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, The Graves theorem revisited, J. Convex Anal. 3 (1996), no. 1, 45–53. MR 1422750
A. L. Dontchev and W. W. Hager, An inverse mapping theorem for set-valued maps, Proc. Amer. Math. Soc. 121 (1994), no. 2, 481–489. MR 1215027, DOI 10.1090/S0002-9939-1994-1215027-7
A. L. Dontchev and R. T. Rockafellar, Characterizations of strong regularity for variational inequalities over polyhedral convex sets, SIAM J. Optim. 6 (1996), no. 4, 1087–1105. MR 1416530, DOI 10.1137/S1052623495284029
Sharon Filipowski, On the complexity of solving sparse symmetric linear programs specified with approximate data, Math. Oper. Res. 22 (1997), no. 4, 769–792. MR 1484682, DOI 10.1287/moor.22.4.769
Robert M. Freund and Jorge R. Vera, Some characterizations and properties of the “distance to ill-posedness” and the condition measure of a conic linear system, Math. Program. 86 (1999), no. 2, Ser. A, 225–260. MR 1725230, DOI 10.1007/s101070050088
Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
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
Xiaojun Chen, Yukihiro Shogenji, and Maretsugu Yamasaki, Verification for existence of solutions of linear complementarity problems, Linear Algebra Appl. 324 (2001), no. 1-3, 15–26. Special issue on linear algebra in self-validating methods. MR 1810442, DOI 10.1016/S0024-3795(99)00272-4
A. S. Lewis, Ill-conditioned convex processes and conic linear systems, Math. Oper. Res. 24 (1999), no. 4, 829–834. MR 1854354, DOI 10.1287/moor.24.4.829
A. S. Lewis, Ill-conditioned inclusions, Set-Valued Anal. 9 (2001), no. 4, 375–381. MR 1869082, DOI 10.1023/A:1012610112736
L. A. Lusternik, Sur les extrêmes relatifs de fonctionnelles, Mat. Sbornik 41 (1934), 390-401. (Russian; French summary)
B. S. Mordukhovich, Coderivatives of set-valued mappings: calculus and applications, Nonlinear Anal. 30 (1997), 3059–3070.
Javier Peña, Understanding the geometry of infeasible perturbations of a conic linear system, SIAM J. Optim. 10 (2000), no. 2, 534–550. MR 1740958, DOI 10.1137/S1052623497323674
James Renegar, Linear programming, complexity theory and elementary functional analysis, Math. Programming 70 (1995), no. 3, Ser. A, 279–351. MR 1361602, DOI 10.1007/BF01585941
Stephen M. Robinson, Normed convex processes, Trans. Amer. Math. Soc. 174 (1972), 127–140. MR 313769, DOI 10.1090/S0002-9947-1972-0313769-9
J. L. Walsh, On interpolation by functions analytic and bounded in a given region, Trans. Amer. Math. Soc. 46 (1939), 46–65. MR 55, DOI 10.1090/S0002-9947-1939-0000055-0
Stephen M. Robinson, Strongly regular generalized equations, Math. Oper. Res. 5 (1980), no. 1, 43–62. MR 561153, DOI 10.1287/moor.5.1.43
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683, DOI 10.1515/9781400873173
R. Tyrrell Rockafellar and Roger J.-B. Wets, Variational analysis, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317, Springer-Verlag, Berlin, 1998. MR 1491362, DOI 10.1007/978-3-642-02431-3
Walter Rudin, Functional analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill, Inc., New York, 1991. MR 1157815
Corneliu Ursescu, Multifunctions with convex closed graph, Czechoslovak Math. J. 25(100) (1975), no. 3, 438–441. MR 388032, DOI 10.21136/CMJ.1975.101337