VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY
INSTITUTE OF MATHEMATICS
NGUYEN THANH QUI
CODERIVATIVES OF NORMAL CONE MAPPINGS
AND APPLICATIONS
DOCTORAL DISSERTATION IN MATHEMATICS
HANOI - 2014
VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY
INSTITUTE OF MATHEMATICS
Nguyen Thanh Qui
CODERIVATIVES OF NORMAL CONE MAPPINGS
AND APPLICATIONS
Speciality: Applied Mathematics
Speciality code: 62 46 01 12
DOCTORAL DISSERTATION IN MATHEMATICS
Supervisors:
1. Prof. Dr. Hab. Nguyen Dong Yen
2. Dr. Bui Trong Kien
HANOI - 2014
To my beloved parents and family members
Confirmation
This dissertation was written on the basis of my research works carried at
Institute of Mathematics (VAST, Hanoi) under the supervision of Profes-
sor Nguyen Dong Yen and Dr. Bui Trong Kien. All the results presented
have never been published by others.
Hanoi, January 2014
The author
Nguyen Thanh Qui
i
Acknowledgments
I would like to express my deep gratitude to Professor Nguyen Dong Yen and

I am so much indebted to my parents, my sisters and brothers, for their
love and support. I thank my wife for her love and encouragement.
iii
Contents
Table of Notations vi
List of Figures viii
Introduction ix
Chapter 1. Preliminary 1
1.1 Basic Definitions and Conventions . . . . . . . . . . . . . . . . 1
1.2 Normal and Tangent Cones . . . . . . . . . . . . . . . . . . . 3
1.3 Coderivatives and Subdifferential . . . . . . . . . . . . . . . . 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 Fr´echet 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 Fr´echet Normal Cone to gphF . . . . . . . . 48
3.3 Estimation of the Limiting Normal Cone to gphF . . . . . . . 54
iv
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

IR
m×n
set of m ×n-real matrices
detA determinant of a matrix A
A

transposition of a matrix A
A norm of a matrix A
X
∗
topological dual of a norm space X
x
∗
, x canonical pairing
x, y canonical inner product

(u, v) angle between two vectors u and v
B(x, δ) open ball with centered at x and radius δ
¯
B(x, δ) closed ball with centered at x and radius δ
B
X
open unit ball in a norm space X
¯
B
X
closed unit ball in a norm space X
posΩ convex cone generated by Ω
spanΩ linear subspace generated by Ω
dist(x; Ω) distance from x to Ω

(x), ∇f(x) Fr´echet derivative of f at x
ϕ : X → IR extended-real-valued function
domϕ effective domain of ϕ
epiϕ epigraph of ϕ
∂ϕ(x) limiting subdifferential of ϕ at x
∂
2
ϕ(x, y) limiting second-order subdifferential of ϕ at x
relative to y
F : X ⇒ Y multifunction from X to Y
domF domain of F
rgeF range of F
gphF graph of F
kerF kernel of F

