Necessary Optimality Conditions and a New Approach to Multiobjective Bilevel Optimization Problems

Abstract

Multiobjective optimization problems typically have conflicting objectives, and a gain in one objective very often is an expense in another. Using the concept of Pareto optimality, we investigate a multiobjective bilevel optimization problem (say, P). Our approach consists of proving that P is locally equivalent to a single level optimization problem, where the nonsmooth Mangasarian–Fromovitz constraint qualification may hold at any feasible solution. With the help of a special scalarization function introduced in optimization by Hiriart–Urruty, we convert our single level optimization problem into another problem and give necessary optimality conditions for the initial multiobjective bilevel optimization problem P.

1 Introduction

Bilevel optimization is an important research area, and many researchers have made contributions [1–15]. It is a sequence of two optimization problems in which the feasible region of the upper-level problem is determined implicitly by the solution set of the lower-level problem. The origin of the bilevel optimization problem can be traced back to von Stackelberg [10], who used it to model the market economy in 1934.

Bard [2] studied the linear bilevel optimization problem and developed first-order necessary optimality conditions. Under semi-Lipschitz property, Zhang [14] extended the classic approach to study nonsmooth problem data and derived existence and optimality conditions for the problems in terms of the graph of the solution multifunction to the lower level problem. Dempe [4] and Outrata [8] derived necessary conditions for the case, where the solution set of the lower level problem is a singleton. Using the optimal value function in the lower-level problem, Ye and Zhu [12, 13] reformulated the bilevel problem as a single level nonconvex optimization problem, where the nonsmooth Mangasarian–Fromovitz constraint qualification does not hold at any feasible solution; under the partial calmness condition, they derived optimality conditions for the general bilevel optimization problems, without convexity assumption on the lower level problem and without the assumption that the solution set of the lower level problem be a singleton. Later, Bao, Gupta and Mordukhovich [17], and Zhang, Truong and Zhang [15] used the variational approach and got necessary conditions directly by using advanced tools of variational analysis such as the extremal principle and the separation theorems for convex sets. For more details on bilevel optimization, see Bard [3], Dempe [5, 6], Vicente and Calamai [11], and Shimizu et al. [9].

Multiobjective optimization problems typically have conflicting objectives, and a gain in one objective very often is an expense in another. We investigate a multiobjective bilevel optimization problem using the optimistic approach. This means we assume that the leader presupposes cooperation of the follower in the sense that the latter will choose in each time that solution in the solution set of his/her parametric optimization problem which is best suited with respect to the leader’s objective function. Using the concept of Pareto optimality, together with a special scalarization function introduced in optimization by Hiriart–Urruty [20, 21], we give necessary optimality conditions. Several intermediate optimization problems are introduced to help us in our investigation.

The outline of the paper is as follows: preliminary results are described in Sect. 2; necessary optimality conditions are established in Sect. 3; conclusions are given in Sect. 4.

2 Preliminaries

Let C⊂ℝⁿ be a pointed (C∩−C={0}), closed, and convex cone with nonempty interior introducing a partial order in ℝⁿ, and let A be a nonempty subset of ℝⁿ. $\overline{z}\in A$ is said to be a Pareto (respectively, a weak Pareto) minimal vector of A with respect to C iff

$$A\subset \overline{z}+ \bigl( \mathbb{R}^{n}\backslash -C \bigr) \cup \{ 0 \}$$

(respectively, $A\subset \overline{z}+\mathbb{R}^{n}\backslash -\mathrm{int}\, C$), where int denotes the topological interior. For a subset S of ℝⁿ, we consider the function

