Solution Concepts and New Optimality Conditions in Bilevel Multiobjective Programming ()
1. Introduction
The class of bilevel optimization (programming) problems (BOP) arises from the stackelberg games theory [1]; and many problem in such fields as economics, management, politics and behavioral sciences which used to be successfully modeled using Stackelberg games theory, can be modeled as bilevel optimization problem [2]. BOP occurs also in diverse applications, such as transportation, engineering, optimal control etc.
A bilevel optimization problem requires to solve a parametric optimization problem at the lower level (the follower problem) to get feasible solutions for the main optimization problem called upper level or leader problem.
The general formulation of a BOP is given by:
where:
With 
For 
fixed, the problem:
is called the lower level or the follower problem parameterized by x. F and f are respectively the leader (or higher level) and the follower (or lower level) objective functions. G and H (respectively g and h) are leader’s inequality and equality constraints (respectively follower’s inequality and equality constraints) functions.
If 
then, the functions F and f are scalar valued; meaning that the higher and lower level decision makers are optimizing each only one objective. This class of problems is called bilevel single objective optimization problems, or simply bilevel optimization problems. Bilevel optimization is an important research area since about three decades and there exists a huge quantity of studies related to that class of problems (see for example the book [3] and bibliography reviews [4-6]).
If 
and/or
, then leader and/or follower objective functions are vector valued. We obtain a more general problem called bilevel multiobjective optimization problem (BMOP). In this case, the upper level decision maker and/or the lower level one are optimizing more than one (in general conflicting) objective simultaneously. This class of optimization problems has not yet received a broad attention in the literature and there are only few studies in the literature dealing with it (see for example [7-11]). According to Pieume et al. [12], this issue can be explained by at least three reasons: The difficulty of searching and defining optimal solutions; the lower level optimization problem has a number of tradeoff optimal solutions; and it is computationally more complex than the conventional multiobjective programming problem or a bilevel programming problem.
We are interested in this paper in establishing optimality conditions in bilevel multiobjective optimization, in the general case were both the higher and the lower level problems are multiobjectives. Inspired by optimality conditions given by A. A. K. Majumdar in [13] and D. S. Kim et al. [14] for (single level) multiobjective optimization problems (MOP), we established new sufficient optimality conditions for a solution of a general BMOP with coupled upper level constraints. To our knowledge, there are very few studies in the literature dealing with optimality conditions in bilevel multiobjective programming. In [7], using the Kunh Tucker conditions for MOP, A. Dell’Aere stated a necessary condition for solution of a BMOP in the case where lower level inequality constraints are absent. Jane J. Ye presented in [15] for bilevel programs in which only the leader problem is vector valued, necessary optimality conditions in the case where the Karush-Kuhn-Tucker (KKT) condition is necessary and sufficient for global optimality of all lower level problems near the optimal solution, by replacing the lower level problem by its KKT conditions. In the case where the KKT conditions are not necessary and sufficient for global optimality, she derives necessary optimality conditions by considering a combined problem where both the value function and the KKT conditions of the lower level problem are involved in the constraints. More recently, S. Dempe et al. in [16] presented for the optimistic formulation of a bilevel optimization problem with multiobjective lower-level problem, necessary optimality conditions by considering the scalarization approach for the lower level multiobjective program and transforming the problem into a scalar-objective optimization problem with inequality constraints by means of the optimal value reformulation.
The rest of the paper is organized as follows: In the next section, definition of solution concepts and characterization of bilevel multiobjective programming problems are presented. In Section 3, after presenting some preliminary notions, we present sufficient optimality conditions for a solution of BMOP; the paper is concluded in Section 4.
2. Definition and Characterization of Bilevel Multiobjective Programming Problems
Let 
and 
be two vectors of
,
. The following ordering relations (in
) will be used:
We consider the following problem:
where:
With 
and 
since
, the problem is a Bilevel Multiobjective Optimization Problem (BMOP).
For all
, let:
For all
, let:
For all
, let:
● 
● 
is the set of the pareto optimal solutions of the follower’s problem parameterized by
.
● 
is the set of weak pareto optimal solutions of the follower’s problem parameterized by
.
Definition 2.1. 
is said to be a solution of BMOP1 if and only if
, 
and there exists no
, 
such that
.
Definition 2.2. 
is said to be a weak solution of BMOP1 if and only if
, 
and there exists no
, 
such that
.
Let’s consider a BMOP with uncoupled upper level inequality constraints and without equality constraints in both levels:
Then under the strict convexity of the upper and lower level objective and constraints functions, the definition 2.1 of a solution of a Bilevel Multiobjective Optimization problem is equivalent to the following conditions:
Theorem 2.1. Assume that F and G are strictly convex, and that
, 
are strictly convex. Then, 
is a solution of (BMOP2) if and only if there are no directions 
such that:
Proof
Suppose that 
is a solution of (BMOP2). We have to prove that 
satisfying 1) and 2) don’t exist.
To the contrary, suppose that 
exist.
Let
.
Define
; Take
.
Since 
(according to 1).
By definition,
. Using the strict convexity assumption on f, we have:
That is
; this implies that
.
Hence
; which contradicts the fact that 
is a solution of (BMOP2).
Suppose that 
don’t exist. Let’s prove that 
is a solution of (BMOP2).
To the contrary, suppose that 
is not a solution of (BMOP2). Then 
or 
and 
● Suppose that
.
Then, 
Define
.
Since 
is convex, 
is convex.
By the convexity of
, we have
.
Let 
and 
fixed.
Hence there exist 
satisfying 1), which is a contradiction with the hypothesis.
● Suppose that 
and
Let
.
(by the convexity of Z).
Let 
and 
arbitrary fixed.
Hence there exist 
satisfying 2); which contradict the hypothesis.
The main difficulty when solving a BMOP comes from the fact that for each feasible alternative x, the leader must know exactly, in order to take his decision, what will be the reaction of the lower level decision maker. But since the lower level problem is a multiobjective one, for each leader’s alternative x, the follower has many (sometimes infinite) possible responses, which are represented by the entire follower pareto optimal set P (x). To circumvent this difficulty, there are rational reformulations of the problem, which really speaking are relaxations of the BMOP. They are: The optimistic or risky formulation, the pessimistic or conservative formulation, the mean formulation and the stochastic formulation.
Definition 2.3.
1) Optimistic or risky formulation of a BMOP
An optimistic or risking leader always chooses for all feasible alternative x, the follower Pareto optimal solution 
which satisfy his objective (in the sense of minimization).
is said to be an optimistic optimal solution of a BMOP if and only if
2) Pessimistic or conservative formulation of a BMOP
A conservative or pessimistic leader always prefer to choose for all feasible alternatives x, the follower pareto optimal solution 
which is the worse for him (in the sense of minimization).
said to be a pessimistic optimal solution of a BMOP if and only if
3) Mean formulation of a BMOP
Suppose that 
and that for all 
is integrable on
.
A mean leader always chooses the mean solution among the follower pareto optimal solutions
, for each feasible higher level decision x.
is said to be a mean optimal solution of a BMOP if and only if
where since F is a vector valued function, we define its integral over 
by:
4) Stochastic formulation of BMOP
Suppose that for all leaders’ alternative x, there exists a probability distribution with 
as density function such that the leader always has the probability 
to choose y as the follower reaction among his pareto optimal solution set
. Then, one can talk of a stochastic formulation of the BMOP.
is said to be a stochastic optimal solution of the BMOP if and only if
where:
When there exists a unique solution to the lower level problem for any x, the above mentioned solutions are not different. But when there are multiple solutions to the lower level problem, the four kinds of solutions are different.
There exists a relationship between the four types of solutions. In [17], a theorem giving the relationship between the optimistic optimal value, pessimistic optimal value and mean optimal value, in case where only the lower level problem is multi-objective is presented and proved.
The following proposition generalize the above mention theorem (theorem 0.5 in [11]) to the general case where both upper and lower level problems are multiobjective.
Proposition 2.1.
Denote 
as optimistic optimal value, pessimistic optimal value, mean optimal value and stochastic optimal value of BMOP1 respectively. Then, we have: 
and
.
Where “
” is the partial order defined above.
Proof
1) Let x be a feasible alternative of the leader. By definition,
For all
, we have
hence
(1)
Let 
(1)
Then 
Hence
2) By a similar reasoning as in 1), we obtain that 
Hence 
by the transitivity of “
”.
The proof of the second relation is analogous while using the fact that
.
3. Suffcient Optimality Conditions for a Solution of BMOP
3.1. Preliminary Definitions
Definition 3.1. Quasiconvexity, strict quasiconvexity, pseudoconvexity, strict pseudoconvexity ([18])
Let 
and
.
1) f is said to be quasiconvex at 
(with respect to A) if:
if in addition f is differentiable, then we have the following equivalent definition:
f is quasiconvex if for all 
2) f is said to be strictly quasiconvex at 
(with respect to A) if:
3) f is said to be pseudoconvex at 
(with respect to A) if it is differentiable and
or
4) f is said to be strictly pseudoconvex at 
(with respect to A) if it is differentiable and
We have the following implications [18]:
strict convexity 
convexity 
strict pseudoconvexity 
pseudoconvexity 
strict quasiconvexity 
quasiconvexity.
3.2. Sufficient Optimality Conditions
We consider the problem BMOP1.
For 
fixed, let
,
.
Let
;
be respectively the sets of active inequality constraints of the follower and leader at 
respectively.
Theorem 3.1.
Let
.
Suppose the following:
1) 
is pseudoconvex at
; F is pseudoconvex at
.
2) 
and 
are quasiconvex and differentiable at
; 
and H are quasiconvex and differentiable at
.
3) There exists 
and 
such that:
a) 
b) 
Then, 
is a weak solution of BMOP1.
Proof
Let 
verifying 1), 2) and 3).
Suppose that 
is not a weak solution of BMOP1.
Then, 
or 
1) Suppose that
.
Then, 
such that 
i.e. 
such that
By the pseudoconvexity of
, we have:
(1)
Let 
be arbitrary fixed.
Then, it holds from (1) that:
(2)
We have:
By the quasiconvexity and differentiability assumption in assertion 2) of the theorem, we have:
(3)
(4)
Let 
and 
be arbitrary fixed.
Then it holds from (3) and (4) that:
(5)
(6)
From (2), (5) and (6), we have:
with 
arbitrary fixed.
i.e. we have:
with 
arbitrary fixed; which violates the assumption 3) a) of the theorem.
2) Suppose that 
By the same way of reasoning as in the first case, we obtain:
It holds from the linearity of the scalar product that:
With 
arbitrary fixed.
This violates the assumption 3) b) of the theorem.
Conclusion: 
is a weak solution of BMOP1.
A suffcient optimality condition for a solution of BMOP1 is obtained by replacing the pseudoconvexity of the upper and lower level objective function by the strict pseudoconvexity.
Theorem 3.2.
Let
.
Suppose the following:
1) 
is strictly pseudoconvex at
; F is strictly pseudoconvex at
.
2) 
and 
are quasiconvex and differentiable at
; 
and H are quasiconvex and differentiable at
.
3) There exists
and 
such that:
a) 
b) 
Then, 
is a solution of BMOP1.
Proof
Let 
verifying 1), 2) and 3).
Suppose that 
is not a solution of BMOP1.
Then
or 
1) Suppose that
; then 
such that
. By the strict pseudoconvexity of 
we have:
by a reasoning similar to that used in the proof of theorem 3.1. we obtain:
; which contradicts the assumption 3) a) of the theorem.
2) Suppose that 
By the strict pseudo convexity of F, we have:
Using a similar reasoning to that used in theorem 3.1, we obtain:
;
which violates the assumption
3) b) of the theorem.
Conclusion: 
is a solution of BMOP1.
As corollaries of theorem 3.1 and theorem 3.2, we obtain the following sufficient optimality theorems:
Corollary 3.1.
Let
.
Suppose the following:
1) 
and 
are convex and differentiable at
.
2) F, G and H are convex and differentiable at
.
3) There exists 
and 
such that:
c) 
d) 
Then, 
is a weak solution of BMOP1.
Corollary 3.2.
Let
.
Suppose the following:
1) 
and 
are strictly convex and differentiable at
.
2) F, G and H are strictly convex and differentiable at
.
3) There exists
and 
such that:
a) 
b) 
Then, 
is a weak solution of BMOP1.
The corollaries 3.1 and 3.2 can be proved in two ways; either analogously to the proofs of theorem 3.1 and 3.2 or using the fact that: Strict convexity 
convexity 
strict pseudoconvexity 
pseudoconvexity 
strict quasiconvexity 
quasiconvexity.
4. Conclusion
In this paper, we have established new sufficient optimality theorems for a solution of a differentiable bilevel multiobjective programming problem. We have also presented a result giving a relationship between the optimistic optimal value, the pessimistic optimal value and the mean optimal value (respectively the stochastic optimal value) of a BMOP. The latter result shows that the mean formulation and the stochastic formulation can be very useful in practice to compute good approximations of the solution set of a BMOP in which the follower is not supposed to always report worst cases (in the leader’s point of view)1 nor to react in a way which will lead to the leader’s goal attainment2. Therefore, investigating these two formulations of a BMOP might be interesting for future research.
NOTES
2This is the case where the optimistic formulation is the most suitable.