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 ∈ R n , y ∈ R m . Consider the following bilevel programming problem (BLPP):

G(x, y) → min, (1.1)

x ∈ X = {x ∈ R n |g j (x) ≤ 0 j ∈ J }, (1.2) y ∈ S(x) ∆ = Arg min{f (x, y) |y ∈ F (x) }, (1.3)

where F (x) = {y ∈ R m |h i (x, y) ≤ 0 i ∈ I }, functions G(x, y), f (x, y), g j (x) and h i (x, y) are continuously differentiable, I = {1, ..., p}, J = {1, ..., s}.

Inequalities g j (x) ≤ 0 j ∈ J and h i (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 (x 0 , y 0 ) is called a solution (local solution) of the problem (BLPP) if G(x 0 , y 0 ) ≤ G(x, y) for all feasible points (x, y) (for all feasible points from some neighborhood of (x 0 , y 0 )).

Consider the multivalued mappings F : x → F (x) and S : x → 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,y , x ∈ X, y ∈ S(x) = {y ∈ F (x) |f (x, y) ≤ φ(x) }, (1.4)

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 (x 0 , 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 (x 0 , y 0 ) if there exist a number µ > 0 and a neighborhood V of the point

(x 0 , y 0 , 0) in R n ×R m × R such that G(x, y)− G(x 0 , 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 (x 0 , y 0 ) if and only if there exists a number µ > 0 such that (x 0 , 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 ∈ R m and a set C ⊂ R m . Let |v| be the Euclidean norm of a vector v, B be an open unit ball centered at 0 in

R m or R n , 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 |h i (x, y) = 0 }, h 0 (x, y) = f (x, y)−φ(x).

Global Penalization in Bilevel Programs

In this section we consider the problem (BLPP) with an additional assumption

f (x, y) = ⟨a 0 , y⟩, h i (x, y) = ⟨a i , y⟩ + b i (x), (H2)

where a 0 , a i ∈ R m , b i (x) are scalar functions.

It is known that under assumption (H2) the tangent cone T F (x) (y) to the set F (x) at a point y ∈ F (x) and a normal cone N S(x) (y) to the set S(x) at a point y ∈ S(x) can be defined as

T F (x) (y) = clcon(F (x) − y) = {ȳ ∈ R m |⟨a i , ȳ⟩ ≤ 0 i ∈ I(x, y) } and N S(x) (y) = { ∑ i∈{0}∪I(x,y) λ i a i |λ i ≥ 0 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, ⟨a 0 , v⟩ − φ(x)} (2.1)for all v ∈ F (x) and all x ∈ domS. Proof. Set h(x, y) = max{h i (x, y) |i = 0, 1, ..., p } where h 0 (x, y) = ⟨a 0 , y⟩ + b 0 (x), b 0 (x) = −φ(x). Then S(x) = {y ∈ R m |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|. Let l = (v − y) |v − y| −1 , v = y(t) = y + tl, where t = |v − y|. In this case l ∈ N (x, y) = {l ∈ R m l ∈ N S(x) (y) ∩ T F (x) (y), |l| = 1 }. Taking into consideration that ⟨a i , v − y⟩ ≤ 0 for i ∈ I(x, y), obtain h(x, v) = h(x, y(t)) ≥ max i∈{0}∪I(x,y) h i (x, y(t)) = max i∈{0}∪I(x,y) {⟨a i , y⟩ + t⟨a i , l⟩ + b i (x)} = = t max i∈{0}∪I(x,y) ⟨a i , l⟩ = t⟨a 0 , l⟩ ≥ t min l∈N (x,y) ⟨a 0 , l⟩ = tδ(x, y) (2.2)

for all l ∈ N (x, y). Suppose that δ(x, y) = ⟨a 0 , l⟩ ≤ 0. Since h i (x, y) < 0 for i / ∈ I(x, y) and h i (x, y) are continuous in y, there exists a number ε 0 > 0 such that h i (x, y + εl) = ⟨a i , y⟩ + b i (x) + ε⟨a i , 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 i∈{0}∪I(x,y) h i (x, y + εl) = max i∈{0}∪I(x,y) {⟨a i , y⟩ + ε⟨a i , l 0 ⟩ + b i (x)} = = ε max i∈{0}∪I(x,y) ⟨a i , l⟩ = ε⟨a 0 , l⟩ = εδ(x, y)

holds for all positive ε ≤ ε 0 . This contradicts the assumption that δ(x, y) ≤ 0. Therefore, δ(x, y)

= ⟨a 0 (x), (v− y) |v − y| −1 ⟩ > 0 for all v ∈ F (x)\S(x)

. The vectors a i 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 ∈ N S(x) (y) ∩ T F (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, d(v, S(x)) ≤ 1 δ max{0, ⟨a i , v⟩ + b i (x) |i = 0, 1, ..., p } = 1 δ max{0, ⟨a 0 , v⟩ − φ(x)}.

Introduce the sets

D = {(x, y) |h i (x, y) ≤ 0 i ∈ I, g j (x) ≤ 0 j ∈ J }, C = {(x, y) ∈ D |h 0 (x, y) ≤ 0 }

and their corresponding multivalued mappings

D(•) : x → D(x) = {y ∈ R m |(x, y) ∈ D }, C(•) : x → C(x) = {y ∈ R m |(x, y) ∈ C }.

(2.3) Theorem 2.1. Suppose that assumptions (H1) and (H2) hold. Let a feasible point (x 0 , y 0 ) be a solution (global) of the problem (BLPP) and the function G be Lipschitz continuous on the set D with Lipschitz constant l 0 > 0. Then there exists a number µ 0 > 0 such that for any µ > µ 0 the point (x 0 , 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 α > l 0 the point (x 0 , 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(x 0 , y 0 ) + αd(y 0 , C(x 0 )) = G(x 0 , y 0 ).

Then, applying Lemma 2.1 to the set C(x), obtain G(x, y)+αM max{0, h 0 (x, y)} ≥ G(x 0 , y 0 ) for all (x, y) ∈ D. The last inequality is equivalent to the assertion of the theorem with µ 0 = l 0 M .

Extended Error Bound Property and Its Application to Bilevel Programming

Let Φ(x) = {y ∈ R m |q i (x, y) ≤ 0 i ∈ K } where K = {1, ..., r}. In this section we consider a multivalued mapping Φ : x → Φ(x) assuming that the functions q i : R n × R m → R are continuous together with their partial gradients ∇ y q i (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 (x 0 , y 0 ) ∈ grΦ (relative to X ⊂ R n ) if there exist a number M > 0 and neighborhoods V (x 0 ) and V (y 0 ) such that

d(y, Φ(x)) ≤ M max{0, q i (x, y) i ∈ K} (3.1)

for all y ∈ V (y 0 ) and all x ∈ V (x 0 ) (x ∈ V (x 0 ) ∩ 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 ∈ R m and all x ∈ domF .

It is known [Luderer et al., 2002, Borwein, 1986] that in the case of continuously differentiable constraints q i : R n ×R m → R EEBP holds at (x 0 , y 0 ) ∈ grΦ if y 0 satisfies the Mangasarian-Fromovitz constraint qualification (MFCQ) [Mangasarian, 1967] for the set Φ(x 0 ) and EEBP also holds at (x 0 , y 0 ) ∈ grΦ relative to domΦ if (x 0 , 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 ⊂ R n at a point (x 0 , y 0 ) ∈ grΦ (where x 0 ∈ X) if there exist a number l Φ > 0 and neighborhoods V δ (x 0 ) and V ε (y 0 ) such that

Φ(x 1 ) ∩ V ε (y 0 ) ⊂ Φ(x 2 ) + l Φ x 2 − x 1 B (3.2) for all x 1 , x 2 ∈ V δ (x 0 ) (all x 1 , x 2 ∈ V δ (x 0 ) ∩ X). Note that in (3.2) Φ(x) ∩ V ε (y 0 ) ̸ = ∅ if δ < ε/l Φ . A mapping Φ is uniformly bounded at x 0 ∈ domΦ if there exist a neighborhood V (x 0 ) and a bounded set Y 0 such that Φ(x) ⊂ Y 0 for all x ∈ V (x 0 ). A mapping Φ is called lower semicontinuous (lsc) at a point (x 0 , y 0 ) ∈ grΦ (relative to X ⊂ R n ) if for any neighborhood V (y 0 ) there is a neighborhood V (x 0 ) such that Φ(x) ∩ V (y 0 ) ̸ = ∅ for all x ∈ V (x 0 ) (for all x ∈ V (x 0 ) ∩ X).

A mapping Φ is called Lipschitz lower semicontinuous at a point (x 0 , y 0 ) ∈ grΦ if there exist positive numbers l and δ such that d(y Rockafellar, 1998] to Φ(x) at y.

0 , Φ(x)) ≤ l x − x 0 ∀x ∈ V δ (x 0 ). Let v ∈ R m , v / ∈ Φ(x). Denote by Π Φ(x) (v) the set of points from Φ(x) closest to v. Let y ∈ Π Φ(x) (v). Then (v − y) |v − y| −1 is a proximal normal [Set Λ v (x, y) = {λ ∈ R r y − v |y − v| + r ∑ i=1 λ i ∇ y q i (x, y) = 0, λ i ≥ 0 and λ i q i (x, y) = 0 i ∈ K }.

The next assertion generalizes results [Minchenko, 2011, Guo, 2013]. Lemma 3.1. Assume that Φ is lsc at (x 0 , y 0 ) ∈ grΦ relative to domΦ. Then the following assertions are equivalent:

(a) Φ has EEBP at (x 0 , y 0 ) relative to domΦ; (b) there exists a number M > 0 such that for any sequences

x k → x 0 (x k ∈ domΦ), v k → y 0 (v k / ∈ Φ(x k )), y k ∈ Π Φ(x k ) (v k )

the condition

Λ M v k (x k , y k ) = {λ ∈ Λ v k (x k , y k ) r ∑ i=1 |λ i | ≤ M } ̸ = ∅ (3.3)

holds starting with some k = k 0 ; (c) for every pair of sequences

x k → x 0 (x k ∈ domΦ), v k → y 0 (v k / ∈ Φ(x k ))

there exists a number M > 0 such that, for all k starting with some k = k 0 , the condition (3.3) holds for some sequence

y k ∈ Π Φ(x k ) (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 (x 0 , y 0 ) relative to domΦ. This means that there exist sequences

x k → x 0 , x k ∈ domΦ and v k → y 0 , v k / ∈ Φ(x k ) such that for all k = 1, 2... d(v k , Φ(x k )) > k max{0, h i (x k , v k ) i ∈ K}. (3.4) Let y k ∈ Π Φ(x k ) (v k ). Then there exists a vector λ k ∈ R r such that r ∑ i=1 λ k i ≤ M and y k − v k |y k − v k | + r ∑ i=1 λ k i ∇ y q i (x k , y k ) = 0, λ k i ≥ 0 i ∈ K(x k , y k ), λ k i = 0 i ∈ K\K(x k , y k ) (3.5)

where K(x, y) = {i ∈ K |q i (x, y) = 0 }. Since Φ is lsc at (x 0 , y 0 ), there exists a sequence q k ∈ Φ(x k ) 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

y k − v k = ⟨ r ∑ i=1 λ k i ∇ y q i (x k , y k ), v k − y k ⟩ ≤ r ∑ i=1 λ k i (q i (x k , v k ) − q i (x k , y k ) + o( v k − y k )) = = r ∑ i=1 λ k i q i (x k , v k ) + r ∑ i=1 λ k i o( v k − y k ) ≤ r ∑ i=1 λ k i q i (x k , v k ) + 1 2 v k − y k . Therefore, d(v k , Φ(x k )) = y k − v k ≤ 2M max{0, q i (x k , v k ) i ∈ K}.

This contradicts (3.4). Thus (c) ⇒ (a). Lemma 3.2. Let (x 0 , y 0 ) ∈ grΦ and |q i (x, y) − q i (x, y)| ≤ l i |x − x| for all x, x ∈ V (x 0 ) and y ∈ V (y 0 ) where l i = const > 0 for all i ∈ K. Assume that the extended error bound property holds at the point (x 0 , y 0 ) relative to domΦ. Then Φ is pseudo-Lipschitzian at this point relative to domΦ.

Proof. If Φ has EEBP at (x 0 , y 0 ) relative to domΦ, it means that there exist numbers M > 0, δ > 0, ε > 0 such that

d(y, Φ(x)) ≤ M max{0, q i (x, y) i ∈ K} (3.6)

for all y ∈ V ε (y 0 ) and all x ∈ V δ (x 0 ) ∩ domΦ. Denote l = max{l i |i = 1, ..., r }. Choose numbers δ and ε such that

V δ (x 0 ) ⊂ V (x 0 ), V ε (y 0 ) ⊂ V (y 0 ). Then d(y 0 , Φ(x)) ≤ M max{0, q i (x, y 0 ) i ∈ K} ≤ ≤ M max{0, q i (x, y 0 ) − q i (x 0 , y 0 ) i ∈ K} ≤ l x − x 0 for all x ∈ V δ (x 0 ) ∩ domΦ.

This means that Φ is lower Lipschitz continuous at (x 0 , y 0 ) relative to domΦ and, consequently, Φ(x)∩V ε (y 0 ) ̸ = ∅ for all x ∈ V δ0 (x 0 ) ∩ domΦ and any δ 0 < min{δ, ε/l}. Let x, x ∈ V δ0 (x 0 ) ∩ domΦ and let ỹ ∈ Φ(x) ∩ V ε (y 0 ). Then from (3.6) follows

d(ỹ, Φ(x)) ≤ M max{0, q i (x, ỹ) i ∈ K} ≤ ≤ M max{0, q i (x, ỹ) − q i (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 (x 0 ) ∩ domΦ.

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 (x 0 , y 0 ) ∈ C if there exist neighborhoods V (x 0 ) and V (y 0 ) such that rank{∇ y h i (x, y) i ∈ K} = const for all x ∈ V (x 0 ), y ∈ V (y 0 ) and any index set K ⊂ {0} ∪ I(x 0 , y 0 ).

It is easy to see that C ⊂ grS and CRCQ for the mapping C(•) at a point (x 0 , 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 (x 0 , y 0 ) ∈ C. Assume that φ is continuous at x 0 relative to domS, S is lsc at (x 0 , y 0 ) relative to domS and CRCQ holds for the mapping S at the point (x 0 , y 0 ). Then S and C(•) have EEBP at (x 0 , y 0 ).

Proof. Suppose that C(•) does not have EEBP at (x 0 , y 0 ). Then, due to Lemma 3.1 there exist sequences

x k → x 0 , v k → y 0 and {y k } such that C(x k ) ̸ = ∅, v k / ∈ C(x k ), y k ∈ Π C(x k ) (v k ), and either Λ v k (x k , y k ) = ∅ or d(0, Λ v k (x k , y k )) → ∞ where Λ v (x, y) = {λ ∈ R p+1 y − v |y − v| + p ∑ i=0

λ i ∇ y h i (x, y) = 0, λ i ≥ 0 and λ i h i (x, y) = 0 i ∈ {0} ∪ I }.

Lower semicontinuity of C(•) implies that y k → y 0 . Then, without loss of generality, one can assume that CRCQ holds at all points (x k , y k ). This means that Λ v k (x k , y k ) ̸ = ∅ and, therefore, λ k → ∅ for each λ k ∈ Λ v k (x k , y k ).

Since there is only a finite number of possible index sets I(x k , 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(x k , y k ) = I * ⊂ I(x 0 , y 0 ), where I * doesn't depend on k = 1, 2, ..., and h i (x k , y k ) = 0 i ∈ {0} ∪ I * , h i (x k , y k ) < 0 i ∈ (I\I * ).

It is known that if Λ v k (x k , y k ) ̸ = ∅, then there exists a maximal linearly independent subfamily {∇ y h i (x k , y k ) i ∈ I * (x k , y k ) ⊂ {0} ∪ I * } in the family {∇ y h i (x k , y k ) i ∈ {0} ∪ I * } and a vector λ k ∈ Λ v k (z k ) such that λ k i = 0 for all i / ∈ I * (x k , y k ). By choosing a subsequence if necessary, we may assume that the index set I * (x k , y k ) is constant and denote it as I * (x k , y k ) = I 0 . Then, for all k = 1, 2, ... {∇ y h i (x k , y k ) i ∈ I 0 } is a maximal linearly independent subfamily in {∇ y h i (x k , y k ) i ∈ {0} ∪ I * } and there exists a vector λ k such that

y k − v k |y k − v k | + p ∑ i=0 λ k i ∇ y h i (x k , y k ) = 0 λ k i ≥ 0 i ∈ {0} ∪ I, λ k i = 0 i / ∈ I 0 . (4.1)

Since λ k → ∞ in (4.1), without loss of generality one may assume that λ k λ k −1 → λ. Then from (4.2) follows