$$\varDelta _{S} ( y ) :=\left \{\begin{array}{l@{\quad}l}d ( y,S ) ,& \text{if }y\in \mathbb{R}^{n}\backslash S,\\[3pt]-d \bigl( y,\mathbb{R}^{n}\backslash S \bigr) ,& \text{if }y\in S,\end{array}\right .$$

where d(y,S):=inf{∥u−y∥:u∈S}. This function is introduced in Hiriart–Urruty [20, 21], and used by Ciligot–Travain [19], and Amahroq and Taa [16].

Let us recall the following result of [20].

Proposition 2.1

[20]

Let S⊂ℝⁿ be a closed and convex cone with nonempty interior and S≠ℝⁿ. The function Δ _S is convex, positively homogeneous, 1-Lipschitzian, decreasing on ℝⁿ with respect to the order introduced by S.

Of course, (ℝⁿ\S)={y∈ℝⁿ:Δ _S (y)>0}, int S={y∈ℝⁿ:Δ _S (y)<0} and the boundary of S is the set bd S={y∈ℝⁿ:Δ _S (y)=0}.

As a direct consequence of Proposition 2.1, one has the following result.

Proposition 2.2

[19]

Let S⊂ℝⁿ be a nonempty, closed, and convex cone with nonempty interior. Then for all y∈ℝⁿ,

$$0\notin \partial_{ca}\varDelta _{S} ( y ).$$

Here, the set ∂ _ca f(x) designs the subdifferential of convex analysis of f at x.

For all the rest, for a locally Lipschitz mapping f:ℝⁿ→ℝ, the set ∂f(x) denotes the Clarke generalized Jacobian of f at x; i.e.,

$$\partial f ( x ) := \biggl\{ x^{\ast }\in \mathbb{R}^{n}:\limsup\limits _{{u\rightarrow x} \atop {t\searrow 0}}\dfrac{f ( u+tv ) -f ( u ) }{t}\geq \bigl\langle x^{\ast },v \bigr\rangle,\ \forall v\in \mathbb{R}^{n} \biggr \} .$$

Recall the following interesting results, which are due to Clarke [18]. For more details, we refer the interested reader to [18].

Proposition 2.3

[18]

Suppose that {f _i } _{i∈{1,…,n}} be a finite collection of functions each of which is Lipschitz near $\overline{x}$. The function h defined by

$$h ( x ) =\max \bigl\{ f_{i} ( x ): i=1,2,\ldots,n \bigr\}$$

is easily seen to be Lipschitz near $\overline{x}$ as well. Moreover,

$$\partial h ( \overline{x} ) \subset \mathrm{conv} \bigl\{ \partial {f_{i}} (\overline{x} ) :i\in I ( \overline{x} ) \bigr\},$$

where $I ( \overline{x} ) :=\{i:f_{i} (\overline{x} ) =h ( \overline{x} )\}$ and conv denotes the convex hull.

Proposition 2.4

[18]

Suppose that T be separable, and {f _t } _t∈T be a collection of locally Lipschitz functions f _t at $\overline{x}$. Set

$$h(x):=\sup_{t\in T} \bigl\{ f_{t} ( x ) \bigr\}\quad \text{\textit{and}}\quad J(\overline{x}):=\bigl\{t\in T:f_{t}(\overline{x})=h(\overline{x})\bigr\}.$$

Then h is Lipschitz near $\overline{x}$ and

$$\partial h ( \overline{x} ) \subset \mathrm{conv} \bigl\{ \partial {f_{t}} (\overline{x} ) :t\in J ( \overline{x} ) \bigr\}.$$

3 Necessary Optimality Conditions

Consider the following multiobjective bilevel optimization problem:

$$(\mathrm{P})\quad \left \{\begin{array}{l}\mathbb{R}_{+}^{n}-\mathop{\mathrm{Minimize}}\limits_{x,y}F ( x,y ):= \bigl( F_{1} ( x,y ) ,\ldots,F_{n} ( x,y ) \bigr)\\[3pt]\begin{array}{l@{\quad}l}\text{subject to}& G_{j}(x,y)\leq0,\quad\forall j\in J, \\[3pt]& y\in S ( x ),\end{array}\end{array}\right .$$

where, for each $x\in \mathbb{R}^{n_{1}}$, S(x) is the solution set of the following parametric optimization problem (the lower level problem)

$$( \mathrm{P}_{x} )\quad \left \{\begin{array}{l}\mathop{\mathrm{Minimize}}\limits_{y} f ( x,y ) \\[3pt]\text{subject to}\quad g_{s}(x,y)\leq 0,\quad\forall s\in S,\end{array}\right .$$

where $f:\mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}\longrightarrow \mathbb{R}$, $g_{s}:\mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}\longrightarrow \mathbb{R}$, s∈S:={1,…,q}, $G_{j}:\mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}\rightarrow \mathbb{R}$, j∈J:={1,…,p}, and $F_{i}:\mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}\rightarrow \mathbb{R}$, i∈I:={1,…,n}, are given locally Lipschitz functions; n ₁≥1 and n ₂≥1 are integers.

A pair $(\overline{x},\overline{y})$ is said to be a local efficient (respectively, weak local efficient) solution of (P) iff there exists a neighborhood V of $(\overline{x}, \overline{y})$ such that $F( \overline{x},\overline{y})$ is a local Pareto (respectively, weak local Pareto) minimal vector of $F( \overline{S}\cap V)$ where

