Transactions of the American Mathematical Society

Author(s): A. L. Dontchev; A. S. Lewis; R. T. Rockafellar
Journal: Trans. Amer. Math. Soc. 355 (2003), 493-517.
MSC (2000): Primary 49J53; Secondary 49J52, 90C31
Posted: October 4, 2002
Retrieve article in: PDF DVI PostScript

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.

1.: J. M. BORWEIN, Norm duality for convex processes and applications, Journal of Optimization Theory and Applications 48 (1986), 53-64. MR 87d:90126
2.: J. M. BORWEIN AND D. M. ZHUANG, Verifiable necessary and sufficient conditions for openness and regularity of set-valued maps, J. Math. Anal. Appl. 134 (1988), 441-459. MR 90h:90185
3.: R. COMINETTI, Metric regularity, tangent cones, and second-order optimality conditions, Appl. Math. Optim. 21 (1990), 265-287. MR 91g:90174
4.: J. DEMMEL, The condition number and the distance to the nearest ill-posed problem, Numerische Math. 51 (1987), 251-289. MR 88i:15014
5.: A. V. DMITRUK, A. A. MILYUTIN, AND N. P. OSMOLOVSKI ${\u{\i}}\kern.15em$ , The Lusternik theorem and the theory of extremum, Uspekhi Math. Nauk 35 (1980), no. 6, 11-46; English transl., Russian Math. Surveys 35 (1980), no. 6, 11-52. MR 82c:58010
6.: A. L. DONTCHEV, The Graves theorem revisited, J. Convex Anal. 3 (1996), 45-53. MR 97g:46055
7.: A. L. DONTCHEV AND W. W. HAGER, An inverse function theorem for set-valued maps, Proc. Amer. Math. Soc. 121 (1994), 481-489. MR 94h:58020
8.: A. L. DONTCHEV AND R. T. ROCKAFELLAR, Characterizations of strong regularity for variational inequalities over polyhedral convex sets, SIAM J. Optim. 6 (1996), 1087-1105. MR 97f:90095
9.: S. FILIPOWSKI, On the complexity of solving sparse symmetric linear approximate data, Math. Oper. Research 22 (1997), 769-792. MR 99a:90201
10.: R. M. FREUND AND J. R. VERA, Some characterizations and properties of the distance to ill-posedness and the condition number of a conic linear system, Math. Programming, Ser. A 86 (1999), 225-260. MR 2000i:90089
11.: L. M. GRAVES, Some mapping theorems, Duke Math. J. 17 (1950), 111-114. MR 11:729e
12.: R. A. HORN AND C. JOHNSON, Matrix Analysis. Cambridge University Press, Cambridge, U.K., 1985. MR 87e:15001
13.: A. D. IOFFE, Nonsmooth analysis: differential calculus of nondifferentiable mappings, Trans. Amer. Math. Soc. 266 (1981), 1-56. MR 82j:58018
14.: A. D. IOFFE, Metric regularity and subdifferential calculus, Uspekhi Mat. Nauk 55 (2000), 103-162 (Russian). English translation: Russian Math. Surveys 55 (2000), 501-558. MR 2001j:90102
15.: A. S. LEWIS, Ill-conditioned convex processes and conic linear systems, Math. of Oper. Research 23 (1999), 829-834. MR 2002f:90128
16.: A. S. LEWIS, Ill-conditioned inclusions, Set-Valued Analysis 9 (2001), 375-381. MR 2002h:49029
17.: L. A. LUSTERNIK, Sur les extrêmes relatifs de fonctionnelles, Mat. Sbornik 41 (1934), 390-401. (Russian; French summary)
18.: B. S. MORDUKHOVICH, Coderivatives of set-valued mappings: calculus and applications, Nonlinear Anal. 30 (1997), 3059-3070.
19.: J. PEÑA, Understanding the geometry of infeasible perturbations of a conic linear system, SIAM J. Optim. 10 (2000), 534-550. MR 2000k:90054
20.: J. RENEGAR, Linear programming, complexity theory and elementary functional analysis, Math. Programming Ser. A 70 (1995), 279-351. MR 96i:90029
21.: S. M. ROBINSON, Normed convex processes, Trans. Amer. Math. Soc. 174 (1972), 127-140. MR 47:2323
22.: S. M. ROBINSON, Regularity and stability for convex multifunctions, Math. of Oper. Research 1 (1976), 130-143. MR 55i:1388
23.: S. M. ROBINSON, Strongly regular generalized equations, Math. of Oper. Research 5 (1980), 43-62. MR 81m:90109
24.: R. T. ROCKAFELLAR, Convex Analysis. Princeton University Press, Princeton, N.J., 1970. MR 43:445
25.: R. T. ROCKAFELLAR AND ROGER J.-B. WETS, Variational Analysis, Springer-Verlag, Berlin, 1997. MR 98m:49001
26.: W. RUDIN, Functional Analysis, Second Ed., McGraw-Hill, New York, 1991. MR 92k:46001
27.: C. URSESCU, Multifunctions with closed convex graph, Czechoslovak Mathematical Journal 25 (1975), 438-441. MR 52:8869

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 49J53, 49J52, 90C31

A. L. Dontchev
Affiliation: Mathematical Reviews, American Mathematical Society, Ann Arbor, Michigan 48107-8604
Email: ald@ams.org

A. S. Lewis
Affiliation: Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6
Email: aslewis@sfu.ca

R. T. Rockafellar
Affiliation: Department of Mathematics, University of Washington, Seattle, Washington 98195
Email: rtr@math.washington.edu

DOI: 10.1090/S0002-9947-02-03088-X
PII: S 0002-9947(02)03088-X
Keywords: Metric regularity, perturbations, distance to irregularity, distance to infeasibility, Eckart-Young theorem, Lusternik-Graves theorem, Robinson-Ursescu theorem, coderivatives
Received by editor(s): July 27, 2000
Posted: October 4, 2002
Additional Notes: Research partially supported by the NSF Grant DMS--9803098 for the first and the third author, and by the Natural Sciences and Engineering Research Council of Canada for the second author
Copyright of article: Copyright 2002, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS