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