$$\overline{S}:= \bigl\{ ( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: G_{j}(x,y)\leq 0,\ \forall j\in J,\ \text{and}\ y\in S ( x ) \bigr\} .$$

In order to derive optimality conditions, we consider a new single level problem which is locally equivalent to the bilevel multiobjective problem (P) at the optimal solution.

Denote by

$$Y ( x ) := \bigl\{ y\in \mathbb{R}^{n_{2}}:g_{s} ( x,y )\leq 0\ \forall s\in S \bigr\}$$

the feasible region of the lower level problem (P _x ).

Let $(\overline{x},\overline{y})$ be a local weak efficient solution of (P). Then there exist neighborhoods U ₀ of $\overline{x}$ and V ₀ of $\overline{y}$ such that

$$F(x,y)-F ( \overline{x},\overline{y} ) \notin -\mathrm{int}\, \mathbb{R}_{+}^{n}\quad\forall (x,y)\in ( U_{0}\times V_{0} ) \cap \overline{S}.$$

Throughout this paper, we assume that the set-valued map Y is uniformly bounded around $\overline{x}$; there exists a bounded neighborhood $U(\overline{x},\overline{y})$ of $( \overline{x},\overline{y})$ such that ⋃ _x∈U Y(x) is bounded. Here,

$$U:= \bigl\{ x\in \mathbb{R}^{n_{1}}:\exists y\in \mathbb{R}^{n_{2}}\text{ such that } ( x,y ) \in U ( \overline{x},\overline{y} ) \bigr\} .$$

Taking $U_{\overline{x}}:=U_{0}\cap U$, the set ${\bigcup}_{x\in U_{\overline{x}}}Y ( x )$ is also bounded. Thus, $\mathrm{cl}{\bigcup }_{x\in U_{\overline{x}}}Y ( x )$ is compact. Then

$$\varTheta := \Bigl( \mathrm{cl}\bigcup_{x\in U_{\overline{x}}}Y ( x )\Bigr) +\overline{B}_{R^{n_{2}}}$$

is a nonempty compact set that contains an open neighborhood of $\mathrm{cl}\bigcup_{x\in U_{\overline{x}}}Y(x)$. Here, cl and $\overline{B}_{R^{n_{2}}}$ denote respectively the closure and the closed unit ball of $R^{n_{2}}$. The following lemmas are crucial for our investigations; we prove that a local weak efficient solution of (P) is also a local weak efficient solution of

$$\bigl( \mathrm{P}^{\ast } \bigr)\quad \left \{\begin{array}{l}\mathbb{R}_{+}^{n}-\mathop{\mathrm{Minimize}}\limits_{x,y}F ( x,y ) = \bigl(F_{1} ( x,y ) ,\ldots,F_{n} ( x,y )\bigr)\\[3pt]\begin{array}{l@{\quad}l}\text{subject to} & G_{j}(x,y)\leq0,\quad\forall j\in J= \{ 1,\ldots,p \} , \\[3pt]& g_{s}(x,y)\leq 0,\quad\forall s\in S= \{ 1,\ldots,q \},\\[3pt]& \varPsi ( x,y ) \leq 0,\end{array}\end{array}\right .$$

where

$$\varPsi ( x,y ) := \max_{z\in \varTheta }\psi ( x,y,z ) , $$

(1)

and

$$\psi ( x,y,z ) :=\min \bigl\{ f ( x,y ) -f ( x,z ) ,-\varDelta _{ ( -R_{+}^{q} ) }\bigl( g_{1}(x,z),\ldots,g_{q}(x,z) \bigr) \bigr\} . $$

(2)

Taking $x\in \mathbb{R}^{n_{1}}$, we consider the optimal value function of the lower level problem (P _x ) defined by

$$V ( x ) := \inf_y \bigl\{ f ( x,y ) :g_{s}(x,y)\leq 0\quad \forall s\in S \bigr\} .$$

Lemma 3.1

$$\left \{\begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]f ( x,y ) -V ( x ) <0.\end{array} \right \}=\left \{\begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]\varPsi ( x,y ) <0.\end{array}\right \} =\emptyset .$$

Proof

Let $x\in U_{\overline{x}}$ and y∈Y(x). Since Θ is compact,

Since $x\in U_{\overline{x}}$, one has Y(x)⊆Θ and

$$Y ( x ) =Y ( x ) \cap \varTheta .$$

Consequently,

$$\left \{ \begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]f ( x,y ) -V ( x ) <0.\end{array} \right \} =\left \{ \begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]\varPsi ( x,y ) <0.\end{array} \right \} .$$

By definition of the optimal value function V(x), one has

$$V ( x ) \leq f ( x,y )\quad \forall y\in Y ( x ) .$$

Then

$$\left \{( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: x\in U_{\overline{x}},y\in Y ( x ) , f ( x,y ) -V ( x ) <0\right \} =\emptyset .$$

 □

Lemma 3.2

$$\left \{ \begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]f ( x,y ) -V ( x ) =0.\end{array} \right \} =\left \{ \begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]\varPsi ( x,y ) =0.\end{array} \right \} .$$

Proof

• Let us prove that

  $$\left \{ \begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]f ( x,y ) -V ( x ) =0.\end{array} \right \} \subseteq \left \{ \begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]\varPsi ( x,y ) =0.\end{array} \right \} .$$

Let $x\in U_{\overline{x}}$ and y∈Y(x) be such that

$$f ( x,y ) -V ( x ) =0.$$

Consequently, y is a global minimizer of (P _x ) for fixed x. Since

