# A novel approach for bilevel programs based on Wolfe duality††thanks: This
work was supported in part by NSFC (Nos. 12071280, 11901380, 11971220).

Yuwei Li, Gui-Hua Lin, Jin Zhang, Xide Zhu School of Management, Shanghai
University, Shanghai 200444, China. E-mail<EMAIL_ADDRESS>author. School of Management, Shanghai University, Shanghai 200444, China.
E-mail<EMAIL_ADDRESS>of Mathematics, SUSTech International
Center for Mathematics, Southern University of Science and Technology,
Shenzhen 518055, China. E-mail<EMAIL_ADDRESS>of Management,
Shanghai University, Shanghai 200444, China. E-mail<EMAIL_ADDRESS>
(January 26, 2022)

Abstract. This paper considers a bilevel program, which has many applications
in practice. To develop effective numerical algorithms, it is generally
necessary to transform the bilevel program into a single-level optimization
problem. The most popular approach is to replace the lower-level program by
its KKT conditions and then the bilevel program can be reformulated as a
mathematical program with equilibrium constraints (MPEC for short). However,
since the MPEC does not satisfy the Mangasarian-Fromovitz constraint
qualification at any feasible point, the well-developed nonlinear programming
theory cannot be applied to MPECs directly. In this paper, we apply the Wolfe
duality to show that, under very mild conditions, the bilevel program is
equivalent to a new single-level reformulation (WDP for short) in the globally
and locally optimal sense. We give an example to show that, unlike the MPEC
reformulation, WDP may satisfy the Mangasarian-Fromovitz constraint
qualification at its feasible points. We give some properties of the WDP
reformulation and the relations between the WDP and MPEC reformulations. We
further propose a relaxation method for solving WDP and investigate its
limiting behavior. Comprehensive numerical experiments indicate that, although
solving WDP directly does not perform very well in our tests, the relaxation
method based on the WDP reformulation is quite efficient.

Keywords. Nonlinear programming, Bilevel programming, Wolfe duality,
Constraint qualification, Relaxation method, Convergence.

2010 Mathematics Subject Classification. 90C30, 90C33, 90C46.

##  1 Introduction

Bilevel programs are hierarchical optimization problems which contain some
parameterized optimization or equilibrium problems as constraints. This type
of leader-follower game problems can be traced back to the model first
introduced by Stackelberg [37] and they have been applied to many fields such
as game theory, industrial engineering, economic planning, management science,
and so on [18, 1, 9, 23]. For more details about their developments, we refer
the readers to [8, 1, 4] and the references therein.

In this paper, we consider the optimistic bilevel program

$\displaystyle(\mathrm{BP})\quad\min$ $\displaystyle F(x,y)$ s.t.
$\displaystyle x\in X,~{}y\in{S}(x).$

Here, $F:\mathbb{R}^{n+m}\rightarrow\mathbb{R}$ denotes the leader’s objective
function, $X\subseteq\mathbb{R}^{n}$ denotes the leader’s strategy set, and
${S}(x)\subseteq\mathbb{R}^{m}$ denotes the follower’s optimal reaction set,
which is the optimal solution set of the parameterized program

$\displaystyle(\mathrm{P}_{x})\quad\min\limits_{y}$ $\displaystyle f(x,y)$
s.t. $\displaystyle g(x,y)\leq 0,~{}h(x,y)=0,$

where $f:\mathbb{R}^{n+m}\rightarrow\mathbb{R}$, $g$:
$\mathbb{R}^{n+m}\rightarrow\mathbb{R}^{p}$, and $h$:
$\mathbb{R}^{n+m}\rightarrow\mathbb{R}^{q}$. Throughout the paper, we denote
by $Y(x):=\\{y\in\mathbb{R}^{m}:g(x,y)\leq 0,~{}h(x,y)=0\\}$ the feasible
region of $({\rm P}_{x})$ and assume that $F$ is continuously differentiable,
$\\{f,g,h\\}$ are all twice continuously differentiable, and
${S}(x)\neq\emptyset$ for each $x\in X$. (BP) describes the case where the
leader can anticipate how the follower makes its decisions. In practice, there
are other cases where the leader and the follower are not cooperative and, in
these cases, the leader may make decisions in the pessimistic manner. See [18,
8, 24, 1, 19] for more details about optimistic and pessimistic bilevel
models.

As is well-known to us, due to the hierarchical structure, bilevel programs
are very difficult to solve. Actually, even for linear cases, bilevel programs
have been shown to be strongly NP-hard. From the perspective of continuous
optimization, to develop effective numerical algorithms, it is generally
necessary to transform bilevel programs into single-level optimization
problems. Along this way, there have been presented several reformulations for
bilevel programs, which include

  * $\diamond$

the reformulation based on lower-level solution functions,

  * $\diamond$

the reformulation based on lower-level optimal value functions,

  * $\diamond$

the reformulation based on lower-level optimality conditions,

  * $\diamond$

the reformulation based on lower-level Lagrangian duality.

See Section 2 given below for details about these reformulations.

Among the reformulations for bilevel programs mentioned above, the first one
requires the lower-level solution functions to be known and, in such cases, it
is generally neither differentiable nor convex even if both the upper-level
and lower-level programs are differentiable and convex. For the second
reformulation, the lower-level optimal value functions are usually difficult
to evaluate because they do not have analytic expressions in general. The
third reformulation is the most popular in literature and it is known as the
mathematical program with equilibrium constraints (MPEC). However, MPECs are
highly nonconvex with combinatorial structure and, in theory, MPECs do not
satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ) at any
feasible point so that the well-developed nonlinear programming theory cannot
be applied to MPECs directly. The fourth reformulation uses the so-called
regularized constrained Lagrangian dual function, but it has some flaws as
follows:

  * •

The regularized constrained Lagrangian dual function used in the duality-based
reformulation is defined by minimizing the lower-level Lagrangian function
over a compact and convex constraint set and hence it generally has no
analytic expressions.

  * •

The lower-level feasible region is assumed to be uniformly contained within
the interior of some compact and convex set, which is too stringent.

  * •

If the lower-level objective function is convex but not strictly convex, an
approximation parameter is introduced and required to tend to 0 in solving the
original bilevel program.

In this paper, we present a new single-level reformulation for (BP) with
better structure and properties than the existing ones. Our strategy is to use
the Wolfe duality for constrained optimization problems to deal with the
lower-level program. Compared with the existing reformulations introduced
above, the new reformulation based on lower-level Wolfe duality does not
involve any function without analytic expression and, more importantly, it may
satisfy the MFCQ at its feasible points.

The paper is organized as follows. In Section 2, we first recall the existing
single-level reformulations for (BP) and then introduce some Wolfe duality
theorems for constrained optimization problems. In Section 3, we apply the
Wolfe duality theorems to present our new single-level reformulation for (BP).
We show their equivalence from both globally and locally optimal senses. In
Section 4, we make a comparison between the new reformulation and the most
popular MPEC reformulation. In particular, we first give an example to show
that the new reformulation may satisfy the MFCQ at its feasible points and
then investigate the relations between the two reformulations. In Section 5,
we present a relaxation scheme for solving the new reformulation and establish
a convergence analysis. In Section 6, we report our numerical experiments on a
number of linear bilevel programs generated randomly. In Section 7, we make
some concluding remarks.

Throughout, for a given differentiable function
$G:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$, we use $\nabla
G(x)\in\mathbb{R}^{n\times m}$ to denote the transposed Jacobian of $G$ at
$x$. When $m=1$, $\nabla G(x)\in\mathbb{R}^{n}$ stands for the gradient of $G$
at $x$. Given two vectors $a,b\in\mathbb{R}^{n}$, $a\bot b$ means $a^{T}b=0$.

##  2 Preliminaries

In this section, we introduce some existing reformulations for bilevel
programs and the Wolfe duality for constrained optimization problems.

###  2.1 Existing reformulations for bilevel programs

As mentioned before, in order to develop effective numerical algorithms, we
need to transform bilevel programs into single-level optimization problems. In
this section, we briefly recall the existing reformulations for bilevel
programs.

####  2.1.1 Reformulation based on lower-level solution functions

If the lower-level program $({\rm P}_{x})$ has a unique optimal solution
$y(x)$ for any given $x\in X$, the bilevel program (BP) can be reformulated
equivalently into the single-level problem

$\displaystyle(\mathrm{SP})\quad\min$ $\displaystyle F(x,y(x))$ s.t.
$\displaystyle x\in X.$

Naturally, this reformulation requires stringent conditions to ensure the
existence of lower-level optimal solutions and, under the condition that the
solution function $y(x)$ is known, the objective function in the above problem
is generally neither differentiable nor convex, even if both the upper-level
and lower-level programs are differentiable and convex. Therefore, this
approach is usually hard to be applied in solving bilevel programs.

####  2.1.2 Reformulation based on lower-level optimal value functions

Another approach for bilevel programs is to use the lower-level optimal value
function defined by $V(x):=\min\limits_{y\in Y(x)}~{}f(x,y).$ Then, the
bilevel program (BP) can be reformulated equivalently into the single-level
optimization problem

$\displaystyle(\mathrm{VP})\quad\min$ $\displaystyle F(x,y)$ s.t.
$\displaystyle f(x,y)-V(x)\leq 0,~{}x\in X,~{}y\in Y(x).$

This reformulation was first proposed by Outrata in [30]. Subsequently, Ye et
al. [43, 42] and Dempe et al. [8] used the lower-level optimal value functions
to study various optimality conditions and constraint qualifications for
bilevel programs.

On the other hand, although the reformulation (VP) looks like a single-level
optimization problem, as the lower-level optimal value function $V(x)$ does
not have analytic expression and may not be differentiable in general, it is
obviously not a normal constrained optimization problem. Moreover, it is easy
to see that the inequality constraint in (VP) is actually an equality
constraint and hence the nonsmooth MFCQ is never satisfied at each feasible
point [43, Proposition 3.2]. In consequence, we cannot apply the well-
developed optimization algorithms to solve it directly. Recently, motivated by
the study of semi-infinite programming, Xu et al. [22, 41] considered a simple
bilevel program with a compact lower-level feasible region and proposed some
approximation methods by using an integral entropy function to approximate the
lower-level optimal value function.

####  2.1.3 Reformulation based on lower-level optimality conditions

Because of the existence of the lower-level optimal solution or optimal value
functions, both reformulations introduced above are hard to be applied in
solving bilevel programs. The most popular approach so far is to use the
lower-level optimality conditions to transform the bilevel program (BP) into
an MPEC. If the lower-level feasible region $Y(x)$ is convex for each $x\in
X$, by means of the classical first-order necessary conditions for $({\rm
P}_{x})$, the bilevel program (BP) can be reformulated as a mathematical
program with parametric variational inequality constraints, which is
essentially a semi-infinite programming problem and mainly useful in the
theoretical study. To develop numerical algorithms, we may use the KKT
conditions for $({\rm P}_{x})$, which usually requires some constraint
qualifications, to reformulate the bilevel program (BP) as the following
mathematical program with complementarity constraints:

$\displaystyle(\mathrm{MPEC})\quad\min$ $\displaystyle F(x,y)$ s.t.
$\displaystyle x\in X,~{}h(x,y)=0,$ $\displaystyle 0\leq u~{}\bot~{}g(x,y)\leq
0,$ $\displaystyle\nabla_{y}f(x,y)+\nabla_{y}g(x,y)u+\nabla_{y}h(x,y)v=0.$

On the one hand, although the globally optimal solutions of the original
bilevel program (BP) and the corresponding MPEC coincide with each other,
their local optimal solutions may not be correspond with each other in the
case that multiple multipliers exist for the lower-level program [7]. In
addition, Mirrlees gave an example to reveal that the optimal solutions of the
original bilevel program may not even be a stationary point of the
corresponding MPEC [27].

On the other hand, MPEC has a combinatorial structure, that is, its feasible
region is usually a union of lots of pieces, and it fails to satisfy the MFCQ
at any feasible point, which means that the well-developed optimization
algorithms in nonlinear programming may not be stable in solving MPEC. During
the past decades, there have been proposed a number of approximation
algorithms for solving MPEC, including relaxation and smoothing algorithms,
penalty function algorithms, interior point algorithms, implicit programming
algorithms, active-set identification algorithms, constrained equation
algorithms, nonsmooth algorithms, etc. We refer the readers to [11, 12, 36,
10, 15, 13, 20, 21, 25, 31, 35] and the references therein for more details
about the recent developments on theory and numerical algorithms for MPEC.

####  2.1.4 Reformulation based on lower-level Lagrangian duality

Recently, Ouattara and Aswani [29] studied another approach to deal with
bilevel programs by using some kind of Lagrangian dual functions of the lower-
level program ($\mathrm{P}_{x}$). Since the classical Lagrangian dual function
of ($\mathrm{P}_{x}$) may not be differentiable and even not real-valued,
under the condition that the lower-level feasible region is convex and
uniformly contained within the interior of some compact and convex set
$\bar{Y}$, the authors defined a so-called constrained Lagrangian dual
function by

