×

Stability theory for parametric generalized equations and variational inequalities via nonsmooth analysis. (English) Zbl 0826.49008

In the paper a new approach to the sensitivity analysis for parametric generalized equations of the form \[ 0\in f(p, z)+ Q(z) \] is presented where \(f(.,.)\) is a continuous vector-valued function and \(Q(.)\) is a multifunction with closed graph. The author describes sufficient and necessary conditions for the locally pseudo-Lipschitz dependence of the solution set on the parameter \(p\).
For this papers generalized differentiability notions are introduced using a new normal cone \(N(x, \Omega)\) to a set \(\Omega\) at a point \(x\in \Omega\). This normal cone is in general not convex, but it is smaller than the Clarke normal cone such that sharper stability assertions can be expected.
In the usual manner the coderivative of the multifunction \(\phi(.)\) at the point \((x, y)\in \text{gph } \phi\) is defined by \[ D^* \phi(x, y)(y^*):= \{x^*\mid (x^*, - y^*)\in N((x, y),\text{ gph } \phi)\}. \] Similarly, for a real-valued function the associated subdifferentials of first- and second-order are introduced which turn out to be smaller than the subdifferentials in sense of Clarke/Rockafellar.
Assuming special Lipschitz properties of the functions \(f\) and \(Q\) the author presents local stability conditions for the generalized equation near the point \((p, z)\) in such a form that the adjoint equation \[ 0\in D^*_z f(p, z)(y^*)+ D^* Q(z, -f(p, z))(y^*) \] admits only the trivial solution \(y^*= 0\).
First the theory is proved for the linear case, i.e., in case of \(f(p, z)= Ap+ z\). Then for the smooth case (i.e., \(f\) is strictly differentiable in \(z\)) the assertion is derived by linearizing the function \(f\). At least for the nonsmooth case the main result is proved using the Robinson strong approximation for the function \(f\) and a stability assertion of Dontchev/Hager.
In all cases some corollaries are formulated regarding a special structure of the multifunction \(Q(.)\), e.g., a) \(\text{gph } Q\) is convex; b) \(Q(z)= E\) for \(z\in \Omega\), \(=\emptyset\) otherwise, where \(\Omega\) and \(E\) are convex sets; c) \(Q(z)= \{y\mid \vartheta(z, y)= \Lambda\}\), where \(\vartheta\) is a (continuous or smooth, respectively) vector-valued function and \(\Lambda\) is a closed set; d) \(Q(z)= \{y\mid \vartheta_i(z, y)\leq 0\), \(i\in I\), \(\vartheta_i(z, y)= 0\), \(i\in J\}\), where \(\vartheta_i\) are smooth real-valued functions; e) \(Q(z)= \partial^-\varphi(z)\) if \(|\varphi(z)|< \infty\), \(=\emptyset\) otherwise using the introduced general subdifferential of a real-valued function \(\varphi\); e) \(Q(z)= \{0\}\).
In the last section the author points out that by assumption of additional monotony properties the solution set is locally single-valued and Lipschitz continuous.

MSC:

49J52 Nonsmooth analysis
49J40 Variational inequalities
90C31 Sensitivity, stability, parametric optimization
58C15 Implicit function theorems; global Newton methods on manifolds
58C25 Differentiable maps on manifolds
58C07 Continuity properties of mappings on manifolds
26B10 Implicit function theorems, Jacobians, transformations with several variables
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Jean-Pierre Aubin, Lipschitz behavior of solutions to convex minimization problems, Math. Oper. Res. 9 (1984), no. 1, 87 – 111. · Zbl 0539.90085
[2] Jean-Pierre Aubin and Hélène Frankowska, Set-valued analysis, Systems & Control: Foundations & Applications, vol. 2, Birkhäuser Boston, Inc., Boston, MA, 1990. · Zbl 0713.49021
[3] 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. · Zbl 0654.49004
[4] 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. · Zbl 0582.49001
[5] Michael G. Crandall and Pierre-Louis Lions, Viscosity solutions of Hamilton-Jacobi equations, Trans. Amer. Math. Soc. 277 (1983), no. 1, 1 – 42. · Zbl 0599.35024
[6] Asen L. Dontchev and William W. Hager, Implicit functions, Lipschitz maps, and stability in optimization, Math. Oper. Res. 19 (1994), no. 3, 753 – 768. · Zbl 0835.49019
[7] M. S. Gowda and J.-S. Pang, Stability analysis of variational inequality and nonlinear complementarity problems, via the mixed linear complementarity problem and degree theory, Math. Oper. Res. (to appear). · Zbl 0821.90114
[8] Patrick T. Harker and Jong-Shi Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. Programming 48 (1990), no. 2, (Ser. B), 161 – 220. · Zbl 0734.90098
[9] A. D. Ioffe, Approximate subdifferentials and applications. I. The finite-dimensional theory, Trans. Amer. Math. Soc. 281 (1984), no. 1, 389 – 416. · Zbl 0531.49014
[10] Alan J. King and R. Tyrrell Rockafellar, Sensitivity analysis for nonsmooth generalized equations, Math. Programming 55 (1992), no. 2, Ser. A, 193 – 212. · Zbl 0766.90075
[11] A. Kruger and B. Mordukhovich, Generalized normals and derivatives, and necessary conditions for extrema in nondifferentiable programming. I, Depon. VINITI No. 408-80 (1980, Russian).
[12] 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). · Zbl 0449.49015
[13] Bernd Kummer, An implicit-function theorem for \?^{0,1}-equations and parametric \?^{1,1}-optimization, J. Math. Anal. Appl. 158 (1991), no. 1, 35 – 46. · Zbl 0742.49006
[14] B. Kummer, Lipschitzian inverse functions, directional derivatives, and applications in \?^{1,1} optimization, J. Optim. Theory Appl. 70 (1991), no. 3, 561 – 581. · Zbl 0795.49012
[15] Jerzy Kyparisis, Parametric variational inequalities with multivalued solution sets, Math. Oper. Res. 17 (1992), no. 2, 341 – 364. · Zbl 0777.49008
[16] J. Liu, Nonsingular solutions of finite-dimensional variational inequalities: theory and methods, preprint, 1992.
[17] 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). · Zbl 0362.49017
[18] -, Metric approximations and necessary optimality conditions for general classes of nonsmooth extremal problems, Soviet Math. Dokl. 22 (1980), 526-530. · Zbl 0491.49011
[19] Методы аппроксимаций в задачах оптимизации и управления, ”Наука”, Мосцощ, 1988 (Руссиан). · Zbl 0643.49001
[20] 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. · Zbl 0769.90075
[21] 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. · Zbl 0761.49003
[22] Boris Mordukhovich, Complete characterization of openness, metric regularity, and Lipschitzian properties of multifunctions, Trans. Amer. Math. Soc. 340 (1993), no. 1, 1 – 35. · Zbl 0791.49018
[23] Boris Mordukhovich, Lipschitzian stability of constraint systems and generalized equations, Nonlinear Anal. 22 (1994), no. 2, 173 – 206. · Zbl 0805.93044
[24] Jong-Shi Pang, A degree-theoretic approach to parametric nonsmooth equations with multivalued perturbed solution sets, Math. Programming 62 (1993), no. 2, Ser. B, 359 – 383. · Zbl 0802.47057
[25] Jean-Paul Penot, Metric regularity, openness and Lipschitzian behavior of multifunctions, Nonlinear Anal. 13 (1989), no. 6, 629 – 643. · Zbl 0687.54015
[26] Yuping Qiu and Thomas L. Magnanti, Sensitivity analysis for variational inequalities, Math. Oper. Res. 17 (1992), no. 1, 61 – 76. · Zbl 0756.49009
[27] Stephen M. Robinson, Stability theory for systems of inequalities. II. Differentiable nonlinear systems, SIAM J. Numer. Anal. 13 (1976), no. 4, 497 – 513. · Zbl 0347.90050
[28] -, Generalized equations and their solutions, part I: basic theory, Math. Programming Stud. 10 (1979), 128-141. · Zbl 0404.90093
[29] Stephen M. Robinson, Strongly regular generalized equations, Math. Oper. Res. 5 (1980), no. 1, 43 – 62. · Zbl 0437.90094
[30] -, Generalized equations, Math, programming: The State of Art , Springer-Verlag, Berlin and New York, 1982, pp. 346-367.
[31] Stephen M. Robinson, An implicit-function theorem for a class of nonsmooth functions, Math. Oper. Res. 16 (1991), no. 2, 292 – 309. · Zbl 0746.46039
[32] R. T. Rockafellar, Conjugate convex functions in optimal control and the calculus of variations, J. Math. Anal. Appl. 32 (1970), 174 – 222. · Zbl 0218.49004
[33] 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. · Zbl 0462.90052
[34] R. Tyrrell Rockafellar, Lipschitzian properties of multifunctions, Nonlinear Anal. 9 (1985), no. 8, 867 – 885. · Zbl 0573.54011
[35] 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). · Zbl 0581.49009
[36] 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. · Zbl 0888.49001
[37] A. Shapiro, Sensitivity analysis of parametric programs via generalized equations, preprint, 1992.
[38] Lionel Thibault, Subdifferentials of compactly Lipschitzian vector-valued functions, Ann. Mat. Pura Appl. (4) 125 (1980), 157 – 192. · Zbl 0486.46037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.