$$\left \{( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: x\in U_{\overline{x}},y\in Y ( x ) , \varPsi ( x,y ) <0\right \} =\emptyset ,$$

one deduces that

$$\varPsi ( x,y ) \geq 0.$$

Suppose that Ψ(x,y)>0. Then there exists z∈Θ such that

$$\psi ( x,y,z ) >0.$$

That is,

$$f ( x,y ) -f ( x,z ) >0\quad\text{and}\quad-\varDelta _{ (-R_{+}^{q} ) } \bigl(g_{1}(x,z),\ldots,g_{q}(x,z) \bigr) >0.$$

Thus,

$$f ( x,y ) -f ( x,z ) >0\quad\text{and}\quad g_{s}(x,z)\leq 0\ \forall s\in S.$$

Then z∈Y(x) such that

$$f ( x,y ) >f ( x,z ) .$$

A contradiction, since y is a global minimizer of (P _x ) for fixed x. One concludes that

$$\varPsi ( x,y ) =0.$$

• Let us prove that

  $$\left \{\begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]f ( x,y ) -V ( x ) =0.\end{array}\right \}\supseteq \left \{\begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]\varPsi ( x,y ) =0.\end{array} \right \} .$$

Let $x\in U_{\overline{x}}$ and y∈Y(x) be such that

$$\varPsi ( x,y ) =0.$$

Then

$$\psi ( x,y,z ) \leq 0\quad\forall z\in \varTheta .$$

Since Y(x)⊆Θ, one gets also

$$\psi ( x,y,z ) \leq 0\quad\forall z\in Y ( x ) .$$

That is, for every z∈Y(x), one has

$$\min \bigl\{ f ( x,y ) -f ( x,z ) ,-\varDelta _{ (-R_{+}^{q} ) } \bigl(g_{1}(x,z),\ldots,g_{q}(x,z) \bigr) \bigr\} \leq 0.$$

Since

$$z\in Y ( x )\quad \Longleftrightarrow\quad g_{s}(x,z)\leq 0\quad \forall s\in S$$

one has

$$\varDelta _{ ( -R_{+}^{q} ) } \bigl( g_{1}(x,z),\ldots,g_{q}(x,z) \bigr) \leq 0.$$

Consequently,

$$f ( x,y ) -f ( x,z ) \leq 0\quad\forall z\in Y ( x ) .$$

Thus,

$$f ( x,y ) -V ( x ) \leq 0.$$

Since

$$\left \{ \begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]f ( x,y ) -V ( x ) <0.\end{array} \right \} =\left \{\begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]x\in U_{\overline{x}},y\in Y ( x ) , \\[3pt]\varPsi ( x,y ) <0.\end{array} \right \} ,$$

one deduces that f(x,y)−V(x)=0. □

Lemma 3.3

If $(\overline{x},\overline{y})$ is a local weak efficient solution of (P), then the solution set of the problem $\max_{z\in \varTheta }\psi (\overline{x},\overline{y},z)$ is given by $S(\overline{x})$.

Proof

Since $(\overline{x},\overline{y})$ is a local weak efficient solution of (P), one has

$$\overline{y}\in S ( \overline{x} ).$$

For any $\overline{z}\in S(\overline{x} )$, one gets

$$f ( \overline{x},\overline{y} ) -f ( \overline{x},\overline{z}) =0$$

and

$$\varDelta _{ ( -R_{+}^{q} ) } \bigl( g_{1} ( \overline{x},\overline{z} ) ,\ldots,g_{q} ( \overline{x},\overline{z} ) \bigr) \leq 0.$$

Consequently,

$$\psi ( \overline{x},\overline{y},\overline{z} ) =0.$$

To get the result, since $S( \overline{x})\subset \varTheta$, it suffices to prove that

$$\psi ( \overline{x},\overline{y},z ) \leq 0\quad\forall z\in \varTheta .$$

By contrary, suppose that there exists z∈Θ such that

$$\psi ( \overline{x},\overline{y},z ) >0.$$

Then

$$f ( \overline{x},\overline{y} ) -f ( \overline{x},z ) >0\quad\text{and}\quad-\varDelta _{ ( -R_{+}^{q} ) } \bigl( g_{1} ( \overline{x},z ) ,\ldots,g_{q} ( \overline{x},z ) \bigr) >0.$$

Thus,

$$f ( \overline{x},\overline{y} ) >f ( \overline{x},z ) \quad\text{and}\quad g_{s} ( \overline{x},z ) \leq 0\quad\forall s\in S.$$

A contradiction with $\overline{y}\in S ( \overline{x})$ □

Remark 3.1

Under the following hypotheses (H₁), (H₂), (H₃), (H₄) and (H₅), the optimization problem (P) has at least one optimal solution.

(H₁)::

F _i (.,.) is lower semicontinuous (l.s.c.) on $\mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}$ for all i∈I;

(H₂)::

G _j (.,.) is lower semicontinuous (l.s.c.) on $\mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}$ for all j∈J;

(H₃)::

g _s (.,.) is lower semicontinuous (l.s.c.) on $\mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}$ for all s∈S;