$\displaystyle\mathcal{V}(x,u,v):=\min_{y\in\bar{Y}}\,f(x,y)+u^{T}g(x,y)+v^{T}h(x,y)$

and showed that, if $f(x,y)$ is strictly convex in $y$ for each $x\in X$, the
constrained Lagrangian dual function is differentiable when $u\geq 0$. In this
case, they presented the following duality-based reformulation:

$\displaystyle(\mathrm{LDP})\quad\min$ $\displaystyle F(x,y)$ s.t.
$\displaystyle f(x,y)\leq\mathcal{V}(x,u,v),$ $\displaystyle u\geq
0,~{}g(x,y)\leq 0,$ $\displaystyle x\in X,~{}h(x,y)=0.$

If $f(x,y)$ is only convex but not necessarily strictly convex in $y$ for each
$x\in X$, they introduced a regularized constrained Lagrangian dual function

$\displaystyle\mathcal{V}_{\delta}(x,u,v):=\min_{y\in\bar{Y}}\,\delta\|y\|^{2}+f(x,y)+u^{T}g(x,y)+v^{T}h(x,y),$

where $\delta>0$, and gave the following approximated duality-based
reformulation:

$\displaystyle\min$ $\displaystyle F(x,y)$ s.t. $\displaystyle
f(x,y)\leq\mathcal{V}_{\delta}(x,u,v),$ $\displaystyle u\geq 0,~{}g(x,y)\leq
0,$ $\displaystyle x\in X,~{}h(x,y)=0.$

Note that both $\mathcal{V}$ and $\mathcal{V}_{\delta}$ do not have analytic
expressions in general and, in addition, the approximation parameter $\delta$
in (2.1.4) is required to tend to $0$ decreasingly in solving the original
bilevel program.

###  2.2 Wolfe duality for constrained optimization problems

This subsection is devoted to gathering some useful results related to the
Wolfe duality for constrained optimization problems, which play a crucial role
in our proposed approach to bilevel programs. For simplicity, in this
subsection, we omit the upper-level variable $x$ and rewrite the lower-level
program ($\mathrm{P}_{x}$) as

$\displaystyle(\mathrm{P})\quad\min$ $\displaystyle f(y)$ s.t. $\displaystyle
g(y)\leq 0,~{}h(y)=0,$

where $f:\mathbb{R}^{m}\rightarrow\mathbb{R}$, $g$:
$\mathbb{R}^{m}\rightarrow\mathbb{R}^{p}$, and $h$:
$\mathbb{R}^{m}\rightarrow\mathbb{R}^{q}$. Denote by $Y$ and ${S}$ the
feasible region and solution set of (P) respectively. The Wolfe dual problem
given in [40] for (P) is

$\displaystyle(\mathrm{WD})\quad\max$ $\displaystyle L(z,u,v)$ s.t.
$\displaystyle\nabla_{z}L(z,u,v)=0,~{}u\geq 0,$

where $L:\mathbb{R}^{m+p+q}\to\mathbb{R}$ represents the Lagrangian function

$\displaystyle L(z,u,v):=f(z)+u^{T}g(z)+v^{T}h(z).$ (2.2)

We denote by $W$ the feasible region of (WD) and, for any fixed $(u,v)$, we
let $Z(u,v):=\\{z\in\mathbb{R}^{m}:\nabla_{z}L(z,u,v)=0\\}$. Note that, since
the Lagrangian function $L$ may not be convex over $W$ due to the existence of
the terms $u^{T}g$ and $v^{T}h$, the Wolfe dual problem (WD) is usually a
nonconvex optimization problem, even though the primal problem (P) is convex.

###### Definition 2.1

We say $f$ to be pseudoconvex on $\mathcal{Y}\subseteq\mathbb{R}^{m}$ if
$(y_{1}-y_{2})^{T}\nabla f(y_{2})\geq 0$ implies $f(y_{1})\geq f(y_{2})$ for
any $y_{1},y_{2}\in\mathcal{Y}$.

From Theorems 3 and 4 in [14], we have the following duality theorems.

###### Theorem 2.1

_(weak Wolfe duality)_ Suppose that $L(\cdot,u,v)$ is pseudoconvex on $Y\cup
Z(u,v)$ for any $u\in\mathbb{R}^{p}_{+}$ and $v\in\mathbb{R}^{q}$. Then, the
optimal value of the primal problem (P) is no less than its Wolfe dual problem
(WD), i.e.,

$\displaystyle\min\limits_{y\in
Y}f(y)\geq\max\limits_{(z,u,v)\in{W}}L(z,u,v).$

Proof.  For any $y\in Y$ and $(z,u,v)\in W$, we have $\nabla_{z}L(z,u,v)=0$
and hence $L(y,u,v)\geq L(z,u,v)$ by the pseudoconvexity of $L(\cdot,u,v)$.
Since $u\in\mathbb{R}^{p}_{+}$ and $y\in Y$ satisfies $h(y)=0$ and $g(y)\leq
0$, we have

$\displaystyle f(y)\geq f(y)+u^{T}g(y)+v^{T}h(y)=L(y,u,v)\geq L(z,u,v).$

By the arbitrariness of $y\in Y$ and $(z,u,v)\in W$, we get the conclusion.

###### Theorem 2.2

_(strong Wolfe duality)_ Suppose that $L(\cdot,u,v)$ is pseudoconvex on $Y\cup
Z(u,v)$ for any $u\in\mathbb{R}^{p}_{+}$, $v\in\mathbb{R}^{q}$ and (P)
satisfies the Guignard constraint qualification at some solution
$\bar{y}\in{S}$. Then, there exists an optimal solution
$(\bar{z},\bar{u},\bar{v})\in{W}$ to (WD) such that

$\displaystyle\min\limits_{y\in
Y}f(y)=f(\bar{y})=L(\bar{z},\bar{u},\bar{v})=\max\limits_{(z,u,v)\in{W}}L(z,u,v).$

Proof.  Since (P) satisfies the Guignard constraint qualification at
$\bar{y}\in{S}$, there exists $(\bar{u},\bar{v})$ such that

$\displaystyle\nabla_{y}L(\bar{y},\bar{u},\bar{v})=0,~{}~{}\bar{u}^{T}g(\bar{y})=0,~{}~{}\bar{u}\geq
0,$

from which we have $(\bar{y},\bar{u},\bar{v})\in W$. We can show that
$(\bar{y},\bar{u},\bar{v})$ is an optimal solution to $(\mathrm{WD})$.
Otherwise, there must exist some $(y,u,v)\in W$ such that

$\displaystyle L(y,u,v)>L(\bar{y},\bar{u},\bar{v})=f(\bar{y}),$

which contradicts the weak Wolfe duality shown in Theorem 2.1. Therefore,
$(\bar{y},\bar{u},\bar{v})$ is an optimal solution to $(\mathrm{WD})$. As a
result, we have

$\displaystyle\min\limits_{y\in
Y}f(y)=f(\bar{y})=L(\bar{y},\bar{u},\bar{v})=\max\limits_{(z,u,v)\in{W}}L(z,u,v).$

This completes the proof.

###### Remark 2.1

Note that the pseudoconvexity assumption for the Lagrangian function in
Theorems 2.1 and 2.2 can be replaced by some other weaker conditions such as
the $\mathcal{F}$-pseudoconvexity or the invexity. Since these conditions are
not easy to understand by definitions, we use the well-known pseudoconvexity
to describe our results. Actually, most results can be weakened by replacing
the pseudoconvexity assumption with these weaker conditions. Note that

Pseudoconvexity $\Rightarrow$ Invexity $\Leftrightarrow$
$\mathcal{F}$-convexity $\Rightarrow$ $\mathcal{F}$-pseudoconvexity,

where the first implication follows from [2], the equivalence follows from
[28], and the last implication follows from [14]. That is, the
$\mathcal{F}$-pseudoconvexity is the weakest condition mentioned above. We
refer the readers to [14, 28, 39, 40] for details about these conditions.

###### Remark 2.2

The results under the $\mathcal{F}$-pseudoconvexity assumption were shown in
[14], where the $\mathcal{F}$-pseudoconvexity was assumed over the feasible
region $Y$ only, rather than the set $Y\cup Z(u,v)$ assumed in Theorems 2.1
and 2.2. However, it can be seen from their proofs that the
$\mathcal{F}$-pseudoconvexity only over the feasible region is not sufficient
to derive their conclusions. This is why we retain the proofs for these
theorems.

###### Remark 2.3

It should be noted that, in Theorem 2.2, the dual optimal solution $\bar{z}$
may not solve the primal problem (P), unless there are some restrictions on
the functions involved. See, e.g., the following converse duality theorem
given in [5, 17].

###### Theorem 2.3

Suppose that (P) is a convex program, $\bar{y}$ solves (P), and
$(\bar{z},\bar{u},\bar{v})$ solves (WD). Then, we have $\bar{z}=\bar{y}$ and
$f(\bar{y})=L(\bar{z},\bar{u},\bar{v})$ if one of the following conditions
holds:

  * (i)

The Hessian matrix $\nabla_{zz}^{2}{L}(\bar{z},\bar{u},\bar{v})$ is
nonsingular.

  * (ii)

The Guignard constraint qualification holds at $\bar{y}$ and the function $f$
is strictly convex near $\bar{z}$.

##  3 New reformulation for bilevel programs

In this section, by applying the Wolfe duality to the lower-level program, we
present a novel single-level reformulation for the bilevel program (BP).
Different from the existing reformulations mentioned in Subsection 2.1, the
new reformulation does not involve any function without analytic expression
and, in addition, an example is given in the next section to show that the new
reformulation may satisfy the MFCQ at its feasible points.

As introduced in Subsection 2.2, for any given $x\in X$, the Wolfe dual
problem for the lower-level program ($\mathrm{P}_{x}$) is

$\displaystyle(\mathrm{WD}_{x})\quad\max\limits_{z,u,v}$ $\displaystyle
L(x,z,u,v)$ s.t. $\displaystyle\nabla_{z}L(x,z,u,v)=0,~{}u\geq 0,$

where $L(x,z,u,v):=f(x,z)+u^{T}g(x,z)+v^{T}h(x,z).$ Similarly, for any fixed
$(x,u,v)$, we let $Z(x,u,v):=\\{z\in\mathbb{R}^{m}:\nabla_{z}L(x,z,u,v)=0\\}$
and denote by ${W}(x)$ the feasible region of ($\mathrm{WD}_{x}$).

###### Theorem 3.1

Suppose that, for any $x\in X$, $L(x,\cdot,u,v)$ is pseudoconvex on $Y(x)\cup
Z(x,u,v)$ for any $u\in\mathbb{R}^{p}_{+}$, $v\in\mathbb{R}^{q}$, and
$(\mathrm{P}_{x})$ satisfies the Guignard constraint qualification at some
solution $y_{x}\in{S(x)}$. Then, if $(\bar{x},\bar{y})$ is an optimal solution
to the bilevel program (BP), there exists
$(\bar{z},{\bar{u}},{\bar{v}})\in{W}(\bar{x})$ such that
$(\bar{x},\bar{y},\bar{z},{\bar{u}},{\bar{v}})$ is an optimal solution to the
single-level optimization problem

$\displaystyle(\mathrm{WDP})\quad\min$ $\displaystyle F(x,y)$ s.t.
$\displaystyle x\in X,\ y\in Y(x),$ $\displaystyle f(x,y)-L(x,z,u,v)\leq 0,$
$\displaystyle\nabla_{z}L(x,z,u,v)=0,\ u\geq 0,$

or equivalently,

$\displaystyle\min$ $\displaystyle F(x,y)$ s.t. $\displaystyle x\in
X,~{}g(x,y)\leq 0,~{}h(x,y)=0,$ $\displaystyle
f(x,y)-f(x,z)-u^{T}g(x,z)-v^{T}h(x,z)\leq 0,$
$\displaystyle\nabla_{z}f(x,z)+\nabla_{z}g(x,z)u+\nabla_{z}h(x,z)v=0,~{}u\geq
0.$

Conversely, if $(\bar{x},\bar{y},\bar{z},{\bar{u}},{\bar{v}})$ is an optimal
solution to (WDP), $(\bar{x},\bar{y})$ is an optimal solution to (BP).

Proof.  Recall that (BP) is equivalent to the value reformulation (VP) with
the same optimal solution set. By the assumptions and Theorem 2.2, for each
$x\in X$, there exists an optimal solution $(z_{x},u_{x},v_{x})\in{W}(x)$ to
($\mathrm{WD}_{x}$) such that

$\min\limits_{y\in
Y(x)}f(x,y)=L(x,z_{x},u_{x},v_{x})=\max\limits_{(z,u,v)\in{W}(x)}L(x,z,u,v).$

Thus, the value reformulation (VP) can be rewritten as

