Skip to main content

Optimality conditions for pessimistic semivectorial bilevel programming problems

Abstract

In this paper, a class of pessimistic semivectorial bilevel programming problems is investigated. By using the scalarization method, we transform the pessimistic semivectorial bilevel programming problem into a scalar objective optimization problem with inequality constraints. Furthermore, we derive a generalized minimax optimization problem using the maximization bilevel optimal value function, of which the sensitivity analysis is constructed via the lower-level value function approach. Using the generalized differentiation calculus of Mordukhovich, the first-order necessary optimality conditions are established in the smooth setting. As an application, we take the optimality conditions of the bilevel programming problems with multiobjective lower level problem when the lower level multiobjective optimization problem is linear with respect to the lower-level variables.

MSC:90C26, 90C30, 90C31, 90C46.

1 Introduction

Bilevel programming (also called two-level programming) problems provide a framework to deal with decision processes involving two decision makers with a hierarchical structure. The leader at the upper level of the hierarchy and the follower at the lower level seek to optimize their individual objective functions and control their own set of decision variables. The hierarchical process means that the leader announces his variables first and then the follower reacts, bearing in mind the selection. The goal of the leader is to optimize his own objective function by incorporating, within the optimization scheme, the reaction of the follower to his course of action. The leader can influence but cannot control the decisions of the follower. In this paper, we consider a bilevel programming problem (BP), which is called semivectorial bilevel programming problem by Bonnel and Morgan [1], where the upper level is a scalar optimization problem and the lower level is a vector optimization problem:

(BP):‘ min x ’F(x,z)
(1.1)
(BP): s.t. G(x)≤0,z∈ Ψ wef (x),
(1.2)

where x∈ R n and z∈ R m denote the upper-level and the lower-level decision variables, respectively, G(x): R n → R q denotes the upper-level constraint function and F: R n × R m →R is the upper-level objective function, Ψ wef (x) is the weakly efficient optimal solutions set of the multiobjective optimization problem with respect to the upper decision variable x:

R + l − min z f(x,z)
(1.3)
s.t. g(x,z)≤0,
(1.4)

where g: R n × R m → R p is the lower-level constrained function, f: R n × R m → R l is the lower-level multiobjective function. The term ‘ R + l −min’ in (1.3) is used to symbolize that vector-values in the lower-level problem are in the sense of weak Pareto minima (see Section 2) with respect to an order induced by the positive orthant of R l .

In order to ensure that the results in this paper are correct, we make some hypotheses throughout the paper as follows.

Hypothesis 1 The set {x∈ R n ∣G(x)≤0} is nonempty and compact.

Hypothesis 2 For any x verifying G(x)≤0, the set {z∈ R m ∣g(x,z)≤0} is nonempty and compact.

Generally speaking, the weakly efficient solution set Ψ wef (x) of the lower-level problem (1.3) and (1.4) is not singleton, i.e., the set Ψ wef (x) in (1.2) has more than one point. In this case, the notion of an optimal solution of the bilevel programming problem may be ambiguous. That is why the word ‘min’ is written in quotes in (1.1). Two ways to deal with this situation are given by the optimistic formulation and the pessimistic formulation in [2].

If the upper-level decision maker (i.e. the leader) supposes that the lower-level decision maker (i.e. the follower) is willing to support him, that is, the follower will select a solution z(x)∈ Ψ wef (x), which is one of the best to the leader, then we get the following optimistic formulation:

min x min z F(x,z)s.t. G(x)≤0,z∈ Ψ wef (x).
(1.5)

For the research papers on the optimistic formulation of the semivectorial bilevel programming problem one is referred to [1, 3–9]. In [1], a penalty method was given to solve the problem in case of weakly efficient solutions in the lower-level problem (1.2). Zheng and Wan [9] developed another penalty method consisting of two penalty parameters in the case where the multiobjective lower-level problem is linear. Ankhili and Mansouri [3] developed an exact penalty method for the problem in the case where the upper-level problem was concave and the lower-level problem was a linear multiobjective optimization problem. Eichfelder [7] considered the problem in the case where F is also vector-valued. In the latter paper, the induced set of the investigated problem is shown to be the set of minima point (with respect to a cone) of another unperturbed multiobjective optimization problem. Hence, the resulting problem is simply a multiobjective optimization problem over an efficient set. Then it is solved by using a scalarization method by Pascoletti and Serafini combined with an adaptive parameter control method based on sensitivity for the problem. Recently, Calvete and Galé [5] also considered the problem in the case where the upper-level objective function is quasiconcave and the lower-level problem is a linear multiobjective optimization problem. The problem was reformulated as an optimization problem over a nonconvex region given by a union of faces of the polyhedron defined by all constraints. An extreme point method was showed to deal with the problem. Then, based on the ‘k th’ best method and genetic algorithm, they developed an exact and a metaheuristic algorithm, respectively. The performance of the above two algorithms were also evaluated. In [8], Nie defined the risk optimal decision, conservative optimal decision and mean optimal decision of the semivectorial bilevel programming problem. Weighting methods were employed to analyze the lower-level multiobjective optimization problem, and some properties about the problem were obtained. In [4], Bonnel derived necessary optimality conditions for the problem (1.5) in general Banach spaces, while considering efficient and weakly efficient solutions for the lower-level multiobjective optimization the problem (1.3). In the latter paper, the author inserted the weak or properly weak solution set-valued mapping of the lower-level problem in the upper-level objective function to derive a set-valued optimization problem. Using the notion of contingent derivative, necessary optimality conditions, which are abstract in nature, were derived. In [6], Dempe et al. considered also the optimistic formulation of the semivectorial bilevel programming problem. Considering the scalarization approach for the lower-level multiobjective optimization problem, they transformed the problem into a scalar objective optimization problem with inequality constraints by means of the optimal value reformulation, completely detailed first-order KKT-type necessary optimality conditions were derived in the smooth and nonsmooth settings while using the generalized differentiation calculus of Mordukhovich. It is worth to mention that the method of [6] was different from that of [4].

If the upper-level decision maker is a conservative leader, the leader is going to be the worst and bound the damage resulting from an undesirable selection of the follower. This leads to the following pessimistic formulation of (1.1):

min x max z F(x,z)s.t. G(x)≤0,z∈ Ψ wef (x).
(1.6)

To the best of our knowledge, there are very few results for the problem (1.6) apart from [8, 10].

Bonnel and Morgan [10] developed optimality conditions for the bilevel optimal control problem, which is a special case of semivectorial bilevel programming problem. For two extreme cases, the optimistic case and the pessimistic case, the optimality conditions were presented, respectively. In [8], Nie defined the conservative optimal decision for the problem (1.1) (i.e. (1.6)). Weighting methods were employed to analyze the lower-level multiobjective optimization problem when the lower-level objective functions were all continuously differentiable and strictly convex and the lower-level constraints were all continuously differentiable, then a minimax optimization problem with constraints was derived. But for the problem (1.6), no detailed optimality conditions and concrete solving methods were found in [8].

Hence, in this paper, our main work is as follows: Using the scalarization method and the maximization bilevel optimal value function, the pessimistic problem (1.6) is transformed into a generalized minimax optimization problem, i.e. the problem (3.4). Then, we develop a link between the problems (1.6) and (3.4), that is, Proposition 3.1, which shows that these two problems have the same local or global optimal solutions under some mild conditions. The results of Proposition 3.1 is formally similar to that of Proposition 3.1 in [6], but is different in nature. Based on Proposition 3.1, we transform the problem (3.4) into the problem (3.9) using the bilevel optimal value function formulation. Furthermore, we develop the necessary optimality conditions (see Theorem 4.4) for the problem (3.4) using generalized differentiation calculus of Mordukhovich. By Proposition 3.1, we obtain the necessary optimality conditions (see Corollary 4.1) for the pessimistic problem (1.6). Our results in this paper and the results in [6] make up together the first-order necessary optimality conditions for the semivectorial bilevel programming problem. It is very important for the development of the optimality theory of the semivectorial bilevel programming problem in the future.

The rest of the paper is organized as follows. In Section 2, we present the definitions of efficient solutions and Pareto minima, and then the relevant notions and properties from variational analysis will be presented as well. The transformation process of the pessimistic semivectorial bilevel programming problem (PSBP) into a single-level generalized minimax optimization problem with constraints by means of the optimal value function reformulation is given in Section 3. In Section 4, we first present the estimation of the lower-level negative value function and the sensitivity analysis of the lower-level optimal solution maps. Based on these, the sensitivity analysis for the maximization bilevel value function is presented. Finally, the necessary optimality conditions are derived for the problem (1.6) while considering the case where all functions involved are strictly differentiable. The special case where the lower-level multiobjective optimization problem is linear in the lower-level variable is studied in Section 5.

2 Preliminaries

In this section, we mainly recall some basic definitions and results.

2.1 Efficient solution and Pareto minima

Definition 2.1 Let C⊂ R n be a closed convex cone with nonempty interior, C is said to be pointed convex cone if C∩−C={0}. We denote a partial order by ⪯ C in R n induced by C.

Definition 2.2 Let A⊆ R n be nonempty. z ∗ ∈A is said to be Pareto (resp. weak Pareto) minima of A w.r.t. C if

A⊂ z ∗ + [ ( R n ∖ ( − C ) ) ∪ { 0 } ] ( resp.  A ⊂ z ∗ + ( R n ∖ − int C ) ) ,
(2.1)

where ‘int’ denotes the topological interior of the set in question.

Considering the multiobjective optimization problem with respect to ≤ C :

C−minf(x)s.t. x∈X,
(2.2)

where f represents a vector-valued function and X the nonempty feasible set. For a nonempty set A⊂X, the image of A by f is defined by f(A):={f(x)∣x∈A}.

Definition 2.3 The point x ∗ ∈X is said to be an efficient (resp. weakly efficient) optimal solution of problem (2.2) if f( x ∗ ) is a Pareto (resp. weak Pareto) minima of f(X).

Definition 2.4 The point x ∗ ∈X is said to be a local efficient (resp. weakly local efficient) optimal solution of problem (2.2) if there exists a neighborhood U of x ∗ such that f( x ∗ ) is a Pareto (resp. weak Pareto) minima of f(X∩U).

Definition 2.5 [11, 12]

A vector-valued function f: R n → R m is said to convex with respect to a partial ⪯ C induced by a pointed, closed, and convex cone C, if we have

f ( λ x 1 + ( 1 − λ ) x 2 ) ⪯ C λf( x 1 )+(1−λ)f( x 2 ),∀ x 1 , x 2 ∈ R n ,∀λ∈(0,1).

2.2 Tools from variational analysis

Details of the material presented here can be found in [13, 14].

Definition 2.6 Given a point x ¯ , lim sup x → x ¯ Γ(x) is said to be the Kuratowski-Painlevé outer/upper limit of a set-valued mapping Γ: R n ⇒ R m at x ¯ , if

lim sup x → x ¯ Γ(x)= { Ï… ∈ R m ∣ ∃ x k → x ¯ , Ï… k → Ï…  with  Ï… k ∈ Γ ( x k )  as  k → ∞ } .
(2.3)

Definition 2.7 For an extended real-valued function ψ: R n → R ¯ , ∂ ˆ ψ( x ¯ ) is said to be the Fréchet subdifferential of ψ at a point x ¯ of its domain, if

∂ ˆ ψ( x ¯ )= { υ ∈ R n | lim inf x → x ¯ ψ ( x ) − ψ ( x ¯ ) − 〈 υ , x − x ¯ 〉 ∥ x − x ¯ ∥ ≥ 0 } .
(2.4)

Definition 2.8 Given a point x ¯ , ∂ψ( x ¯ ) is said to be the basic/Mordukhovich subdifferential of ψ at x ¯ , if

∂ψ( x ¯ )=lim sup x → x ¯ ∂ ˆ ψ( x ¯ ).
(2.5)

If ψ is convex, ∂ψ( x ¯ ) is reduced to the subdifferential in the sense of convex analysis:

∂ψ( x ¯ )= { υ ∈ R n ∣ ψ ( x ) − ψ ( x ¯ ) ≥ 〈 υ , x − x ¯ 〉 , ∀ x ∈ R n } .
(2.6)

∂ψ( x ¯ ) is nonempty and compact when ψ is local Lipschitz continuous, its convex hull is the Clarke subdifferential ∂ ¯ ψ( x ¯ ), i.e.

∂ ¯ ψ( x ¯ )=co∂ψ( x ¯ )
(2.7)

where ‘co’ denotes the convex hull of the set in question. Via this link between the Basic and Clarke subdifferential, we have the following convex hull property:

co∂(−ψ)( x ¯ )=−co∂ψ( x ¯ ),
(2.8)

where ψ is Lipschitz continuous near x ¯ .

Definition 2.9 ∂ x ψ( x ¯ , y ¯ ) is said to be the partial basic (resp. Clarke) subdifferential of ψ with respect to x, if we have

∂ x ψ( x ¯ , y ¯ )=∂ψ(â‹…, y ¯ )( x ¯ ) ( resp.  ∂ ¯ x ψ ( x ¯ , y ¯ ) = ∂ ¯ ψ ( â‹… , y ¯ ) ( x ¯ ) ) .
(2.9)

The partial basic (resp. Clarke) subdifferential with respect to y can be defined analogously as follows:

∂ y ψ( x ¯ , y ¯ )=∂ψ( y ¯ ,â‹…)( y ¯ ) ( resp.  ∂ ¯ y ψ ( x ¯ , y ¯ ) = ∂ ¯ ψ ( y ¯ , â‹… ) ( y ¯ ) ) .
(2.10)

Definition 2.10 Given a point x ¯ ∈Ω, N Ω ( x ¯ ) is said to be the basic/Mordukhovich normal cone to a set Ω⊂ R n at x ¯ , if

N Ω ( x ¯ )=lim sup x → x ¯ ( x ∈ Ω ) N ˆ Ω ( x ¯ ),
(2.11)

where N ˆ Ω ( x ¯ ) represents the prenormal/Fréchet normal cone to a set Ω at x ¯ defined by

N ˆ Ω ( x ¯ )= { υ ∈ R n | lim sup x → x ¯ ( x ∈ Ω ) 〈 υ , x − x ¯ 〉 ∥ x − x ¯ ∥ ≤ 0 } .
(2.12)

The set Ω will be said to be regular at x ¯ ∈Ω if

N Ω ( x ¯ )= N ˆ Ω ( x ¯ ).

For the lower semicontinuous function ψ with the epigraph epiψ, we can equivalently define the basic/Mordukhovich subdifferential (2.5) using the normal cone (2.11) by

∂ψ( x ¯ )= { υ ∈ R n ∣ ( υ , − 1 ) ∈ N epi ψ ( x ¯ , ψ ( x ¯ ) ) } .
(2.13)

The singular subdifferential of ψ at x ¯ ∈domψ by

∂ ∞ ψ( x ¯ )= { υ ∈ R n ∣ ( υ , 0 ) ∈ N epi ψ ( x ¯ , ψ ( x ¯ ) ) } .
(2.14)

If ψ is lower semicontinuous near x ¯ , then ∂ ∞ ψ( x ¯ )={0} if and only if ψ is locally Lipschitz continuous near x ¯ . Given a set-valued mapping Ξ: R n → 2 R m with its graph

gphΞ:= { ( x , y ) ∈ R n × R m ∣ y ∈ Ξ ( x ) } ,

recall the notion of coderivative for Ξ at ( x ¯ , y ¯ )∈gphΞ is defined by

D ∗ Ξ( x ¯ , y ¯ )(Ï…):= { u ∈ R n ∣ ( u , − Ï… ) ∈ N gph Ξ ( x ¯ , y ¯ ) } for Ï…∈ R m ,
(2.15)

via the normal cone (2.11) to the graph of Ξ. If Ξ is single-valued and locally Lipschitz continuous near x ¯ , its coderivative can be denoted analytically as

D ∗ Ξ( x ¯ )(Ï…)=∂〈υ,Ξ〉( x ¯ )for Ï…∈ R m ,

via the basic subdifferential (2.5) of the Lagrange scalarization 〈υ,Ξ〉(x):=〈υ,Ξ(x)〉, where the component y ¯ (=Ξ( x ¯ )) is omitted in the coderivative notation for single-valued mappings. This implies that the coderivative can be represented as

D ∗ Ξ( x ¯ )(Ï…)= { ∇ Ξ ( x ¯ ) ⊤ Ï… } for Ï…∈ R m ,

where Ξ is strictly differentiable at point x ¯ , ∇Ξ( x ¯ ) denotes its Jacobian matrix at x ¯ and ‘⊤’ stands for transposition.

Definition 2.11 A set-valued mapping Ξ is said to be inner semicompact at x ¯ with Ξ( x ¯ )≠∅, if for every sequence x k → x ¯ with Ξ( x k )≠∅, there exists a sequence of y k ∈Ξ( x k ) which contains a convergent subsequence as k→∞.

It follows that inner semicompactness holds whenever Ξ is uniformly bounded near x ¯ , i.e., there exist a neighborhood U and a bounded set Ω⊂ R m such that Ξ(x)⊂Ω for all x∈U.

Definition 2.12 A set-valued mapping Ξ is said to be inner semicontinuous at ( x ¯ , y ¯ )∈gphΞ, if for every sequence x k → x ¯ there exists a sequence of y k ∈Ξ( x k ) that converges to y ¯ as k→∞.

From Definitions 2.11 and 2.12, it is clear that Ξ is inner semicontinuous at ( x ¯ , y ¯ ), if Ξ is inner semicompact at x ¯ with Ξ( x ¯ )={ y ¯ }. Generally speaking, the inner semicontinuity which is much stronger than the inner semicompactness, is a necessary condition for the Lipschitz-like/Aubin property, which means that there exist two neighborhoods U of x ¯ and V of y ¯ , and a constant κ>0 such that

∀x,u∈U and y∈Ξ(u)∩V,d ( y , Ξ ( x ) ) ≤κ∥u−x∥,
(2.16)

where d means the distance from a point to a set in R m . When V= R m in (2.16), this property is reduced to the classical local Lipschitz continuity of Ξ near x ¯ . A complete characterization of the Lipschitz-like/Aubin property (2.16), and hence a sufficient condition for the inner semicontinuity of Ξ at ( x ¯ , y ¯ ), is given for closed graph mappings by the following coderivative/Mordukhovich criterion (see [[13], Theorem 5.7] and [[14], Theorem 9.40]):

D ∗ Ξ( x ¯ , y ¯ )(0)={0}.
(2.17)

In addition, the infimum of all κ>0 for which (2.16) holds is equal to the coderivative norm ∥ D ∗ Ξ( x ¯ , y ¯ )∥ as a positively homogeneous mapping D ∗ Ξ( x ¯ , y ¯ ). Set x= x ¯ in (2.16), the resulting weaker property is known as calmness of Ξ at ( x ¯ , y ¯ ) [14], which is used to derive the sensitivity analysis of the lower-level optimal solution mapping of the problem (3.4) in the sequel. For V= R m , the Lipschitz-like property in (2.16) corresponds to the upper Lipschitz property of Robinson [15].

3 Optimal value function reformulation for the pessimistic semivectorial bilevel programming problem

In this section, we shall discuss the reformulation process of the problems (1.6), (1.3), and (1.4) into a single-level generalized minimax optimization problem with constraints. We firstly by using scalarization technique transform the problems (1.3) and (1.4) into a usual one-level optimization problem, which consists of solving the following parametric problem:

min z f(x,y,z)= 〈 y , f ( x , z ) 〉 s.t. g(x,z)≤0,
(3.1)

where the parameter y is a nonnegative point of the unit sphere, i.e.,

y∈Y= { y ∈ R l ∣ y ≥ 0 , ∥ y ∥ = 1 } .
(3.2)

For a given upper-level variable x, the weakly efficient solution set Ψ wef (x) of the lower-level problem (1.3) is not in general a singleton, hence it is difficult to choose the best point z(x) on the set Ψ wef (x). Furthermore, we consider the set Y (3.2) as a new constraint set for the upper-level problem [6]. For all (x,y)∈X×Y (where X:={x∈ R n ∣G(x)≤0}), we denote by Ψ(x,y) the solution set of the problem (3.1). When the weakly efficient solutions are considered for the lower-level problem (1.3), the relationship (see e.g. [16]) relates the solution set of this problem and that of (3.1) as follows.

Theorem 3.1 Assume that the functions g(x,⋅) and f(x,⋅) are R + p -convex and R + l -convex for all x∈X, respectively. Then

Ψ wef (x)=Ψ(x,Y):=⋃ { Ψ ( x , y ) ∣ y ∈ Y } .
(3.3)

Hence, the pessimistic semivectorial bilevel programming problem (1.6) can be replaced by the following classical pessimistic bilevel programming problem:

{ min x max y max z F ( x , z ) s.t.  ( x , y ) ∈ X × Y , z ∈ Ψ ( x , y ) ,
(3.4)

where the set Y (3.2) on the new parameter of the lower-level problem acts like additional upper-level constraints. Now, we define the maximization bilevel optimal value function by

φ p (x,y)= max z { F ( x , z ) ∣ z ∈ Ψ ( x , y ) } ,
(3.5)

then the problem (3.4) can be expressed as the following generalized minimax problem with constraints:

min x max y { φ p ( x , y ) ∣ y ∈ Y , x ∈ X } .
(3.6)

We can also define the maximization another a bilevel optimal value function by

φ p p (x)= max y { φ p ( x , y ) ∣ y ∈ Y } ,
(3.7)

then the problem (3.4) can be further expressed as one-level optimization problem:

min x { φ p p ( x ) ∣ x ∈ X } .
(3.8)

Remark 3.1 The variable y in (3.4) is regarded as an upper-level decision making variable rather than lower-level decision variable. That is why we use the representation ‘ min x max y max z ’ and not use the representation ‘ min x max y , z ’. The hierarchically decision making process of the pessimistic bilevel programming problem (3.4) is as follows: The leader announces his variables (x,y) first and then the follower, bearing in mind, optimizes the objective function of himself and reacts the lower-level decision making variable z which is an optimal solution of the lower-level problem. In essence, we regard y in (3.4) as a weight vector to which the leader attaches the follower rather than the follower gives himself. For the problem (3.4), the existence and approximation of solution, the regularization properties and so on were studied in [11, 12, 17–27]. In [28], Loridan and Morgan considered the pessimistic formulation (i.e., the weak Stackelberg problem). Based on a method of Molodtsov, they presented an approach to approximate such problem by sequences of the optimistic formulation (i.e., the strong Stackelberg problem). The results related to the convergence of marginal functions and approximated solutions were given and the case of data perturbations was also considered. In [29], Aboussoror and Mansouri considered a class of weak linear bilevel programming with nonunique lower-level solutions, they gave an existence theorem of solution and a solving algorithm via exact penalty method. In [30], Lv et al. developed a penalty function method for the weak price control problem. In [31], Tsoukalas et al. provided an introduction to bilevel programming problems that illustrates some of the applications and computational challenges, and that outlines how bilevel programming problems can be solved. In [32], they and Kleniati provided a formal justification for the conjectures given in [31], the computational complexity of pessimistic bilevel programming problems were examined, and a solution scheme was developed and analyzed for the pessimistic programming problems. In [33], Malyshev and Strekalovsky considered the pessimistic formulation of a quadratic-linear bilevel programming problem, they reduced the problem to a series of bilevel programming problems in its optimistic formulation and then to nonconvex optimization problems by the KKT-optimality condition of the lower-level problem. Global and local search algorithms for the latter problems are developed. In [34], Dassanayaka studied the pessimistic formulation of the bilevel programming problems in finite dimensional spaces. Using the analysis tools from modern variational and generalized differentiation developed by Mordukhovich, first-order necessary and sufficient optimality conditions were established. A genetic algorithm for the weak linear bilevel programming problem was developed by Xiao and Li in [35]. Very recently, the pessimistic formulation for the bilevel programming problem was considered by Zemkoho in [36] and by Dempe et al. in [37] in the case where the functions involved were nonsmooth and smooth, respectively, the necessary optimality conditions were derived via the bilevel optimal value function reformulation.

Before discussing the link between the problems (1.6) and (3.4), we firstly recall that the notion of optimal solution for the upper-level problem in pessimistic formulation (see [[2], Definition 5.3]), namely, a point ( x ∗ , z ∗ ) is said to be a local optimal solution for the problem (1.6) if x ∗ ∈X, z ∗ ∈ Ψ wef ( x ∗ ) with

F ( x ∗ , z ∗ ) ≥F ( x ∗ , z ) ,∀z∈ Ψ wef ( x ∗ ) ,

and there exists an open neighborhood U δ ( x ∗ ), with

φ p p ( x ∗ ) ≤ φ p p (x),∀x∈X∩ U δ ( x ∗ ) .

It is called a global pessimistic solution if δ=∞ can be selected.

Now, we present the theorem of the existence of solution to the problem (3.4) (see [[2], Theorem 5.3]).

Theorem 3.2 If the set {(x,y,z)∣(x,y)∈X×Y,g(x,z)≤0} is nonempty and compact, and for each x∈X, the Mangasarian-Fromowitz Constraint Qualification (MFCQ) holds. Suppose that the lower-level solution set mapping Ψ(x,y) is lower semicontinuous at all points (x,y)∈X×Y. Then the problem (3.4) has an optimal solution.

Proof Due to lower semicontinuity of the lower-level solution set mapping Ψ(x,y), thus, the optimal value function φ p (x,y) in (3.5) is lower semicontinuous. Hence, this optimal value function φ p (x,y) attains its minimum on the compact set X×Y provided that this set is nonempty. □

The link between the problems (1.6) and (3.4) will be given in the next result. For this purpose, note that a set-valued mapping Ξ: R a → 2 R b is closed-valued at a point (u,v)∈ R a × R b if for any sequence ( u k , v k )∈gphΞ with ( u k , v k )→(u,v), one has v∈Ξ(u). Ξ is said to be closed-valued if it is closed-valued at any point of R a × R b .

Proposition 3.1 Consider the problems (1.6) and (1.3)-(1.4), where the lower-level constraint function g(x,⋅) is R + p -convex and f(x,⋅) is R + l -convex for all x∈X. Assume that Ψ is lower semicontinuous on X×Y. Then the following assertions hold.

  1. (i)

    Let ( x ∗ , z ∗ ) be a local (resp. global) optimal solution of the problem (1.6). Then, for all y ∗ ∈Y with z ∗ ∈Ψ( x ∗ , y ∗ ), the point ( x ∗ , y ∗ , z ∗ ) is a local (resp. global) optimal solution of the problem (3.4).

  2. (ii)

    Let ( x ∗ , y ∗ , z ∗ ) be a local (resp. global) optimal solution of the problem (3.4). Assume the set-valued mapping Ψ is closed-valued. Then ( x ∗ , z ∗ ) is a local (resp. global) optimal solution of the problem (1.6).

Proof We provide the proofs of (i) and (ii) in the local cases. The global cases can be obtained analogously.

  1. (i)

    Let ( x ∗ , z ∗ ) be a local optimal solution of the problem (1.6). Then

    { x ∗ = arg min { φ p p ( x ) ∣ x ∈ X } , z ∗ = arg max { F ( x , z ) ∣ z ∈ Ψ wef ( x ) } .

Suppose that there exists y ¯ ∈Y with z ∗ ∈Ψ( x ∗ , y ¯ ) such that ( x ∗ , y ¯ , z ∗ ) is not a local optimal solution of the problem (3.4). Then there exists a sequence ( x k , y k , z k ) with x k → x ∗ , y k → y ¯ , z k → z ∗ and ( x k , y k )∈X×Y, z k ∈Ψ( x k , y k ) such that F( x k , z k ) is better than F( x ∗ , z ∗ ). By the equality (3.3), we know that [ y k ∈Y, z k ∈Ψ( x k , y k )]⇒ z k ∈ Ψ wef ( x k ), and moreover, x ∗ ∈X (since X is closed) and [ y ¯ ∈Y, z ∗ ∈Ψ( x ∗ , y ¯ )]⇒ z ∗ ∈ Ψ wef ( x ∗ ), that is, ( x k , y k , z k ) and ( x ∗ , y ¯ , z ∗ ) are the feasible solutions to the problem (3.4). To sum up, we can find a sequence ( x k , z k )→( x ∗ , z ∗ ) with x k ∈X, z k ∈ Ψ wef ( x k ) such that F( x k , z k ) is better than F( x ∗ , z ∗ ), which contradicts the initial statement that ( x ∗ , z ∗ ) is a local optimal solution of the problem (1.6).

  1. (ii)

    Assume that ( x ∗ , y ∗ , z ∗ ) is a local optimal solution of the problem (3.4). Then we have

    { x ∗ = arg min { φ p p ( x ) ∣ x ∈ X } , y ∗ = arg max { φ p ( x , y ) ∣ y ∈ Y } , z ∗ = arg max { F ( x , z ) ∣ z ∈ Ψ ( x , y ) } .

Since Ψ is lower semicontinuous and closed-valued, for any sequence ( x k , y k ) with x k → x ∗ , y k → y ∗ and z ∗ ∈Ψ( x ∗ , y ∗ ), there exists z k ∈Ψ( x k , y k ) for all k such that z k → z ∗ . By the equality (3.3), we have [ y ∗ ∈Y, z ∗ ∈Ψ( x ∗ , y ∗ )]⇒ z ∗ ∈ Ψ wef ( x ∗ ). Considering that x ∗ ∈X and X is closed, we have

{ x ∗ = arg min { φ p p ( x ) ∣ x ∈ X } , z ∗ = arg max { F ( x , z ) ∣ z ∈ Ψ wef ( x ) } .

Therefore ( x ∗ , z ∗ ) is a local optimal solution of the problem (1.6). This completes the proof. □

Next, we give the optimal value function reformulation for the pessimistic bilevel programming problem (3.4) as follows:

min φ p p ( x ) s.t.  x ∈ X , { φ p p ( x ) = max y { φ p ( x , y ) ∣ y ∈ Y } , φ p ( x , y ) = max z { F ( x , z ) ∣ z ∈ Ψ ( x , y ) } , Ψ ( x , y ) = { z ∈ R m ∣ f ( x , y , z ) − φ ( x , y ) ≤ 0 , g ( x , z ) ≤ 0 } , φ ( x , y ) = min z { f ( x , y , z ) ∣ g ( x , z ) ≤ 0 } .
(3.9)

Based on this result, we will attempt to derive the necessary optimality conditions of the pessimistic semivectorial bilevel programming problem (1.6) via deriving those of the auxiliary problem (3.4). Obviously, if we set the minimization optimal value function as

φ p o (x,y)= min z { − F ( x , z ) ∣ z ∈ Ψ ( x , y ) } ,
(3.10)

then the maximization optimal value function φ p (x,y) (3.5) coincides with the negative of φ p o (x,y), i.e., for all (x,y)∈X×Y, we have

φ p (x,y)=− φ p o (x,y).
(3.11)

Analogously, we can set the minimization another optimal value function as

φ p p o (x)= min y { − φ p ( x , y ) ∣ y ∈ Y } ,
(3.12)

then, for all x∈X, we also have

φ p p (x)=− φ p p o (x).
(3.13)

By (3.11) and (3.13), we analyze the maximized bilevel optimal value function φ p (x,y) and φ p p (x) via analyzing the minimization bilevel optimal value functions φ p o (x,y) in (3.10) and φ p p o (x) in (3.12), respectively. In order to analyze the bilevel value function φ p o (x,y) and φ p p o (x), we consider a general ‘abstract’ framework of the marginal function:

μ(x)= min y { ψ ( x , y ) ∣ y ∈ Ξ ( x ) } ,
(3.14)

where ψ: R n × R m → R ¯ and Ξ: R n → 2 R m . Denote the argminimum mapping in (3.14) by Ξ o (x)=argmin{ψ(x,y)∣y∈Ξ(x)}={y∈Ξ(x)∣ψ(x,y)≤μ(x)}. We summarize in the next theorem some known results on general value functions needed in the paper (see [[13], Corollary 1.109] and [[38], Theorem 5.2]).

Theorem 3.3 Let the value function μ be given in (3.14), where the graph of Ξ is locally closed around ( x ¯ , y ¯ )∈gphΞ and ψ is strictly differentiable at this point. The following assertions hold:

  1. (i)

    Let Ξ o be inner semicompact at x ¯ . Then μ is lower semicontinuous at x ¯ and the upper bound for its basic subdifferential is given as follows:

    ∂μ( x ¯ )⊂ ⋃ y ¯ ∈ Ξ o ( x ¯ ) { ∇ x ψ ( x ¯ , y ¯ ) + D ∗ Ξ ( x ¯ , y ¯ ) ( ∇ y ψ ( x ¯ , y ¯ ) ) } .

    If in addition Ξ is Lipschitz-like around ( x ¯ , y ¯ ) for all vectors y ¯ ∈ Ξ o ( x ¯ ), then we also have the Lipschitz continuity of μ around x ¯ .

  2. (ii)

    Let Ξ o be inner semicontinuous at ( x ¯ , y ¯ ). Then μ is lower semicontinuous at x ¯ and the upper bound for its basic subdifferential is given as follows:

    ∂μ( x ¯ )⊂ ∇ x ψ( x ¯ , y ¯ )+ D ∗ Ξ( x ¯ , y ¯ ) ( ∇ y ψ ( x ¯ , y ¯ ) ) .

    If in addition Ξ is Lipschitz-like around ( x ¯ , y ¯ ), then μ is Lipschitz continuous around  x ¯ .

By the equalities (3.11), (3.13), and (2.8), we have

∂ φ p ( x , y ) = ∂ ( − φ p o ) ( x , y ) ⊂ co ∂ ( − φ p o ) ( x , y ) = − co ∂ φ p o ( x , y ) , ∂ φ p p ( x ) = ∂ ( − φ p p o ) ( x ) ⊂ co ∂ ( − φ p p o ) ( x ) = − co ∂ φ p p o ( x ) ,

and so

∂ φ p (x,y)⊂−co∂ φ p o (x,y),
(3.15)
∂ φ p p (x)⊂−co∂ φ p p o (x).
(3.16)

By Theorem 3.3, we can estimate the upper bound of the subdifferential of the bilevel optimal value function φ p (x,y) (resp. φ p p (x)) via estimating the subdifferential of ∂ φ p o (x,y) (resp. ∂ φ p p o (x)). In the next section, based on specific structures of the set-valued mapping Ξ, our aim is to give detailed upper bounds for D ∗ Ξ( x ¯ , y ¯ ) in terms of problem data. Verifiable rules for Ξ to be Lipschitz-like will also be provided. Further, we present the sensitivity analysis for the maximization bilevel optimal value function ∂ φ p (x,y) and ∂ φ p p (x). Based on these results, we develop the necessary optimality conditions for the problems (3.4) and (1.6).

4 Main results

In this section, we study the necessary optimality conditions for the optimal value function reformulation (3.9) of the problem (3.4). Firstly, we recall that the argminimun/solution map of the lower-level problem (3.1) as

Ψ(x,y)= { z ∈ R m ∣ f ( x , y , z ) − φ ( x , y ) ≤ 0 , g ( x , z ) ≤ 0 } ,
(4.1)

with φ denoting the optimal value function associated to the lower-level problem (3.1), i.e.,

φ(x,y)= min z { f ( x , y , z ) ∣ g ( x , z ) ≤ 0 } .
(4.2)

Here, we employ the lower-level value function approach [39] to sensitivity analysis of the bilevel value function φ p o (x,y) in (3.10). Hence, we have the lower-level optimal value function reformulation of φ p o (x,y):

φ p o (x,y)= min z { − F ( x , z ) ∣ g ( x , z ) ≤ 0 , f ( x , y , z ) − φ ( x , y ) ≤ 0 } .
(4.3)

Since the basic subdifferential ∂φ does not satisfy the plus symmetry, an appropriate estimate of ∂(−φ) is needed to proceed with this approach. By the well-known convex hull property (2.8), the estimate of ∂(−φ) can be done.

In order to study the sensitivity analysis of the negative value function in the lower-level problem (3.1), we first recall the lower-level and upper-level regularity conditions [40], which are defined, respectively, as

∑ i = 1 p β i ∇ z g i ( x ∗ , z ∗ ) = 0 , β i ≥ 0 , β i g i ( x ∗ , z ∗ ) = 0 , i = 1 , … , p } ⇒ β i =0,i=1,…,p,
(4.4)
∑ j = 1 q α j ∇ G j ( x ∗ ) = 0 , α j ≥ 0 , α j G j ( x ∗ ) = 0 , j = 1 , … , q } ⇒ α j =0,j=1,…,q.
(4.5)

It is clear that these are the dual forms of the MFCQ for the lower-level constraints g i ( x ∗ ,z)≤0, i=1,…,p (for the fixed parameter x= x ∗ ) and the upper-level constraints G j (x)≤0, j=1,…,q, respectively. A particularity of the new constraint set Y (3.2), that the related Lagrange multipliers can be completely eliminated from the optimality conditions, is given in the next lemma (see [[6], Lemma 4.2]).

Lemma 4.1 The set of vectors ( x ∗ , y ∗ , z ∗ )∈ R n × R l × R m , γ, z s ∈ R l and μ,r, υ s ∈R with s=1,…,n+l+1, satisfies the system

{ r f ( x ∗ , z ∗ ) − r ∑ s = 1 n + l + 1 υ s f ( x ∗ , z s ) − γ + μ ⋅ y ∗ = 0 , γ ≥ 0 , γ ⊤ y ∗ = 0 , ∥ y ∗ ∥ = 1
(4.6)

if and only if the following inequality holds:

r { [ ∑ k = 1 l y k ( f k ( x ∗ , z ∗ ) − ∑ s = 1 n + l + 1 υ s f k ( x ∗ , z s ) ) ] y ∗ − [ f ( x ∗ , z ∗ ) − ∑ s = 1 n + l + 1 υ s f ( x ∗ , z s ) ] } ≤0.
(4.7)

4.1 Sensitivity analysis of the lower-level negative value function

In this subsection, we shall study the sensitivity analysis of the negative value function in the lower-level problem (3.1).

Theorem 4.1 If f and g are strictly differentiable, and the following assertions hold for the negation of the value function φ in (4.2).

  1. (i)

    If the solution map Ψ(x,y) in (4.1) is inner semicompact at ( x ∗ , y ∗ ) for all ( x ∗ , y ∗ ,z)∈gphΨ satisfying (4.4), then φ is Lipschitz continuous around ( x ∗ , y ∗ ), and the following inclusion holds:

    ∂ ( − φ ) ( x ∗ , y ∗ ) ⊂ { [ ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z s ) + ∑ i = 1 p β i s ∇ z g i ( x ∗ , z s ) = 0 , β i s ≥ 0 , β i s g i ( x ∗ , z s ) = 0 , η s ≥ 0 , ∑ s = 1 n + l + 1 η s = 1 , z s ∈ Ψ ( x ∗ , y ∗ ) , ∀ s = 1 , … , n + l + 1 , k = 1 , … , l , i = 1 , … , p − ∑ s = 1 n + l + 1 η s ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z s ) + ∑ i = 1 p β i s ∇ x g i ( x ∗ , z s ) ) − ∑ s = 1 n + l + 1 η s f ( x ∗ , z s ) ] | ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z s ) + ∑ i = 1 p β i s ∇ z g i ( x ∗ , z s ) = 0 , β i s ≥ 0 , β i s g i ( x ∗ , z s ) = 0 , η s ≥ 0 , ∑ s = 1 n + l + 1 η s = 1 , z s ∈ Ψ ( x ∗ , y ∗ ) , ∀ s = 1 , … , n + l + 1 , k = 1 , … , l , i = 1 , … , p } .
    (4.8)
  2. (ii)

    Assume that ( x ∗ , y ∗ , z ∗ )∈gphΨ with x ∗ ∈domφ satisfying (4.4) and that either Ψ is inner semicontinuous at this point or f and g are convex. Then φ is Lipschitz continuous around ( x ∗ , y ∗ ), and the following inclusion holds:

    ∂ ( − φ ) ( x ∗ , y ∗ ) ⊂ { [ − ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z ∗ ) − ∑ i = 1 p β i ∇ x g i ( x ∗ , z ∗ ) − f ( x ∗ , z ∗ ) ] | ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z ∗ ) + ∑ i = 1 p β i ∇ z g i ( x ∗ , z ∗ ) = 0 , β i ≥ 0 , β i g i ( x ∗ , z ∗ ) = 0 , k = 1 , … , l , i = 1 , … , p } .
    (4.9)

Proof The local Lipschitz continuity of φ is justified from [[38], Theorem 5.2] under the fulfillment of (4.4) in both the inner semicontinuity and inner semicompactness cases. If the functions f and g are convex, then the value function φ is also convex, in this case the Lipschitz continuity follows from [[41], Theorem 6.3.2]. To prove the subdifferential inclusion of (i), recall that

∂ φ ( x ∗ , y ∗ ) ⊂ { [ ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z ) + ∑ i = 1 p β i ∇ z g i ( x ∗ , z ) = 0 , β i ≥ 0 , β i g i ( x ∗ , z ) = 0 , z ∈ Ψ ( x ∗ , y ∗ ) , k = 1 , … , l , i = 1 , … , p ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z ) + ∑ i = 1 p β i ∇ x g i ( x ∗ , z ) f ( x ∗ , z ) ] | ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z ) + ∑ i = 1 p β i ∇ z g i ( x ∗ , z ) = 0 , β i ≥ 0 , β i g i ( x ∗ , z ) = 0 , z ∈ Ψ ( x ∗ , y ∗ ) , k = 1 , … , l , i = 1 , … , p }
(4.10)

by [[42], Corollary 4] under the assumptions of (i). The claimed estimate of ∂(−φ) follows from this by combining (2.8) and the classical Carathéodory’s theorem.

When Ψ is inner semicontinuous at ( x ∗ , y ∗ , z ∗ ), we have by [[43], Corollary 5.3] that

∂ ¯ φ ( x ∗ , y ∗ ) ⊂ { [ ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z ∗ ) + ∑ i = 1 p β i ∇ x g i ( x ∗ , z ∗ ) f ( x ∗ , z ∗ ) ] | ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z ∗ ) + ∑ i = 1 p β i ∇ z g i ( x ∗ , z ∗ ) = 0 , β i ≥ 0 , β i g i ( x ∗ , z ∗ ) = 0 , k = 1 , … , l , i = 1 , … , p } .
(4.11)

This implies the subdifferential inclusion of (ii) by (2.7) and (2.8). If both f and g are convex, inclusion (4.11) holds without the inner semicontinuity assumption (see [[40], Theorem 4.2] and [[44], Corollary 4]). This completes the proof. □

Note that in the fully convex (even nonsmooth) case, the assumption (4.4) in Theorem 4.1 can be replaced by a much weaker qualification condition [44] requiring that the set epi f ∗ +cone( ⋃ i = 1 p epi g i ∗ ) is closed on R n × R m ×R, where epi f ∗ denotes the conjugate function for an extended real-valued function f.

4.2 Sensitivity analysis of the lower-level optimal solution maps

In this subsection, we present an upper estimate for the coderivative of the solution mapping Ψ given in (4.1) and establish its Lipschitz-like property. For this purpose, we first present the calmness property. By (2.15), calculating the coderivative of Ψ, we must compute the limiting normal cone to the graph of Ψ:

gph Ψ = { ( x , y , z ) ∈ K ∣ f ( x , y , z ) − φ ( x , y ) ≤ 0 } with  K = { ( x , y , z ) ∣ g ( x , z ) ≤ 0 }
(4.12)

in terms of the initial data. To proceed this way by using the conventional results of the generalized differential calculus [13] requires the fulfillment of the basic qualification condition, which reads in this case

∂(f−g) ( x ∗ , y ∗ , z ∗ ) ∩ ( − N K ( x ∗ , y ∗ , z ∗ ) ) =∅.
(4.13)

However, it is shown in [[45], Theorem 3.1] that condition (4.13) fails in common situations; in particular, when φ is locally Lipschitz around the point in question. The weaker assumption which helps circumventing this difficulty is given as follows:

Φ(ν)= { ( x , y , z ) ∈ K ∣ f ( x , y , z ) − φ ( x , y ) ≤ ν }  is calm at  ( 0 , x ∗ , y ∗ , z ∗ ) .
(4.14)

The condition (4.14) is automatically satisfied if f and g are linear. Furthermore, (4.14) holds at ( x ∗ , y ∗ , z ∗ ) for the locally Lipschitzian function φ if we pass to the boundary of the normal cone in (4.13), that is, if the following qualification condition holds:

∂(f−g) ( x ∗ , y ∗ , z ∗ ) ∩ ( − bd N K ( x ∗ , y ∗ , z ∗ ) ) =∅,
(4.15)

with K being semismooth, in particular, convex. The condition (4.15) seems to be especially effective for so-called simple convex bilevel programming problems. For the more details, the readers can be refer to [45, 46]. It is deserved that for the latter case, the condition (4.15) can be further weakened by passing to the boundary of the subdifferential of f [45]. It is also worth mentioning that, except the condition (4.15), another sufficient condition for the validity of the calmness property (4.14) is provided by the notion of uniform weak sharp minima. More details can be found in [34, 43, 47].

For estimating the coderivative of Ψ, we present additional qualification condition:

[ ( λ , β i ) ∈ Λ z ( x ∗ , y ∗ , z ∗ , 0 ) , x ∗ ∗ ∈ ∂ ( − φ ) ( x ∗ , y ∗ ) ] ⇒ λ x ∗ ∗ = { − λ ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z ∗ ) − ∑ i = 1 p β i ∇ x g i ( x ∗ , z ∗ ) } ,
(4.16)

where Λ z ( x ∗ , y ∗ , z ∗ , z ∗ ∗ ) is a particular multipliers set, i.e.,

Λ z ( x ∗ , y ∗ , z ∗ , z ∗ ∗ ) = { ( λ , β i ) | λ ≥ 0 , β i ≥ 0 , β i g i ( x ∗ , z ∗ ) = 0 , z ∗ ∗ + λ ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z ∗ ) + ∑ i = 1 p β i ∇ z g i ( x ∗ , z ∗ ) = 0 , λ ≥ 0 , β i ≥ 0 , β i g i ( x ∗ , z ∗ ) = 0 , z ∗ ∗ + λ ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z ∗ ) + ∑ i = 1 p β i ∇ z g i ( x ∗ , z ∗ ) = 0 , k = 1 , 2 , … , l ; i = 1 , 2 , … , p } .
(4.17)

By [[39], Proposition 5.6], if the functions f and g are fully convex and continuously differentiable and the lower constraint function g does not contain the upper-level decision maker variables and the lower-level value function φ is finite, the condition (4.4) is a sufficient condition for (4.17) holding at point ( x ∗ , y ∗ , z ∗ ). The following lower-level Lagrange multipliers set plays an important role in the sequel:

Λ ( x ∗ , y ∗ , z ∗ ) = { β i | β i ≥ 0 , β i g i ( x ∗ , z ∗ ) = 0 , i = 1 , 2 , … , p , ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z ∗ ) + ∑ i = 1 p β i ∇ z g i ( x ∗ , z ∗ ) = 0 } .
(4.18)

Now, we present the coderivative estimate and Lipschitz-like property of lower-level solution maps.

Theorem 4.2 (i) For all ( x ∗ , y ∗ ,z)∈gphΨ, let the conditions (4.4) and (4.14) hold at this point, and let the solution map Ψ (4.1) be inner semicompact at ( x ∗ , y ∗ ). Then, for all z∈ R m , (4.7) and the inclusion (4.19) hold:

D ∗ Ψ ( x ∗ , y ∗ , z ∗ ) ( z ) ⊂ ⋃ z s ∈ Ψ ( x ∗ , y ∗ ) ⋃ ( λ , β i ) ∈ Λ z ( x ∗ , y ∗ , z ∗ , z ) ⋃ β i s ∈ Λ ( x ∗ , y ∗ , z ∗ ) { λ ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z ) − ∑ s = 1 n + l + 1 η s × ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z s ) + ∑ i = 1 p β i s ∇ x g i ( x ∗ , z s ) ) ) + ∑ i = 1 p β i ∇ x g i ( x ∗ , z ) , λ f ( x ∗ , z ) − λ ∑ s = 1 n + l + 1 η s f ( x ∗ , z s ) , ∑ s = 1 n + l + 1 η s = 1 , η s ≥ 0 , s = 1 , … , n + l + 1 } ,
(4.19)

with ∑ s = 1 n + l + 1 η s =1 and η s ≥0 for s=1,2,…,n+l+1. If in addition the condition (4.16) holds at ( x ∗ , y ∗ , z s ), then Ψ is Lipschitz-like around this point.

(ii) Let the solution map Ψ (4.1) be inner semicontinuous at ( x ∗ , y ∗ , z ∗ )∈gphΨ, and let the qualification conditions (4.4) and (4.14) hold at this point. Then, for all z ∗ ∗ ∈ R m , we have

D ∗ Ψ ( x ∗ , y ∗ , z ∗ ) ( z ∗ ∗ ) ⊂ ⋃ ( λ , β i ) ∈ Λ z ( x ∗ , y ∗ , z ∗ , z ∗ ∗ ) ⋃ γ i ∈ Λ ( x ∗ , y ∗ , z ∗ ) { ∑ i = 1 p ( β i − λ γ i ) ∇ x g i ( x ∗ , z ∗ ) } .
(4.20)

If in addition the condition (4.16) holds at ( x ∗ , y ∗ , z ∗ ), then Ψ is Lipschitz-like around this point.

Proof We first show the proof for (i). It follows from Theorem 4.1(i) that the lower-level function φ is Lipschitz continuous around ( x ∗ , y ∗ ) under assumption condition (4.4) and the inner semicompactness assumptions. If we add the calmness property (4.14), then we have

N gph Ψ ( x ∗ , y ∗ , z ∗ ) ⊂ ⋃ z s ∈ Ψ ( x ∗ , y ∗ ) ⋃ λ ≥ 0 { λ ( ∇ f ( x ∗ , y ∗ , z ∗ ) + ∂ ( − φ ) ( x ∗ , y ∗ ) × { 0 } ) + N K ( x ∗ , y ∗ , z ∗ ) } ,

by [[48], Theorem 4.1] taking into account that the constraint f(x,y,z)−φ(x,y)≤0 is working at point ( x ∗ , y ∗ , z ∗ ). By (4.12), we have

N K ( x ∗ , y ∗ , z ∗ ) = { ∑ i = 1 p β i ∇ z g i ( x ∗ , z ∗ ) | β i ≥ 0 , β i g i ( x ∗ , z ∗ ) = 0 , i = 1 , … , p } ,
(4.21)

which holds under the validity of the condition (4.4) at point ( x ∗ , y ∗ , z t ). Combining the definition of the coderivative (2.15), we derive the coderivative estimate (4.19). Further, by (4.19) and the coderivative criterion (2.17) for the Lipschitz-like property, the coderivative criterion holds provided that

x ∗ ∗ ∈ λ ( ∑ k = 1 l y k ∗ ∇ x f ( x ∗ , z ∗ ) + ∂ ( − φ ) ( x ∗ , y ∗ ) ) + ∑ i = 1 p β i ∇ x g i ( x ∗ , z ∗ ) , ( λ , β i ) ∈ Λ z ( x ∗ , y ∗ , z ∗ , 0 ) } ⇒ x ∗ ∗ = 0 .
(4.22)

Let us prove (ii). According to Theorem 4.1(ii), the lower-level function φ is Lipschitz continuous around ( x ∗ , y ∗ ) under the condition (4.4) and the inner semicontinuous assumptions. If we add the calmness property (4.14), then we have

N gph Ψ ( x ∗ , y ∗ , z ∗ ) ⊂ ⋃ λ ≥ 0 { λ ( ∇ f ( x ∗ , y ∗ , z ∗ ) + ∂ ( − φ ) ( x ∗ , y ∗ ) × { 0 } ) + N K ( x ∗ , y ∗ , z ∗ ) } ,

by [[48], Theorem 4.1] taking into account that the constraint f(x,y,z)−φ(x,y)≤0 is active at point ( x ∗ , y ∗ , z ∗ ). By (4.12), the equality (4.21) holds. Combining the definition of the coderivative (2.15), we derive the coderivative estimate (4.20). Further, by (4.20) and the coderivative criterion (2.17) for the Lipschitz-like property, the coderivative criterion holds provided the (4.22). This completes the proof. □

Noting that if the functions f and g are convex, the inner semicontinuity of Ψ can be dropped in Theorem 4.2(ii).

4.3 Sensitivity analysis of the maximization bilevel optimal value functions φ p (x,y) and φ p p (x) using the lower-level value function approach

For simplicity, we define the upper-level optimal solution set mapping as follows:

Ψ o (x,y)= { z ∈ Ψ ( x , y ) ∣ − F ( x , z ) − φ p o ( x , y ) ≤ 0 } .
(4.23)

In the rest of this paper, we always assume that the set Ψ o (x,y) is nonempty. The following results illustrate the local sensitivity analysis of the bilevel value function φ p defined in (3.5).

Theorem 4.3 Considering (3.5) and (4.23), the following assertions hold:

  1. (i)

    Assume that Ψ o is inner semicompact at ( x ∗ , y ∗ ), the condition (4.4) holds at ( x ∗ , y ∗ ,z)∈gphΨ, while the condition (4.14) holds at ( x ∗ , y ∗ ,z) for all z∈ Ψ o ( x ∗ , y ∗ ). Then the following inclusion holds:

    ∂ φ p ( x ∗ , y ∗ ) ⊂ ⋃ z t ∈ Ψ ( x ∗ , y ∗ ) ⋃ z s ∈ Ψ ( x ∗ , y ∗ ) ⋃ ( λ t , β i t ) ∈ Λ z ( x ∗ , y ∗ , z ∗ , z t ) ⋃ β i s ∈ Λ ( x ∗ , y ∗ , z ∗ ) { x t ∗ ∗ ∈ ∑ t = 1 n + l + 1 ν t { ∇ x F ( x ∗ , z t ) − λ t ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z t ) − ∑ s = 1 n + l + 1 η s ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z s ) + ∑ i = 1 p β i s ∇ x g i ( x ∗ , z s ) ) ) + ∑ i = 1 p β i t ∇ x g i ( x ∗ , z t ) } , y t ∗ ∗ ∈ λ t f ( x ∗ , z t ) − λ t ∑ s = 1 n + l + 1 η s f ( x ∗ , z s ) , ∑ t = 1 n + l + 1 ν t = 1 , ν t ≥ 0 , t = 1 , … , n + l + 1 , ∑ s = 1 n + l + 1 η s = 1 , η s ≥ 0 , s = 1 , … , n + l + 1 ( x t ∗ ∗ , y t ∗ ∗ ) | x t ∗ ∗ ∈ ∑ t = 1 n + l + 1 ν t { ∇ x F ( x ∗ , z t ) − λ t ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z t ) − ∑ s = 1 n + l + 1 η s ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z s ) + ∑ i = 1 p β i s ∇ x g i ( x ∗ , z s ) ) ) + ∑ i = 1 p β i t ∇ x g i ( x ∗ , z t ) } , y t ∗ ∗ ∈ λ t f ( x ∗ , z t ) − λ t ∑ s = 1 n + l + 1 η s f ( x ∗ , z s ) , ∑ t = 1 n + l + 1 ν t = 1 , ν t ≥ 0 , t = 1 , … , n + l + 1 , x t ∗ ∗ ∈ ∑ t = 1 n + l + 1 ν t { ∇ x F ( x ∗ , z t ) − λ t ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z t ) x t ∗ ∗ ∈ − ∑ s = 1 n + l + 1 η s ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z s ) x t ∗ ∗ ∈ + ∑ i = 1 p β i s ∇ x g i ( x ∗ , z s ) ) ) + ∑ i = 1 p β i t ∇ x g i ( x ∗ , z t ) } , y t ∗ ∗ ∈ λ t f ( x ∗ , z t ) − λ t ∑ s = 1 n + l + 1 η s f ( x ∗ , z s ) , ∑ t = 1 n + l + 1 ν t = 1 , ν t ≥ 0 , t = 1 , … , n + l + 1 , ∑ s = 1 n + l + 1 η s = 1 , η s ≥ 0 , s = 1 , … , n + l + 1 } .
    (4.24)

If in addition (4.16) is satisfied at ( x ∗ , y ∗ ,z) for all z∈ Ψ o ( x ∗ , y ∗ ), then φ p is Lipschitz continuous around ( x ∗ , y ∗ ).

  1. (ii)

    Assume that Ψ o is inner semicontinuous at ( x ∗ , y ∗ , z ∗ ), the conditions (4.4) and (4.14) hold at this point. Furthermore, assume that the set co N gph Ψ ( x ∗ , y ∗ , z ∗ ) is closed. Then the following inclusion holds:

    ∂ φ p ( x ∗ , y ∗ ) ⊂ ⋃ ( λ t , β i t ) ∈ Λ z ( x ∗ , y ∗ , z ∗ , z ∗ ∗ ) ⋃ γ i t ∈ Λ ( x ∗ , y ∗ , z ∗ ) { ∇ x F ( x ∗ , z ∗ ) − ∑ t = 1 n + l + 1 ν t { ∑ i = 1 p ( β i t − λ t γ i t ) ∇ x g i ( x ∗ , z ∗ ) } | ∑ t = 1 n + l + 1 ν t = 1 , ν t ≥ 0 , t = 1 , … , n + l + 1 } .
    (4.25)

If in addition (4.16) is satisfied at point ( x ∗ , y ∗ , z ∗ ), then φ p is Lipschitz continuous around ( x ∗ , y ∗ ).

Proof We first provide the proof of (i). To justify (i), observe by Theorem 3.3(i) that

∂ φ p o ( x ∗ , y ∗ ) ⊂ ⋃ z t ∈ Ψ o ( x ∗ , y ∗ ) { ( ∇ x ( − F ( x ∗ , z t ) ) ∇ y ( − F ( x ∗ , z t ) ) ) + D ∗ Ψ ( x ∗ , y ∗ , z t ) ( ∇ z ( − F ( x ∗ , z t ) ) ) } ,

under the inner semicompactness assumption on Ψ o . Since Ψ o (x,y)⊂Ψ(x,y) for all (x,y)∈X×Y, the lower-level optimal solution map Ψ in (4.1) is also inner semicompact at ( x ∗ , y ∗ , z t )∈gph Ψ o . Hence, by the subdifferential of the lower-level negation value function −φ in Theorem 4.1(i) and the coderivative of Ψ in Theorem 4.2(i), combining with (3.15) and Carathéodory’s theorem, we can derive the upper estimate of φ p ( x ∗ , y ∗ ).

To prove the local Lipschitz continuity of φ p ( x ∗ , y ∗ ) in (i) under the condition (4.16), the latter condition implies the Lipschitz-like property of Ψ around ( x ∗ , y ∗ , z t )∈gph Ψ o . Thus the desired result is obtained from Theorem 3.3(i).

For justifying (ii), since the function F is strictly differentiable and Ψ o is inner semicontinuous at ( x ∗ , y ∗ , z ∗ ), we get from [[43], Theorem 5.1]

∂ ¯ φ p o ( x ∗ , y ∗ ) ⊂ { ( ∇ x ( − F ( x ∗ , z ∗ ) ) ∇ y ( − F ( x ∗ , z ∗ ) ) ) + D ¯ ∗ Ψ ( x ∗ , y ∗ , z ∗ ) ( ∇ z ( − F ( x ∗ , z ∗ ) ) ) } .

Combining with (4.20) and Carathéodory’s theorem, we can derive the estimation for the coderivative D ¯ ∗ Ψ( x ∗ , y ∗ , z ∗ )( ∇ z (−F( x ∗ , z ∗ ))):

D ¯ ∗ Ψ ( x ∗ , y ∗ , z ∗ ) ( ∇ z ( − F ( x ∗ , z ∗ ) ) ) ⊂ ⋃ ( λ t , β i t ) ∈ Λ z ( x ∗ , y ∗ , z ∗ , z ∗ ∗ ) ⋃ γ i t ∈ Λ ( x ∗ , y ∗ , z ∗ ) { ∑ t = 1 n + l + 1 ν t { ∑ i = 1 p ( β i t − λ t γ i t ) ∇ x g i ( x ∗ , z ∗ ) } | ∑ t = 1 n + l + 1 ν t = 1 , ν t ≥ 0 , t = 1 , … , n + l + 1 } .

The latter inclusion implies that N ¯ gph Ψ ( x ∗ , y ∗ , z ∗ )=co N gph Ψ ( x ∗ , y ∗ , z ∗ ) provided the set co N gph Ψ ( x ∗ , y ∗ , z ∗ ) is closed. Combining the above two results, by (2.7) and (3.15), we can justify (4.25). To justify the local Lipschitz continuity of φ p ( x ∗ , y ∗ ) in (ii) under the condition (4.16), the latter condition implies the Lipschitz-like property of Ψ around ( x ∗ , y ∗ , z ∗ ). This completes the proof. □

In the following, we shall present a local sensitivity analysis of the maximization bilevel optimal value function φ p p (x) in (3.7). For this goal, we need to estimate ∂ φ p p o (x). Combining (3.13) and the conclusion on the sensitivity analysis for the value function of the nonparametric minimax problem (see [[49], Lemma 3.3]), we have

∂ φ p p o (x)⊆∂(− φ p )(x,y)=∂ φ p o (x,y).

By (3.16), we derive that ∂ φ p p (x)⊂−co∂ φ p o (x,y) and φ p p (x) is Lipschitz continuous around x ∗ under the corresponding conditions of Theorem 4.3.

Remark 4.1 Observe that for the subdifferential estimate of φ p in Theorem 4.3(ii), the upper bound of the basic subdifferential does not contain the partial derivative of the lower-level objective function f(x,y,z) with respect to the upper-level variable x. Such a phenomenon is no longer true if the inner semicontinuity for Ψ o is replaced by the inner semicompactness in Theorem 4.3(i), this phenomenon can also be found in [6, 40]. We mention that the inner semicompactness of Ψ o in Theorem 4.3(i) can be replaced by the restrictive uniform boundedness assumption on Ψ o or even on Ψ. Finally, by Theorem 3.3(ii) and Theorem 4.2(ii), we can derive the subdifferential estimate for φ p , which is different from (4.25). In this case, the gradient of the upper-level objective function F is involved in the convex combinations summation, while that of (4.25) not be. This will be shown in the following Theorem 4.4(ii).

4.4 Necessary optimality conditions using the bilevel optimal value function formulation

In this subsection, we shall establish the necessary optimality conditions for the optimal value reformulation (3.9) of the problem (3.4) using the above sensitivity analysis results.

Theorem 4.4 Let ( x ∗ , y ∗ ) be an upper-level regular local optimal solution to the problem (3.4), whereas F and G are strictly differentiable at ( x ∗ , z ∗ ) and x ∗ , respectively, and let X×Y be closed. Then the following assertions hold:

  1. (i)

    Let Ψ o be inner semicompact at ( x ∗ , y ∗ ) while for all z∈Ψ( x ∗ , y ∗ ) and the point ( x ∗ ,z) is lower-level regular, let f and g be strictly differentiable at ( x ∗ ,z), z∈Ψ( x ∗ , y ∗ ), and let the conditions (4.14) and (4.16) be satisfied at all point ( x ∗ , y ∗ ,z) with z∈ Ψ o ( x ∗ , y ∗ ). Then there exist λ t ≥0, α, β t , β s , η s and z t , z s ∈Ψ( x ∗ , y ∗ ) with t,s=1,…,n+l+1 such that (4.7) and the following conditions hold:

    { ∑ t = 1 n + l + 1 ν t { ∇ x F ( x ∗ , z t ) − λ t ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z t ) − ∑ s = 1 n + l + 1 η s ( ∑ k = 1 l y k ∗ ∇ x f k ( x ∗ , z s ) + ∑ i = 1 p β i s ∇ x g i ( x ∗ , z s ) ) ) + ∑ i = 1 p β i t ∇ x g i ( x ∗ , z t ) } + ∑ j = 1 q α j ∇ G j ( x ∗ ) = 0 , ∇ z F ( x ∗ , z t ) − λ t ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z t ) − ∑ i = 1 p β i t ∇ z g i ( x ∗ , z t ) = 0 , ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z s ) + ∑ i = 1 p β i s ∇ z g i ( x ∗ , z s ) = 0 , ∀ j = 1 , … , q : α j ≥ 0 , α j G j ( x ∗ ) = 0 , ∀ t = 1 , … , n + l + 1 , ∀ i = 1 , … , p : β i t ≥ 0 , β i t g i ( x ∗ , z t ) = 0 , ∀ s = 1 , … , n + l + 1 , ∀ i = 1 , … , p : β i s ≥ 0 , β i s g i ( x ∗ , z s ) = 0 , ∀ s = 1 , … , n + l + 1 : η s ≥ 0 , ∑ s = 1 n + l + 1 η s = 1 , ∀ t = 1 , … , n + l + 1 : ν t ≥ 0 , ∑ t = 1 n + l + 1 ν t = 1 .
    (4.26)

    The relationships (4.7) and (4.26) considered together are called the KM-stationarity conditions.

  2. (ii)

    Let Ψ o be inner semicontinuous at ( x ∗ , y ∗ , z ∗ ), ( x ∗ , z ∗ ) be lower-level regular, f and g be strictly differentiable at ( x ∗ , z ∗ ), and let the conditions (4.14) and (4.16) be satisfied at ( x ∗ , y ∗ , z ∗ ) and the set co N gph Ψ ( x ∗ , y ∗ , z ∗ ) be closed. Then there exist λ t ≥0, α, β t , and γ t such that the following conditions hold:

    { ∇ x F ( x ∗ , z ∗ ) − ∑ t = 1 n + l + 1 ν t ∑ i = 1 p ( β i t − λ t γ i t ) ∇ x g i ( x ∗ , z ∗ ) + ∑ j = 1 q α j ∇ G j ( x ∗ ) = 0 , ∇ z F ( x ∗ , z ∗ ) − ∑ t = 1 n + l + 1 ν t ( λ t ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z ∗ ) + ∑ i = 1 p β i t ∇ z g i ( x ∗ , z ∗ ) ) = 0 , ∑ k = 1 l y k ∗ ∇ z f k ( x ∗ , z ∗ ) + ∑ i = 1 p γ i ∇ z g i ( x ∗ , z ∗ ) = 0 , ∀ j = 1 , … , q : α j ≥ 0 , α j G j ( x ∗ ) = 0 , ∀ t = 1 , … , n + l + 1 , ∀ i = 1 , … , p : β i t ≥ 0 , β i t g i ( x ∗ , z ∗ ) = 0 , ∀ t = 1 , … , n + l + 1 , ∀ i = 1 , … , p : γ i t ≥ 0 , γ i t g i ( x ∗ , z ∗ ) = 0 , ∀ t = 1 , … , n + l + 1 : ν t ≥ 0 , ∑ t = 1 n + l + 1 ν t = 1 .
    (4.27)

The relationships (4.27) are called the KN-stationarity conditions.

Proof Under the assumptions of (ii), the bilevel value function φ p p in (3.7) is Lipschitz continuous near x ∗ . Since X is closed, one has from [[13], Proposition 5.3] that

0∈∂ φ p p ( x ∗ ) + N X ( x ∗ ) .
(4.28)

By the inner semicontinuity of Ψ o at ( x ∗ , y ∗ , z ∗ ) and the upper regularity (4.5), we have

N X ( x ∗ ) = { ∑ j = 1 q α j ∇ G j ( x ∗ ) | α j ≥ 0 , α j G j ( x ∗ ) = 0 , j = 1 , … , q } .
(4.29)

Combining with Theorem 4.3(ii) and (4.29), Theorem 4.4(ii) is easily derived. If Ψ o is inner semicompact around ( x ∗ , y ∗ ), the condition (4.7) holds at all point ( x ∗ , y ∗ ,z) with z∈Ψ( x ∗ , y ∗ ), and that (4.14) and (4.16) are satisfied at all point ( x ∗ , y ∗ ,z) with z∈ Ψ o ( x ∗ , y ∗ ). Thus, by Theorem 4.3(i), we obtain the conclusion (i). This completes the proof. □

Remark 4.2 (i) The prefixes ‘KN’ and ‘KM’ in Theorem 4.4 reflect the difference between the KKT-type optimality conditions via the inner semicompactness and inner semicontinuity of the upper-level optimal solution set mapping Ψ o , respectively. For the notions ‘KM-stationary’ and ‘KM-stationarity’, the readers can be referred to [50]. In (4.27), the gradient of F does not involve the convex combinations summation, in this case, analogously to [37], we call (4.27) KKT-type necessary optimality (stationarity) conditions for the problem (3.4).

(ii) Under the inner semicontinuity of the lower-level optimal set-valued mapping Ψ, the necessary optimality conditions (ii) in Theorem 4.4 are in fact those of the problem

{ min x max y max z F ( x , z ) s.t.  x ∈ X , z ∈ Ψ ( x , y ) .
(4.30)

This means that the above framework, the constraints described by Y (3.2) can be dropped and the condition that set X×Y is closed is reduced to that the set X is closed, the latter is immediately reached by Hypothesis 1 in Section 1, while deriving the necessary optimality conditions of the problem (1.6), which is a strange phenomenon just as that said in [6].

By Proposition 3.1(i) and Theorem 4.4, the necessary optimality conditions for the pessimistic semivectorial bilevel programming problem (1.6) are derived when the involved functions are strictly differentiable.

Corollary 4.1 Let ( x ∗ , z ∗ ) be a local optimal solution of the problem (1.6), where F and G j , j=1,…,q are strictly differentiable at ( x ∗ , z ∗ ) and z ∗ , respectively. For all x∈X, f(x,⋅) and g(x,⋅) are R + l - and R + p -convex, respectively. Let x ∗ be upper-level regular. Then the following assertions hold:

  1. (i)

    (KM-stationarity conditions) Let Ψ o be inner semicompact at ( x ∗ , y ∗ ) while for all z∈Ψ( x ∗ , y ∗ ) and the point ( x ∗ ,z) is lower-level regular. Let f and g be strictly differentiable at ( x ∗ ,z), z∈Ψ( x ∗ , y ∗ ), and let the conditions (4.14) and (4.16) be satisfied at all point ( x ∗ , y ∗ ,z) with z∈ Ψ o ( x ∗ , y ∗ ) and the set X×Y be closed. Then there exist λ t ≥0, α, β t , β s , η s and z t , z s ∈Ψ( x ∗ , y ∗ ) with t,s=1,…,n+l+1 such that (4.7) and (4.26) hold.

  2. (ii)

    (KN-stationarity conditions) Let Ψ o be inner semicontinuous at ( x ∗ , y ∗ , z ∗ ) and the point ( x ∗ , z ∗ ) be lower-level regular. Let f and g be strictly differentiable at ( x ∗ , z ∗ ), X×Y be closed, and let the conditions (4.14) and (4.16) be satisfied at ( x ∗ , y ∗ , z ∗ ) and the set co N gph Ψ ( x ∗ , y ∗ , z ∗ ) be closed. Then there exist λ t ≥0, α, β t and γ t such that (4.27) holds.

5 BP with linear multiobjective optimization lower-level problems

In this section, we consider the following pessimistic semivectorial bilevel programming problem (PSBP) with a linear multiobjective optimization lower-level problem:

min x max z F(x,z)s.t. G(x)≤0,z∈ Ψ wef (x),
(5.1)

where the functions F and G defined in Section 1, and Ψ wef (x) is the weak Pareto optimal solutions set of the following problem with respect to the upper decision variable x:

R + l − min z A(x)z+b(x)s.t. C(x)z−d(x)=0,z≥0,
(5.2)

where b: R n → R l and d: R n → R p are strictly differentiable, A: R n → R l × m and C: R n → R p × m are defined by

A(x)= ( a k t ( x ) ) 1 ≤ k ≤ l , 1 ≤ t ≤ m ,
(5.3)
C(x)= ( c i t ( x ) ) 1 ≤ i ≤ p , 1 ≤ t ≤ m ,
(5.4)

where the real value functions a k t (1≤k≤l, 1≤t≤m) and c i t (1≤i≤p, 1≤t≤m) are strictly differentiable.

Considering the bilevel optimal value function approach developed in the previous section, for deriving the necessary optimality conditions for the problem (5.1), we firstly recall the bilevel optimal value function reformulation of the problem (5.1) according to Section 3,

min φ p p ( x ) s.t.  x ∈ X , { φ p p ( x ) = max y { φ p ( x , y ) ∣ y ∈ Y } , φ p ( x , y ) = max z { F ( x , z ) ∣ z ∈ Ψ ( x , y ) } , Ψ ( x , y ) = { z ∈ R m ∣ f ( x , y , z ) − φ ( x , y ) ≤ 0 , C ( x ) z − d ( x ) = 0 } , φ ( x , y ) = min z { f ( x , y , z ) ∣ C ( x ) z − d ( x ) = 0 , z ≥ 0 } .
(5.5)

Here X={x∈ R n ∣G(x)≤0} and Y is given in (3.2), the function f is defined as

f(x,y,z)= 〈 y , A ( x ) z 〉 + 〈 y , b ( x ) 〉 .
(5.6)

The lower-level regularity condition for the problem (5.1) is given as follows:

∃ z Ëœ :C ( x ∗ ) z Ëœ =d ( x ∗ ) , z Ëœ >0,k=1,…,l and C ( x ∗ )  has full row rank.
(5.7)

The following result which is a consequence of Theorem 4.4 is the necessary optimality conditions for the problem (5.1).

Theorem 5.1 (The necessary optimality conditions for the problem (5.1))

Let x ∗ be an upper-level regular local optimal solution to the problem (5.1), F and G be strictly differentiable at ( x ∗ , z ∗ ) and x ∗ , respectively. The following assertions hold:

  1. (i)

    (KM-stationarity conditions) Let Ψ o (where Ψ(x,y) in (4.1) is replaced by Ψ(x,y) in (5.5)) be inner semicompact at ( x ∗ , y ∗ ) while for all z∈Ψ( x ∗ , y ∗ ), ( x ∗ ,z) is lower-level regular in the sense of (5.7), f and g be strictly differentiable at ( x ∗ ,z), z∈Ψ( x ∗ , y ∗ ), and let the conditions (4.14) and (4.16) be satisfied at all point ( x ∗ , y ∗ ,z) with z∈ Ψ o ( x ∗ , y ∗ ) and the set X×Y be closed. Then there exist λ r ≥0, α, β r , β s , η s and z r , z s ∈Ψ( x ∗ , y ∗ ) with r,s=1,…,n+l+1 such that (4.7) (with f(x,z)=A(x)z+b(x)) and the following hold:

    { ∑ r = 1 n + l + 1 ν r { ∇ x F ( x ∗ , z r ) − λ r ( ∑ k = 1 l y k ∗ ∑ t = 1 m z t r ∇ a k t ( x ∗ ) − ∑ s = 1 n + l + 1 η s ( ∑ k = 1 l y k ∗ ∑ t = 1 m z t s ∗ ∇ a k t ( x ∗ ) + ∑ i = 1 p β i s ( ∑ t = 1 m z t s ∇ c i t ( x ∗ ) − ∇ d i ( x ∗ ) ) ) ) + ∑ i = 1 p β i r ( ∑ t = 1 m z t r ∇ c i t ( x ∗ ) − ∇ d i ( x ∗ ) ) } + ∑ j = 1 q α j ∇ G j ( x ∗ ) = 0 , ∀ r = 1 , … , n + l + 1 : ∇ z F ( x ∗ , z r ) − λ r ∑ k = 1 l y k ∗ a k ( x ∗ ) − ∑ i = 1 p β i r c i ( x ∗ ) ≤ 0 , ∀ r = 1 , … , n + l + 1 : z r ⊤ [ ∇ z F ( x ∗ , z r ) − λ r ∑ k = 1 l y k ∗ a k ( x ∗ ) ∀ r = 1 , … , n + l + 1 : − ∑ i = 1 p β i r c i ( x ∗ ) ≤ 0 ] = 0 , ∀ s = 1 , … , n + l + 1 : ∑ k = 1 l y k ∗ a k ( x ∗ ) + ∑ i = 1 p β i s c i ( x ∗ ) ≤ 0 , ∀ r , s = 1 , … , n + l + 1 : z r ⊤ [ ∑ k = 1 l y k ∗ a k ( x ∗ ) + ∑ i = 1 p β i s c i ( x ∗ ) ≤ 0 ] = 0 , ∀ j = 1 , … , q : α j ≥ 0 , α j G j ( x ∗ ) = 0 , ∀ s = 1 , … , n + l + 1 : η s ≥ 0 , ∑ s = 1 n + l + 1 η s = 1 , ∀ r = 1 , … , n + l + 1 : ν r ≥ 0 , ∑ r = 1 n + l + 1 ν r = 1 .
    (5.8)
  2. (ii)

    (KN-stationarity conditions) Let Ψ o (where Ψ(x,y) in (4.1) is replaced by Ψ(x,y) in (5.5)) be inner semicontinuous at ( x ∗ , y ∗ , z ∗ ), ( x ∗ , z ∗ ) be lower-level regular in the sense of (5.7), f and g be strictly differentiable at ( x ∗ , z ∗ ) and the set X×Y be closed and let the conditions (4.14) and (4.16) be satisfied at ( x ∗ , y ∗ , z ∗ ) and the set co N gph Ψ ( x ∗ , y ∗ , z ∗ ) be closed. Then there exist λ r ≥0, α, β r and γ r such that

    { ∇ x F ( x ∗ , z ∗ ) + ∑ j = 1 q α j ∇ G j ( x ∗ ) − ∑ r = 1 n + l + 1 ν r ∑ i = 1 p ( β i r − λ r γ i r ) ( ∑ t = 1 m z t r ∇ c i t ( x ∗ ) − ∇ d i ( x ∗ ) ) = 0 , ∇ z F ( x ∗ , z ∗ ) − ∑ r = 1 n + l + 1 ν r ( λ r ∑ k = 1 l y k ∗ a k ( x ∗ ) + ∑ i = 1 p β i r c i ( x ∗ ) ) ≤ 0 , z ∗ ⊤ [ ∇ z F ( x ∗ , z ∗ ) − ∑ r = 1 n + l + 1 ν r ( λ r ∑ k = 1 l y k ∗ a k ( x ∗ ) + ∑ i = 1 p β i r c i ( x ∗ ) ) ≤ 0 ] = 0 , ∀ r = 1 , … , n + l + 1 : ∑ k = 1 l y k ∗ a k ( x ∗ ) + ∑ i = 1 p γ i r c i ( x ∗ ) ≤ 0 , ∀ r = 1 , … , n + l + 1 : z ∗ ⊤ [ ∑ k = 1 l y k ∗ a k ( x ∗ ) + ∑ i = 1 p γ i r c i ( x ∗ ) ≤ 0 ] = 0 , ∀ j = 1 , … , q : α j ≥ 0 , α j G j ( x ∗ ) = 0 , ∀ r = 1 , … , n + l + 1 : ν r ≥ 0 , ∑ r = 1 n + l + 1 ν r = 1 .
    (5.9)

Proof The proof is similar to that of Theorem 4.4 and so is omitted here. □

Remark 5.1 (i) If the term b(x) of the lower-level objective function in the problem (5.2) is removed, we can obtain the same result for Theorem 5.1(i) and (ii), which is

λ r ∑ k = 1 l y k ∗ ∇ b k ( x ∗ ) − λ r ∑ s = 1 n + l + 1 η s ∑ k = 1 l y k ∗ ∇ b k ( x ∗ ) = λ r ∑ k = 1 l y k ∗ ∇ b k ( x ∗ ) − λ r ∑ k = 1 l y k ∗ ∇ b k ( x ∗ ) ∑ s = 1 n + l + 1 η s = 0 ,

note that ∑ s = 1 n + l + 1 η s =1.

(ii) If F and G are linear functions with respect to their variables, then the calmness condition (4.14) is automatically satisfied in this case by [15]. Then we can obtain the more concise results, which is the particular case of Corollary 4.1. The interested reader can try to give detailed results of the optimality conditions for this case.

6 Conclusions

In this paper, we develop the necessary optimality conditions for the pessimistic formulation of semivectorial bilevel optimization problem. Firstly, we transform our problem into a scalar objective optimization problem with inequality constraints via the scalarization method for the multiobjective optimization problem. Furthermore, we derive a generalized minimax optimization problem by means of the bilevel optimal value function, of which the sensitivity analysis is constructed via the lower-level value function approach. Considering the special case where the lower-level multiobjective optimization problem is linear, we also give it the necessary optimality conditions. In the further work, we intend to develop the necessary optimality conditions in the nonsmooth setting and develop the solving algorithms for the pessimistic formulation of semivectorial bilevel optimization problem, especially the latter, which is challenging. For the problem (1.1), if the leader is not certain of that the follower cooperates or dose not cooperate fully with him, it would be inappropriate for the leader who considers only the optimistic or pessimistic formulation. Hence, when both the leader and the follower are neither fully cooperative nor fully non-cooperative, it is meaningful to consider a partial cooperation model which combines the optimistic formulation and the pessimistic formulation for the problem (1.1).

References

  1. Bonnel H, Morgan J: Semivectorial bilevel optimization problem: penalty approach. J. Optim. Theory Appl. 2006,131(3):365-382. 10.1007/s10957-006-9150-4

    Article  MathSciNet  Google Scholar 

  2. Dempe S Nonconvex Optimization and Its Applications Series 61. In Foundations of Bilevel Programming. Kluwer Academic, Dordrecht; 2002.

    Google Scholar 

  3. Ankhili Z, Mansouri A: An exact penalty on bilevel programs with linear vector optimization lower level. Eur. J. Oper. Res. 2009, 197: 36-41. 10.1016/j.ejor.2008.06.026

    Article  MathSciNet  Google Scholar 

  4. Bonnel H: Optimality conditions for the semivectorial bilevel optimization problem. Pac. J. Optim. 2006,2(3):447-467.

    MathSciNet  Google Scholar 

  5. Calvete HI, Galé C: On linear bilevel problems with multiple objectives at the lower level. Omega 2011, 39: 33-40. 10.1016/j.omega.2010.02.002

    Article  Google Scholar 

  6. Dempe S, Gadhi N, Zemkoho AB: New optimality conditions for the semivectorial bilevel optimization problem. J. Optim. Theory Appl. 2013, 157: 54-74. 10.1007/s10957-012-0161-z

    Article  MathSciNet  Google Scholar 

  7. Eichfelder G: Multiobjective bilevel optimization. Math. Program. 2010, 123: 419-449. 10.1007/s10107-008-0259-0

    Article  MathSciNet  Google Scholar 

  8. Nie P: A note on bilevel optimization problems. Int. J. Appl. Math. Sci. 2005,2(1):31-38.

    MathSciNet  Google Scholar 

  9. Zheng Y, Wan Z: A solution method for semivectorial bilevel programming problem via penalty method. J. Appl. Math. Comput. 2011, 37: 207-219. 10.1007/s12190-010-0430-7

    Article  MathSciNet  Google Scholar 

  10. Bonnel H, Morgan J: Optimality conditions for semivectorial bilevel convex optimal control problem. Springer Proceedings in Mathematics 50. In Computational and Analytical Mathematics: In Honor of Jonathan Borwein on the Occasion of His 60th Birthday Edited by: Bauschke H, Théra M. 2013, 45-78.

    Chapter  Google Scholar 

  11. Chen J, Cho YJ, Kim JK, Li J: Multiobjective optimization problems with modified objective functions and cone constraints and applications. J. Glob. Optim. 2011, 49: 137-147. 10.1007/s10898-010-9539-3

    Article  MathSciNet  Google Scholar 

  12. Chen J, Wan Z, Cho YJ: Nonsmooth multiobjective optimization problems and weak vector quasi-variational inequalities. Comput. Appl. Math. 2013, 32: 291-301. 10.1007/s40314-013-0014-x

    Article  MathSciNet  Google Scholar 

  13. Mordukhovich BS: Variational Analysis and Generalized Differentiation. I: Basic Theory. II: Applications. Springer, Berlin; 2006.

    Google Scholar 

  14. Rockafellar RT, Wets RJ-B: Variational Analysis. Springer, Berlin; 1998.

    Book  Google Scholar 

  15. Robinson SM: Some continuity properties of polyhedral multifunctions. Math. Program. Stud. 1981, 14: 206-214. 10.1007/BFb0120929

    Article  Google Scholar 

  16. Ehrgott M: Multicriteria Optimization. 2nd edition. Springer, Berlin; 2005.

    Google Scholar 

  17. Aboussoror A: Weak bilevel programming problems: existence of solutions. Adv. Math. Res. 2002, 1: 83-92.

    MathSciNet  Google Scholar 

  18. Aboussoror A, Loridan P: Strong-weak Stackelberg problems in finite dimensional spaces. Serdica Math. J. 1995, 21: 151-170.

    MathSciNet  Google Scholar 

  19. Aboussoror A, Loridan P: Existence of solutions to two level optimization problems with nonunique lower-level solutions. J. Math. Anal. Appl. 2001, 254: 348-357. 10.1006/jmaa.2000.7001

    Article  MathSciNet  Google Scholar 

  20. Lignola MB, Morgan J: Stability of regularized bilevel programming problems. J. Optim. Theory Appl. 1997,93(3):575-596. 10.1023/A:1022695113803

    Article  MathSciNet  Google Scholar 

  21. Loridan P, Morgan J: Approximate solutions for two level optimization problems. Int. Ser. Numer. Math. 1988, 84: 181-196.

    MathSciNet  Google Scholar 

  22. Loridan P, Morgan J: ϵ -Regularized two-level optimization problems: approximation and existence results. In:Optimization (Fifth French-German Conference, Castel Novel). Lecture Notes in Mathematics, vol. 1405 Optimization 1989, 99-113.

    Chapter  Google Scholar 

  23. Loridan P, Morgan J: Least-norm regularization for weak two-level optimization problem. International Series of Numerical Mathematics 107. In Optimization, Optimal Control and Partial Differential Equations. Birkhäuser, Basel; 1992:307-318.

    Chapter  Google Scholar 

  24. Loridan P, Morgan J: On strict ϵ -solutions for a two-level optimization problem. 90. In Proceedings of the International Conference on Operations Research. Springer, Berlin; 1992:165-172.

    Google Scholar 

  25. Lucchetti R, Mignanego F, Pieri G: Existence theorems of equilibrium points in Stackelberg games with constraints. Optimization 1987, 18: 857-866. 10.1080/02331938708843300

    Article  MathSciNet  Google Scholar 

  26. Marhfour A: Mixed solutions for weak Stackelberg problems: existence and stability results. J. Optim. Theory Appl. 2000,105(2):417-440. 10.1023/A:1004618103646

    Article  MathSciNet  Google Scholar 

  27. Tian G, Zhou J: Transfer continuities, generalizations of the Weierstrass and maximum theorems: a full characterization. J. Math. Econ. 1995, 24: 281-303. 10.1016/0304-4068(94)00687-6

    Article  MathSciNet  Google Scholar 

  28. Loridan P, Morgan J: Weak via strong Stackelberg problem: new results. J. Glob. Optim. 1996, 8: 263-287. 10.1007/BF00121269

    Article  MathSciNet  Google Scholar 

  29. Aboussoror A, Mansouri A: Weak linear bilevel programming problems: existence of solutions via a penalty method. J. Math. Anal. Appl. 2005, 304: 399-408. 10.1016/j.jmaa.2004.09.033

    Article  MathSciNet  Google Scholar 

  30. Lv Y, Hu T, Wan Z: A penalty function method for solving weak price control problem. Appl. Math. Comput. 2007, 186: 1520-1525. 10.1016/j.amc.2006.07.151

    Article  MathSciNet  Google Scholar 

  31. Tsoukalas A, Wiesemann W, Rustem B: Global optimization of pessimistic bilevel problems. Fields Institute Communications. In Lecture on Global Optimization. Edited by: Pardalos PM, Coleman TF. Am. Math. Soc., Providence; 2009:215-243. Chapter 10

    Google Scholar 

  32. Wiesemann W, Tsoukalas A, Kleniati P, Rustem B: Pessimistic bi-level optimisation. SIAM J. Optim. 2013,23(1):353-380. 10.1137/120864015

    Article  MathSciNet  Google Scholar 

  33. Malyshev AV, Strekalovsky AS: On global search for pessimistic solution in bilevel problems. Biomed. Soft Comput. Human Sci. 2012,18(1):57-61.

    Google Scholar 

  34. Dassanayaka, S: Methods of variational analysis in pessimistic bilevel programming. Dissertation for Doctor of philosophy, Wayne State University, Detroit, Michigan (2010)

  35. Xiao Y, Li H: A genetic algorithm for solving weak nonlinear bilevel programming problems. 1. ICICTA’11 Proceedings of the 2011 Fourth International Conference on Intelligent Computation Technology and Automation, Changsha vol. 1, 2011, 7-9.

    Chapter  Google Scholar 

  36. Zemkoho, AB: Optimization problems with value function objectives. Optimization online (2011). http://www.optimization-online.org/DB_FILE/2011/11/3223.pdf. Accessed 24 Dec 2011

  37. Dempe S, Mordukhovich BS, Zemkoho AB: Necessary optimality conditions in pessimistic bilevel programming. Optimization 2012. 10.1080/02331934.2012.696641

    Google Scholar 

  38. Mordukhovich BS, Nam NM: Variational stability and marginal functions via generalized differentiation. Math. Oper. Res. 2005,30(4):800-816. 10.1287/moor.1050.0147

    Article  MathSciNet  Google Scholar 

  39. Dempe S, Mordukhovich BS, Zemkoho AB: Sensitivity analysis for two-level value functions with applications to bilevel programming. SIAM J. Optim. 2012,22(4):1309-1343. 10.1137/110845197

    Article  MathSciNet  Google Scholar 

  40. Dempe S, Dutta J, Mordukhovich BS: New necessary optimality conditions in optimistic bilevel programming. Optimization 2007, 56: 577-604. 10.1080/02331930701617551

    Article  MathSciNet  Google Scholar 

  41. Clarke FH: Optimization and Nonsmooth Analysis. Wiley, New York; 1983.

    Google Scholar 

  42. Mordukhovich BS, Nam MN, Yen ND: Subgradients of marginal functions in parametric mathematical programming. Math. Program. 2009,116(1-2):369-396. 10.1007/s10107-007-0120-x

    Article  MathSciNet  Google Scholar 

  43. Mordukhovich BS, Nam MN, Phan HM: Variational analysis of marginal functions with applications to bilevel programming. J. Optim. Theory Appl. 2012,152(3):557-586. 10.1007/s10957-011-9940-1

    Article  MathSciNet  Google Scholar 

  44. Dinh N, Mordukhovich BS, Nghia TTA: Subdifferentials of value functions and optimality conditions for DC and bilevel infinite and semi-infinite programs. Math. Program. 2010,123(1):101-138. 10.1007/s10107-009-0323-4

    Article  MathSciNet  Google Scholar 

  45. Dempe S, Zemkoho AB: The generalized Mangasarian-Fromowitz constraint qualification and optimality conditions for bilevel optimization problem. J. Optim. Theory Appl. 2011, 148: 433-441.

    Article  MathSciNet  Google Scholar 

  46. Dempe S, Dinh N, Dutta J: Optimality conditions for a simple convex bilevel porgramming problem. Springer Optimization and Its Applications 47. In Variational Analysis and Generalized Differentiation in Optimization and Control Edited by: Burachik RS, Yao J-C. 2010, 149-161.

    Chapter  Google Scholar 

  47. Henrion R, Surowiec T: On calmness conditions in convex bilevel programming. Appl. Anal. 2011,90(6):951-970. 10.1080/00036811.2010.495339

    Article  MathSciNet  Google Scholar 

  48. Henrion R, Jourani A, Outrata JV: On the calmness of a class of multifunctions. SIAM J. Optim. 2002,13(2):603-618. 10.1137/S1052623401395553

    Article  MathSciNet  Google Scholar 

  49. Zemkoho AB: A simple approach to optimality conditions in minmax programming. Optimization 2012. 10.1080/02331934.2011.653788

    Google Scholar 

  50. Zemkoho, AB: Bilevel programming: reformulations, regularity, and stationarity. PhD thesis, TU Bergakademie Freiberg (2012)

Download references

Acknowledgements

This work was supported by the Natural Science Foundation of China (71171150, 11201039, 11301570), the Youth Foundation of Educational Commission of Anhui Province of China (2009SQRZ121, 2011SQRL097), the Doctor Fund of Southwest University (SWU113037) and the Fundamental Research Fund for the Central Universities (XDJK2014C073). The authors would like to thank two anonymous referees for numerous insightful comments and suggestions, which have greatly improved the paper.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Jiawei Chen.

Additional information

Competing interests

The authors declare that they have no competing interests.

Authors’ contributions

All authors contributed equally to this paper. They read and approved the final manuscript.

Rights and permissions

Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License ( https://creativecommons.org/licenses/by/2.0 ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Reprints and permissions

About this article

Cite this article

Liu, B., Wan, Z., Chen, J. et al. Optimality conditions for pessimistic semivectorial bilevel programming problems. J Inequal Appl 2014, 41 (2014). https://doi.org/10.1186/1029-242X-2014-41

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1186/1029-242X-2014-41

Keywords