(H₄)::

Ψ(.,.) is lower semicontinuous (l.s.c.) on $\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}$;

(H₅)::

The problem (P^∗) has at least one feasible solution and its feasible set is bounded.

Especially, under these conditions, $\overline{S}$ is a nonempty compact set and F _i (.,.) is lower semicontinuous on $\mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}$ for all i∈I.

Remark 3.2

The function Ψ(.,.) is locally Lipschitz near $(\overline{x},\overline{y})$.

Let

$$E:=\left \{ \begin{array}{l}( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}: \\[3pt]G_{j}(x,y)\leq 0,\forall j\in J= \{1,\ldots,p \} , \\[3pt]g_{s}(x,y)\leq 0\ \forall s\in S= \{1,\ldots,q \} , \\[3pt]\varPsi ( x,y ) \leq 0.\end{array} \right \} .$$

Let m ₀:=p+q+1,m:=n+m ₀,Π ₀:={1,…,m ₀} and Π:={1,…,m}. We denote by G, g, π, and $\overleftrightarrow{\psi}$ the mappings defined as follows:

and

$$\overleftrightarrow{\psi } ( x,y ) := \bigl( F ( x,y ) ,G ( x,y ) ,g ( x,y ),\varPsi ( x,y ) \bigr) .$$

Here,

and

$$\overleftrightarrow{\psi }_{i} ( x,y ) :=\left \{\begin{array}{l@{\quad}l}F_{i} ( x,y ) & \forall i\in \{ 1,\ldots,n \} , \\[3pt]G_{i-n} ( x,y ) & \forall i\in \{n+1,\ldots,n+p \} \\ [3pt]g_{i-n-p} ( x,y ) & \forall i\in \{n+p+1,\ldots,n+p+q \} .\end{array}\right .$$

For $t^{\ast }= ( \mu^{\ast },\upsilon^{\ast },\gamma^{\ast } )\in \mathbb{R}_{+}^{p}\times \mathbb{R}_{+}^{q}\times \mathbb{R}_{+}$, we consider the set

$$C_{t^{\ast }}:= \Biggl\{ u:=(x,y)\in E\text{ such that }0=\sum_{i=1}^{m_{0}}t_{i}^{\ast }\pi_{i}(x,y) \Biggr\} .$$

Let $\overline{u}:=(\overline{x},\overline{y})\in E$. In the following theorem, we will need

and

$$T^{\mathit{Lin}} ( \overline{u} ) := \Biggl\{ d\in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}:\forall t^{\ast }\in \varDelta ( \overline{u} )\ \forall p_{i}^{\ast }\in \partial \pi_{i}(\overline{u})\text{ we have }\Biggl\langle\sum_{i=1}^{m_{0}}t_{i}^{\ast }p_{i}^{\ast },d\Biggr\rangle \leq 0 \Biggr\}$$

Definition 3.1

We say that the nonsmooth Abadie constraint qualification holds at $( \overline{x},\overline{y})\in E$ iff

$$T^{\mathit{Lin}} ( \overline{u} ) \subseteq K ( E,\overline{u} ).$$

Here, $K ( E,\overline{u})$ denotes the contingent cone to E at $\overline{u}$.

Remark 3.3

In general,

$$K ( E,\overline{u} ) \subseteq T^{\mathit{Lin}} ( \overline{u} ).$$

The following theorem gives necessary optimality conditions.

Theorem 3.1

Let $\overline{u}= ( \overline{x},\overline{y} ) \in E$ be a local weak efficient solution of (P). Suppose that the nonsmooth Abadie constraint qualification holds at $\overline{u}$. Then there exist $y^{\ast }\in ( -\mathbb{R}_{+}^{n} )^{\circ }\setminus \{ 0 \}$ such that

$$0\in \partial \bigl( y^{\ast }\circ F \bigr) ( \overline{u} ) +\mathrm{cl}\;\mathrm{cone}\Biggl\{\bigcup_{i=1}^{m_{0}}t_{i}^{\ast }\partial \pi_{i}(\overline{u})\text{ \textit{such that} }t^{\ast }= \bigl( t_{1}^{\ast },\ldots,t_{m_{0}}^{\ast } \bigr) \in \varDelta ( \overline{u})\Biggr\} .$$

Proof

Since $\overline{u}= ( \overline{x},\overline{y} )\in E$ is a local weak efficient solution of (P), it is also a local weak efficient solution of (P^∗) with respect to $\mathbb{R}_{+}^{n}$. Setting

$$\overleftrightarrow{F} ( u ) :=F ( u ) -F ( \overline{u} ) ,$$

one deduces that $\overline{u}$ minimizes $\varDelta _{-\mathrm{int}\,\mathbb{R}_{+}^{n}}\circ \overleftrightarrow{F}$ over the feasible set E. Since $\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{n}}\circ \overleftrightarrow{F}$ is a locally Lipschitz function, denote by k ₀>0 the Lipschitz constant of $\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{n}}\circ \overleftrightarrow{F}$. Then