$\displaystyle\min$ $\displaystyle F(x,y)$ s.t. $\displaystyle x\in X,\ y\in
Y(x),$ $\displaystyle f(x,y)\leq\max\limits_{(z,u,v)\in W(x)}L(x,z,u,v).$

Next, we show the equivalence between (3) and (WDP).

(i) Suppose that $(\bar{x},\bar{y})$ is an optimal solution to (3). Then, we
have

$\displaystyle F(\bar{x},\bar{y})\leq F(x,y)$ (3.2)

for any feasible point $(x,y)$ to (3) and, by the feasibility of
$(\bar{x},\bar{y})$ to (3),

$\displaystyle f(\bar{x},\bar{y})\leq\max\limits_{(z,u,v)\in
W(\bar{x})}L(\bar{x},z,u,v)=L(\bar{x},z_{\bar{x}},u_{\bar{x}},v_{\bar{x}}).$

This together with $(z_{\bar{x}},u_{\bar{x}},v_{\bar{x}})\in{W}(\bar{x})$
indicates that $(\bar{x},\bar{y},z_{\bar{x}},u_{\bar{x}},v_{\bar{x}})$ is
feasible to (WDP). For any feasible point $(x,y,z,u,v)$ to (WDP), since

$\displaystyle f(x,y)\leq
L(x,z,u,v)\leq\max\limits_{(z^{\prime},u^{\prime},v^{\prime})\in{W}(x)}L(x,z^{\prime},u^{\prime},v^{\prime}),$

where the second inequality follows from $(z,u,v)\in{W}(x)$, $(x,y)$ is
feasible to (3) and hence we have (3.2). By the arbitrariness of
$(x,y,z,u,v)$, $(\bar{x},\bar{y},z_{\bar{x}},u_{\bar{x}},v_{\bar{x}})$ is an
optimal solution to (WDP).

(ii) Suppose that $(\bar{x},\bar{y},\bar{z},{\bar{u}},{\bar{v}})$ is an
optimal solution to (WDP). We have
$\nabla_{z}L(\bar{x},\bar{z},{\bar{u}},{\bar{v}})=0,\bar{u}\geq 0$ (i.e.,
$(\bar{z},{\bar{u}},{\bar{v}})\in W(\bar{x})$), and

$\displaystyle f(\bar{x},\bar{y})\leq
L(\bar{x},\bar{z},{\bar{u}},{\bar{v}})\leq\max\limits_{(z,u,v)\in
W(\bar{x})}L(\bar{x},z,u,v).$

This means that $(\bar{x},\bar{y})$ is feasible to (3). For any feasible point
$(x,y)$ to (3), we have

$\displaystyle
f(x,y)\leq\max\limits_{(z,u,v)\in{W}(x)}L(x,z,u,v)=L(x,z_{x},u_{x},v_{x})$

and so $(x,y,z_{x},u_{x},v_{x})$ is feasible to (WDP). By the optimality of
$(\bar{x},\bar{y},\bar{z},{\bar{u}},{\bar{v}})$ to (WDP), we have (3.2). By
the arbitrariness of $(x,y)$, $(\bar{x},\bar{y})$ is an optimal solution to
(3).

This completes the proof.

###### Remark 3.1

As stated in Remark 2.1, the pseudoconvexity assumption in Theorem 3.1 can be
weakened by the $\mathcal{F}$-pseudoconvexity. The following example shows
that, even if the lower-level program does not satisfy the
$\mathcal{F}$-pseudoconvexity, the original bilevel program (BP) is still
possibly equivalent to (WDP).

###### Example 3.1

Consider the bilevel program

$\displaystyle\min$ $\displaystyle 2x-y$ (3.3) s.t. $\displaystyle x\geq
0,~{}y\in S(x)=\arg\min\limits_{y}\\{-e^{-(y-x)^{2}}+0.3y^{2}-0.6xy:y\geq
x\\}.$

For any $x\geq 0$, since the lower-level objective function is strictly
increasing with respect to $y$ on $[x,+\infty)$, we always have
$S(x)=\\{x\\}$. Hence, (3.3) has a unique optimal solution
$(\bar{x},\bar{y})=(0,0)$ with the optimal value to be $0$.

For this problem, (WDP) becomes

$\displaystyle\min$ $\displaystyle 2x-y$ s.t. $\displaystyle x\geq 0,~{}y\geq
x,$ $\displaystyle-e^{-(y-x)^{2}}+0.3y^{2}-0.6xy-L(x,z,u)\leq 0,$
$\displaystyle 2(z-x)e^{-(z-x)^{2}}+0.6(z-x)-u=0,~{}u\geq 0,$

where the lower-level Lagrangian function

$L(x,z,u):=-e^{-(z-x)^{2}}+0.3z^{2}-0.6xz-u(z-x).$

We next show that, for any given $x\geq 0$, $L(x,\cdot,\bar{u})$ is not
$\mathcal{F}$-pseudoconvex on $Y(x)\cup Z(x,\bar{u})=[x,+\infty)$ for some
$\bar{u}\geq 0$, but the original bilevel program (3.3) is still equivalent to
(3.1) in the sense of Theorem 3.1.

Figure 1: The graph of the function $L(x,\cdot,\bar{u})-0.3x^{2}$ with
$\bar{u}=1.3$

(i) Recall that $L(x,\cdot,\bar{u})$ is $\mathcal{F}$-pseudoconvex over
$[x,+\infty)$ if there exists a sublinear function
${\mathcal{F}}(z_{1},z_{2};\cdot)$, depend on $z_{1},z_{2}\in[x,+\infty)$,
such that

$\displaystyle{\mathcal{F}}\big{(}z_{1},z_{2};\nabla_{z}L(x,z_{2},\bar{u})\big{)}\geq
0\ \Rightarrow\ L(x,z_{1},\bar{u})\geq L(x,z_{2},\bar{u}).$

Take $\bar{u}=1.3$, $z_{1}=1.75+x$, and select $z_{2}$ as drawn in Figure 1
such that $\nabla_{z}L(x,z_{2},\bar{u})=0$. For any sublinear function
${\mathcal{F}}(z_{1},z_{2};\cdot)$, by the positive homogeneity, we have
${\mathcal{F}}\big{(}z_{1},z_{2};\nabla_{z}L(x,z_{2},\bar{u})\big{)}=0$.
However, by direct calculations, we have

$L(x,z_{1},\bar{u})\approx-1.403+0.3x^{2}<-1.376+0.3x^{2}\approx
L(x,z_{2},\bar{u}).$

This means that $L(x,\cdot,\bar{u})$ is not $\mathcal{F}$-pseudoconvex on
$[x,+\infty)$ for $\bar{u}=1.3$.

(ii) By substituting with $y=x+s$, $z=x+t$, and eliminating the variable $u$,
problem (3.1) can be rewritten as

$\displaystyle\min$ $\displaystyle x-s$ s.t. $\displaystyle x\geq 0,~{}s\geq
0,~{}t\geq 0,$
$\displaystyle-e^{-s^{2}}+0.3s^{2}\leq-e^{-t^{2}}(2t^{2}+1)-0.3t^{2}.$

Consider two functions

$\displaystyle\pi(a):=-e^{-a}+0.3a,\qquad\theta(b):=-e^{-b}(2b+1)-0.3b.$

The function $\pi$ is strictly increasing and hence it has a unique minimal
point $\bar{a}=0$ on $[0,\infty)$ with $\pi(\bar{a})=-1$. On the other hand,
since $\theta(b)\rightarrow-\infty$ as $b\rightarrow+\infty$ and
$\theta(b)\leq 0$ for any $b\geq 0$, the function $\theta$ must attain its
maximum on $[0,\infty)$ at the endpoint $\bar{b}=0$ or the stationary points
satisfying $\theta^{\prime}(\hat{b})=0$ with $\hat{b}>0$. Solving
$\theta^{\prime}(\hat{b})=e^{-\hat{b}}(2\hat{b}-1)-0.3=0$ with $\hat{b}>0$, we
have

$\displaystyle e^{-\hat{b}}=\frac{3}{10(2\hat{b}-1)}$ (3.6)

and $\hat{b}>0.65$ by $e^{-\hat{b}}<1$. Substituting (3.6) into $\theta$, we
have $\theta(\hat{b})=-\frac{6\hat{b}^{2}+3\hat{b}+3}{10(2\hat{b}-1)}.$ Since
$\theta(\bar{b})=-1$ and $\hat{b}>0.65$, we have

$\displaystyle\theta(\hat{b})-\theta(\bar{b})=1-\frac{6\hat{b}^{2}+3\hat{b}+3}{10(2\hat{b}-1)}=-\frac{6((\hat{b}-\frac{17}{12})^{2}+\frac{23}{144})}{10(2\hat{b}-1)}<0.$

This means that $\theta$ attains its maximum on $[0,\infty)$ at $\bar{b}=0$
with $\theta(\bar{b})=-1$.

The above analysis indicates that the last constraint holds only when $s=t=0$.
As a result, problem (3.1) has a unique optimal solution
$(\tilde{x},\tilde{s},\tilde{t})=(0,0,0)$. Then, problem (3.1) has a unique
optimal solution $(\tilde{x},\tilde{y},\tilde{z},\tilde{u})=(0,0,0,0)$ with
the optimal value to be $0$. Consequently, the bilevel program (3.3) is still
equivalent to its (WDP) reformulation (3.1) in the sense of Theorem 3.1,
although the assumptions of Theorem 3.1 are not satisfied.

###### Theorem 3.2

Let $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ be feasible to (WDP) and the
weak Wolfe duality hold for $(\mathrm{P}_{\bar{x}})$ and
($\mathrm{WD}_{\bar{x}}$). Then, $\bar{y}$ is globally optimal to
(P${}_{\bar{x}}$) and $(\bar{z},\bar{u},\bar{v})$ is globally optimal to
($\mathrm{WD}_{\bar{x}}$).

Proof.  By the feasibility of $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ to
(WDP), we have

$\displaystyle\min\limits_{y\in Y(\bar{x})}f(\bar{x},y)\leq
f(\bar{x},\bar{y})\leq
L(\bar{x},\bar{z},\bar{u},\bar{v})\leq\max\limits_{(z,u,v)\in
W(\bar{x})}L(\bar{x},z,u,v).$ (3.7)

By the weak Wolfe duality assumption, we have

$\min\limits_{y\in Y(\bar{x})}f(\bar{x},y)\geq\max\limits_{(z,u,v)\in
W(\bar{x})}L(\bar{x},z,u,v).$

Therefore, all inequalities in (3.7) should be equalities, which means that
$\bar{y}$ is a globally optimal solution to (P${}_{\bar{x}}$) and
$(\bar{z},\bar{u},\bar{v})$ is a globally optimal solution to
($\mathrm{WD}_{\bar{x}}$). This completes the proof.

Theorem 3.1 shows the equivalence between (BP) and (WDP) in the globally
optimal sense. Since they are both nonconvex optimization problems, it is
necessary to investigate their equivalence in the locally optimal sense.
Denote by $U(w)$ some neighborhood of a point $w$.

###### Theorem 3.3

(i) Suppose that $(\bar{x},\bar{y})$ is locally optimal to (BP) restricted on
$U(\bar{x})\times U(\bar{y})$ and ($\mathrm{P}_{\bar{x}}$) satisfies the
Guignard constraint qualification at some optimal solution $\bar{z}$ with
$\\{\bar{u},\bar{v}\\}$ being the corresponding Lagrange multipliers. If
$(\mathrm{P}_{x})$ and ($\mathrm{WD}_{x}$) satisfy the weak Wolfe duality for
any $x\in U(\bar{x})$, $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ is locally
optimal to (WDP).

(ii) Conversely, let $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ be locally
optimal to ($\mathrm{WDP}$) restricted on $U(\bar{x})\times U(\bar{y})\times
U(\bar{z})\times\mathbb{R}^{p}\times\mathbb{R}^{q}$ with $U(\bar{y})\subseteq
U(\bar{z})$. If ($\mathrm{P}_{x}$) satisfies the Guignard constraint
qualification at all points in $S(x)$ for any $x\in U(\bar{x})$,
$(\bar{x},\bar{y})$ is locally optimal to (BP).

Proof.  (i) Since both $\bar{y}$ and $\bar{z}$ are globally optimal solutions
to ($\mathrm{P}_{\bar{x}}$) and $\\{\bar{u},\bar{v}\\}$ are the Lagrange
multipliers corresponding to $\bar{z}$, we have

$\displaystyle
f(\bar{x},\bar{y})=f(\bar{x},\bar{z})=L(\bar{x},\bar{z},\bar{u},\bar{v})$

and hence $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ is feasible to (WDP).

On the other hand, for any feasible point $(x,y,z,u,v)$ to (WDP) in the
neighborhood $U(\bar{x})\times U(\bar{y})\times U(\bar{z})\times
U(\bar{u})\times U(\bar{v})$ with $U(\bar{z})\times U(\bar{u})\times
U(\bar{v})$ to be a neighbourhood of $(\bar{z},\bar{u},\bar{v})$, by the weak
Wolfe duality assumption, the conclusion of Theorem 3.2 is true and hence
$y\in S(x)$, which means that $(x,y)$ is feasible to (BP) and belongs to
$U(\bar{x})\times U(\bar{y})$. Noting that $(\bar{x},\bar{y})$ is locally
optimal to (BP) restricted on $U(\bar{x})\times U(\bar{y})$, we have

$\displaystyle F(\bar{x},\bar{y})\leq F(x,y).$ (3.8)

By the arbitrariness of $(x,y,z,u,v)$, we get that
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ is a locally optimal solution to
(WDP).

(ii) Let $(x,y)\in U(\bar{x})\times U(\bar{y})$ be feasible point to (BP). It
follows that $y\in S(x)$. By the assumptions, ($\mathrm{P}_{x}$) satisfies the
Guignard constraint qualification at $y$ and hence there exist multipliers
$\\{u,v\\}$ satisfying

$\displaystyle\nabla_{y}L(x,y,u,v)=0,~{}u\geq 0,~{}u^{T}g(x,y)=0.$

It then follows from $h(x,y)=0$ that $f(x,y)=L(x,y,u,v)$. In consequence,
$(x,y,y,u,v)$ is feasible to (WDP) and belongs to $U(\bar{x})\times
U(\bar{y})\times U(\bar{y})\times U(\bar{u})\times U(\bar{v})$. Since
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ is locally optimal to
($\mathrm{WDP}$) restricted on $U(\bar{x})\times U(\bar{y})\times
U(\bar{z})\times\mathbb{R}^{p}\times\mathbb{R}^{q}$ with $U(\bar{y})\subseteq
U(\bar{z})$, we have (3.8). By the arbitrariness of $(x,y)$,
$(\bar{x},\bar{y})$ is a locally optimal solution to (BP). This completes the
proof.

The local optimality restricted on $U(\bar{x})\times U(\bar{y})\times
U(\bar{z})\times\mathbb{R}^{p}\times\mathbb{R}^{q}$ assumed in Theorem 3.3(ii)
is obviously very stringent. In the rest of this subsection, we derive a
result by restricting the local optimality on $U(\bar{x})\times
U(\bar{y})\times U(\bar{y})\times U(\bar{u})\times U(\bar{v})$. We start with
the following lemma.

###### Lemma 3.1

The set-valued mapping
$\Lambda:\mathbb{R}^{n+2m}\rightrightarrows\mathbb{R}^{p+q}$ defined by

$\displaystyle\Lambda(x,y,z):=\big{\\{}(u,v)\in\mathbb{R}^{p+q}:(x,y,z,u,v)\in{\Omega}\big{\\}}$
(3.9)

is outer semicontinuous, where

$\displaystyle{\Omega}:=\left\\{(x,y,z,u,v):\begin{array}[]{l}\nabla_{z}L(x,z,u,v)=0,~{}u\geq
0\\\ f(x,y)-L(x,z,u,v)\leq 0\end{array}\right\\}.$ (3.12)

Proof.  By Theorem 5.7 in [34], $\Lambda$ is outer semicontinuous if and only
if $\Lambda^{-1}(B)$ is closed for every compact set
$B\subset\mathbb{R}^{p+q}$, which can be obtained by the twice continuous
differentiability of the functions $\\{f,g,h\\}$.

###### Theorem 3.4

Let $(\bar{x},\bar{y},\bar{y},\bar{u},\bar{v})$ be locally optimal to (WDP)
for any $(\bar{u},\bar{v})\in\Lambda(\bar{x},\bar{y},\bar{y})$ and the weak
Wolfe duality hold for $(\mathrm{P}_{\bar{x}})$ and ($\mathrm{WD}_{\bar{x}}$).
If ($\mathrm{P}_{{x}}$) satisfies the MFCQ at ${y}\in S({x})$ for all $(x,y)$
closely to $(\bar{x},\bar{y})$, $(\bar{x},\bar{y})$ is locally optimal to
(BP).

Proof.  Since $(\bar{x},\bar{y},\bar{y},\bar{u},\bar{v})$ is feasible to
(WDP), it follows from the weak Wolfe duality assumption and Theorem 3.2 that
$\bar{y}\in S(\bar{x})$ and hence $(\bar{x},\bar{y})$ is feasible to (BP). We
next show the result by contradiction.

Suppose that $(\bar{x},\bar{y})$ is not locally optimal to (BP). There must
exist a sequence $\\{(x^{k},y^{k})\\}$ converging to $(\bar{x},\bar{y})$ with
$x^{k}\in X$, $y^{k}\in S(x^{k})$ such that

$\displaystyle F(x^{k},y^{k})<F(\bar{x},\bar{y}),\quad k=1,2,\cdots.$ (3.13)

By the assumptions, when $k$ is large sufficiently, ($\mathrm{P}_{{x^{k}}}$)
satisfies the MFCQ at ${y^{k}}\in S({x^{k}})$, there exist multipliers
$u^{k}\in\mathbb{R}^{p}$ and $v^{k}\in\mathbb{R}^{q}$ such that

$\displaystyle\nabla_{y}L(x^{k},y^{k},u^{k},v^{k})=0,~{}~{}h(x^{k},y^{k})=0,$
(3.14) $\displaystyle u^{k}\geq 0,~{}g(x^{k},y^{k})\leq
0,~{}(u^{k})^{T}g(x^{k},y^{k})=0.$ (3.15)

We next show that the sequence of $\\{(u^{k},v^{k})\\}$ is bounded.

Suppose by contradiction that $\\{(u^{k},v^{k})\\}$ is unbounded. Without loss
of generality, we may assume that $\\{\frac{u^{k}}{\|u^{k}\|+\|v^{k}\|}\\}$
and $\\{\frac{v^{k}}{\|u^{k}\|+\|v^{k}\|}\\}$ are convergent. Denote their
limits by $\hat{u}$ and $\hat{v}$ respectively. It follows that

$\displaystyle\|\hat{u}\|+\|\hat{v}\|=1.$ (3.16)

Dividing by $\|{u}^{k}\|+\|{v}^{k}\|$ on both sides of (3.14)-(3.15) and
letting $k\rightarrow\infty$ yield

$\displaystyle\nabla_{y}g(\bar{x},\bar{y})\hat{u}+\nabla_{y}h(\bar{x},\bar{y})\hat{v}=0,$
(3.17) $\displaystyle\hat{u}\geq 0,~{}g(\bar{x},\bar{y})\leq
0,~{}\hat{u}^{T}g(\bar{x},\bar{y})=0.$ (3.18)

Let ${\cal I}_{y}$ be the active index set of $g$ at $(\bar{x},\bar{y})$. By
(3.18), (3.17) reduces to

$\displaystyle\sum_{i\in{\cal
I}_{y}}\hat{u}_{i}\nabla_{y}g_{i}(\bar{x},\bar{y})+\sum_{j=1}^{q}\hat{v}_{j}\nabla_{y}h_{j}(\bar{x},\bar{y})=0.$
(3.19)

Since the MFCQ holds at $\bar{y}$ for ($\mathrm{P}_{\bar{x}}$), the gradients
$\nabla_{y}h_{j}(\bar{x},\bar{y})~{}(j=1,\cdots,q)$ are linearly independent
and there exists $d\in\mathbb{R}^{m}$ such that
$d^{T}\nabla_{y}h_{j}(\bar{x},\bar{y})=0$ for each $j$ and
$d^{T}\nabla_{y}g_{i}(\bar{x},\bar{y})<0$ for each $i\in{\cal I}_{y}$. Taking
the inner product on both sides of (3.19) with $d$, we have

$\displaystyle 0=\sum_{i\in{\cal
I}_{y}}\hat{u}_{i}d^{T}\nabla_{y}g_{i}(\bar{x},\bar{y})<0,$

which implies ${\cal I}_{y}=\emptyset$ and hence $\hat{u}=0$ by (3.18). Thus,
(3.17) becomes $\nabla_{y}h(\bar{x},\bar{y})\hat{v}=0$, which implies
$\hat{v}=0$ because the gradients
$\nabla_{y}h_{j}(\bar{x},\bar{y})~{}(j=1,\cdots,q)$ are linearly independent.
This contradicts (3.16). Therefore, the sequence of $\\{(u^{k},v^{k})\\}$ is
bounded.

Since $(x^{k},y^{k},y^{k})\to(\bar{x},\bar{y},\bar{y})$ as $k\to\infty$, by
the outer semicontinuousness of $\Lambda$ from Lemma 3.1, the sequence
$\\{(u^{k},v^{k})\\}$ has at least an accumulation point
$(\tilde{u},\tilde{v})\in\Lambda(\bar{x},\bar{y},\bar{y})$ as $k\to\infty$. By
the assumptions, the limit point
$(\bar{x},\bar{y},\bar{y},\tilde{u},\tilde{v})$ is also locally optimal to
(WDP). Note that, from the definition of $\Lambda$,
$(x^{k},y^{k},y^{k},u^{k},v^{k})$ is feasible to (WDP) for each $k$. Thus, the
inequality (3.13) is a contradiction. Consequently, $(\bar{x},\bar{y})$ must
be a locally optimal solution to (BP). This completes the proof.

##  4 Comparison between WDP and MPEC

In the previous section, it is shown that, under mild assumptions, the bilevel
program (BP) is equivalent to the single-level optimization problem (WDP) in
the globally or locally optimal sense. Note that, unlike the reformulations
(SP), (VP), and (LDP) introduced in Section 2, (WDP) does not involve any
function without analytic expression. In this section, our first purpose is to
compare (WDP) with the most popular reformulation MPEC to reveal which is
better and our second purpose is to investigate their relations.

###  4.1 WDP may satisfy the MFCQ at its feasible points

As stated before, in order to solve the bilevel program (BP) effectively, it
is generally required to transform it into some single-level optimization
problem, no matter whether it satisfies those conditions to ensure their
equivalence in theory. So, which is better between (WDP) and MPEC?

Recall that MPEC fails to satisfy the MFCQ at any feasible point. This means
that the well-developed optimization algorithms in nonlinear programming may
not be stable in solving MPEC. What about (WDP)?

###### Example 4.1

Consider the bilevel program

$\displaystyle\min$ $\displaystyle(x-y-8)^{2}$ (4.1) s.t. $\displaystyle x\geq
1,~{}y\in{S}(x)=\arg\min\limits_{y}\\{y:y^{3}\leq x,y\geq 0\\}.$

Obviously, ${S}(x)=\\{0\\}$ for any $x\geq 1$ and so (4.1) has a unique
minimizer $(8,0)$. The (WDP) reformulation for (4.1) is

$\displaystyle\min$ $\displaystyle(x-y-8)^{2}$ s.t. $\displaystyle x\geq
1,~{}y^{3}-x\leq 0,~{}y\geq 0,$ $\displaystyle y-z-u_{1}(z^{3}-x)+u_{2}z\leq
0,$ $\displaystyle 1+3u_{1}z^{2}-u_{2}=0,~{}u_{1}\geq 0,~{}u_{2}\geq 0.$

Consider the feasible point
$(x^{*},y^{*},z^{*},u_{1}^{*},u_{2}^{*}):=(8,0,-3,0,1)$, which is actually a
globally optimal solution of (4.1). In what follows, we show that the MFCQ
holds at this point.

  * •

The gradient corresponding to the unique equality constraint at the point is
$\mathbf{g}_{0}:=(0,0,0,27,-1)^{T}$, which is a nonzero vector, and hence it
is linearly independent.

  * •

The active inequality constraints at the point include

$y\geq 0,\quad y-z-u_{1}(z^{3}-x)+u_{2}z\leq 0,\quad u_{1}\geq 0.$

The corresponding gradients at the point are respectively given by

$\displaystyle\mathbf{g}_{1}:=(0,-1,0,0,0)^{T},$
$\displaystyle\mathbf{g}_{2}:=(0,1,0,35,-3)^{T},~{}~{}~{}~{}$
$\displaystyle\mathbf{g}_{3}:=(0,0,0,-1,0)^{T}.$

Take a vector $d:=(0,1,0,1,27)^{T}$. It is trivial to verify that
$d^{T}\mathbf{g}_{0}=0$, $d^{T}\mathbf{g}_{1}<0$, $d^{T}\mathbf{g}_{2}<0$, and
$d^{T}\mathbf{g}_{3}<0$.

The above analysis indicates that (4.1) satisfies the MFCQ at its feasible
point $(8,0,-3,0,1)$.

Example 4.1 shows that (WDP) may satisfy the MFCQ at its feasible points. In
consequence, compared with MPEC, (WDP) is relatively easy to deal with.

###  4.2 Relations between WDP and MPEC

