=Paper=
{{Paper
|id=Vol-1987/paper60
|storemode=property
|title=On Global Partial Calmness for Bilevel Programming Problems with Linear Lower Level Problem
|pdfUrl=https://ceur-ws.org/Vol-1987/paper60.pdf
|volume=Vol-1987
|authors=Leonid I. Minchenko,Daniil E. Berezhnov,Nataliia K. Obrosova,Alexander A. Shananin,Nicholas N. Olenev,Andrei V. Orlov,Nicolás Majorel Padilla,Pedro Araujo,Adrián Will,Sebastián Rodríguez,Alexander V. Pesterev,Lev F. Petrov,Nikolay Pogodaev,Boris T. Polyak,Andrey A. Tremba,Yuri S. Popkov,Larisa Rybak,Elena Gaponenko,Viktoria Kuzmina,Olga N. Samsonyuk,Natalya Sedova,Vadim I. Shmyrev,Ruslan Yu. Simanchev,Inna V. Urazova,Alexander K. Skiba,Stepan P. Sorokin,Maxim V. Staritsyn,Alexander S. Strekalovsky,Anna Tatarczak,Nikolay P. Tikhomirov,Dmitry V. Aron,Alexey A. Tret'yakov,Sergey Trofimov,Aleksey Ivanov,Yury Fettser,Tatiana S. Zarodnyuk,Alexander Yu. Gornov,Anton S. Anikin,Evgeniya A. Finkelstein,Elena S. Zasukhina,Sergey V. Zasukhin,Vitaly Zhadan,Anna V. Zykina,Olga N. Kaneva
}}
==On Global Partial Calmness for Bilevel Programming Problems with Linear Lower Level Problem==
https://ceur-ws.org/Vol-1987/paper60.pdf
On Global Partial Calmness for Bilevel Programming
Problems with Linear Lower Level Problem
Leonid I. Minchenko
Belarusian State University of Informatics and Radioelectronics
6 Brovki str, 220013 Minsk, Belarus, e-mail: inform@bsuir.by
Daniil E. Berezhnov
Belarusian State University of Informatics and Radioelectronics
6 Brovki str, 220013 Minsk, Belarus, e-mail: inform@bsuir.by
Abstract
Bilevel programming problems occupy an important place in optimiza-
tion theory and its various applications. We consider bilevel programs
such that their lower level problem is linear with respect to the lower
level variable. It is known that such programs are partially calm and,
therefore, can be reduced to a one level optimization problem by means
of local penalization. One of the goals of our paper is to show that
these programs can be reduced to a one level optimization problem via
a global exact penalization. In the paper we also prove sufficient con-
ditions of partial calmness for bilevel programs and study the pseudo-
Lipschitzian continuity (Aubin property) of the solution mapping of
the lower level problem.
Keywords: bilevel programming, partial calmness, optimal value func-
tion, penalization, solution mapping, pseudo-Lipschitzian continuity.
2000 AMS subject classifications: 90C30, 91A65, 90B06
1 Introduction
A bilevel programming problem is a hierarchical optimization problem with two players, where the upper level
player (leader) pursues the goal to minimize his objective function while taking into account the reaction of the
lower level player (follower).
Let x ∈ Rn , y ∈ Rm . Consider the following bilevel programming problem (BLPP):
G(x, y) → min, (1.1)
x ∈ X = {x ∈ Rn |gj (x) ≤ 0 j ∈ J }, (1.2)
∆
y ∈ S(x) = Arg min{f (x, y) |y ∈ F (x) }, (1.3)
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of
the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org
412
where F (x) = {y ∈ Rm |hi (x, y) ≤ 0 i ∈ I }, functions G(x, y), f (x, y), gj (x) and hi (x, y) are continuously
differentiable, I = {1, ..., p}, J = {1, ..., s}.
Inequalities gj (x) ≤ 0 j ∈ J and hi (x, y) ≤ 0 i ∈ I are usually referred to as the upper level and the lower
level constraints, variables x and y are called the upper level and the lower level variables, respectively.
Thus, the problem (BLPP) consists in minimizing the upper level (leader’s) objective function G(x, y) subject
to the upper level constraints and to solutions y(x) ∈ S(x) of the lower level (follower’s) problem (1.3). The
solution y(x) ∈ S(x) of the lower level problem (1.3) is called the rational reaction of the follower on the leader’s
choice x. The point (x, y) is said to be a feasible point in the problem (BLPP) if x ∈ X, y ∈ S(x). A feasible
point (x0 , y 0 ) is called a solution (local solution) of the problem (BLPP) if G(x0 , y 0 ) ≤ G(x, y) for all feasible
points (x, y) (for all feasible points from some neighborhood of (x0 , y 0 )).
Consider the multivalued mappings F : x 7→ F (x) and S : x 7→ S(x). Their graphs and domains are denoted
by grF, domF and grS, domS.
Note that the problem (BLPP) has been mostly investigated in [Dempe, 2002]-[Henrion, 2011], sometimes it
is referred to as a classical bilevel programming problem or simply a classical bilevel program.
In [Outrata, 1988] Outrata proposed the following reformulation of the problem (BLPP) into the equivalent
one level problem:
G(x, y) → min, x ∈ X, y ∈ S(x) = {y ∈ F (x) |f (x, y) ≤ φ(x) }, (1.4)
x,y
where φ(x) is the optimal value function of the lower level problem (1.3), that is,
φ(x) = min{f (x, y) |y ∈ F (x) }.
The problem (BLPP) in the form (1.4) was studied in numerous works [Dempe, 2002], [Ye, 1997]-
[Dempe, 2013]. The main difficulty in solving (1.4) is a nonsmooth constraint involving the value function
φ(x). In [Ye, 1995] Ye and Zhu introduced the now well-known concept of partial calmness and a new method
which allowed to move the nonsmooth constraint from the feasible set to the objective function in (1.4).
Let (x0 , y 0 ) be a feasible point of the problem (BLPP). Recall [Ye, 1995] that the problem (BLPP) in the
form (1.4) is called partial calm at (x0 , y 0 ) if there exist a number µ > 0 and a neighborhood V of the point
(x0 , y 0 , 0) in Rn ×Rm × R such that G(x, y)− G(x0 , y 0 )+ µ |u| ≥ 0 for all (x, y, u) ∈ V such that x ∈ X, y ∈ S(x),
f (x, y) − φ(x) + u = 0.
In [Ye, 1995] Ye and Zhu proved that the problem (BLPP) in the form (1.4) is partial calm at its local solution
(x0 , y 0 ) if and only if there exists a number µ > 0 such that (x0 , y 0 ) is a local solution of the partially penalized
problem
G(x, y) + µ(f (x, y) − φ(x)) → min, x ∈ X, y ∈ F (x). (1.5)
In their seminal paper [Ye, 1995] where Ye and Zhu introduced the partial calmness, they proved that the
problem (BLPP) with a lower level problem linear in (x, y) is partially calm. Dempe and Zemkoho showed
in [Dempe, 2013] that this proof can be adapted to the case where the lower level problem is linear only in y.
Since the partial exact penalization via partial calmness allows to obtain necessary optimality conditions for
(BLPP) and calculate stationary points for partially calm bilevel programs, partial calmness has drawn a lot
of attention in literature (see e.g. [Ye, 2010, Dempe, 2007, Henrion, 2011]). However, an approach involving a
global penalty function can be also interesting.
In Section 2 we consider a bilevel program (BLPP) with the lower level problem linear in y and prove that its
solutions (global) are global solutions of the penalized problem (1.5). Section 3 is devoted to so-called extended
error bound property for multivalued mappings. In Section 4 we prove some sufficient conditions of the pseudo-
Lipschitz continuity for the solution mapping S and the partial calmness for the problem (BLPP).
In our paper we consider the bilevel program (BLPP) under the following assumption:
X ∩ domS = X ∩ domF. (H1)
In other words, (H1) is a quite natural assumption that there exists a rational reaction y(x) ∈ S(x) of the
follower on every leader’s choice x ∈ X ∩ domF .
Denote by d(v, C) the Euclidean distance between a point v ∈ Rm and a set C ⊂ Rm . Let |v| be the Euclidean
norm of a vector v, B be an open unit ball centered at 0 in Rm or Rn , V (x), V (y) and Vε (y) = y + εB, Vε (x) =
x+εB (ε > 0) be neighborhoods of x and y. Also denote I(x, y) = {i ∈ I |hi (x, y) = 0 }, h0 (x, y) = f (x, y)−φ(x).
413
2 Global Penalization in Bilevel Programs
In this section we consider the problem (BLPP) with an additional assumption
f (x, y) = ⟨a0 , y⟩, hi (x, y) = ⟨ai , y⟩ + bi (x), (H2)
where a0 , ai ∈ R , bi (x) are scalar functions.
m
It is known that under assumption (H2) the tangent cone TF (x) (y) to the set F (x) at a point y ∈ F (x) and a
normal cone NS(x) (y) to the set S(x) at a point y ∈ S(x) can be defined as
TF (x) (y) = clcon(F (x) − y) = {ȳ ∈ Rm |⟨ai , ȳ⟩ ≤ 0 i ∈ I(x, y) }
and
∑
NS(x) (y) = { λi ai |λi ≥ 0 i ∈ {0} ∪ I(x, y) },
i∈{0}∪I(x,y)
respectively.
Lemma 2.1. Let assumptions (H1) and (H2) hold. Then there exists a number M > 0 such that
d(v, S(x)) ≤ M max{0, ⟨a0 , v⟩ − φ(x)} (2.1)
for all v ∈ F (x) and all x ∈ domS.
Proof. Set h(x, y) = max{hi (x, y) |i = 0, 1, ..., p } where h0 (x, y) = ⟨a0 , y⟩ + b0 (x), b0 (x) = −φ(x). Then
S(x) = {y ∈ Rm |h(x, y) ≤ 0 }. Consider any point x ∈ domS. If v ∈ S(x), the inequality (2.1) holds for all
v ∈ F (x) provided that M > 0.
In case v ∈ F (x)\S(x) denote as y = y(x, v) the point from S(x) closest to v. Then d(v, S(x)) = |v − y|.
−1
Let l = (v − y) |v − y| , v = y(t) = y + tl, where t = |v − y|. In this case l ∈ N (x, y) = {l ∈
R l ∈ NS(x) (y) ∩ TF (x) (y), |l| = 1 }.
m
Taking into consideration that ⟨ai , v − y⟩ ≤ 0 for i ∈ I(x, y), obtain
h(x, v) = h(x, y(t)) ≥ max hi (x, y(t)) = max {⟨ai , y⟩ + t⟨ai , l⟩ + bi (x)} =
i∈{0}∪I(x,y) i∈{0}∪I(x,y)
=t max ⟨ai , l⟩ = t⟨a0 , l⟩ ≥ t min ⟨a0 , l⟩ = tδ(x, y) (2.2)
i∈{0}∪I(x,y) l∈N (x,y)
for all l ∈ N (x, y).
Suppose that δ(x, y) = ⟨a0 , l⟩ ≤ 0. Since hi (x, y) < 0 for i ∈/ I(x, y) and hi (x, y) are continuous in y, there
exists a number ε0 > 0 such that hi (x, y + εl) = ⟨ai , y⟩ + bi (x) + ε⟨ai , l⟩ < 0 for all i ∈
/ I(x, y) and all positive
numbers ε ≤ ε0 .
On the other hand, y + εl ∈
/ S(x) for all ε0 ≥ ε > 0 and, therefore, the inequality
0 < h(x, y + εl) = max hi (x, y + εl) = max {⟨ai , y⟩ + ε⟨ai , l0 ⟩ + bi (x)} =
i∈{0}∪I(x,y) i∈{0}∪I(x,y)
=ε max ⟨ai , l⟩ = ε⟨a0 , l⟩ = εδ(x, y)
i∈{0}∪I(x,y)
holds for all positive ε ≤ ε0 . This contradicts the assumption that δ(x, y) ≤ 0. Therefore, δ(x, y) = ⟨a0 (x), (v−
−1
y) |v − y| ⟩ > 0 for all v ∈ F (x)\S(x).
The vectors ai don’t depend on x, consequently, the set N (x, y) and the value of δ(x, y) are fully determined
by a choice of subsets I(x, y) in the set I = {1, ..., p}. Since there exists only a finite number of subsets I(x, y)
in the set I, positivity of δ(x, y) implies that δ(x, y) ≥ δ > 0 as y ranges over all boundary points in S(x) and x
ranges over all points in domS.
Since any point v ∈ F (x)\S(x) can be represented as v = y + tl where l ∈ NS(x) (y) ∩ TF (x) (y), |l| = 1, t > 0,
y is a boundary point in S(x), then from (2.2) follows h(x, v) ≥ δt = δd(v, S(x)) and, therefore,
1 1
d(v, S(x)) ≤ max{0, ⟨ai , v⟩ + bi (x) |i = 0, 1, ..., p } = max{0, ⟨a0 , v⟩ − φ(x)}.
δ δ
Introduce the sets
414
D = {(x, y) |hi (x, y) ≤ 0 i ∈ I, gj (x) ≤ 0 j ∈ J }, C = {(x, y) ∈ D |h0 (x, y) ≤ 0 }
and their corresponding multivalued mappings
D(·) : x 7→ D(x) = {y ∈ Rm |(x, y) ∈ D }, C(·) : x 7→ C(x) = {y ∈ Rm |(x, y) ∈ C }. (2.3)
Theorem 2.1. Suppose that assumptions (H1) and (H2) hold. Let a feasible point (x0 , y 0 ) be a solution
(global) of the problem (BLPP) and the function G be Lipschitz continuous on the set D with Lipschitz constant
l0 > 0. Then there exists a number µ0 > 0 such that for any µ > µ0 the point (x0 , y 0 ) is a global solution of the
problem G(x, y) + µ(f (x, y) − φ(x)) → min, (x, y) ∈ D.
Proof. First of all, note that domD(·) = domC(·) due to (H1). Moreover, from (H1) follows d(y, C(x)) =
d((x, y), {x} × C(x)) ≥ d((x, y), C) for all (x, y) ∈ D.
In virtue of Proposition 2.4.3 [Clarke, 1983] for all α > l0 the point (x0 , y 0 ) is a solution of the problem
G(x, y) + αd((x, y), C) → min, (x, y) ∈ D. Then d((x, y), C) ≤ d(y, C(x)) for all (x, y) ∈ D and, therefore,
G(x, y) + αd(y, C(x)) ≥ G(x0 , y 0 ) + αd(y 0 , C(x0 )) = G(x0 , y 0 ).
Then, applying Lemma 2.1 to the set C(x), obtain G(x, y)+αM max{0, h0 (x, y)} ≥ G(x0 , y 0 ) for all (x, y) ∈ D.
The last inequality is equivalent to the assertion of the theorem with µ0 = l0 M .
3 Extended Error Bound Property and Its Application to Bilevel Programming
Let Φ(x) = {y ∈ Rm |qi (x, y) ≤ 0 i ∈ K } where K = {1, ..., r}. In this section we consider a multivalued mapping
Φ : x 7→ Φ(x) assuming that the functions qi : Rn × Rm → R are continuous together with their partial gradients
∇y qi (x, y). Following [Fedorov, 1979, Luderer et al., 2002] introduce the so-called extended error bound property
(named R-regularity in [Luderer et al., 2002, Minchenko, 2015, Minchenko, 2011]).
We say the multivalued mapping Φ has the extended error bound property (EEBP) at a point (x0 , y 0 ) ∈ grΦ
(relative to X ⊂ Rn ) if there exist a number M > 0 and neighborhoods V (x0 ) and V (y 0 ) such that
d(y, Φ(x)) ≤ M max{0, qi (x, y) i ∈ K} (3.1)
for all y ∈ V (y 0 ) and all x ∈ V (x0 ) (x ∈ V (x0 ) ∩ X).
We say that the multivalued mapping Φ has the global extended error bound property (GEEBP) if there exists
a number M > 0 such that (3.1) is valid for all y ∈ Rm and all x ∈ domF .
It is known [Luderer et al., 2002, Borwein, 1986] that in the case of continuously differentiable constraints
qi : Rn ×Rm → R EEBP holds at (x0 , y 0 ) ∈ grΦ if y 0 satisfies the Mangasarian-Fromovitz constraint qualification
(MFCQ) [Mangasarian, 1967] for the set Φ(x0 ) and EEBP also holds at (x0 , y 0 ) ∈ grΦ relative to domΦ if (x0 , y 0 )
satisfies the constant rank constraint qualification (CRCQ) [Luderer et al., 2002, Rockafellar, 1998].
Recall some definitions (see, e.g. [Rockafellar, 1998, Klatte, 2015]).
We say that a mapping Φ is pseudo-Lipschitzian or it has the Aubin property relative to X ⊂ Rn at a point
(x0 , y 0 ) ∈ grΦ (where x0 ∈ X) if there exist a number lΦ > 0 and neighborhoods Vδ (x0 ) and Vε (y 0 ) such that
Φ(x1 ) ∩ Vε (y 0 ) ⊂ Φ(x2 ) + lΦ x2 − x1 B (3.2)
for all x1 , x2 ∈ Vδ (x0 ) (all x1 , x2 ∈ Vδ (x0 ) ∩ X).
Note that in (3.2) Φ(x) ∩ Vε (y 0 ) ̸= ∅ if δ < ε/lΦ .
A mapping Φ is uniformly bounded at x0 ∈ domΦ if there exist a neighborhood V (x0 ) and a bounded set Y0
such that Φ(x) ⊂ Y0 for all x ∈ V (x0 ).
A mapping Φ is called lower semicontinuous (lsc) at a point (x0 , y 0 ) ∈ grΦ (relative to X ⊂ Rn ) if for
any neighborhood V (y 0 ) there is a neighborhood V (x0 ) such that Φ(x) ∩ V (y 0 ) ̸= ∅ for all x ∈ V (x0 ) (for all
x ∈ V (x0 ) ∩ X).
A mapping Φ is called Lipschitz lower semicontinuous at a point (x0 , y 0 ) ∈ grΦ if there exist positive numbers
l and δ such that d(y 0 , Φ(x)) ≤ l x − x0 ∀x ∈ Vδ (x0 ).
Let v ∈ Rm , v ∈ / Φ(x). Denote by ΠΦ(x) (v) the set of points from Φ(x) closest to v. Let y ∈ ΠΦ(x) (v). Then
−1
(v − y) |v − y| is a proximal normal [Rockafellar, 1998] to Φ(x) at y.
Set
415
y−v ∑
r
Λv (x, y) = {λ ∈ Rr + λi ∇y qi (x, y) = 0, λi ≥ 0 and λi qi (x, y) = 0 i ∈ K }.
|y − v| i=1
The next assertion generalizes results [Minchenko, 2011, Guo, 2013].
Lemma 3.1. Assume that Φ is lsc at (x0 , y 0 ) ∈ grΦ relative to domΦ. Then the following assertions are
equivalent:
(a) Φ has EEBP at (x0 , y 0 ) relative to domΦ;
(b) there exists a number M > 0 such that for any sequences
xk → x0 (xk ∈ domΦ), v k → y 0 (v k ∈
/ Φ(xk )), y k ∈ ΠΦ(xk ) (v k )
the condition
∑
r
v k (x , y ) = {λ ∈ Λv k (x , y )
ΛM |λi | ≤ M } ̸= ∅
k k k k
(3.3)
i=1
holds starting with some k = k0 ;
(c) for every pair of sequences xk → x0 (xk ∈ domΦ), v k → y 0 (v k ∈ / Φ(xk )) there exists a number M > 0
such that, for all k starting with some k = k0 , the condition (3.3) holds for some sequence y k ∈ ΠΦ(xk ) (v k ).
Proof. The implication (a) ⇒ (b) follows immediately from the proof of Theorem 2 [Minchenko, 2011]. The
implication (b) ⇒ (c) is obvious. Prove that (c) ⇒ (a). Suppose to the contrary that EEBP does not hold at
(x0 , y 0 ) relative to domΦ. This means that there exist sequences xk → x0 , xk ∈ domΦ and v k → y 0 , v k ∈
/ Φ(xk )
such that for all k = 1, 2...
d(v k , Φ(xk )) > k max{0, hi (xk , v k ) i ∈ K}. (3.4)
∑
r
Let y k ∈ ΠΦ(xk ) (v k ). Then there exists a vector λk ∈ Rr such that λki ≤ M and
i=1
yk − vk ∑
r
+ λk ∇y qi (xk , y k ) = 0, λki ≥ 0 i ∈ K(xk , y k ), λki = 0 i ∈ K\K(xk , y k ) (3.5)
|y k − v k | i=1 i
where K(x, y) = {i ∈ K |qi (x, y) = 0 }.
Since Φ is lsc at (x0 , y 0 ), there exists a sequence q k ∈ Φ(xk ) such that q k → y 0 and v k − y k ≤ v k − q k .
This means that y k → y 0 .
Then from (3.5) follows
∑r ∑
r
yk − vk = ⟨ λki ∇y qi (xk , y k ), v k − y k ⟩ ≤ λki (qi (xk , v k ) − qi (xk , y k ) + o( v k − y k )) =
i=1 i=1
∑
r ∑
r ∑
r
1 k
= λki qi (xk , v k ) + λki o( v k − y k ) ≤ λki qi (xk , v k ) + v − yk .
i=1 i=1 i=1
2
Therefore, d(v , Φ(x )) = y − v ≤ 2M max{0, qi (x , v ) i ∈ K}.
k k k k k k
This contradicts (3.4). Thus (c) ⇒ (a).
Lemma 3.2. Let (x0 , y 0 ) ∈ grΦ and |qi (x, y) − qi (x̃, y)| ≤ li |x − x̃| for all x, x̃ ∈ V (x0 ) and y ∈ V (y 0 ) where
li = const > 0 for all i ∈ K. Assume that the extended error bound property holds at the point (x0 , y 0 ) relative
to domΦ. Then Φ is pseudo-Lipschitzian at this point relative to domΦ.
Proof. If Φ has EEBP at (x0 , y 0 ) relative to domΦ, it means that there exist numbers M > 0, δ > 0, ε > 0
such that
d(y, Φ(x)) ≤ M max{0, qi (x, y) i ∈ K} (3.6)
for all y ∈ Vε (y ) and all x ∈ Vδ (x ) ∩ domΦ.
0 0
Denote l = max{li |i = 1, ..., r }. Choose numbers δ and ε such that Vδ (x0 ) ⊂ V (x0 ), Vε (y 0 ) ⊂ V (y 0 ). Then
d(y 0 , Φ(x)) ≤ M max{0, qi (x, y 0 ) i ∈ K} ≤
416
≤ M max{0, qi (x, y 0 ) − qi (x0 , y 0 ) i ∈ K} ≤ l x − x0
for all x ∈ Vδ (x0 ) ∩ domΦ.
This means that Φ is lower Lipschitz continuous at (x0 , y 0 ) relative to domΦ and, consequently, Φ(x)∩Vε (y 0 ) ̸=
∅ for all x ∈ Vδ0 (x0 ) ∩ domΦ and any δ0 < min{δ, ε/l}. Let x, x̃ ∈ Vδ0 (x0 ) ∩ domΦ and let ỹ ∈ Φ(x̃) ∩ Vε (y 0 ).
Then from (3.6) follows
d(ỹ, Φ(x)) ≤ M max{0, qi (x, ỹ) i ∈ K} ≤
≤ M max{0, qi (x, ỹ) − qi (x̃, ỹ) i ∈ K} ≤ l |x − x̃| .
This is equivalent to Φ(x̃) ∩ Vε (y 0 ) ⊂ Φ(x) + l |x − x̃| B for all x, x̃ ∈ Vδ0 (x0 ) ∩ domΦ.
4 Pseudo-Lipschitz Continuity of Solution Mapping and Partial Calmness in BLPP
In this section we consider the problem BLPP which was stated in Section 1.
It is well known that the pseudo-Lipschitz continuity of a multivalued mapping at some point of its graph
is closely related to constraint qualifications that hold at that point. However, it is easy to see that if the
Kuhn-Tucker necessary condition holds for a solution of the lower level problem, then such classical constraint
qualifications as the linear independence of the gradients of all active constraints and the Mangasarian-Fromovitz
condition [Mangasarian, 1967] can’t be fulfilled for the mapping S. It means that we need to involve some other
constraint qualifications.
Following [Janin, 1984] we say that the constant rank constraint qualification condition (CRCQ) holds for the
mapping S at a point (x0 , y 0 ) ∈ C if there exist neighborhoods V (x0 ) and V (y 0 ) such that rank{∇y hi (x, y) i ∈
K} = const for all x ∈ V (x0 ), y ∈ V (y 0 ) and any index set K ⊂ {0} ∪ I(x0 , y 0 ).
It is easy to see that C ⊂ grS and CRCQ for the mapping C(·) at a point (x0 , y 0 ) ∈ C is equivalent to CRCQ
for the mapping S at this point. Before we prove the next lemma we also note that domC(·) ⊂ domS and the
lower semicontinuity of S relative to domS implies the lower semicontinuity of C(·) relative to domC(·).
Lemma 4.1. Let (x0 , y 0 ) ∈ C. Assume that φ is continuous at x0 relative to domS, S is lsc at (x0 , y 0 )
relative to domS and CRCQ holds for the mapping S at the point (x0 , y 0 ). Then S and C(·) have EEBP at
(x0 , y 0 ).
Proof. Suppose that C(·) does not have EEBP at (x0 , y 0 ). Then, due to Lemma 3.1 there exist sequences
x → x0 , v k → y 0 and {y k } such that C(xk ) ̸= ∅, v k ∈
k
/ C(xk ), y k ∈ ΠC(xk ) (v k ), and either Λvk (xk , y k ) = ∅ or
d(0, Λvk (xk , y k )) → ∞ where
y−v ∑
p
Λv (x, y) = {λ ∈ Rp+1 + λi ∇y hi (x, y) = 0, λi ≥ 0 and λi hi (x, y) = 0 i ∈ {0} ∪ I }.
|y − v| i=0
Lower semicontinuity of C(·) implies that y k → y 0 . Then, without loss of generality, one can assume that
CRCQ holds at all points (xk , y k ). This means that Λvk (xk , y k ) ̸= ∅ and, therefore, λk → ∅ for each λk ∈
Λvk (xk , y k ).
Since there is only a finite number of possible index sets I(xk , y k ), by working with a subsequence if necessary,
we may assume that these index sets are the same for all k = 1, 2, .... In other words, I(xk , y k ) = I ∗ ⊂ I(x0 , y 0 ),
where I ∗ doesn’t depend on k = 1, 2, ..., and hi (xk , y k ) = 0 i ∈ {0} ∪ I ∗ , hi (xk , y k ) < 0 i ∈ (I\I ∗ ).
It is known that if Λvk (xk , y k ) ̸= ∅, then there exists a maximal linearly independent subfamily
{∇y hi (xk , y k ) i ∈ I ∗ (xk , y k ) ⊂ {0} ∪ I ∗ } in the family {∇y hi (xk , y k ) i ∈ {0} ∪ I ∗ } and a vector λk ∈ Λvk (zk )
such that λki = 0 for all i ∈ / I ∗ (xk , y k ). By choosing a subsequence if necessary, we may assume that the index
set I (x , y ) is constant and denote it as I ∗ (xk , y k ) = I 0 . Then, for all k = 1, 2, ... {∇y hi (xk , y k ) i ∈ I 0 } is a
∗ k k
maximal linearly independent subfamily in {∇y hi (xk , y k ) i ∈ {0} ∪ I ∗ } and there exists a vector λk such that
yk − vk ∑
p
+ λk ∇y hi (xk , y k ) = 0 λki ≥ 0 i ∈ {0} ∪ I, λki = 0 i ∈
/ I 0. (4.1)
|y k − v k | i=0 i
−1
Since λk → ∞ in (4.1), without loss of generality one may assume that λk λk → λ̄. Then from (4.2)
follows
417
∑
λ̄i ∇y hi (x0 , y 0 ) = 0, λ̄i ≥ 0 i ∈ {0} ∪ I, λ̄i = 0 ∀i ∈
/ I 0 , λ̄ = 1.
i∈I 0
This means that the vectors {∇y hi (x0 , y 0 ) i ∈ I 0 } are linearly dependent and we arrive to the contradiction
with CRCQ for the mapping C(·) at the point (x0 , y 0 ).
Lemma 4.2. Let the solution mapping S be uniformly bounded at x0 and S be lsc relative to domS at some
point (x0 , y 0 ) where y 0 ∈ S(x0 ). Then φ is continuous at x0 relative to domS.
Proof. Consider an arbitrary sequence {xk } ⊂ domS such that xk → x0 . Lower semicontinuity of S provides
that there exists y k ∈ S(xk ) such that y k → y 0 . Then
lim sup φ(xk ) = lim f (xk , y k ) = f (x0 , y 0 ) = φ(x0 ).
k→∞
On the other hand, lim inf φ(xk ) ≥ φ(x0 ) due to Lemma 3.18 [Luderer et al., 2002].
k→∞
Lemma 4.3. Assume that:
1) the solution mapping S is uniformly bounded at x0 and S is lsc at (x0 , y 0 ) ∈ grS relative to domS;
2) CRCQ holds for the mapping S at (x0 , y 0 ).
Then the mapping S has EEBP at (x0 , y 0 ).
Proof. According to Lemma 4.2, the function φ is continuous at x0 relative to domS. Then due to Lemma
4.1 EEBP holds at (x0 , y 0 ).
Theorem 4.1. Let (x0 , y 0 ) ∈ grS. Assume that:
1) the solution mapping S is uniformly bounded at x0 and S is lsc at (x0 , y 0 ) relative to domS;
2) CRCQ holds for the mapping S at (x0 , y 0 ).
Then the mapping S is pseudo-Lipschitzian at (x0 , y 0 ) relative to domS.
Proof. Lemma 4.2 implies that CRCQ holds for the mapping S at (x0 , y 0 ). Then due to Lemma 3.2 S is
pseudo-Lipschitzian at (x0 , y 0 ).
Example 4.1. Let y1 − y2 → min, y22 − y1 + x ≤ 0, (y1 − x)2 + y2 ≤ 0, 0 ≤ y3 ≤ 1, 0 ≤ x ≤ 1.
Let x0 = 0, y 0 = (0, 0, 0). CRCQ and other conditions of Theorem 4.1 hold at (x0 , y 0 ), therefore, S is
pseudo-Lipschitzian at (x0 , y 0 ). On the other hand, it is easy to check that φ(x) = x and S(x) = {y ∈
R3 |y1 = x, y2 = 0, x ≤ y3 ≤ 1 }.
Theorem 4.2. Let a feasible point (x0 , y 0 ) be a local solution of the problem BLPP. Assume that:
1) the function G is Lipschitz continuous on the set D with Lipschitz constant l0 > 0;
2) the solution mapping S is uniformly bounded at x0 and S is lsc at (x0 , y 0 ) relative to domS;
3) CRCQ holds for the mapping S at (x0 , y 0 ).
Then there exists a number µ0 > 0 such that for any µ > µ0 the point (x0 , y 0 ) is a local solution of the problem
G(x, y) + µ(f (x, y) − φ(x)) → min, (x, y) ∈ D.
The proof is similar to the proof of Theorem 2.1.
References
[Dempe, 2002] Dempe S. Foundations of bilevel programming. Kluwer Acad. Publishers, Dordrecht, 2002.
[Bard, 1998] Bard J.F. Practical bilevel optimization. Kluwer Acad. Publishers, Dordrecht, 1998.
[Ye, 1995] Ye J.J., Zhu D.L. Optimality conditions for bilevel programming problems. Optimization, 33, 1995.
9–27.
[Ye, 1997] Ye J.J., Zhu D.L., Zhu Q.J. Exact penalization and necessary optimality conditions for generalized
bilevel programming problems. SIAM J. Optim. 7 (1997), no. 2. 481–507.
[Ye, 2010] Ye J.J., Zhu D.L. New necessary optimality conditions for bilevel programs by combining the MPEC
and value function approaches. SIAM J. Optim. 20 (2010), no. 4. 1885–1905.
[Dempe, 2007] Dempe S., Dutta J., Mordukhovich B.S. New necessary optimality conditions in optimistic bilevel
programming. Optimization 56 (2007), no. 5-6. 577–604.
[Dempe, 2013] Dempe S., Zemkoho A.B. Bilevel programming: reformulations, constraint qualifications and
optimality conditions. Math. Programming 138, 2013. 447–473.
418
[Henrion, 2011] Henrion R., Surowiec T.M. On calmness conditions in convex bilevel programming. Appl. Anal.
90 (2011), no. 6. 951–970.
[Outrata, 1988] Outrata J.V. A note on the usage of nondifferentiable exact penalties in some special optimization
problems. Kybernetika 24 (1988), no. 4. 251–258.
[Clarke, 1983] Clarke F. Optimization and nonsmooth analysis. Wiley, New York, 1983.
[Fedorov, 1979] Fedorov V.V. Numerical methods of maxmin. Nauka, Moscow, 1979.
[Luderer et al., 2002] Luderer B., Minchenko L., Satsura T. Multivalued analysis and nonlinear programming
problems with perturbations. Kluwer Acad. Publishers, Dordrecht, 2002.
[Minchenko, 2015] Minchenko L.I., Tarakanov A.N. On second order derivatives of value functions. Optimization
64 (2015). 389–407.
[Minchenko, 2011] Minchenko L., Stakhovski S. Parametric nonlinear programming problems under the relaxed
constant rank condition. SIAM J.Optim. 21 (2011), no. 1. 314–332.
[Borwein, 1986] Borwein J.M. Stability and regular points of inequality systems. J. Optimiz. Theory and Appl.
48 (1986). 9–52.
[Mangasarian, 1967] Mangasarian O. L., Fromovitz S. The Fritz John necessary optimality conditions in the
presence of equality and inequality constraints. Journal of Mathem. Analysis and Applications 17
(1967). 37–47.
[Rockafellar, 1998] Rockafellar R.T., Wets R.J.-B. Variational analysis. Springer, Berlin, 1998.
[Klatte, 2015] Klatte D., Kummer B. On calmness of the argmin mapping in parametric optimization problems.
J. Optimiz. Theory and Appl. 165 (2015). 708–719.
[Guo, 2013] Guo L., Lin G.H. Notes on some constraint qualifications for mathematical programs with equilib-
rium. J. Optimiz. Theory and Appl. 156 (2013). 600–616.
[Janin, 1984] Janin R. Directional derivative of the marginal function in nonlinear programming. Mathematical
Programming Studies 21 (1984). 110–126.
419