$$\exists u^{\ast }\in \partial ( \varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{n}}\circ \overleftrightarrow{F} ) ( \overline{u}) ,\quad\forall d\in K ( E,\overline{u} )\quad \text{such that}\quad \bigl\langle u^{\ast },d \bigr \rangle \geq 0.$$

Since the nonsmooth Abadie constraint qualification holds at $\overline{u}$,

$$\exists u^{\ast }\in \partial ( \varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{n}}\circ \overleftrightarrow{F} ) ( \overline{u}) ,\quad\forall d\in T^{\mathit{Lin}} ( \overline{u} )\quad \text{such that}\quad \bigl\langle u^{\ast },d \bigr\rangle \geq 0.$$

Thus,

$$\bigl\langle u^{\ast },d \bigr\rangle \geq 0\quad\text{whenever}\ \max_{a^{\ast }\in C ( \overline{u} ) } \bigl\langle a^{\ast },d \bigr\rangle \leq 0,$$

where

$$C ( \overline{u} ) := \Bigl\{ a^{\ast }=\theta \sum t^{\ast }p^{\ast }\text{ such that }\theta \in \mathbb{R},t^{\ast }\in \varDelta ( \overline{u} ) \text{ and }p^{\ast }\in \partial \pi (\overline{u}) \Bigr\}$$

denotes the convex cone generated by $\varDelta (\overline{u} ) \times \partial \pi (\overline{u})$.

Thus, there exists $u^{\ast }\in \partial(\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{n}}\circ \overleftrightarrow{F} ) ( \overline{u} )$ such that the function $d\mapsto \langle u^{\ast },d \rangle +\delta_{C^{0}(\overline{u})}(d)$ attains its minimum at 0, where $C^{0} ( \overline{u})$ is the polar cone of $C(\overline{u})$ and $\delta_{C^{0}(\overline{u})}$ is the indicator function of $C^{0} ( \overline{u})$.

Applying the chain rule [18], there exist $v^{\ast }\in \partial_{ca}\varDelta _{-\mathrm{int}\,\mathbb{R}_{+}^{n}} ( 0 )$ such that

$$0\in \partial \bigl( v^{\ast }\circ F \bigr) ( \overline{u} ) +\mathrm{cl}\;\mathrm{cone}\Biggl\{\bigcup_{i=1}^{m_{0}}t_{i}^{\ast }\partial \pi_{i}(\overline{u})\text{ such that }t^{\ast }= \bigl( t_{1}^{\ast },\ldots,t_{m_{0}}^{\ast } \bigr) \in \varDelta ( \overline{u})\Biggr\} .$$

Since $\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{n}}(.)$ is a convex function and $\varDelta _{-\mathrm{int}\,\mathbb{R}_{+}^{n}}(0)=0$ we have for all v∈ℝⁿ

$$\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{n}} ( v ) \geq \bigl\langle v^{\ast },v \bigr\rangle $$

and hence for all $v\in - ( \mathbb{R}_{+}^{n} )$

$$\bigl\langle v^{\ast },v \bigr\rangle \leq \varDelta _{-\mathrm{int}\,\mathbb{R}_{+}^{n}} ( v ) =-d\bigl( v,\mathbb{R}^{n}\backslash -\mathrm{int}\,\mathbb{R}_{+}^{n} \bigr) \leq 0.$$

That is $v^{\ast }\in (-(\mathbb{R}_{+}^{n}))^{\circ }$. We conclude from Proposition 2.2 that v ^∗≠0. □

In the following lemma, we prove that any local weak efficient solution of (P^∗) is also a local weak efficient solution of the unconstrained optimization problem