In this subsection, for simplicity, we take the upper constraint $x\in X$ and
the lower equality constraint $h(x,y)=0$ away from the original program (BP).
In this case, the corresponding MPEC becomes

$\displaystyle\min$ $\displaystyle F(x,y)$ s.t.
$\displaystyle\nabla_{y}L(x,y,u)=0,$ $\displaystyle 0\leq
u~{}\bot~{}g(x,y)\leq 0,$

where $L(x,y,u):=f(x,y)+u^{T}g(x,y)$, while (WDP) becomes

$\displaystyle\min$ $\displaystyle F(x,y)$ s.t. $\displaystyle
f(x,y)-L(x,z,u)\leq 0,$ $\displaystyle\nabla_{z}L(x,z,u)=0,~{}u\geq
0,~{}g(x,y)\leq 0.$

In what follows, we investigate the relations between the stationarity
conditions of the above problems. There is no difficulty to extend the
subsequent analysis to the general MPEC and the general (WDP).

By simple deduction, we have the following result immediately.

###### Theorem 4.1

The point $(x,y,u)$ is feasible to (4.2) if and only if $(x,y,y,u)$ is
feasible to (4.2).

Let $(\bar{x},\bar{y},\bar{u})$ be a feasible point of (4.2). We define the
following index sets:

$\displaystyle I_{0+}:=\\{i:g_{i}(\bar{x},\bar{y})=0,~{}\bar{u}_{i}>0\\},$
$\displaystyle I_{-0}:=\\{i:g_{i}(\bar{x},\bar{y})<0,~{}\bar{u}_{i}=0\\},$
$\displaystyle I_{00}:=\\{i:g_{i}(\bar{x},\bar{y})=0,~{}\bar{u}_{i}=0\\}.$

###### Definition 4.1

We call $(\bar{x},\bar{y},\bar{u})$ a strongly stationary point (or
S-stationary point) of (4.2) if there exists
$(\lambda^{g},\lambda^{u},\gamma)\in\mathbb{R}^{2p+m}$ such that

$\displaystyle\nabla_{x}F(\bar{x},\bar{y})+\nabla_{yx}^{2}L(\bar{x},\bar{y},\bar{u})\gamma+\nabla_{x}g(\bar{x},\bar{y})\lambda^{g}=0,$
(4.5)
$\displaystyle\nabla_{y}F(\bar{x},\bar{y})+\nabla_{yy}^{2}L(\bar{x},\bar{y},\bar{u})\gamma+\nabla_{y}g(\bar{x},\bar{y})\lambda^{g}=0,$
(4.6) $\displaystyle\nabla_{y}g(\bar{x},\bar{y})^{T}\gamma-\lambda^{u}=0,$
(4.7)
$\displaystyle\nabla_{y}L(\bar{x},\bar{y},\bar{u})=0,~{}g(\bar{x},\bar{y})\leq
0,~{}\bar{u}\geq 0,$ (4.8) $\displaystyle\lambda^{g}_{i}=0,~{}~{}i\in I_{-0},$
(4.9) $\displaystyle\lambda^{u}_{i}=0,~{}~{}i\in I_{0+},$ (4.10)
$\displaystyle\lambda^{g}_{i}\geq 0,~{}\lambda^{u}_{i}\geq 0,~{}~{}i\in
I_{00}.$ (4.11)

###### Remark 4.1

Other popular stationarity conditions for MPEC include the Mordukhovich
stationarity (or M-stationarity) and the Clarke stationarity (or
C-stationarity). Among these stationarities, the S-stationarity is the
strongest and the most favorable one in the study of MPEC.

###### Theorem 4.2

Let $(\bar{x},\bar{y},\bar{y},\bar{u})$ be a KKT point of (4.2). Then,
$(\bar{x},\bar{y},\bar{u})$ is an S-stationary point of (4.2).

Proof.  If $(\bar{x},\bar{y},\bar{y},\bar{u})$ is a KKT point of (4.2), there
exists $(\eta^{g},\eta^{u},\alpha,\beta)\in\mathbb{R}^{2p+1+m}$ such that

$\displaystyle\nabla_{x}F(\bar{x},\bar{y})+\nabla_{yx}^{2}L(\bar{x},\bar{y},\bar{u})\beta+\nabla_{x}g(\bar{x},\bar{y})(\eta^{g}-\alpha\bar{u})=0,$
(4.12)
$\displaystyle\nabla_{y}F(\bar{x},\bar{y})+\alpha\nabla_{y}f(\bar{x},\bar{y})+\nabla_{y}g(\bar{x},\bar{y})\eta^{g}=0,$
(4.13)
$\displaystyle-\alpha\nabla_{y}L(\bar{x},\bar{y},\bar{u})+\nabla_{yy}^{2}L(\bar{x},\bar{y},\bar{u})\beta=0,$
(4.14) $\displaystyle-\alpha
g(\bar{x},\bar{y})+\nabla_{y}g(\bar{x},\bar{y})^{T}\beta-\eta^{u}=0,$ (4.15)
$\displaystyle\nabla_{y}L(\bar{x},\bar{y},\bar{u})=0,$ (4.16) $\displaystyle
0\leq\alpha~{}\bot~{}\bar{u}^{T}g(\bar{x},\bar{y})\geq 0,$ (4.17)
$\displaystyle 0\leq\eta^{g}~{}\bot~{}g(\bar{x},\bar{y})\leq 0,$ (4.18)
$\displaystyle 0\leq\eta^{u}~{}\bot~{}\bar{u}\geq 0.$ (4.19)

Adding (4.13) and (4.14) together yields

$\displaystyle\nabla_{y}F(\bar{x},\bar{y})+\nabla_{yy}^{2}L(\bar{x},\bar{y},\bar{u})\beta+\nabla_{y}g(\bar{x},\bar{y})(\eta^{g}-\alpha\bar{u})=0.$
(4.20)

Set $\lambda^{g}:=\eta^{g}-\alpha\bar{u},~{}\lambda^{u}:=\eta^{u}+\alpha
g(\bar{x},\bar{y})$ and $\gamma:=\beta$. We obtain (4.5)-(4.8) from (4.12) and
(4.15)-(4.20) immediately. Next, we show (4.9)-(4.11).

  * •

If $i\in I_{-0}$, which means $g_{i}(\bar{x},\bar{y})<0$ and $\bar{u}_{i}=0$,
we have $\eta_{i}^{g}=0$ by (4.18) and hence
$\lambda_{i}^{g}=\eta_{i}^{g}-\alpha\bar{u}_{i}=0$. Namely, (4.9) holds.

  * •

If $i\in I_{0+}$, which means $g_{i}(\bar{x},\bar{y})=0$ and $\bar{u}_{i}>0$,
we have $\eta_{i}^{u}=0$ by (4.19) and hence
$\lambda_{i}^{u}=\eta_{i}^{u}+\alpha g_{i}(\bar{x},\bar{y})=0$. Namely, (4.10)
holds.

  * •

If $i\in I_{00}$, which means $g_{i}(\bar{x},\bar{y})=\bar{u}_{i}=0$, we have
$\lambda_{i}^{g}=\eta_{i}^{g}\geq 0$ and $\lambda_{i}^{u}=\eta_{i}^{u}\geq 0$
by (4.18) and (4.19) respectively. Namely, (4.11) holds.

This completes the proof.

The following example shows that the converse of Theorem 4.2 is not true.

###### Example 4.2

Consider the bilevel program

$\displaystyle\min$ $\displaystyle x^{2}-(2y+1)^{2}$ s.t. $\displaystyle x\leq
0,$ $\displaystyle y\in\arg\min\limits_{y}\\{(y-1)^{2}:3x-y-3\leq
0,~{}x+y-1\leq 0\\}.$

It is easy to see that $(0,1)$ is the unique globally optimal solution of
(4.2). Since the lower-level program is convex and satisfies the linear
constraint qualification everywhere, we can equivalently transform (4.2) into
the MPEC

$\displaystyle\min$ $\displaystyle x^{2}-(2y+1)^{2}$ s.t. $\displaystyle x\leq
0,~{}2(y-1)-u_{1}+u_{2}=0,$ $\displaystyle 0\leq u_{1}~{}\bot~{}3x-y-3\leq
0,~{}0\leq u_{2}~{}\bot~{}x+y-1\leq 0,$

or (WDP)

$\displaystyle\min$ $\displaystyle x^{2}-(2y+1)^{2}$ s.t. $\displaystyle
x\leq 0,~{}2(z-1)-u_{1}+u_{2}=0,$
$\displaystyle(y-1)^{2}-(z-1)^{2}-u_{1}(3x-z-3)-u_{2}(x+z-1)\leq 0,$
$\displaystyle u_{1}\geq 0,~{}u_{2}\geq 0,~{}3x-y-3\leq 0,~{}x+y-1\leq 0.$

Consider the feasible point $(0,1,0,0)$ of the MPEC (4.2). The S-stationarity
conditions at this point are

$\displaystyle\alpha+3\lambda_{1}^{g}+\lambda_{2}^{g}=0,~{}~{}-12+2\beta-\lambda_{1}^{g}+\lambda_{2}^{g}=0,$
$\displaystyle-\beta-\lambda_{1}^{u}=0,~{}~{}\beta-\lambda_{2}^{u}=0,~{}~{}\alpha\geq
0,$ $\displaystyle\lambda^{g}_{1}=0,~{}~{}\lambda^{g}_{2}\geq
0,~{}~{}\lambda^{u}_{2}\geq 0,$

where $\\{\alpha,\beta\\}$ are multipliers corresponding to the first two
constraints in (4.2) and $\\{\lambda^{u},\lambda^{g}\\}$ are multipliers
corresponding to the complementarity constraints. It is obvious that
$\alpha=0,\beta=6,\lambda^{u}=(-6,6),$ and $\lambda^{g}=(0,0)$ satisfy the
above conditions and hence $(0,1,0,0)$ is an S-stationary point of the MPEC
(4.2).

Next, we consider the feasible point $(0,1,1,0,0)$ of problem (4.2). The KKT
conditions at this point are

$\displaystyle\xi+3\mu_{1}^{g}+\mu_{2}^{g}=0,~{}~{}-12-\mu_{1}^{g}+\mu_{2}^{g}=0,~{}~{}2\eta=0,$
$\displaystyle-\eta+4\zeta-\mu_{1}^{u}=0,~{}~{}\eta-\mu_{2}^{u}=0,$
$\displaystyle\xi\geq 0,~{}~{}\zeta\geq
0,~{}~{}\mu^{g}_{1}=0,~{}~{}\mu^{g}_{2}\geq 0,~{}~{}\mu^{u}\geq 0,$

where $\\{\xi,\eta,\zeta\\}$ are multipliers corresponding to the first three
constraints in (4.2) and $\\{\mu^{u},\mu^{g}\\}$ are multipliers corresponding
to the others. Note that

$\mu^{g}_{1}=0\quad\Rightarrow\quad\mu^{g}_{2}=12\quad\Rightarrow\quad\xi=-12,$

which contradicts $\xi\geq 0$. Therefore, $(0,1,1,0,0)$ is not a KKT point of
(4.2).

We further have the following result.

###### Theorem 4.3

Let $(x,y,z,u)$ be a feasible point of (4.2). Then, the MFCQ fails to hold at
this point if $z=y$.

Proof.  The set of abnormal multipliers for (4.2) at $(x,y,z,u)$ is given by

$\displaystyle\mathcal{M}:=\left\\{\begin{array}[]{lll}&{0=\alpha(\nabla_{x}f(x,y)-\nabla_{x}L(x,z,u))}\\\
{}&{~{}~{}~{}~{}~{}+\nabla^{2}_{zx}L(x,z,u)\beta+\nabla_{x}g(x,y)\eta^{g}}\\\\[2.84526pt]
{}&{0=\alpha\nabla_{y}f(x,y)+\nabla_{y}g(x,y)\eta^{g}}\\\\[2.84526pt]
{(\alpha,\beta,\eta^{g},\eta^{u}):}&{0=-\alpha\nabla_{z}L(x,z,u)+\nabla^{2}_{zz}L(x,z,u)\beta}\\\
&{0=-\alpha g(x,z)+\nabla_{z}g(x,z)^{T}\beta-\eta^{u}}\\\\[2.84526pt]
{}&{\alpha\geq 0,~{}\alpha(f(x,y)-L(x,z,u))=0}\\\\[2.84526pt] {}&{\eta^{u}\geq
0,~{}u^{T}\eta^{u}=0,~{}\eta^{g}\geq
0,~{}g(x,y)^{T}\eta^{g}=0}\end{array}\right\\}.$

If $z=y$, it is not difficult to verify by the feasibility of $(x,y,y,u)$ to
(4.2) that $\big{(}1,0,u,-g(x,y)\big{)}\in\mathcal{M}$. Recall that, by [3,
Chapter 6.3], a nonzero abnormal multiplier exists if and only if the MFCQ
does not hold. Therefore, the MFCQ does not hold at $(x,y,y,u)$. This
completes the proof.

