Tiến Sĩ Đối đạo hàm của ánh xạ nón pháp tuyến và ứng dụng

CODERIVATIVES OF NORMAL CONEMAPPINGS AND APPLICATIONS (Đối đạo hàm của ánh xạ nón pháp tuyến và ứng dụng)
LUẬN ÁN TIẾN SỸ TOÁN HỌC
NĂM 2014
Contents
Table of Notations vi
List of Figures viii
Introduction ix
Chapter 1. Preliminary 1
1.1 Basic Denitions and Conventions 1
1.2 Normal and Tangent Cones . 3
1.3 Coderivatives and Subdierential 6
1.4 Lipschitzian Properties and Metric Regularity . 9
1.5 Conclusions 11

Chapter 2. Linear Perturbations of Polyhedral Normal Cone Mappings 12
2.1 The Normal Cone Mapping F(x; b) . 12
2.2 The Frechet Coderivative of F(x; b) . 16
2.3 The Mordukhovich Coderivative of F(x; b) . 26
2.4 AVIs under Linear Perturbations 37
2.5 Conclusions 42
Chapter 3. Nonlinear Perturbations of Polyhedral Normal Cone Mappings 43
3.1 The Normal Cone Mapping F(x; A; b) 43
3.2 Estimation of the Frechet Normal Cone to gphF 48
3.3 Estimation of the Limiting Normal Cone to gphF . 54
3.4 AVIs under Nonlinear Perturbations . 59
3.5 Conclusions 66

Chapter 4. A Class of Linear Generalized Equations 67
4.1 Linear Generalized Equations 67
4.2 Formulas for Coderivatives 69
4.2.1 The Frechet Coderivative of N(x; ) 70
4.2.2 The Mordukhovich Coderivative of N(x; ) 78
4.3 Necessary and Sucient Conditions for Stability 83
4.3.1 Coderivatives of the KKT point set map 83
4.3.2 The Lipschitz-like property 84
4.4 Conclusions 91
General Conclusions 92
List of Author's Related Papers 93
References 94