$$\bigl( \mathrm{P}_{1}^{\ast } \bigr)\quad \left \{ \begin{array}{l}\text{Minimize }\overleftrightarrow{\psi } ( x,y ) \\[3pt]\text{subject to}\quad ( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}\mathbb{.}\end{array} \right .$$

Lemma 3.4

Let $(\overline{x},\overline{y})\in E$ be a local weak efficient solution of (P^∗). Then $(\overline{x},\overline{y})$ is a local weak efficient solution of $( \mathrm{P}_{1}^{\ast})$ with respect to $\mathbb{R}_{+}^{m}$.

Proof

Suppose the contrary. One can find sequences $( x_{n},y_{n} )\rightarrow ( \overline{x},\overline{y})$ such that

$$\overleftrightarrow{\psi } ( \overline{x},\overline{y} ) -\overleftrightarrow{\psi } ( x_{n},y_{n} ) \in \mathrm{int}\,\mathbb{R}_{+}^{m}.$$

Thus,

$$\left \{ \begin{array}{l}F ( \overline{x},\overline{y} ) -F ( x_{n},y_{n} ) \in \mathrm{int}\, \mathbb{R}_{+}^{n}, \\[3pt]G ( \overline{x},\overline{y} ) -G ( x_{n},y_{n} ) \in \mathrm{int}\, \mathbb{R}_{+}^{p}, \\[3pt]g ( \overline{x},\overline{y} ) -g ( x_{n},y_{n} ) \in \mathrm{int}\, \mathbb{R}_{+}^{q}, \\[3pt]\varPsi ( \overline{x},\overline{y} ) -\varPsi (x_{n},y_{n} ) \in \mathrm{int}\, \mathbb{R}_{+}.\end{array} \right .$$

Since $(\overline{x},\overline{y})\in E$, one has

$$G ( \overline{x},\overline{y} ) \in {-}\mathbb{R}_{+}^{p},\qquad g ( \overline{x},\overline{y} ) \in -\mathbb{R}_{+}^{q}\quad \text{and}\quad \varPsi ( \overline{x},\overline{y} ) \leq 0.$$

Consequently,

$$\left \{ \begin{array}{l}G ( x_{n},y_{n} ) \in G ( \overline{x},\overline{y} ) -\mathrm{int}\, \mathbb{R}_{+}^{p}\subseteq ({-}\mathbb{R}_{+}^{p} )+ ( -\mathrm{int}\, \mathbb{R}_{+}^{p} ) \subseteq ( {-}\mathbb{R}_{+}^{p} ) , \\[3pt]g ( x_{n},y_{n} ) \in g ( \overline{x},\overline{y} ) -\mathrm{int}\, \mathbb{R}_{+}^{q}\subseteq ({-}\mathbb{R}_{+}^{q} )+ ( -\mathrm{int}\, \mathbb{R}_{+}^{q} ) \subseteq ( {-}\mathbb{R}_{+}^{q} ) , \\[3pt]\varPsi ( x_{n},y_{n} ) \in \varPsi ( \overline{x},\overline{y}) -\mathrm{int}\, \mathbb{R}_{+}\subseteq ({-}\mathbb{R}_{+} )+ ( - \mathrm{int}\, \mathbb{R}_{+} ) \subseteq ( {-}\mathbb{R}_{+} ) .\end{array} \right .$$

Then

$$\left \{ \begin{array}{l}F ( \overline{x},\overline{y} ) -F ( x_{n},y_{n} ) \in \mathrm{int}\, \mathbb{R}_{+}^{n} \\[3pt]G ( x_{n},y_{n} ) \in ( {-}\mathbb{R}_{+}^{p} ),g ( x_{n},y_{n} ) \in ( {-}\mathbb{R}_{+}^{q} ),\varPsi ( x_{n},y_{n} ) \leq 0.\end{array} \right .$$

A contradiction with the fact that $(\overline{x},\overline{y})\in E$ be a local weak efficient solution of (P^∗). □

The theorem below uses Lemma 3.4 to get necessary optimality conditions.

Theorem 3.2

Let $(\overline{x},\overline{y})\in E$ be a local weak efficient solution of (P). Then there exist $y^{\ast }\in( -\mathbb{R}_{+}^{m} )^{\circ }\setminus\{0\}$ such that

Proof

Since $(\overline{x},\overline{y})\in E$ is a local weak efficient solution of (P), it is also a local weak efficient solution of $(\mathrm{P}_{1}^{\ast})$ with respect to $\mathbb{R}_{+}^{m}$.

The proof of this theorem consists of several steps.

• Let us prove that $(\overline{x},\overline{y})$ solves locally the following scalar convex minimization problem:

  $$\left \{ \begin{array}{l}\text{Minimize}\quad \varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{m} } \bigl(\overleftrightarrow{\psi }_{1} ( x,y ) -\overleftrightarrow{\psi }_{1} ( \overline{x},\overline{y} ) ,\ldots,\overleftrightarrow{\psi }_{m} ( x,y ) -\overleftrightarrow{\psi }_{m} ( \overline{x},\overline{y} ) \bigr) \\[3pt]\text{subject to}\quad ( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}.\end{array} \right .$$

By assumption, $(\overline{x},\overline{y})\in E$ is a local weak efficient solution of $(\mathrm{P}_{1}^{\ast})$ with respect to $\mathbb{R}_{+}^{m}$; there exists a neighborhood V of $(\overline{x},\overline{y})$ such that

$$\overleftrightarrow{\psi } ( x,y ) -\overleftrightarrow{\psi }(\overline{x},\overline{y} ) \notin -\mathrm{int}\, \mathbb{R}_{+}^{m}\quad \text{for all } (x,y) \in V.$$

Hence by Proposition 2.1,

$$\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{m} } \bigl( \overleftrightarrow{\psi } ( x,y ) -\overleftrightarrow{\psi }( \overline{x},\overline{y} ) \bigr) \geq 0.$$

Since $\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{m} } ( 0 )=0$, it follows that $(\overline{x},\overline{y})$ solves locally the problem

$$\text{Minimize }\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{m}} \bigl( \overleftrightarrow{\psi } ( x,y )-\overleftrightarrow{\psi } ( \overline{x},\overline{y} ) \bigr)\quad\text{subject to}\quad ( x,y ) \in \mathbb{R}^{n_{1}}\times \mathbb{R}^{n_{2}}\mathbb{.}$$

• Set

  $$\overleftrightarrow{\psi }_{\overline{u}} ( x,y ) :=\overleftrightarrow{\psi } ( u ) -\overleftrightarrow{\psi } ( \overline{u} ) .$$

As $\varDelta _{-int}\, \mathbb{R}_{+}^{m}$ and $\overleftrightarrow{\psi }$ are locally Lipschitz, then there exists α≥1 such that $\varDelta _{-\mathrm{int}}\, \mathbb{R}_{+}^{m}\circ \overleftrightarrow{\psi }$ is locally Lipschitz with a Lipschitz constant α. Consequently, $\varDelta _{-\mathrm{int}}\, \mathbb{R}_{+}^{m}\circ \overleftrightarrow{\psi }_{\overline{u}}$ is Lipschitzian. Then

$$0\in \partial ( \varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{m} }\circ \overleftrightarrow{\psi }_{\overline{u}} ) ( \overline{u} ) .$$