##  5 Relaxation scheme for WDP

Theorem 4.3 indicates that, although (WDP) may satisfy the MFCQ at its
feasible points, it is still difficult to solve directly in some cases.
Moreover, our numerical experiments given in Subsection 6.2 show that the
efficiency was not very high if we solved the bilevel program (BP) by solving
(WDP) directly. Based on these reasons, we present a relaxation scheme to deal
with (WDP) in this section.

Our strategy is to use the following problem to approximate (WDP):

$\displaystyle\mathrm{WDP}(t)\quad\min$ $\displaystyle F(x,y)$ s.t.
$\displaystyle x\in X,~{}g(x,y)\leq 0,~{}h(x,y)=0,$ $\displaystyle
f(x,y)-L(x,z,u,v)\leq t,$ $\displaystyle\nabla_{z}L(x,z,u,v)=0,~{}u\geq 0,$

where $t$ is a positive parameter. Obviously, all feasible points of (WDP) are
also feasible to the above problem and, in addition, the second inequality
constraint is not active any more at these points so that the popular
constraint qualifications may be easily satisfied. Therefore, we may solve
$\mathrm{WDP}(t)$ as a constrained optimization problem directly.

We first give some results related to constraint qualifications. To this end,
we introduce the following definition.

###### Definition 5.1

[6] The vectors $\\{a^{1},\cdots,a^{l}\\}\cup\\{b^{1},\cdots,b^{r}\\}$ are
called to be positive-linearly dependent if there exist
$\alpha\in\mathbb{R}^{l}_{+}$ and $\beta\in\mathbb{R}^{r}$ with
$(\alpha,\beta)\not=0$ such that

$\sum_{i=1}^{l}\alpha_{i}a^{i}+\sum_{i=1}^{r}\beta_{i}b^{i}=0.$

Otherwise, the set is called to be positive-linearly independent.

By [32, Proposition 1.8.2], the MFCQ is satisfied at a feasible point if and
only if the gradients of all active constraints at the point are positive-
linearly independent. By [33, Proposition 2.2], for given continuous functions
$\\{G_{1}(w),\cdots,G_{l}(w)\\}\cup\\{H_{1}(w),\cdots,H_{r}(w)\\}$, if they
are positive-linearly independent at some point $\bar{w}$, there exists a
neighborhood $U(\bar{w})$ such that they are positive-linearly independent at
any point in $U(\bar{w})$.

From the above introduction, we have the following result immediately.

###### Theorem 5.1

If $\mathrm{WDP}(t)$ satisfies the MFCQ at a feasible point
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$, there exists a neighborhood
$\bar{U}$ of $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ such that
$\mathrm{WDP}(t)$ satisfies the MFCQ at any feasible point in $\bar{U}$.

The above theorem can be extended to the following constraint qualification,
which is weaker than the MFCQ and has attracted lots of attention recently.

###### Definition 5.2

[33] Let $\bar{y}\in{Y}$ be a feasible point of the constrained optimization
problem (P) in Subsection 2.2. We say that (P) satisfies the constant positive
linear dependence (CPLD) at $\bar{y}$ if, for any
$I_{0}\subseteq\\{i:g_{i}(\bar{y})=0\\}$ and $J_{0}\subseteq\\{1,\cdots,q\\}$
such that $\\{\nabla g_{i}(\bar{y}),i\in I_{0}\\}\cup\\{\nabla
h_{j}(\bar{y}),j\in J_{0}\\}$ is positive-linearly dependent, there exists a
neighborhood $U(\bar{y})$ such that $\\{\nabla g_{i}(y),i\in I_{0};~{}\nabla
h_{j}(y),j\in J_{0}\\}$ is linearly dependent for any $y\in U(\bar{y})$.

###### Theorem 5.2

If $\mathrm{WDP}(t)$ satisfies the CPLD at a feasible point
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$, there exists a neighborhood
$\bar{U}$ of $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ such that
$\mathrm{WDP}(t)$ satisfies the CPLD at any feasible point in $\bar{U}$.

Proof.  For simplicity, we take the upper constraint $x\in X$ away from
$\mathrm{WDP}(t)$ and denote by
$\bar{w}:=(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$, $w:=(x,y,z,u,v)$. We
further denote by $G_{i}(w)~{}(i=0,1,\cdots,2p)$ all inequality constraint
functions and by $H_{i}(w)~{}(i=1,\cdots,m+q)$ all equality constraint
functions.

Suppose by contradiction that the conclusion is wrong. That is, there is a
sequence $\\{w^{k}\\}$ of feasible points tending to $\bar{w}$ such that
$\mathrm{WDP}(t)$ does not satisfy the CPLD at each $w^{k}$. Violation of CPLD
means that there exist $I_{0}^{k}\subseteq\\{i:G_{i}(w^{k})=0\\}$ and
$J_{0}^{k}\subseteq\\{1,\cdots,m+q\\}$ such that $\\{\nabla G_{i}(w^{k}),i\in
I_{0}^{k}\\}\cup\\{\nabla H_{j}(w^{k}),j\in J_{0}^{k}\\}$ is positive-linearly
dependent, but linearly independent in some points arbitrarily close to
$w^{k}$. Note that the number of subsets of the index sets
$\\{i:G_{i}(w^{k})=0\\}$ and $\\{1,\cdots,m+q\\}$ is finite. Taking a
subsequence if necessary, we may assume $I_{0}^{k}\equiv I_{0}$ and
$J_{0}^{k}\equiv J_{0}$. Therefore, there is another sequence
$\\{\tilde{w}^{k}\\}$ tending to $\bar{w}$, together with $\\{w^{k}\\}$,
satisfying

  * (i)

$\\{\nabla G_{i}(w^{k}),i\in I_{0}\\}\cup\\{\nabla H_{j}(w^{k}),j\in J_{0}\\}$
is positive-linearly dependent;

  * (ii)

$\\{\nabla G_{i}(\tilde{w}^{k}),i\in I_{0};~{}\nabla H_{j}(\tilde{w}^{k}),j\in
J_{0}\\}$ is linearly independent.

If $\\{\nabla G_{i}(\bar{w}),i\in I_{0}\\}\cup\\{\nabla H_{j}(\bar{w}),j\in
J_{0}\\}$ is positive-linearly dependent, by the CPLD assumption, there exists
a neighborhood which remains the linear dependence, which contradicts the
existence of $\\{\tilde{w}^{k}\\}$ in (ii). If $\\{\nabla G_{i}(\bar{w}),i\in
I_{0}\\}\cup\\{\nabla H_{j}(\bar{w}),j\in J_{0}\\}$ is positive-linearly
independent, by [33, Proposition 2.2], this property should remain in a
neighborhood, which contradicts the existence of $\\{w^{k}\\}$ in (i). As a
result, the conclusion is true. This completes the proof.

###### Remark 5.1

It is easy to see from the proofs that the above results related to constraint
qualifications remain true if $\mathrm{WDP}(t)$ is replaced by (WDP).

In what follows, we consider the limiting behavior of ${\mathrm{WDP}(t)}$ as
the approximation parameter $t$ tends to $0$. The following convergence result
related to globally optimal solutions is evident.

###### Theorem 5.3

Let $\\{t_{k}\\}\downarrow 0$ and $(x^{k},y^{k},z^{k},u^{k},v^{k})$ be a
globally optimal solution of ${\mathrm{WDP}(t_{k})}$ for each $k$. Then, every
accumulation point $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ of the sequence
$\\{(x^{k},y^{k},z^{k},u^{k},v^{k})\\}$ is globally optimal to ${\rm(WDP)}$.

Since ${\mathrm{WDP}(t)}$ is usually a nonconvex optimization problem, it is
necessary to investigate the limiting properties of its stationary points.

###### Theorem 5.4

Let $\\{t_{k}\\}\downarrow 0$ and $(x^{k},y^{k},z^{k},u^{k},v^{k})$ be a KKT
point of ${\mathrm{WDP}(t_{k})}$ for each $k$. Assume that
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ is an accumulation point of the
sequence $\\{(x^{k},y^{k},z^{k},u^{k},v^{k})\\}$. If (WDP) satisfies the CPLD
at $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$, then
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v})$ is a KKT point of ${\rm(WDP)}$.

Proof.  For simplicity, we take the upper constraint $x\in X$ away from (WDP)
and $\mathrm{WDP}(t)$. In addition, we denote

$\displaystyle\bar{w}:=(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v}),~{}~{}~{}w^{k}:=(x^{k},y^{k},z^{k},u^{k},v^{k}),~{}~{}~{}w:=(x,y,z,u,v),$
$\displaystyle F_{0}(w):=F(x,y),~{}~{}~{}G_{0}(w):=f(x,y)-L(x,z,u,v),$
$\displaystyle G_{i}(w):=g_{i}(x,y)~{}(1\leq i\leq
p),~{}~{}~{}G_{i}(w):=-u_{i-p}~{}(p+1\leq i\leq 2p),$ $\displaystyle
H_{i}(w):=h_{i}(x,y)~{}(1\leq i\leq
q),~{}~{}H_{i}(w):=\nabla_{z_{i-q}}L(x,z,u,v)~{}(q+1\leq i\leq q+m).$

Then, (WDP) and $\mathrm{WDP}(t_{k})$ become

$\displaystyle\min$ $\displaystyle F_{0}(w)$ s.t. $\displaystyle G_{i}(w)\leq
0,~{}i=0,1,\cdots,2p,$ $\displaystyle H_{i}(w)=0,~{}i=1,\cdots,q+m,$

and

$\displaystyle\min$ $\displaystyle F_{0}(w)$ s.t. $\displaystyle G_{0}(w)\leq
t_{k},$ $\displaystyle G_{i}(w)\leq 0,~{}i=1,\cdots,2p,$ $\displaystyle
H_{i}(w)=0,~{}i=1,\cdots,q+m.$

Obviously, $\bar{w}$ is a feasible point of (WDP) and, without loss of
generality, we may assume that the whole sequence $\\{w^{k}\\}$ converges to
$\bar{w}$.

Since $w^{k}$ is a KKT point of (5), it follows from [38, Lemma A.1] that
there exists
$(\lambda_{0}^{k},\lambda^{k},\mu^{k})\in\mathbb{R}\times\mathbb{R}^{2p}\times\mathbb{R}^{q+m}$
such that

$\displaystyle\nabla F_{0}(w^{k})+\lambda_{0}^{k}\nabla G_{0}(w^{k})+\nabla
G(w^{k})\lambda^{k}+\nabla H(w^{k})\mu^{k}=0,$
$\displaystyle\lambda_{0}^{k}(G_{0}(w^{k})-t_{k})=0,~{}~{}\lambda_{0}^{k}\geq
0,$ (5.3) $\displaystyle G(w^{k})^{T}\lambda^{k}=0,~{}~{}\lambda^{k}\geq 0,$

and the gradients

$\displaystyle\\{\nabla G_{i}(w^{k}):\lambda_{i}^{k}>0,0\leq i\leq
2p\\}\cup\\{\nabla H_{i}(w^{k}):\mu_{i}^{k}\not=0\\}$ (5.4)

are linearly independent. To show that $\bar{w}$ is a KKT point of (5), it is
sufficient to show the boundedness of the sequence of multipliers
$\\{\lambda_{0}^{k},\lambda^{k},\mu^{k}\\}$.

Assume by contradiction that $\\{\lambda_{0}^{k},\lambda^{k},\mu^{k}\\}$ is
unbounded. Taking a subsequence if necessary, we may assume

$\displaystyle\lim_{k\to\infty}\frac{(\lambda_{0}^{k},\lambda^{k},\mu^{k})}{\|(\lambda_{0}^{k},\lambda^{k},\mu^{k})\|}=(\lambda_{0}^{*},\lambda^{*},\mu^{*}).$
(5.5)

In particular, for every $k$ sufficiently large, we have

$\displaystyle\lambda_{i}^{*}>0\ \Rightarrow\
\lambda_{i}^{k}>0,\quad\mu_{i}^{*}\not=0\ \Rightarrow\ \mu_{i}^{k}\not=0.$
(5.6)

Dividing by $\|(\lambda_{0}^{k},\lambda^{k},\mu^{k})\|$ in (5.3) and taking a
limit, we have

$\displaystyle\lambda_{0}^{*}\nabla
G_{0}(\bar{w})+\sum_{\lambda_{i}^{*}>0}\lambda_{i}^{*}\nabla
G_{i}(\bar{w})+\sum_{\mu_{i}^{*}\not=0}\mu_{i}^{*}\nabla
H_{i}(\bar{w})=0,~{}~{}\lambda_{0}^{*}\geq 0.$ (5.7)

Since $\|(\lambda_{0}^{*},\lambda^{*},\mu^{*})\|=1$ by (5.5), (5.7) implies
that the gradients