D
∗
F (x, y) Fr´echet coderivative of F at (x, y)
D
∗
F (x, y) Mordukhovich coderivative of F at (x, y)
vii
List of Figures
4.1 The sequences {(x
k
, α
k
)}
k∈IN
, {z

tion under the supervision of R. T. Rockafellar. In Clarke’s theory, convexity
is a key point; for instance, subdifferential in the sense of Clarke is always a
closed convex set. In the later 1970s, the concepts of Clarke have been devel-
oped 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 subdifferential
and the Clarke normal cone face with the challenge of being too big, so too
ix
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 subdifferential which are based entirely on dual-
space constructions. His dual approach led to a modern theory of generalized
differentiation [28] with a variety of applications [29]. Long before the publi-
cation 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 subdifferential is generally nonconvex and smaller than the
Clarke subdifferential. 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 pro-
gramming and optimal control in terms of the limiting subdifferential and
limiting normal cone are much tighter than that given by the corresponding
Clarke’s concepts. Furthermore, the Mordukhovich criteria for the Lipchitz-
like property (that is the pseudo-Lipschitz property in the original terminol-
ogy 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 Banach spaces, ϕ : X × W
1
→ IR is a continuously
Fr´echet differentiable function, Θ : W
2
⇒ X is a multifunction (i.e., a set-
valued map) with closed convex values. Consider the minimization problem
min{ϕ(x, w
1
)| x ∈ Θ(w
2
)} (1)
depending on the parameters w = (w
1
, w
2
), which is given by the data set
{ϕ, Θ}. According to the generalized Fermat rule (see, for instance, [20,
pp. 85–86]), if ¯x is a local solution of (1) then
0 ∈ f(¯x, w
1
) + N(¯x; Θ(w
2
)),
where f(¯x, w
1
) = ∇
x
ϕ(¯x, w
1

)) for every x ∈ Θ(w
2
) and F(x, w
2
) := ∅ for
every x ∈ Θ(w
2
), is the parametric normal cone mapping related to the
multifunction Θ(·). Equilibrium problems of the form (2) have been in-
vestigated intensively in the literature (see, e.g., [11], [12], [24], [27], [28,
Chapter 4], [43]). Necessary and sufficient conditions for the Lipschitz-like
property of the solution map (w
1
, w
2
) → S(w
1
, w
2
) of (2) can be character-
ized by using the Mordukhovich criterion. According to the method proposed
by A. L. Dontchev and R. T. Rockafellar [11], which has been developed by
A. B. Levy and B. S. Mordukhovich [24] and by G. M. Lee and N. D. Yen
xi
[22], one has to compute the Fr´echet and the Mordukhovich coderivatives of
F : X × W
2
⇒ X
∗
. Such a computation has been done in [11] for the case

we would like to mention a recent paper [9] where the authors have computed
coderivatives of the normal cone to a rotating closed half-space.
The normal cone mapping considered in [23] is a special case of the normal
cone mapping to the solution set Θ(w
2
) = Θ(p) := {x ∈ X| ψ(x, p) ≤ 0}
where ψ : X ×P → IR is a C
2
-smooth function defined on the product space
of Banach spaces X and P .
More generally, for the solution map
Θ(w
2
) = Θ(p) := {x ∈ X| Ψ(x, p) ∈ K}
of a parametric generalized equality system with Ψ : X × P → Y being
a C
2
-smooth vector function which maps the product space X × P into a
Banach space Y , K ⊂ Y a closed convex cone, the problems of computing
the Fr´echet coderivative (respectively, the Mordukhovich coderivative) of the
Fr´echet normal cone mapping (x, w
2
) →

N(x; Θ(w
2
)) (respectively, of the
limiting normal cone mapping (x, w
2
) → N(x; Θ(w

mental properties of multifunctions: the local Lipschitz-like property defined
by J P. Aubin and the metric regularity which has origin in Ljusternik’s
theorem [16, p. 30].
Chapter 2 studies generalized differentiability properties of the normal cone
mappings associated to perturbed polyhedral convex sets in reflexive Banach
spaces. The obtained results lead to solution stability criteria for a class
of variational inequalities in finite dimensional spaces under linear perturba-
tions. This chapter also answers the two open questions in [52].
Chapter 3 computes the Fr´echet and the Mordukhovich coderivatives of
the normal cone mappings studied in the previous chapter with respect to
xiii
total perturbations. As a consequence, solution stability of affine variational
inequalities under nonlinear perturbations in finite dimensional spaces can
be addressed by means of the Mordukhovich criterion and the coderivative
formula for implicit multifunctions due to A. B. Levy and B. S. Mordukhovich
[24, Theorem 2.1].
Based on a recent paper of G. M. Lee and N. D. Yen [23], Chapter 4 presents
a comprehensive study of the solution stability of a class of linear generalized
equations connected with the parametric trust-region subproblems which are
well-known in nonlinear programming. We show that exact formulas for the
coderivatives of the normal cone mappings associated to perturbed Euclidean
balls can be obtained. Then, combining the formulas with the necessary
and the sufficient conditions for the local Lipschitz-like property of implicit
multifunctions from a paper by G. M. Lee and N. D. Yen [22], we get new
results on stability of the Karush-Kuhn-Tucker point set maps of parametric
trust-region subproblems. This chapter also solves the two open questions in
[23].
The results of Chapter 2 and Chapter 3 were published on the journals
Nonlinear Analysis [38], Journal of Mathematics and Applications [39], Acta
Mathematica Vietnamica [40], Journal of Optimization Theory and Applica-

¯
B
X
respectively for B(0
X
, 1) and
¯
B(0
X
, 1). Unless otherwise stated, every
norm in question in a product norm space is a sum norm. Let Ω be a subset
of X. When Ω = ∅, dist(x; Ω) is the distance from x ∈ X to the nonempty
set Ω, that is
dist(x; Ω) = inf
u∈Ω
x − u.
If Ω = ∅, we put dist(x; Ω) = +∞ by convention. The negative dual cone of
Ω ⊂ X is defined by
Ω
∗
:= {x
∗
∈ X
∗
| x
∗
, v ≤ 0, ∀v ∈ Ω}
with X
∗
being the dual space of X, and ·, · standing for the canonical pairing


x ∈ X| F(x) = ∅

,
rgeF :=

y ∈ Y | y ∈ F(x) for some x ∈ X

the domain and the range of F . The multifunction F : X ⇒ Y is uniquely
associated with its graph
gphF :=

(x, y) ∈ X ×Y | y ∈ F(x)

in the product set X×Y . Note that if X and Y are Banach spaces, then X×Y
is also a Banach space with respect to the sum norm (x, y) = x + y
imposed on X × Y unless otherwise stated. In this case, the kernel of F is
defined by
kerF :=

x ∈ X| 0 ∈ F(x)

.
The image of a set Ω ⊂ X and the inverse image of a set Θ ⊂ Y under F are
defined in succession by setting
F (Ω) :=

y ∈ Y | y ∈ F(x) for some x ∈ X

and


y


y ∈ F (x) with x ≤ 1

.
2
1.2 Normal and Tangent Cones
In this section, we recall the concepts of normals and tangents to sets in
Banach spaces and discuss their properties and relationships.
Let F : X ⇒ Y be a multifunction between topological spaces X and Y .
Following [28] and [48], the sequential Painlev´e-Kuratowski upper/outer limit
of F as x → ¯x is defined by
Limsup
x→¯x
F (x) =

y ∈ Y


exist sequences x
k
→ ¯x and y
k
→ y
with y
k
∈ F(x
k

k
w
∗
→ x
∗
with x
∗
k
∈ F(x
k
) for all k ∈ IN

.
(1.2)
In what follows, all the reference spaces are real Banach spaces.
Definition 1.1 (See [28, Definition 1.1]) Let Ω be a nonempty subset of a
Banach space X.
(i) Given ¯x ∈ Ω and ε ≥ 0, we define the set of ε-normals to Ω at ¯x by

N
ε
(¯x; Ω) :=

x
∗
∈ X
∗




→ ¯x, and x
∗
k
w
∗
→ x
∗
such that x
∗
k
∈

N
ε
k
(x
k
; Ω) for
all k ∈ IN. The collection of such normals
N(¯x; Ω) := Limsup
x→¯x
ε↓0

N
ε
(x; Ω) (1.4)
is the limiting normal cone to Ω at ¯x. We put N(¯x; Ω) = ∅ when ¯x ∈ Ω.
3
We see that for each ε ≥ 0 the ε-normal set


= {(v, v)| v ≤ 0}∪ {(v, −v)| v ≥ 0}
is a nonconvex set. Since duality implies convexity, the example shows that
the limiting normal cone to a set Ω at a given point ¯x cannot be dual to any
tangential approximation of Ω at ¯x in the primal space. Example 1.7 in [28]
shows that, in general, the limiting normal cone may not be norm closed in
the dual space X
∗
(hence it is not weakly* closed).
A set Ω ⊂ X is said to be normally regular at ¯x ∈ Ω if N(¯x; Ω) =

N(¯x; Ω).
From (1.3) and (1.4) it follows that

N(¯x; Ω) ⊂ N(¯x; Ω) for any Ω ⊂ X and
¯x ∈ Ω. If Ω is convex, then by Propositions 1.3 and 1.5 in [28] it holds

N(¯x; Ω) = N(¯x; Ω) =

x
∗
∈ X
∗


x
∗
, x − ¯x ≤ 0, ∀x ∈ Ω

.
In this case, both the Fr´echet and the limiting normal cones coincide with

(i) X is Asplund.
(ii) For every closed set Ω ⊂ X and every ¯x ∈ Ω one has the representation
N(¯x; Ω) = Limsup
x→¯x

N(x; Ω). (1.6)
The Fr´echet normal cone has a tight connection with the concepts of con-
tingent tangent cone and of weak contingent cone.
Definition 1.3 (See [28, Definition 1.8]) Let Ω be a subset of a Banach space
X and ¯x ∈ Ω.
(i) The set T(¯x; Ω) ⊂ X defined by
T (¯x; Ω) := Limsup
t↓0
Ω − ¯x
t
, (1.7)
where the “ Limsup ” is taken with respect to the norm topology of X,
is called the contingent cone to Ω at ¯x.
(ii) If the “ Limsup ” in (i) is taken with respect to the weak topology of X,
then the resulting construction, denoted by T
W
(¯x; Ω), is called the weak
contingent cone to Ω at ¯x.
The contingent cone T(¯x; Ω) in Definition 1.7 was introduced by Bouligand,
and it was also introduced independently by Severi. Hence, another, better
name for this cone would be the Bouligand-Severi tangent cone. Note that
when Ω is convex, the contingent cone T(¯x; Ω) coincides with the notion of
tangent cone in the sense of Convex Analysis. This means that T (¯x; Ω) is
the topological closure of the cone {λ(x − ¯x)| x ∈ Ω, λ ≥ 0}.
In contrast to the limiting normal cone, the Fr´echet normal cone can be

N(¯x; Ω) =

T (¯x; Ω)

∗
.
1.3 Coderivatives and Subdifferential
The Fr´echet and the Mordukhovich coderivatives of multifunctions [28] are
two basic concepts of the generalized differentiation theory constructed by the
dual-space approach. They are defined via the concepts of Fr´echet normal
cone and limiting normal cone.
Definition 1.4 (See [28, Definition 1.32]) Let F : X ⇒ Y be a multifunction
between Banach spaces X and Y .
(i) For any (¯x, ¯y) ∈ X × Y and ε ≥ 0, ε-coderivative of F at (¯x, ¯y) is the
multifunction

D
∗
ε
F (¯x, ¯y) : Y
∗
⇒ X
∗
defined by

D
∗
ε
F (¯x, ¯y)(y
∗

ε
F (¯x, ¯y) with ε = 0 is said to be the Fr´echet coderivative
of F at (¯x, ¯y) and is denoted by

D
∗
F (¯x, ¯y).
(ii) The Mordukhovich coderivative (or the normal coderivative) of F at
(¯x, ¯y) ∈ gphF is the multifunction D
∗
F (¯x, ¯y) : Y
∗
⇒ X
∗
given by
D
∗
F (¯x, ¯y)(¯y
∗
) = Limsup
(x,y)→(¯x,¯y)
y
∗
w
∗
→¯y
∗
ε↓0

D

of such ¯x
∗
∈ X
∗
for which there are sequences ε
k
↓ 0, (x
k
, y
k
) → (¯x, ¯y),
and (x
∗
k
, y
∗
k
)
w
∗
→ (¯x
∗
, ¯y
∗
) with (x
k
, y
k
) ∈ gphF and x
∗

F (¯x, ¯y)(y
∗
) :=

x
∗
∈ X
∗


(x
∗
, −y
∗
) ∈ N

(¯x, ¯y); gphF


, ∀y
∗
∈ Y
∗
.
(1.10)
From (1.6) and (1.10) it is clear that the computation of the Fr´echet normal
cone to the graph of a multifunction between Asplund spaces is a crucial step
towards a complete differentiation of that multifunction.
One says that F is graphically regular at a given point (¯x, ¯y) ∈ gphF if
D

lim
x→¯x
f(x) − f(¯x) − ∇f(¯x)(x − ¯x)
x − ¯x
= 0.
Function f : X → Y is said to be strictly differentiable [28, Definition 1.13]
at ¯x with the strict derivative denoted by ∇f(¯x) if
lim
x→¯x
u→¯x
f(x) − f(u) − ∇f(¯x)(x − u)
x − u
= 0.
According to [28, Theorem 1.38], if f : X → Y is Fr´echet differentiable at ¯x,
then

D
∗
f(¯x)(y
∗
) = {∇f(¯x)
∗
y
∗
} for all y
∗
∈ Y
∗
with ∇f(¯x)
∗

is nonempty, then ϕ is said to be a proper function. To ϕ we associate the
epigraph
epiϕ := {(x, α) ∈ X ×IR| α ≥ ϕ(x)}.
Definition 1.5 (See [28, Definition 1.77 and 1.118]) Let ϕ : X → IR be finite
at ¯x ∈ X.
(i) The limiting subdifferential of ϕ at ¯x is the set
∂ϕ(¯x) :=

x
∗
∈ X
∗
| (x
∗
, −1) ∈ N

(¯x, ϕ(¯x)); epiϕ

,
and its elements are called limiting subgradients of ϕ at this point. When
ϕ(¯x) = ∞, one puts ∂ϕ(¯x) = ∅.
(ii) For any ¯y ∈ ∂ϕ(¯x), the mapping ∂
2
ϕ(¯x, ¯y) : X
∗∗
⇒ X
∗
with the values
∂
2

∗
F (¯x, ¯x
∗
)(u) =

D
∗
∂δ(·; Ω)

(¯x, ¯x
∗
)(u) = ∂
2
δ(·; Ω)(¯x, ¯x
∗
)(u), ∀u ∈ X
∗∗
.
The latter implies that the problem of computing the limiting second-order
subdifferential of the indicator function of a set reduces to that of computing
coderivatives of the normal cone mapping.
8