Applying the chain rule [18], there exist $y^{\ast }\in \partial \varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{m} } ( 0 )$ such that

$$0\in \partial \bigl( y^{\ast }\circ \overleftrightarrow{\psi }_{\overline{u}} \bigr) ( \overline{u} ) .$$

Since $\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{m} }( . )$ is a convex function and $\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{n} } (0 ) =0$ we have for all v∈ℝ^m

$$\varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{m} } ( v ) \geq \bigl\langle v^{\ast },v \bigr\rangle $$

and hence for all $v\in - ( \mathbb{R}_{+}^{m})$

$$\bigl\langle v^{\ast },v \bigr\rangle \leq \varDelta _{-\mathrm{int}\, \mathbb{R}_{+}^{m} } ( v ) =-d\bigl( v,\mathbb{R}^{m}\backslash -\mathrm{int}\, \mathbb{R}_{+}^{m}\bigr) \leq 0.$$

That is $v^{\ast }\in ( -\mathbb{R}_{+}^{m} )^{\circ }$. From Proposition 2.2, we have that v ^∗≠0.

Thus, there exist $v^{\ast }\in ( -\mathbb{R}_{+}^{m} )^{\circ }\setminus \{ 0 \}$ such that

$$0\in \partial \Biggl(\sum_{i=1}^{m}y_{i}^{\ast }\overleftrightarrow{\psi }_{i} \Biggr) ( \overline{u} ) .$$

Applying the sum rule [18], we obtain

$$0\in \sum_{i=1}^{m}y_{i}^{\ast }\partial \overleftrightarrow{\psi }_{i} ( \overline{x},\overline{y} ) .$$

Finally, there exist $y^{\ast }\in ( -\mathbb{R}_{+}^{m} )^{\circ }\setminus \{ 0 \}$ such that

 □

Remark 3.4

Using Propositions 2.3 and 2.4, one gets

$$\partial \varPsi ( \overline{x},\overline{y} ) \subset \mathrm{co} \bigl\{ \partial \psi (\overline{x},\overline{y},z ) :z\in J ( \overline{x} ) \bigr\}$$

and

$$J ( \overline{x} ) :=\bigl\{z\in \varTheta :\psi ( \overline{x},\overline{y},z ) =\varPsi ( \overline{x},\overline{y} ) \bigr\}.$$

Moreover, setting

$$\psi_{1} ( x,y,z ) =f ( x,y ) -f ( x,z ) ,\psi_{2} (x,y,z ) =-\varDelta _{ ( -R_{+}^{q} ) } \bigl( g_{1}(x,z),\ldots,g_{q}(x,z) \bigr)$$

and

$$I ( \overline{x} ) :=\bigl\{i:\psi_{i} ( \overline{x},\overline{y},z ) ( \overline{x} ) =\psi ( \overline{x},\overline{y},z ) \bigr\},$$

one obtains

$$\partial \psi ( \overline{x},\overline{y},z ) :=\mathrm{conv} \bigl\{ \partial \psi_{i} ( \overline{x},\overline{y},z ) :i\in I (\overline{x}) \bigr\} .$$

4 Conclusions

As a hierarchical optimization problem, the multiobjective bilevel problem (P) combines decisions of the so-called leader and the so-called follower. While the leader has the first choice and the follower reacts optimally on the leaders selection, the leaders aim consists in finding such a selection which, together with the followers response, minimizes the mapping F with respect to a given cone. With the help of the concept of Pareto optimality, together with a special scalarization function introduced by Hiriart–Urruty, we give necessary optimality conditions. Our approach consists of proving that (P) is locally equivalent to a single level optimization problem, where the nonsmooth Mangasarian–Fromovitz constraint qualification may hold at any feasible solution.