$\displaystyle\\{\nabla G_{i}(\bar{w}):\lambda_{i}^{*}>0,0\leq i\leq
2p\\}\cup\\{\nabla H_{i}(\bar{w}):\mu_{i}^{*}\not=0\\}$

are positive-linearly dependent. Since problem (5) satisfies the CPLD at
$\bar{w}$, the gradients

$\displaystyle\\{\nabla G_{i}(w):\lambda_{i}^{*}>0,0\leq i\leq
2p\\}\cup\\{\nabla H_{i}(w):\mu_{i}^{*}\not=0\\}$

are linearly dependent in a neighborhood. This, together with (5.6),
contradicts the linear independence of the vectors in (5.4). Consequently,
$\\{\lambda_{0}^{k},\lambda^{k},\mu^{k}\\}$ is bounded. This completes the
proof.

##  6 Numerical experiments

In this section, we report our numerical experience in applying the proposed
approach to solve linear bilevel programs. In our experiments, we generated
tested problems randomly and made a numerical comparison of the (WDP) approach
with the popular MPEC approach by solving them respectively as nonlinear
optimization problems and through relaxation methods. In particular, all
experiments were implemented in MATLAB 9.8.0 and run on the same computer with
Windows Server 2019 Standard, Intel(R) Xeon(R) Platinum 8268, CPU $@$ 2.90 GHz
2.89 GHz (4 processors) and 2.00 TB memory.

###  6.1 Test problems

We designed a procedure to generate the following linear bilevel program:

$\displaystyle\min$ $\displaystyle c_{1}^{T}x+c_{2}^{T}y$ s.t. $\displaystyle
A_{1}x\leq b_{1},$ $\displaystyle
y\in\arg\min\limits_{y}\\{d_{2}^{T}y:A_{2}x+B_{2}y\leq b_{2},\ l_{b}\leq y\leq
u_{b}\\},$

where all coefficients $A_{1}\in\mathbb{R}^{p\times n}$,
$A_{2}\in\mathbb{R}^{q\times n}$, $B_{2}\in\mathbb{R}^{q\times m}$,
$b_{1}\in\mathbb{R}^{p}$, $b_{2}\in\mathbb{R}^{q}$, $c_{1}\in\mathbb{R}^{n}$,
and $\\{c_{2},d_{2}\\}\subset\mathbb{R}^{m}$ were generated sparsely by
_sprand_ in $[0,1]$ with density to be 0.1, the lower and upper bounds were
given by $l_{b}=-10*ones(m,1)$ and $u_{b}=10*ones(m,1)$ respectively. Since
the lower-level program is linear, (6.1) can be equivalently transformed into
the MPEC

$\displaystyle\min$ $\displaystyle c_{1}^{T}x+c_{2}^{T}y$ s.t. $\displaystyle
A_{1}x\leq b_{1},~{}d_{2}+B_{2}^{T}u_{1}+u_{2}-u_{3}=0,$ $\displaystyle 0\leq
u_{1}\perp A_{2}x+B_{2}y-b_{2}\leq 0,$ $\displaystyle 0\leq u_{2}\perp
y-u_{b}\leq 0,~{}0\leq u_{3}\perp y-l_{b}\geq 0$

or (WDP)

$\displaystyle\min$ $\displaystyle c_{1}^{T}x+c_{2}^{T}y$ s.t. $\displaystyle
A_{1}x\leq b_{1},~{}d_{2}+B_{2}^{T}u_{1}+u_{2}-u_{3}=0,$ $\displaystyle
d_{2}^{T}y\leq
d_{2}^{T}z+u_{1}^{T}(A_{2}x+B_{2}z-b_{2})+u_{2}^{T}(z-u_{b})+u_{3}^{T}(l_{b}-z),$
$\displaystyle u_{1}\geq 0,~{}u_{2}\geq 0,~{}u_{3}\geq 0,~{}A_{2}x+B_{2}y\leq
b_{2},~{}l_{b}\leq y\leq u_{b}.$

In our experiments, we generated 20 problems, which contain two groups:
Problems 1-10 were generated with $\\{n=50,p=40,m=60,q=50\\}$ and problems
11-20 were generated with $\\{n=50,p=40,m=100,q=80\\}$. We only adjusted the
numbers $m$ and $q$ because the lower-level variables and constraints are the
essential factors in solving bilevel programs.

Besides, when evaluating the numerical results, we mainly focused on three
aspects: the feasibility of the approximation solutions, the objective values,
and the CPU times. In particular, we adopted the following unified criterion
to measure the infeasibility for both MPEC and (WDP) in our tests:

$\displaystyle{\rm{Infeasibility}}$ $\displaystyle:=$
$\displaystyle\|\max(0,A_{1}x^{k}-b_{1})\|+\|\max(0,A_{2}x^{k}+B_{2}y^{k}-b_{2})\|$
$\displaystyle+\|\max(0,y^{k}-u_{b})\|+\|\max(0,l_{b}-y^{k})\|+|d_{2}^{T}y^{k}-h^{*}(x^{k})|,$

where $(x^{k},y^{k},u^{k})$ or $(x^{k},y^{k},z^{k},u^{k})$ is the current
approximation solution to the MPEC or (WDP), and
$h^{*}(x^{k}):=\min\\{d_{2}^{T}y:A_{2}x^{k}+B_{2}y\leq b_{2},~{}l_{b}\leq
y\leq u_{b}\\}$. The last term in the definition of Infeasibility is used to
approximate the distance from $y^{k}$ to the solution set of the lower-level
program, which is difficult to calculate in practice.

###  6.2 Solving WDP and MPEC as nonlinear programs

Table 1: Numerical results by solving WDP and MPEC as nonlinear programs

Problem | Method | Upper-Level Objective Value | Infeasibility | CPU Time
---|---|---|---|---
1 | MPCC | -3.1463e+12 | 2.1900e-11 | 1.4554e+02
| WDP | -3.3923e+08 | 5.6843e-14 | 6.4458e+01
2 | MPCC | -2.5857e+09 | 4.8005e-07 | 7.7537e+01
| WDP | -3.0284e+13 | 1.4604e+09 | 1.0761e+02
3 | MPCC | -3.7596e+12 | 9.0261e-05 | 2.4301e+02
| WDP | -2.2363e+22 | 3.2708e+10 | 2.3440e+02
4 | MPCC | -1.0616e+12 | 1.3316e+05 | 1.0887e+02
| WDP | -2.9227e+21 | 1.6209e+07 | 1.6791e+02
5 | MPCC | -1.1837e+10 | 1.7053e-13 | 4.9124e+02
| WDP | -6.3853e+17 | 8.1583e+05 | 9.1536e+01
6 | MPCC | -2.5239e+05 | 6.2759e+01 | 1.1706e+02
| WDP | -1.5364e+08 | 4.0963e-08 | 6.3872e+01
7 | MPCC | -1.0972e+10 | 2.6241e-06 | 1.1103e+02
| WDP | -2.3061e+09 | 3.0972e-08 | 3.7846e+01
8 | MPCC | -1.1108e+10 | 1.8574e-04 | 1.6481e+02
| WDP | -6.3271e+06 | 7.1054e-15 | 4.6037e+02
9 | MPCC | -3.5679e+11 | 4.4173e+02 | 1.3203e+02
| WDP | -3.8552e+12 | 2.3625e-04 | 9.3630e+01
10 | MPCC | -1.6421e+11 | 5.1916e+04 | 9.1017e+01
| WDP | -3.1135e+13 | 3.1974e-04 | 1.2583e+02
11 | MPCC | -8.8731e+09 | 4.1478e-06 | 3.5987e+02
| WDP | -4.9310e+12 | 4.4921e-06 | 3.6791e+02
12 | MPCC | -5.9250e+00 | 6.1676e+02 | 5.8209e+01
| WDP | -1.3248e+10 | 3.1468e+02 | 7.7642e+02
13 | MPCC | -3.7345e+10 | 1.8982e-06 | 6.2414e+02
| WDP | -7.3841e+10 | 2.2366e+02 | 4.4411e+02
14 | MPCC | -4.9281e+00 | 3.3777e+02 | 6.2954e+01
| WDP | -6.5233e+12 | 1.4604e-01 | 3.2927e+02
15 | MPCC | -6.4304e+08 | 3.5476e-08 | 6.7769e+02
| WDP | -3.3281e+10 | 1.2171e+01 | 2.8304e+02
16 | MPCC | -1.2443e+01 | 3.5345e+02 | 1.1613e+02
| WDP | -9.6905e+12 | 1.0489e+02 | 3.1826e+02
17 | MPCC | -7.2061e+09 | 8.1419e+00 | 8.5065e+02
| WDP | -2.5564e+11 | 5.9209e+02 | 4.0125e+02
18 | MPCC | -1.0965e+08 | 7.0720e-08 | 3.1691e+02
| WDP | -4.3347e+07 | 3.3506e-08 | 1.4159e+02
19 | MPCC | -4.2493e+00 | 5.9103e+02 | 5.2648e+01
| WDP | -7.2757e+15 | 1.9079e+02 | 7.5048e+02
20 | MPCC | -2.1158e+08 | 2.0894e-07 | 4.7101e+02
| WDP | -5.2877e+10 | 8.5212e-06 | 9.7612e+01

a Problems 1-10 were generated with $n=50,p=40;m=60,q=50$.
b Problems 11-20 were generated with $n=50,p=40;m=100,q=80$.

In the first part of our experiments, we solved both MPEC and (WDP) directly
by invoking the SQP algorithm of the solver _fmincon_. We chose all starting
points to be the origins and selected the required parameters, together with
the termination criterion, to default settings as set in the package. See
Table 1 for the numerical results on the tested problems.

There are two aspects different from what we had predicted before the
experiments. The first is related to the feasibility of the approximation
solutions. Since all lower-level programs are equivalent to their KKT
conditions for the tested problems, the MPEC approach should have greater
advantages in feasibility than (WDP), but the numerical results indicate that
this is not always the case, at least in our tests. In fact, from Table 1, we
can see that, if we set the tolerance for infeasibility to be $10^{-4}$, there
were 10 and 8 satisfactory cases among 20 problems for MPEC and (WDP)
respectively.

The second aspect is that the efficiency of solving linear (BP) through the
(WDP) approach directly was lower than we had expected before the experiments.
From Table 1, among the five cases where the infeasibility of both was lower
than $10^{-4}$ (that is, problems 1, 7, 11, 18, 20), there were only two cases
where the (WDP) approach had advantages over the MPEC approach in the
objective values. This may be caused by the increase of dimension of (WDP). On
the other hand, it reminds us that (WDP) is still difficult to solve directly
in many cases, although it may satisfy the MFCQ at its feasible points.

Delightfully, we observed that, among the five cases mentioned above, the
(WDP) approach had greater advantages than the MPEC approach in the CPU times.
Our experiments on relaxation methods given in the next subsection show that
the (WDP) approach had overall advantages over the MPEC approach in both
objective values and CPU times in our tests.

###  6.3 Solving (WDP) and MPEC by relaxation methods

Table 2: Numerical results for WDP and MPEC by relaxation methods Problem | Method | Upper-Level Objective Value | Infeasibility | CPU Time
---|---|---|---|---
1 | MPCC | -3.6778e+22 | 5.6843e-14 | 4.8954e+02
| WDP | -1.5743e+24 | 5.6843e-14 | 1.6175e+03
2 | MPCC | -2.1392e+11 | 0.0000e+00 | 9.5534e+02
| WDP | -1.0887e+18 | 0.0000e+00 | 8.8564e+02
3 | MPCC | -2.9363e+11 | 6.8764e-08 | 1.8591e+02
| WDP | -5.8726e+10 | 2.8422e-14 | 1.0515e+02
4 | MPCC | -2.5200e+08 | 0.0000e+00 | 1.8158e+02
| WDP | -1.7895e+10 | 2.7830e-11 | 1.1953e+03
5 | MPCC | -5.2419e+10 | 1.1377e-11 | 1.2217e+03
| WDP | -2.6210e+11 | 3.3307e-16 | 3.9862e+02
6 | MPCC | -3.3349e+10 | 1.6620e-11 | 1.0940e+02
| WDP | -1.7702e+15 | 5.6843e-14 | 1.1025e+02
7 | MPCC | -1.1298e+10 | 5.6843e-14 | 9.9915e+02
| WDP | -3.5136e+16 | 5.6843e-14 | 8.3334e+02
8 | MPCC | -1.4392e+16 | 0.0000e+00 | 3.4346e+03
| WDP | -3.3058e+10 | 1.1559e-11 | 1.4444e+03
9 | MPCC | -7.0267e+09 | 6.8374e-07 | 1.0926e+03
| WDP | -2.3466e+15 | 5.6843e-14 | 1.1597e+02
10 | MPCC | -3.4852e+17 | 2.8422e-14 | 3.0776e+03
| WDP | -2.3240e+17 | 2.8422e-14 | 8.2931e+01
11 | MPCC | -5.5652e+10 | 1.8271e-12 | 1.2597e+03
| WDP | -1.2063e+11 | 0.0000e+00 | 7.7513e+02
12 | MPCC | -6.6887e+10 | 9.2383e-07 | 1.4390e+03
| WDP | -2.7658e+11 | 2.2737e-13 | 2.7867e+03
13 | MPCC | -1.0222e+10 | 9.9172e-07 | 2.0430e+03
| WDP | -5.1128e+10 | 1.3984e-12 | 7.0663e+02
14 | MPCC | -1.6065e+10 | 1.7830e-12 | 2.3482e+03
| WDP | -7.3393e+11 | 5.6843e-14 | 2.5877e+03
15 | MPCC | -1.5798e+11 | 0.0000e+00 | 7.3459e+03
| WDP | -3.9495e+12 | 2.1346e-32 | 5.8045e+02
16 | MPCC | -1.0787e+11 | 1.2280e-10 | 1.9163e+03
| WDP | -3.3889e+08 | 5.6843e-14 | 3.1293e+02
17 | MPCC | -2.5465e+19 | 0.0000e+00 | 2.4133e+03
| WDP | -6.3969e+10 | 4.7536e-07 | 6.6342e+03
18 | MPCC | -2.7215e+10 | 7.4023e-13 | 1.0163e+03
| WDP | -3.2015e+11 | 5.6843e-14 | 2.1804e+03
19 | MPCC | -1.4700e+10 | 9.2752e-13 | 1.3563e+03
| WDP | -5.6359e+07 | 1.1369e-13 | 9.1482e+02
20 | MPCC | -7.6390e+10 | 4.2411e-07 | 4.5808e+02
| WDP | -1.5278e+10 | 3.1483e-09 | 2.2327e+03