Introduction
Motivated by solving optimization problems, the concept of derivative was
rst introduced by Pierre de Fermat. It led to the Fermat stationary princi-
ple, which plays a crucial role in the development of dierential calculus and
serves as an eective tool in various applications. Nevertheless, many fundamental
objects having no derivatives, no rst-order approximations (dened
by certain derivative mappings) occur naturally and frequently in mathematical
models. The objects include nondierentiable functions, sets with nonsmooth
boundaries, and set-valued mappings. Since the classical dierential
calculus is inadequate for dealing with such functions, sets, and mappings, the
appearance of generalized dierentiation theories is an indispensable trend.
In the 1960s, dierential properties of convex sets and convex functions
have been studied. The fundamental contributions of J.-J. Moreau and
R. T. Rockafellar have been widely recognized. Their results led to the beautiful
theory of convex analysis [47]. The derivative-like structure for convex
functions, called subdierential, is one of the main concepts in this theory.
In contrast to the singleton of derivatives, subdierential is a collection of
subgradients. Convex programming which is based on convex analysis plays
a fundamental role in Mathematics and in applied sciences.
In 1973, F. H. Clarke dened basic concepts of a generalized dierentiation
theory, which works for locally Lipschitz functions, in his doctoral dissertation
under the supervision of R. T. Rockafellar. In Clarke's theory, convexity
is a key point; for instance, subdierential in the sense of Clarke is always a
closed convex set. In the later 1970s, the concepts of Clarke have been developed
for lower semicontinuous extended-real-valued functions in the works of
R. T. Rockafellar, J.-B. Hiriart-Urruty, J.-P. Aubin, and others. Although
the theory of Clarke is beautiful due to the convexity used, as well as to
the elegant proofs of many fundamental results, the Clarke subdierential
and the Clarke normal cone face with the challenge of being too big, so too
rough, in complicated practical problems where nonconvexity is an inherent
property. Despite to this, Clarke's theory has opened a new chapter in the
development of nonlinear analysis and optimization theory (see, e.g., [8], [2]).
In the mid 1970s, to avoid the above-mentioned convexity limitations of
the Clarke concepts, B. S. Mordukhovich introduced the notions of limiting
normal cone and limiting subdierential which are based entirely on dualspace
constructions. His dual approach led to a modern theory of generalized
dierentiation [28] with a variety of applications [29]. Long before the publication
of these books, Mordukhovich's contributions to Variational Analysis
had been presented in the well-known monograph of R. T. Rockafellar and
R. J.-B. Wets [48].
The limiting subdierential is generally nonconvex and smaller than the
Clarke subdierential. Similarly, the limiting normal cone to a closed set in
a Banach space is nonconvex in general and usually smaller than the Clarke
normal cone. Therefore, necessary optimality conditions in nonlinear programming
and optimal control in terms of the limiting subdierential and
limiting normal cone are much tighter than that given by the corresponding
Clarke's concepts. Furthermore, the Mordukhovich criteria for the Lipchitzlike
property (that is the pseudo-Lipschitz property in the original terminology
of J.-P. Aubin [1], or the Aubin continuity as suggested by A. L. Dontchev

and R. T. Rockafellar [11], [12]) and the metric regularity of multifunctions
are remarkable tools to study stability of variational inequalities, generalized
equations, and the Karush-Kuhn-Tucker point sets in parametric optimization
problems. Note that if one uses Clarke's theory then only sucient
conditions for stability can be obtained. Meanwhile, Mordukhovich's theory
provides one with both necessary and sucient conditions for stability. Another
advantage of the latter theory is that its system of calculus rules is
much more developed than that of Clarke's theory. So, the wide range of applications
and bright prospects of Mordukhovich's generalized dierentiation
theory are understandable.
In the late 1990s, V. Jeyakumar and D. T. Luc introduced the concepts of
approximate Jacobian and corresponding generalized subdierential. It can
be seen [18] that using the approximate Jacobian one can establish conditions
for stability, metric regularity, and local Lipschitz-like property of the solution
maps of parametric inequality systems involving nonsmooth continuous
functions and closed convex sets. Calculus rules and various applications of
the approximate Jacobian can be found in the monograph [17]. It is worthy
to study relationships between the concepts of coderivative and approximate
Jacobian. In [33], the authors show that the Mordukhovich coderivative and
the approximate Jacobian have a little in common. These concepts are very
dierent, and they require dierent methods of study and lead to results in
dierent forms.
References
[1] J.-P. Aubin, Lipschitz behavior of solutions to convex minimization
problems, Math. Oper. Res., 9 (1984), pp. 87{111.
[2] J.-P. Aubin and H. Frankowska, Set-Valued Analysis, Birkhauser
Boston-Basel-Berlin, 1990.
[3] D. Bartl, A short algebraic proof of the Farkas lemma, SIAM J. Optim.,
19 (2008), pp. 234{239.
[4] J. M. Borwein and Q. J. Zhu, Techniques of Variational Analysis,
CMS Books in Mathematics, Springer, New York, 2005.
[5] N. H. Chieu, T. D. Chuong, J.-C. Yao, and N. D. Yen, Charac-
terizing convexity of a function by its Frechet and limiting second-order
subdierentials, Set-Valued Var. Anal., 19 (2011), pp. 75{96.
[6] N. H. Chieu and N. Q. Huy, Second-order subdierentials and con-
vexity of real-valued functions, Nonlinear Anal., 74 (2011), pp. 154{160.
[7] N. H. Chieu and N. T. Q. Trang, Coderivative and monotonicity of
continuous mappings, Taiwanese J. Math., 16 (2012), pp. 353{365.
[8] F. H. Clarke, Optimization and Nonsmooth Analysis, CMS Books in
Mathematics, Wiley, New York, 1983.
[9] G. Colombo, R. Henrion, N. D. Hoang, and B. S. Mor-
dukhovich, Optimal control of the sweeping process, Dyn. Contin. Discrete
Impuls. Syst. Ser. B Appl. Algorithms, 19 (2012), pp. 117{159.
[10] A. R. Conn, N. I. M. Gould, and P. L. Toint, Trust-Region
Methods, MPS-SIAM Ser. Optim., Philadelphia, 2000.
[11] A. L. Dontchev and R. T. Rockafellar, Characterizations of
strong regularity for variational inequalities over polyhedral convex sets,
SIAM J. Optim., 6 (1996), pp. 1087{1105.
94
[12] A. L. Dontchev and R. T. Rockafellar, Implicit Functions and
Solution Mappings, Springer, Dordrecht, 2009.
[13] R. Henrion, B. S. Mordukhovich, and N. M. Nam, Second-order
analysis of polyhedral systems in nite and innite dimensions with ap-
plications to robust stability of variational inequalities, SIAM J. Optim.,
20 (2010), pp. 2199{2227.
[14] R. Henrion, J. Outrata, and T. Surowiec, Analysis of M-
stationary points to an EPEC modeling oligopolistic competition in an
electricity spot market, ESAIM Control Optim. Calc. Var., 18 (2012),
pp. 295{317.
[15] N. Q. Huy and J.-C. Yao, Exact formulae for coderivatives of normal
cone mappings to perturbed polyhedral convex sets, J. Optim. Theory
Appl., 157 (2013), pp. 25{43.
[16] A. D. Ioffe and V. M. Tihomirov, Theory of Extremal Problems,
North-Holland Publishing Company, Amsterdam-New York-Oxford,
1979.
[17] V. Jeyakumar and D. T. Luc, Nonsmooth Vector Functions and
Continuous Optimization, Optimization and Its Applications, Springer,
New York, 2008.
[18] V. Jeyakumar and N. D. Yen, Solution stability of nonsmooth contin-
uous systems with applications to cone-constrained optimization, SIAM
J. Optim., 14 (2004), pp. 1106{1127.
[19] H. A. Le Thi, T. Pham Dinh, and N. D. Yen, Properties of two
DC algorithms in quadratic programming, J. Global Optim., 49 (2011),
pp. 481{495.
[20] G. M. Lee, N. N. Tam, and N. D. Yen, Quadratic Programming and
Ane Variational Inequalities: A Qualitative Study, Springer-Verlag,
New York, 2005.
[21] G. M. Lee, N. N. Tam, and N. D. Yen, Stability of linear-quadratic
minimization over Euclidean balls, SIAM J. Optim., 22 (2012), pp. 936{
952.
[22] G. M. Lee and N. D. Yen, Frechet and normal coderivatives of im-
plicit multifunctions, Appl. Anal., 90 (2011), pp. 1011{1027.
95
[23] G. M. Lee and N. D. Yen, Coderivatives of a Karush-Kuhn-Tucker
point set map and applications, Nonlinear Anal., 95 (2014), pp. 191{201.
[24] A. B. Levy and B. S. Mordukhovich, Coderivatives in parametric
optimization, Math. Program., 99 (2004), pp. 311{327.
[25] S. Lu and S. M. Robinson, Variational inequalities over perturbed
polyhedral convex sets, Math. Oper. Res., 33 (2008), pp. 689{711.
[26] J. M. Martinez, Local minimizers of quadratic functions on Euclidean
balls and spheres, SIAM J. Optim., 4 (1994), pp. 159{176.
[27] B. S. Mordukhovich, Coderivative analysis of variational systems, J.
Global Optim., 28 (2004), pp. 347{362.
[28] B. S. Mordukhovich, Variational Analysis and Generalized Dieren-
tiation, vol. I: Basic Theory, Springer-Verlag, Berlin, 2006.
[29] B. S. Mordukhovich, Variational Analysis and Generalized Dieren-
tiation, vol. II: Applications, Springer-Verlag, Berlin, 2006.
[30] B. S. Mordukhovich and J. V. Outrata, On second-order subdif-
ferentials and their applications, SIAM J. Optim., 12 (2001), pp. 139{
169.
[31] B. S. Mordukhovich and R. T. Rockafellar, Second-order subdif-
ferential calculus with applications to tilt stability in optimization, SIAM
J. Optim., 22 (2012), pp. 953{986.
[32] N. M. Nam, Coderivatives of normal cone mappings and Lipschitzian
stability of parametric variational inequalities, Nonlinear Anal., 73
(2010), pp. 2271{2282.
[33] N. M. Nam and N. D. Yen, Relationships between approximate Jaco-
bians and coderivatives, J. Nonlinear Convex Anal., 8 (2007), pp. 121{
133.
[34] T. Pham Dinh and H. A. Le Thi, A d.c. optimization algorithm for
solving the trust-region subproblem, SIAM J. Optim., 8 (1998), pp. 476{
505.
[35] R. R. Phelps, Convex Functions, Monotone Operators and Dieren-
tiability, Springer-Verlag, Berlin, 1993.
96
[36] H. T. Phung, On the locally uniform openness of polyhedral sets, Acta
Math. Vietnam., 25 (2000), pp. 273{284.
[37] R. A. Poliquin and R. T. Rockafellar, Tilt stability of a local
minimum, SIAM J. Optim., 8 (1998), pp. 287{299.
[38] N. T. Qui, Linearly perturbed polyhedral normal cone mappings and
applications, Nonlinear Anal., 74 (2011), pp. 1676{1689.
[39] N. T. Qui, New results on linearly perturbed polyhedral normal cone
mappings, J. Math. Anal. Appl., 381 (2011), pp. 352{364.
[40] N. T. Qui, Upper and lower estimates for a Frechet normal cone, Acta