In this subsection, we report our numerical results in solving (WDP) and MPEC
by relaxation methods. The relaxation method for (WDP) has been studied in
Section 5, while the relaxation scheme for MPEC employed here follows from the
work [36], by using

$\displaystyle\mathrm{MPEC}(t)\quad\min$ $\displaystyle c_{1}^{T}x+c_{2}^{T}y$
s.t. $\displaystyle A_{1}x\leq b_{1},~{}d_{2}+B_{2}^{T}u_{1}+u_{2}-u_{3}=0,$
$\displaystyle u_{1}\geq 0,~{}u_{2}\geq 0,~{}u_{3}\geq 0,~{}A_{2}x+B_{2}y\leq
b_{2},~{}l_{b}\leq y\leq u_{b},$ $\displaystyle
u_{1}^{T}(A_{2}x+B_{2}y-b_{2})+u_{2}^{T}(y-u_{b})+u_{3}^{T}(l_{b}-y)\leq t$

to approximate the MPEC (6.1), where $t>0$ is an approximation parameter.

We implemented Algorithm 1 given below to solve the tested problems. Note
that, for the linear bilevel programs, the feasibility of $\tilde{w}^{k}$ to
(WDP) or MPEC is evident.

Algorithm 1

Step 0 Choose $\tilde{x}^{0}$ such that $A_{1}\tilde{x}^{0}\leq b_{1}$, an
initial parameter $t_{0}>0$, a parameter $\sigma\in(0,1)$, and some accuracy
tolerances $\\{\epsilon_{\rm p},\epsilon_{\rm r},\delta_{\min}\\}$. Set
$k:=0$.

Step 1 Solve the lower-level program in (6.1) with $x=\tilde{x}^{k}$ by
_linprog_ to get $\tilde{y}^{k}$ and $\tilde{u}^{k}$. Set
$\tilde{w}^{k}:=(\tilde{x}^{k},\tilde{y}^{k},\tilde{y}^{k},\tilde{u}^{k})$ in
the case of (WDP) and
$\tilde{w}^{k}:=(\tilde{x}^{k},\tilde{y}^{k},\tilde{u}^{k})$ in the case of
MPEC. If $\tilde{w}^{k}$ satisfies a termination criterion with $\epsilon_{\rm
p}$ as the accuracy tolerance, stop. Otherwise, go to Step 2.

Step 2 Solve WDP$(t_{k})$ or MPEC$(t_{k})$ by _fmincon_ with $\tilde{w}^{k}$
as the starting point and $\epsilon_{\rm r}$ as the accuracy tolerance to
obtain an iterative $w^{k}:=(x^{k},y^{k},z^{k},u^{k})$ or
$w^{k}:=(x^{k},y^{k},u^{k})$. If $w^{k}$ satisfies the above termination
criterion, stop. Otherwise, go to Step 3.

Step 3 Set $\tilde{x}^{k+1}:=\tilde{x}^{k}$ and $t_{k+1}:=\max\\{\sigma
t_{k},\delta_{\min}\\}$. Let $k:=k+1$ and go to Step 1.

In our experiments, we chose $\tilde{x}^{0}$ to be the origins and set
$t_{0}=1$, $\sigma=10^{-1}$, $\epsilon_{\rm p}=10^{-8}$, and $\epsilon_{\rm
r}=\delta_{\min}=10^{-16}$. The termination criteria for both (WDP) and MPEC
were defined as the residuals of some kinds of optimality conditions. See
Table 2 for the numerical results on the tested problems.

From Table 2, we can see that there were 18 and 15 cases with sufficient
feasibility for the (WDP) and MPEC approaches respectively. Among the 14 cases
with sufficient feasibility for both, the (WDP) approach had overall
advantages over the MPEC approach in both objective values and CPU times. In
particular, compared with Table 1, the CPU times did not increase
significantly. This indicates that, at least in our tests, the relaxation
method based on the (WDP) reformulation was quite efficient.

##  7 Conclusions

We have shown that, under mild conditions such as pseudoconvexity, the bilevel
program (BP) is equivalent to the new single-level optimization problem (WDP)
in the globally or locally optimal sense. Unlike the existing single-level
reformulations (SP), (VP), and (LDP), (WDP) does not involve any function
without analytic expression. Compared with another existing single-level
reformulation MPEC, we have shown by an example that (WDP) may satisfy the
MFCQ at its feasible points, unlike the MPEC that fails to satisfy the MFCQ at
any feasible point, and hence (WDP) is relatively easy to deal with. Based on
our realization that (WDP) is still difficult to solve directly in some cases,
we have proposed a relaxation method for solving (WDP) and established a
convergence analysis. Comprehensive numerical experiments indicate that,
although solving (WDP) directly did not perform very well in our tests, the
relaxation method based on the (WDP) reformulation was quite efficient. As
future work, we will be devoted to analyzing the (WDP) reformulation more
deeply from theoretical and numerical aspects so as to develop more efficient
algorithms for the bilevel program (BP).

## References

  * [1] Bard, J.F.: Practical Bilevel Optimization: Algorithms and Applications. Kluwer, Dordrecht (1998)
  * [2] Ben-Israel, A., Mond, B.: What is invexity? J. Austral. Math. Soc. Ser. B. 28(1), 1–9 (1986)
  * [3] Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990)
  * [4] Colson, B., Marcotte, P., Savard, G.: An overview of bilevel optimization. Ann. Oper. Res. 153(1), 235–256 (2007)
  * [5] Craven, B.D., Mond, B.: Technical Note–On converse duality in nonlinear programming. Oper. Res. 19(4), 1075–1078 (1971)
  * [6] Davis, C.: Theory of positive linear dependence. Am. J. Math. 76(4), 733–746 (1954)
  * [7] Dempe, S., Dutta, J.: Is bilevel programming a special case of a mathematical program with complementarity constraints? Math. Program. 131(1–2), 37–48 (2012)
  * [8] Dempe, S., Zemkoho, A.B.: The bilevel programming problem: Reformulations, constraint qualifications and optimality conditions. Math. Program. 138(1–2), 447–473 (2013)
  * [9] Franceschi, L., Frasconi, P., Salzo, S., Grazzi, R., Pontil, M.: Bilevel programming for hyperparameter optimization and meta-learning. Proceedings of the 35th International Conference on Machine Learning, 1563–1572 (2018)
  * [10] Fukushima, M., Lin, G.H.: Smoothing methods for mathematical programs with equilibrium constraints. Proceedings of the International Conference on Informatics Research for Development of Knowledge Society Infrastructure, 206–213 (2004)
  * [11] Fukushima, M., Luo, Z.Q., Pang, J.S.: A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints. Comput. Optim. Appl. 10(1), 5–34 (1998)
  * [12] Izmailov, A.F., Pogosyan, A.L., Solodov, M.V.: Semismooth Newton method for the lifted reformulation of mathematical programs with complementarity constraints. Comput. Optim. Appl. 51(1), 199–221 (2012)
  * [13] Guo, L., Lin, G.H., Ye, J.J.: Solving mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 166(1), 234–256 (2015)
  * [14] Hanson, M., Mond, B.: Further generalizations of convexity in mathematical programming. J. Inform. Optim. Sci. 3(1), 25–32 (1982)
  * [15] Hoheisel, T., Kanzow, C., Schwartz, A.: Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. Math. Program. 137(1–2), 257–288 (2013)
  * [16] Jeroslow, R.G.: The polynomial hierarchy and a simple model for competitive analysis. Math. Program. 32(2), 146–164 (1985)
  * [17] Kanniappan, P.: Duality theorems for convex programming without constraint qualification. J. Austral. Math. Soc. 36(2), 253–266 (1984)
  * [18] Kunapuli, G., Bennett, K.P., Hu, J., Pang, J.S.: Classification model selection via bilevel programming. Optim. Method Softw. 23(4), 475–489 (2008)
  * [19] Lampariello, L., Sagratella, S.: Numerically tractable optimistic bilevel problems. Comput. Optim. Appl. 76(2), 277–303 (2020)
  * [20] Lin, G.H., Chen, X., Fukushima, M.: Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization. Math. Program. 116(1–2), 343–368 (2009)
  * [21] Lin, G.H., Fukushima, M.: Hybrid approach with active set identification for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 128(1), 1–28 (2006)
  * [22] Lin, G.H., Xu, M., Ye, J.J.: On solving simple bilevel programs with a nonconvex lower level program. Math. Program. 144(1–2), 277–305 (2014)
  * [23] Liu, R., Mu, P., Yuan, X., Zeng, S., Zhang, J.: A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. Proceedings of the 37th International Conference on Machine Learning, 6305–6315 (2020)
  * [24] Loridan, P., Morgan, J.: Weak via strong Stackelberg problem: New results. J. Glob. Optim. 8(3), 263–287 (1996)
  * [25] Luo, Z.Q., Pang, J.S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
  * [26] Mangasarian, O.L.: Pseudo-convex functions. J. Soc. Indust. Appl. Math. Ser. A Control. 3(2), 281–290 (1965)
  * [27] Mirrlees, J.A.: The theory of moral hazard and unobservable bevaviour: Part I. Rev. Econ. Stud. 66(1), 3–21 (1999)
  * [28] Osuna-Gómez, R., Rufián-Lizana, A., Ruiz-Canales, P.: Invex functions and generalized convexity in multiobjective programming. J. Optim. Theory Appl. 98(3), 651–661 (1998)
  * [29] Ouattara, A., Aswani, A.: Duality approach to bilevel programs with a convex lower level. Proceedings of the Annual American Control Conference, 1388–1395 (2018)
  * [30] Outrata, J.V.: On the numerical solution of a class of Stackelberg problems. ZOR–Methods Models Oper. Res. 34, 255–277 (1990)
  * [31] Pang, J.S., Fukushima, M.: Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints. Comput. Optim. Appl. 13(1–3), 111–136 (1999)
  * [32] Polak, E.: Optimization: Algorithms and Consistent Approximations. Springer-Verlag, New York (1997)
  * [33] Qi, L., Wei, Z.: On the constant positive linear dependence condition and its application to SQP methods. SIAM J. Optim. 10(4), 963–981 (2000)
  * [34] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Berlin (2004)
  * [35] Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25(1), 1–22 (2000)
  * [36] Scholtes, S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11(4), 918–936 (2001)
  * [37] Stackelberg, H.V.: The Theory of the Market Economy. Oxford University Press, Oxford (1952)
  * [38] Steffensen, S., Ulbrich, M.: A new relaxation scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 20(5), 2504–2539 (2010)
  * [39] Weir, T., Mond, B.: Pre-invex functions in multiple objective optimization. J. Math. Anal. Appl. 136, 29–38 (1988)
  * [40] Wolfe, P.: A duality theorem for nonlinear programming. Q. Appl. Math. 19(3), 239–244 (1961)
  * [41] Xu, M., Ye, J.J.: A smoothing augmented Lagrangian method for solving simple bilevel programs. Comput. Optim. Appl. 59(1–2), 353–377 (2014)
  * [42] Ye, J.J., Zhu, D.: New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches. SIAM J. Optim. 20(4), 1885–1905 (2010)
  * [43] Ye, J.J., Zhu, D.: Optimality conditions for bilevel programming problems. Optimization 33(1), 9–27 (1995)