Imane Benchouk, Khadra Nachi, Alain Zemkoho

Scholtes relaxation method for pessimistic bilevel optimization

Scholtes relaxation method for pessimistic bilevel optimization

Imane Benchouk Laboratory of Mathematics and its Applications, University
Oran1, Algeria<EMAIL_ADDRESS>
Khadra Nachi Laboratory of Mathematics and its Applications, University Oran1,
Algeria, ORCID: 0000-0003-3210-5643<EMAIL_ADDRESS>Alain Zemkoho
School of Mathematics, University of Southampton, United Kingdom, ORCID:
0000-0003-1265-4178<EMAIL_ADDRESS>https://www.southampton.ac.uk/maths/about/staff/abz1e14.page

When the lower-level optimal solution set-valued mapping of a bilevel
optimization problem is not single-valued, we are faced with an ill-posed
problem, which gives rise to the optimistic and pessimistic bilevel
optimization problems, as tractable algorithmic frameworks. However, solving
the pessimistic bilevel optimization problem is far more challenging than the
optimistic one; hence, the literature has mostly been dedicated to the latter
class of the problem. The Scholtes relaxation has appeared to be one of the
simplest and efficient way to solve the optimistic bilevel optimization
problem in its Karush-Kuhn-Tucker (KKT) reformulation or the corresponding
more general mathematical program with complementarity constraints (MPCC).
Inspired by such a success, this paper studies the potential of the Scholtes
relaxation in the context of the pessimistic bilevel optimization problem. To
proceed, we consider a pessimistic bilevel optimization problem, where all the
functions involved are at least continuously differentiable. Then assuming
that the lower-level problem is convex, the KKT reformulation of the problem
is considered under the Slater constraint qualification. Based on this KKT
reformulation, we introduce the corresponding version of the Scholtes
relaxation algorithm. We then construct theoretical results ensuring that a
sequence of global/local optimal solutions (resp. stationarity points) of the
aforementioned Scholtes relaxation converges to a global/local optimal
solution (resp. stationarity point) of the KKT reformulation of the
pessimistic bilevel optimization. The results are accompanied by technical
results ensuring that the Scholtes relaxation algorithm is well-defined or the
corresponding parametric optimization can easily be solved.

pessimistic bilevel optimization, KKT reformulation, Scholtes relaxation,
C-stationarity 90C26, 90C31, 90C33, 90C46

##  1 Introduction.

We consider the pessimistic bilevel optimization problem

$\underset{x\in X}{\min}\leavevmode\nobreak\ \varphi_{p}(x):=\underset{y\in
S(x)}{\max}\leavevmode\nobreak\ F(x,y),$ ($P_{p}$)

where $X:=\left\\{x\in\mathbb{R}^{n}\left|\;G(x)\leq 0\right.\right\\}$ and
$F\,:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}$ represent the
upper-level/leader’s feasible set and objective function, respectively. The
upper-level constraint function $G$ is defined from $\mathbb{R}^{n}$ to
$\mathbb{R}^{p}$. As for the set-valued map
$S:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$, it collects the optimal
solutions of the lower-level/follower’s problem for selections of the leader;
i.e., for all $x\in X$, we have

$S(x):=\underset{y\in K(x)}{\arg\min}\leavevmode\nobreak\ f(x,y)$ (1.1)

and assume throughout that $S(x)\neq\emptyset$ if $x\in X$ and
$S(x)=\emptyset$ otherwise. Note that in (1.1), the function
$f\,:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}$ represents the
lower-level/follower’s objective function, while the set-valued mapping
$K:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ describes the lower-
level/follower’s feasible points defined by

$K(x):=\left\\{y\in\mathbb{R}^{m}|\;g(x,y)\leq 0\right\\}$

with $g\,:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}^{q}$. We
assume that the functions $F$, $f$, $G$, and $g$ are continuously
differentiable. More general functions and feasible sets can be considered for
our analysis. But to focus our attention on the main ideas, we let these
differentiability assumptions hold throughout the paper.

Although problem ($P_{p}$) represents the most difficult class of the bilevel
optimization problem (see [2, 6, 8, 9, 19, 38]), it has only scantly been
addressed in the literature, in comparison to its optimistic counterpart,
which is at the centre of almost all the attention; see, e.g., the books [6,
13, 30] and references therein. However, problem ($P_{p}$) is more realistic
from the practical modelling perspective, given that it assumes that there is
no cooperation between the leader and the follower, in contrary to the
situation in the optimistic version of the problem. For a more detailed
analysis of the pessimistic and optimistic bilevel optimization problems and
the related structural challenges and differences between them, interested
readers are referred to the latter references.

In this paper, we consider the Karush-Kuhn-Tcuker (KKT) reformulation

$\underset{x\in X}{\min}\leavevmode\nobreak\
\psi_{p}(x):=\underset{(y,u)\in\mathcal{D}(x)}{\max}\leavevmode\nobreak\
F(x,y)$ (KKT)

of problem ($P_{p}$), where the set-valued mapping
$\mathcal{D}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}\times\mathbb{R}^{q}$
is given by

$\mathcal{D}(x):=\left\\{\left.(y,u)\in\mathbb{R}^{m+q}\right|\;\;\mathcal{L}(x,y,u)=0,\;\;u\geq
0,\;\,g(x,y)\leq 0,\;\,u^{\top}g(x,y)=0\right\\},$ (1.2)

where $\mathcal{L}(x,y,u):=\nabla_{y}L(x,y,u)$ with $L:(x,y,u)\rightarrow
L(x,y,u):=f(x,y)+u^{T}g(x,y)$ being the Lagrangian function associated to the
parametric optimization problem describing the lower-level optimal solution
set-valued mapping (1.1). Of course, as it is the case for any KKT
reformulation in bilevel optimization [2, 7, 11, 12], we will assume
throughout that the lower-level problem (1.1) is convex (i.e., the functions
$f$ and $g_{i}$, $i=1,\ldots,q$ are convex w.r.t. $y$) and a constraint
qualification (CQ) is satisfied. For this purpose, we will use the following
Slater CQ holds throughout:

$\forall x\in X,\;\;\exists
y(x)\in\mathbb{R}^{m}:\;g_{i}(x,y(x))<0,\;\;\forall i=1,\ldots,q.$ (SCQ)

Obviously, problem (KKT) is a special class of the minmax optimization problem
with parametric complementarity or equilibrium constraints in the inner
problem. In the sequel, we will refer to it as the KKT reformulation of the
pessimistic bilevel optimization problem ($P_{p}$).

Algorithm 1 Scholtes relaxation method for pessimistic bilevel optimization

Step 0: Choose $t^{0}$ and set $k:=0$.

Step 1: Solve problem (KKTt) for $t:=t^{k}$.

Step 2: Select $t^{k+1}<t^{k}$, set $k:=k+1$, and go to Step 1.

The KKT reformulation for the optimistic counterpart of problem ($P_{p}$) is
one of the standard approaches in the process of solving the problem. In the
context of the KKT reformulation of the optimistic bilevel program, one of the
most popular class of solution techniques is represented by relaxation
methods, which enables a mitigation of the difficulties caused by the presence
of the complementarity constraints present in the feasible set of problem
(KKT). Various relaxation methods have been proposed in the literature (see,
e.g., [18]) to address the KKT reformulation of the optimistic bilevel
optimization or more precisely, for the corresponding more general
mathematical program with complementary constraints (MPCC). The latter
publication provides a comparison of these relaxations and shows that the
Scholtes relaxation introduced in [33] is not only simpler, from its
construction, but it is also superior in terms of its numerical efficiency.
Motivated by this, we introduce the following Scholtes relaxation for the
pessimistic bilevel optimization problem ($P_{p}$) via its KKT reformulation
(KKT):

$\underset{x\in X}{\min}\leavevmode\nobreak\
\psi_{p}^{t}(x):=\underset{(y,u)\in\mathcal{D}^{t}(x)}{\max}F(x,y),$ (KKTt)

where, for all $t>0$, $\mathcal{D}^{t}$ represents the Scholtes perturbation
of the set-valued map in $\mathcal{D}$ (1.2)

$\mathcal{D}^{t}(x):=\left\\{(y,u)\in\mathbb{R}^{m+q}\left|\,\mathcal{L}(x,y,u)=0,\;\,u\geq
0,\;\;g(x,y)\leq 0,\;\,-u_{i}g_{i}(x,y)\leq t,\;\;i=1,...,q\right.\right\\},$
(1.3)

which is assumed to be nonempty throughout the paper.

We then introduce Algorithm 1, which can be seen as the Scholtes relaxation
algorithm for the KKT reformulation (KKT) of the pessimistic bilevel
optimization problem ($P_{p}$). Our primary goal in this paper is to provide a
theoretical framework ensuring that a sequence of global/local optimal
solutions $(x^{k})$ for problem (KKTt) for $t:=t^{k}$, computed through
Algorithm 1, converges to a global/local optimal solution of problem (KKT) as
$t^{k}\downarrow 0$. Considering the fact that problems (KKTt) and (KKT) are
both nonconvex, it will typically be more realistic to aim at computing their
stationary points. Hence, we also carefully address the case where the
sequence of points computed in Step 1 of Algorithm 1 are only stationary
points $(\zeta^{k})$ of problem (KKTt) for $t:=t^{k}$. And therefore, we
establish that this sequence can converge to a stationary point of (KKT) as
$t^{k}\downarrow 0$, under suitable assumptions. As we study these questions,
we also provide technical conditions ensuring that the problem solved in Step
1 (i.e., solving problem (KKTt) directly or computing its stationary points)
remains tractably solvable as we get close to a limit point of interest. It is
important to note that a global/local optimal solution of the KKT
reformulation (KKT) is equivalent to a global/local optimal solution of
problem ($P_{p}$) under mild assumptions [2].

Note that only a very small number of papers have investigated solution
algorithms to solve problem ($P_{p}$). As to the few works that we are aware
of, we can mention [8], which provides necessary optimality conditions for
various scenarios of the problem; the results there are extended to nonsmooth
functions in [10]. Various papers, including [21, 22], from the same authors
and their collaborators, propose approximations and stability results based on
perturbations in the value function constraint of the lower-level value
function reformulation of problem ($P_{p}$), in the case where the lower-level
feasible set is independent from $x$. In [35], a semi-infinite programming-
based algorithm is developed for a slightly general version of problem
($P_{p}$), also in the case where the lower-level feasible set is independent
from $x$. The article [4] proposes a two step process to compute a special
class of equilibrium for ($P_{p}$), which consists of solving the problem with
an off-the-shelf solver while for fixed values of $x$, the parametric
optimization problem defining $\varphi_{p}$ is solved with a certain BFO
(Brute-Force Optimizer). Finally, drawing inspiration from the optimistic
bilevel optimization literature, the paper [19] proposes a standard-type
approximation model for problem ($P_{p}$), where $F(x,y)$ is minimized w.r.t.
$(x,y)$ over a feasible set described in part by the optimal solution set of
the problem to minimize $F(x,y)$ w.r.t. $y$ subject to an approximation of the
lower-level optimal solution set-valued map $S$ (1.1). And finally, as already
mentioned above, [2] studies the relationship between problem ($P_{p}$) and
(KKT). Clearly, we are not aware of any attempt to solve problem ($P_{p}$)
from a perspective that is close to the one considered in this paper.

The remainder of the paper is organized as follows. In the next section, we
introduce basic concepts from variational analysis that will be useful in the
subsequent sections. Section 3 develops a framework to ensure that global
(resp. local) optimal solutions for problem (KKT) can be obtained from a
sequence of global (resp. local) optimal solutions of problem (KKTt). In
Section 4, we study the situation where Step 1 of Algorithm 1 instead computes
a special class of stationarity points for (KKTt) and show how the
corresponding sequence of points converges to a C-stationary point for problem
(KKT). As we proceed in Sections 3 and 4, examples are given to illustrate the
main results. Conclusions and some ideas for future investigations are
provided in Section 5.

##  2 Basic mathematical tools.

In this section, we briefly present some basic properties, mostly related to
variational analysis, which will be used throughout the paper; for more detail
on the main concepts, interested readers are referred to [25, 32], for
instance.

We start with some notation. We begin $\boldsymbol{B}_{\mathbb{R}^{n}}$ to
denote the unit ball in $\mathbb{R}^{n}$ centered at the origin of
$\mathbb{R}^{n}$. Given two subsets $A$ and $B$ of $\mathbb{R}^{n}$, their
Hausdorff distance $d_{H}(A,B)$ is given as

$d_{H}(A,B):=\max\leavevmode\nobreak\ \\{e(A,B),\;\,e(B,A)\\},$

where the excess $e(A,B)$ of $A$ over $B$ is defined by the formula

$e(A,B):=\underset{x\in A}{\sup}\leavevmode\nobreak\ d(x,B)$

with $d(x,B):=\underset{y\in B}{\inf}\leavevmode\nobreak\ d(x,y)$ denoting the
distance from $x$ to $B$, while considering the usual conventions
$e(\emptyset,B)=0$ and $e(A,\emptyset)=+\infty$ if $A\neq\emptyset$.
Furthermore, let

$\mathrm{dom}\,\Psi:=\left\\{x\in\mathbb{R}^{n}|\;\;\Psi(x)\neq\varnothing\right\\}\;\,\mbox{
and }\;\,\mbox{gph}\,\Psi:=\\{(x,y)\in\mathbb{R}^{n+m}|\;\;y\in\Psi(x)\\}$

denote the domain and graph of the set-valued mapping/multimap
$\Psi:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$.

###### Definition 2.1

A set-valued mapping $\Psi:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is
said to be

  * (i)

inner semicompact at $\bar{x}\in\mathrm{dom}\Psi$ if for any sequence
$(x_{k})_{k}\rightarrow\bar{x}$ there exists a sequence $(y_{k})$ with
$y_{k}\in\Psi(x_{k})$ such that $(y_{k})$ admits a convergent subsequence;

  * (ii)

inner semicontinuous at $(\bar{x},\bar{y})\in\mbox{gph }\Psi$ if for any
sequence $(x_{k})_{k}\rightarrow\bar{x}$ there exists a sequence $(y_{k})$
such that $y_{k}\in\Psi(x_{k})$ and $y_{k}\rightarrow\bar{y}$ or equivalently,
if $d(\bar{y},\Psi(x))\rightarrow 0$ whenever $x\rightarrow\bar{x}$.

  * (iii)

lower semicontinuous at $\bar{x}\in\mathrm{dom}\Psi$ (in Hausdorff sense) if,
for every $\varepsilon>0$, there exists a neighborhood $U$ of $\bar{x}$ such
that for any $x\in U$,

$e(\Psi(\bar{x}),\Psi(x))<\varepsilon\;\,\mbox{ or equivalently
}\;\,\Psi(\bar{x})\subset\Psi(x)+\varepsilon\boldsymbol{B}_{\mathbb{R}^{m}};$

  * (iv)

upper semicontinuous at $\bar{x}\in\mathrm{dom}\Psi$ (in Hausdorff sense) if,
for every $\varepsilon>0$, there exists a neighborhood $U$ of $\bar{x}$ such
that for any $x\in U$,

$e(\Psi(x),\Psi(\bar{x}))<\varepsilon\;\,\mbox{ or equivalently
}\;\,\Psi(x)\subset\Psi(\bar{x})+\varepsilon\boldsymbol{B}_{\mathbb{R}^{m}};$

  * (v)

Aubin continuous (or Lipschitz-like) around $(\bar{x},\bar{y})\in\mbox{gph
}\Psi$ if there are a constant $\tau>0$ and a neighborhood $U\times V$ of
$(\bar{x},\bar{y})$ such that for any $x,x^{\prime}\in U$,

$e(\Psi(x)\cap V,\Psi(x^{\prime}))\leq\tau\left\|x-x^{\prime}\right\|;$ (2.1)

i.e., for any $y\in\Psi(x)\cap V$, there exists
$y^{\prime}\in\Psi(x^{\prime})$ such that
$\left\|y-y^{\prime}\right\|\leq\tau\left\|x-x^{\prime}\right\|.$

Observe that the lower semicontinuity of
$\Psi:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ at $\bar{x}$ implies the
inner semicontinuity of $\Psi$ at $(\bar{x},\bar{y})$ for every
$\bar{y}\in\Psi(\bar{x})$. The Lipschitz-likeness of $\Psi$ around
$(\bar{x},\bar{y})$ clearly implies the inner semicontinuity of $\Psi$ at
$(\bar{x},\bar{y})$, which obviously implies the inner semicompactness of
$\Psi$ at $\bar{x}$. Moreover, any nonempty set-valued mapping that is
uniformly bounded around $\bar{x}$ is obviously inner semicompact at this
point. It is important to recall that the Lipschitz-likeness of a set-valued
mapping $\Psi:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ around a point
$(\bar{x},\bar{y})$ is ensured by the Mordukhovich criterion [23] (see also
Theorem 9.40 in [32]); i.e., $\Psi$ is Lipschitz-like around
$(\bar{x},\bar{y})$ if and only if it holds that

$D^{*}\Psi(\bar{x},\bar{y})(0)=\left\\{0\right\\},$

provided that the graph of $\Psi$ is closed. Here,
$D^{*}\Psi(\bar{x},\bar{y}):\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$
denotes the coderivative of $\Psi$ at $(\bar{x},\bar{y})$, defined by $w\in
D^{*}\Psi(\bar{x},\bar{y})(v)$ if and only if $(w,-v)\in
N_{\mathrm{gph}\Psi}(\bar{x},\bar{y})$ with
$N_{\mathrm{gph}\Psi}(\bar{x},\bar{y})$ being the limiting normal cone to
$\mbox{gph}\,\Psi$ at $(\bar{x},\bar{y})$; see relevant details in the latter
references.

In the sequel, we will also use the concept of Painlevé–Kuratowski
_outer/upper_ and _inner/lower_ limit for a set-valued mapping
$\Psi:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ at a point $\bar{x}$,
which are respectively defined by

$\begin{array}[]{rcl}\underset{x\longrightarrow\bar{x}}{\limsup}\leavevmode\nobreak\
\Psi(x)&:=&\left\\{y\in\mathbb{R}^{m}|\;\;\exists
x_{k}\rightarrow\bar{x},\;\;,y_{k}\rightarrow y\;\;\mbox{ with }\;y_{k}\\-\in
F(x_{k})\;\mbox{ for all }\;k\right\\},\\\
\underset{x\longrightarrow\bar{x}}{\liminf}\leavevmode\nobreak\
\Psi(x)&:=&\left\\{y\in\mathbb{R}^{m}|\;\;\forall
x_{k}\rightarrow\bar{x},\;\,\exists y_{k}\rightarrow y\;\mbox{ with
}\;y_{k}\\-\in F(x_{k})\;\mbox{ for all }\;k\right\\}.\end{array}$

Note that if $\underset{x\longrightarrow\bar{x}}{\limsup}\leavevmode\nobreak\
\Psi(x)=\underset{x\longrightarrow\bar{x}}{\liminf}\leavevmode\nobreak\
\Psi(x)$, then the Painlevé–Kuratowski limit is said to exist at $\bar{x}$ and
can simply be denoted by
$\underset{x\longrightarrow\bar{x}}{\lim}\leavevmode\nobreak\
\Psi(x)=\underset{x\longrightarrow\bar{x}}{\limsup}\leavevmode\nobreak\
\Psi(x)=\underset{x\longrightarrow\bar{x}}{\liminf}\leavevmode\nobreak\
\Psi(x)$.

Finally, we collect some basic properties that will be useful in the sequel.

###### Proposition 2.2

For any $x\in\mathbb{R}^{n}$, it holds that:

  1. 1.

$\mathcal{D}(x)$ and $\mathcal{D}^{t}(x)$ are closed ($t>0$);

  2. 2.

$\mathcal{D}^{t_{1}}(x)\subset\mathcal{D}^{t_{2}}(x)$ for any $t_{2}>t_{1}>0$;

  3. 3.

$\mathcal{D}(x)=$ $\underset{t>0}{\cap}\mathcal{D}^{t}(x)\ $ and so for all
$t>0$, $e(\mathcal{D}(x),\mathcal{D}^{t}(x))=0$ and
$\psi_{p}(x)\leq\psi^{t}_{p}(x)$;

  4. 4.

$\mathcal{D}(x)=$ $\underset{t\downarrow 0}{\lim}\mathcal{D}^{t}(x)$ in the
Painlevé-Kuratowski sense.

###### Proof 2.3

_Proof._ By continuity of the functions describing the sets $\mathcal{D}(x)$
and $\mathcal{D}^{t}(x)$, they are obviously closed. Assertions 2 is also
obvious and so is assertion 3 given that
$\mathcal{D}(x)\subset\mathcal{D}^{t}(x)$ for all $t>0$. Let us prove the
Painlevé -Kuratowski convergence (assertion 4); i.e.,

$\underset{t\downarrow 0}{\lim\inf}\,\mathcal{D}^{t}(x)=\mathcal{D}(x)=\text{
}\underset{t\downarrow 0}{\lim\sup}\,\mathcal{D}^{t}(x).$

Note that from assertion 3, it holds that $\mathcal{D}(x)\subset$
$\underset{t\rightarrow 0^{+}}{\lim\inf}\,\mathcal{D}^{t}(x)\subset$
$\underset{t\rightarrow 0^{+}}{\lim\sup}\,\mathcal{D}^{t}(x)$.

Conversely, taking $(y,u)\in$ $\underset{t\downarrow
0}{\lim\sup}\,\mathcal{D}^{t}(x)$, it follows that for a sequence
$(t_{k})\downarrow 0$, the point $(y,u)$ is a cluster point of a sequence in
$\mathcal{D}^{t_{k}}(x)$; i.e., there exists a sequence $(y^{k},u^{k})_{k}$
with $(y^{k},u^{k})\in\mathcal{D}^{t_{k}}(x)$ which converges (up to a
subsequence) to $(y,u)$. Thus, for any $k$, we have

$\begin{array}[c]{l}\mathcal{L}(x,y^{k},u^{k})=0,\;\;u_{i}^{k}\geq 0,\text{
}g_{i}(x,y^{k})\leq 0,\;\;-u_{i}^{k}g_{i}(x,y^{k})\leq
t_{k},\;\;i=1,...,q.\end{array}$

Applying the limit to this system, we get $(y,u)\in\mathcal{D}(x)$. Hence,
$\underset{t\rightarrow
0^{+}}{\lim\sup}\,\mathcal{D}^{t}(x)\subset\,\mathcal{D}(x).$ ∎

##  3 Computing global and local optimal solutions.

In this section, we assume that in Step 1 of Algorithm 1, we compute a global
or local optimal solution of problem (KKTt) for $t:=t_{k}$ in the process of
solving problem (KKT). Recall that a point $\bar{x}\in X$ is a local optimal
solution for ($P_{p}$) (resp. (KKT)) if there exists a neighborhood $U$ of
$\bar{x}$ such that the following condition holds:

$\forall x\in X\cap U:\;\varphi_{p}(\bar{x})\leq\varphi_{p}(x)\text{ \ (resp.
}\psi_{p}(\bar{x})\leq\psi_{p}(x)\text{)}.$ (3.1)

Similarly, $\bar{x}\in X$ will be said to be a global optimal solution for
($P_{p}$) (resp. (KKT)) if (3.1) holds with $U=\mathbb{R}^{n}$. Let us start
here by showing next that the objective function of problem (KKTt) for
$t:=t_{k}$ can converge to that of problem (KKT) as $t_{k}\downarrow 0$ with
$k\rightarrow\infty$.

###### Theorem 3.1

Let $t\mapsto\psi_{p}^{t}(x)$ be upper semicontinuous at $0$, for any
$x\in\mathbb{R}^{n}$ and let $t_{k}\downarrow 0$. Then for any
$x\in\mathbb{R}^{n}$, we have $\psi_{p}^{t_{k}}(x)\rightarrow\psi_{p}(x)$ as
$k\rightarrow\infty$.

###### Proof 3.2

_Proof._ It is obvious that for any $x\in\mathbb{R}^{n},$ the sequence
$(\psi_{p}^{t_{k}}(x))$ converges for any decreasing sequence $(t_{k})$ to
$0.$ Indeed, since $t_{k+1}\leq t_{k}$, we have
$\mathcal{D}^{t_{k+1}}(x)\subset\mathcal{D}^{t_{k}}(x)$ so that
$\psi_{p}^{t_{k+1}}(x)\leq\psi_{p}^{t_{k}}(x)$ for any $k$ and since the
sequence is bounded from below by $\psi_{p}(x)$, it converges. Hence,

$\psi_{p}(x)\leq\underset{k\rightarrow\infty}{\lim}\psi_{p}^{t_{k}}(x)=\lim\sup\psi_{p}^{t_{k}}(x)\leq\psi_{p}(x)\;\;\mbox{
for every }\;\;x\in\mathbb{R}^{n}.$ ∎

We now state the convergence of Algorithm 1 when problem (KKTt) is solved
globally as $t\downarrow 0$.

###### Theorem 3.3

Assume that the function $x\mapsto\psi_{p}(x)$ is lower semicontinuous at
$\bar{x}$, while the function $t\mapsto\psi_{p}^{t}(x)$ is upper
semicontinuous at $0$, for all $x\in\mathbb{R}^{n}$. Let $t_{k}\downarrow 0$
and $(x^{k})$ be a sequence such that the point $x^{k}$ is a global optimal
solution of problem (KKTt) for $t:=t_{k}$. If $x^{k}\rightarrow\bar{x}$ as
$k\rightarrow\infty$, then the point $\bar{x}$ is a global optimal solution of
problem (KKT).

###### Proof 3.4

_Proof._ Based on the definitions of $\psi_{p}^{t}$ and $\psi_{p}$, as well as
the fact that $x^{k}$ is a global optimal solution of problem (KKTt) for
$t:=t_{k}$, we have

$\psi_{p}(x^{k})\leq\psi_{p}^{t_{k}}(x^{k})\leq\psi_{p}^{t_{k}}(x)\text{ \ \
}\;\,\mbox{ for all }\;\,x\in X$

with $x^{k}\in X$ and the first inequality resulting from Proposition 2.2(3).
Since $x^{k}\rightarrow\bar{x}$ as $k\rightarrow\infty$, $\bar{x}\in X$ ($X$
being closed by continuity of $G$). Now, let $x\in X$. Given that $\psi_{p}$
is lower semicontinuous at $\bar{x}$ and $t\mapsto\psi_{p}^{t}(x)$ is upper
semicontinuous at $0$, for all $x\in\mathbb{R}^{n}$, we have the string of
inequalities

$\psi_{p}(\bar{x})\leq\text{
}\underset{k\rightarrow\infty}{\lim\inf}\,\psi_{p}(x^{k})\leq\text{
}\underset{k\rightarrow\infty}{\lim\inf}\,\psi_{p}^{t_{k}}(x)\leq\text{
}\underset{k\rightarrow\infty}{\lim\sup}\,\psi_{p}^{t_{k}}(x)\leq\psi_{p}(x).$
∎

Considering the fact that problems (KKT) and (KKTt) are both nonconvex, it is
more likely that in practice, a scheme to solve either problem would only
compute local optimal solutions. Hence, we next provide two scenarios where
iteratively solving (KKTt) can ensure that a local optimal solution for
problem (KKT) is obtained.

###### Theorem 3.5

Let $x\mapsto\psi_{p}(x)$ be lower semicontinuous at $\bar{x}$ and
$t\mapsto\psi_{p}^{t}(x)$ be upper semicontinuous at $0$, for all
$x\in\mathbb{R}^{n}$. Furthermore, let $t_{k}\downarrow 0$ and $(x^{k})$ be a
sequence such that $x^{k}$ is a local optimal solution of problem (KKTt) for
$t:=t_{k}$; i.e., there exists $r^{k}>0$ such that

$\psi_{p}^{t_{k}}(x^{k})\leq\psi_{p}^{t_{k}}(x)\text{ \ \ }\forall x\in X\cap
B(x^{k},r^{k}).$

If, additionally, $\underset{k\rightarrow\infty}{\lim\inf}\,r^{k}>0$ and
$x^{k}\rightarrow\bar{x}$ as $k\rightarrow+\infty$, then $\bar{x}$ is a local
optimal solution of (KKT).

###### Proof 3.6

_Proof._ Take $0<\bar{r}<\underset{k\rightarrow\infty}{\text{
}\lim\inf}\,r^{k}$ such that for $k$ large enough, $r^{k}>\bar{r}$. Let $x\in
X\cap B\left(\bar{x},\dfrac{\bar{r}}{2}\right)$. Since
$x^{k}\rightarrow\bar{x}$ as $k\rightarrow+\infty,$ $x^{k}\in
B\left(\bar{x},\dfrac{\bar{r}}{2}\right)$ for any $k$ large enough and hence
$x\in B(x^{k},r^{k})$ given that

$\left\|x-x^{k}\right\|\leq\left\|x-\bar{x}\right\|+\left\|\bar{x}-x^{k}\right\|<\bar{r}<r^{k}.$

Thus, $x\in X\cap B(x^{k},r^{k})$ and
$\psi_{p}^{t_{k}}(x^{k})\leq\psi_{p}^{t_{k}}(x)$ for any $k$ sufficiently
large. We can then conclude the proof by proceeding as in the proof of Theorem
3.3. ∎

###### Theorem 3.7

Let the function $\psi_{p}$ be lower semicontinuous at $\bar{x}$, and
$\bar{r}>0$ be such that $(t,u)\mapsto\psi_{p}^{t}(u)$ is upper semicontinuous
at $(0,x)$ for any $x\in B(\bar{x},\bar{r})$. Furthermore, let
$t_{k}\downarrow 0$, $r^{k}>0$, and $(x^{k})$ be a sequence of optimal
solutions of $(KKT_{t})$ for $t:=t^{k}$ in $X\cap B(x^{k},r^{k})$; i.e.,

$\psi_{p}^{t_{k}}(x^{k})\leq\psi_{p}^{t_{k}}(x)\text{ \ \ }\forall x\in X\cap
B(x^{k},r^{k}).$ (3.2)

If, additionally, it holds that for any $x\in X\cap B(\bar{x},\bar{r})$,

$d\left(x,\;\;X\cap
B(x^{k},r^{k})\right)\underset{k\longrightarrow\infty}{\longrightarrow}0,$
(3.3)

then the point $\bar{x}$ is a local optimal solution of problem (KKT).

###### Proof 3.8

_Proof._ Clearly $\bar{x}\in X$. Let $x\in X\cap B(\bar{x},\bar{r}).$ Since
$d(x,X\cap B(x^{k},r^{k}))\rightarrow 0$ as $k\rightarrow\infty$, one can pick
a subsequence $(u^{k})$ such that $u^{k}\in X\cap B(x^{k},r^{k})$ and
$u^{k}\rightarrow x$ as $k\rightarrow\infty.$ Thus,

$\psi_{p}(x^{k})\leq\psi_{p}^{t_{k}}(x^{k})\leq\psi_{p}^{t_{k}}(u^{k})$

from (3.2). Consequently, applying the lower semicontinuity of $\psi_{p}$ at
$\bar{x}$ and the upper semicontinuity of $\psi_{p}^{t}(u)$ at $(0,x)$, we get
the following chain of inequalities, which conclude the proof:

$\psi_{p}(\bar{x})\leq\text{
}\underset{k\rightarrow\infty}{\lim\inf}\psi_{p}(x^{k})\leq\text{
}\underset{k\rightarrow\infty}{\lim\inf}\psi_{p}^{t_{k}}(u^{k})\leq\text{
}\underset{k\rightarrow\infty}{\lim\sup}\psi_{p}^{t_{k}}(u^{k})\leq\psi_{p}(x).$
∎

One common point from all these three convergence results is the requirement
that $(x^{k})$ be a sequence of (global/local) optimal solutions of (KKTt) for
$t:=t^{k}$ as $t_{k}\downarrow 0$. Hence, it is important to look closely at a
framework that can ensure that such solutions actually exist or the
corresponding problems can be tractably solved. In particular, it would be
important to know under what conditions around the point of interest
$\bar{x}$, the function $\psi_{p}^{t}$ is lower semicontinuous or locally
Lipschitz continuous as $t\downarrow 0$. First, we recall conditions ensuring
that these properties are satisfied for a fixed value of $t>0$. In the sequel,
we use the notation

$\mathcal{S}_{p}(x):=\left\\{(y,u)\in\mathcal{D}(x)\left|\;F(x,y)\geq\psi_{p}(x)\right.\right\\}\;\mbox{
and
}\;\mathcal{S}_{p}^{t}(x):=\left\\{(y,u)\in\mathcal{D}^{t}(x)\left|\;F(x,y)\geq\psi_{p}^{t}(x)\right.\right\\}$

to describe the optimal solution set-valued mappings of the parametric
optimization problems associated to the optimal value functions $\psi_{p}$ and
$\psi^{t}_{p}$, respectively.

######  Theorem 3.9 ([3, 27])

For any number $t>0$, the function $\psi_{p}^{t}$ is

  * _(i)_

lower semicontinuous at $\bar{x}$ if $\mathcal{D}^{t}$ is lower semicontinuous
at $\bar{x}$;

  * _(ii)_

Lipschitz continuous around $\bar{x}$ if the set-valued mapping
$\mathcal{S}_{p}^{t}$ (resp. $\mathcal{D}^{t}$) is inner semicontinuous (resp.
Lipschitz-like) at (resp. around) $(\bar{x},(\bar{y},\bar{u}))$.

Recall that for problem (KKTt), with $t>0$, to admit an optimal solution, it
is at least necessary that its objective function $\psi^{t}_{p}$ be lower
semicontinuous. According to Theorem 3.9(i), the latter holds if the set-
valued mapping $\mathcal{D}^{t}$ is lower semicontinuous. Secondly,
considering the nonsmooth nature of $\psi^{t}_{p}$ ($t>0$), the local
Lipschitz continuity of this function would enable problem (KKTt) to be solved
by appropriate Lipschitz optimization tools from the literature; see, e.g.,
[25, 32] and references therein. It is therefore clear from Theorem 3.9(ii)
that for problem (KKTt) to be effectively solved as a Lipschitz optimization
problem, we need $\mathcal{S}_{p}^{t}$ (resp. $\mathcal{D}^{t}$) be inner
semicontinuous (resp. Lipschitz-like). Hence, an important question is to know
whether the satisfaction of these properties at the limit point of interest
can ensure that they hold at the relevant close points. To state a result
ensuring this, let us consider the following set-valued mappings:
$\mathcal{D}_{x}:t\rightrightarrows\mathcal{D}_{x}(t):=\mathcal{D}^{t}\mathcal{(}x\mathcal{)}$
for any $x\in\mathbb{R}^{n}$ and
$\mathcal{D}(\cdot,\cdot\mathcal{)}:(t,x)\rightrightarrows\mathcal{D(}t,x\mathcal{)}:=\mathcal{D}^{t}\mathcal{(}x\mathcal{)}$,
where $\mathcal{D}^{t}\mathcal{(}x\mathcal{)}$ is defined in (1.3) for $t>0$
and $\mathcal{D}^{0}(x)=\mathcal{D}(x)$ is given in (1.2).

###### Theorem 3.10

The following statements hold:

  * _(i)_

Let the set-valued mapping $\mathcal{D(\cdot)}$ be lower semicontinuous at
$\bar{x}$ and $\mathcal{D}(\cdot,\cdot\mathcal{)}$ be upper semicontinuous at
$(0,\bar{x})$. Then, there exists a neighborhood $U$ of the point $\bar{x}$
such that for $t\downarrow 0$, the set-valued mapping $\mathcal{D}^{t}$ is
lower semicontinuous at all $x\in U$.

  * _(ii)_

Let $\mathcal{D(\cdot)}$ be Lipschitz-like around
$(\bar{x},(\bar{y},\bar{u}))\in\mbox{gph }\mathcal{D}$ and
$\mathcal{D}_{x}\mathcal{(\cdot)}$ be upper semicontinuous at $0^{+}$ for any
$x$ around $\bar{x}$. Then, there exists a neighborhood $U\times V$ of
$(\bar{x},(\bar{y},\bar{u}))$ such that for $t\downarrow 0$, $\mathcal{D}^{t}$
is Lipschitz-like around all points $(x,(y,u))$ with $x\in U$ and $(y,u)\in
V\cap\mathcal{D}^{t}(x)$.

  * _(iii)_

Let $\mathcal{S}_{p}\mathcal{(\cdot)}$ _(_ resp.
$t\rightrightarrows\mathcal{S}_{p}^{t}(x)$_)_ be inner (resp. lower)
semicontinuous at $(\bar{x},(\bar{y},\bar{u}))\in\mbox{gph }\mathcal{S}_{p}$
_(_ resp. $0^{+}$ for any $x$ close to $\bar{x}$_)_. Then, there exists a
neighborhood $U\times V$ of $(\bar{x},(\bar{y},\bar{u}))$ such that for
$t\downarrow 0$, $\mathcal{S}_{p}^{t}\mathcal{(\cdot)}$ is inner
semicontinuous at all points $(x,(y,u))$ with $x\in U$ and $(y,u)\in
V\cap\mathcal{S}_{p}^{t}(x)$.

###### Proof 3.11

_Proof._ For (i), let $\varepsilon>0.$ Since
$\mathcal{D}(\cdot,\cdot\mathcal{)}$ is upper semicontinuous at $(0,\bar{x})$,
there exist $\alpha>0$ and $r_{1}>0$ such that for any $t\in(0,\alpha)$ and
$x\in B(\bar{x},r_{1})$, one has

$\mathcal{D}^{t}\mathcal{(}x\mathcal{)\subset
D(}\bar{x}\mathcal{)+}\frac{\varepsilon}{2}\mathbb{B}_{\mathbb{R}^{m+q}}$

and since $\mathcal{D(\cdot)}$ is lower semicontinuous at $\bar{x}$, there
exists $r_{2}>0$ such that for any $x^{\prime}$ in $B(\bar{x},r_{2})$,

$\mathcal{D}(\bar{x})\;\;\subset\;\;\mathcal{D}(x^{\prime})+\frac{\varepsilon}{2}\mathbb{B}_{\mathbb{R}^{m+q}}\;\;\subset\;\;\mathcal{D}^{t}(x^{\prime})+\frac{\varepsilon}{2}\mathbb{B}_{\mathbb{R}^{m+q}}\;\;\mbox{
for all }\;t>0.$

Hence, there exists a neighborhood $U$ of $\bar{x}$ such that for any
$x,x^{\prime}\in U$ and for any $t\in(0,\alpha)$,

$\mathcal{D}^{t}\mathcal{(}x\mathcal{)\;\;\subset\;\;D}^{t}\mathcal{(}x^{\prime}\mathcal{)\;+\;}\varepsilon\mathbb{B}_{\mathbb{R}^{m+q}}.$

This means that $\mathcal{D}^{t}\mathcal{(\cdot)}$ is lower semicontinuous at
all $x\in U$.

For (ii), note that as $\mathcal{D}$ is Lipschitz-like around
$(\bar{x},(\bar{y},\bar{u}))\in\mbox{gph}\,\mathcal{D}$, there are strictly
positive numbers $\tau$, $\delta_{1}$, and $r>0$ such that for any
$x,x^{\prime}\in B(\bar{x},\delta_{1})$, we have

$\mathcal{D}(x)\cap
B((\bar{y},\bar{u}),r)\subset\mathcal{D}(x^{\prime})+\tau\left\|x-x^{\prime}\right\|\mathbb{B}_{\mathbb{R}^{m+q}}$

and so

$\mathcal{D}(x)\cap
B((\bar{y},\bar{u}),r)\subset\mathcal{D}^{t}(x^{\prime})+\tau\left\|x-x^{\prime}\right\|\mathbb{B}_{\mathbb{R}^{m+q}}$
(3.4)

for all $t>0$. On the other hand, as
$t\rightrightarrows\mathcal{D}^{t}\mathcal{(}x\mathcal{)}$ is upper
semicontinuous at $0^{+}$ for all $x$ around $\bar{x}$, then there exists
$\delta_{2}>0$ so that for any $x\in B(\bar{x},\delta_{2})$ and
$\varepsilon>0$ there is a constant $\alpha>0$ such that

$\mathcal{D}^{t}(x)\subset\mathcal{D}(x)+\varepsilon\mathbb{B}_{\mathbb{R}^{m+q}}\text{
\ }\;\,\mbox{ for all }\;\,t\in(0,\alpha).$ (3.5)

Fix $(x,(y,u))$ such that $x\in B(\bar{x},\delta)$ with
$\delta=\min(\delta_{1},\delta_{2})$ and $(y,u)\in
B\left((\bar{y},\bar{u}),\dfrac{r}{3}\right)\cap\mathcal{D}^{t}(x).$ Let $U$
be a neighborhood of $x$ such that $U\subset B(\bar{x},\delta)$ and
$w,w^{\prime}\in U$ ($w\neq w^{\prime}$). Take $(z,v)\in\mathcal{D}^{t}(w)\cap
B\left((y,u),\dfrac{r}{3}\right)$ with $t\in(0,\alpha).$ From (3.5), there
exists for
$\varepsilon\in\left(0,\;\,\min(\dfrac{r}{3},\left\|w-w^{\prime}\right\|)\right),$
$(\hat{y},\hat{u})\in\mathcal{D}(w)$ such that

$\left\|(z,v)-(\hat{y},\hat{u})\right\|<\varepsilon$

so that $(\hat{y},\hat{u})\in\mathcal{D}(w)\cap B((\bar{y},\bar{u}),r).$ Now,
from (3.4), it holds that

$(\hat{y},\hat{u})\in\mathcal{D}(w)\cap
B((\bar{y},\bar{u}),r)\subset\mathcal{D}^{t}(w^{\prime})+\tau\left\|w-w^{\prime}\right\|\mathbb{B}_{\mathbb{R}^{m+q}}.$

Therefore, there exists
$\left(z^{\prime},\;\,v^{\prime})\in\mathcal{D}^{t}(w^{\prime}\right)$ such
that the inequality

$\left\|(\hat{y},\hat{u})-(z^{\prime},v^{\prime})\right\|\leq\tau\left\|w-w^{\prime}\right\|$

is satisfied. Hence, we have

$\displaystyle\left\|(z,v)-(z^{\prime},v^{\prime})\right\|$
$\displaystyle\leq\left\|(z,v)-(\hat{y},\hat{u})\right\|+\left\|(\hat{y},\hat{u})-(z^{\prime},v^{\prime})\right\|$
$\displaystyle<\varepsilon+\tau\left\|w-w^{\prime}\right\|<(1+\tau)\left\|w-w^{\prime}\right\|$

and so

$d((z,v),\mathcal{D}^{t}(w^{\prime}))\leq\left\|(z,v)-(z^{\prime},v^{\prime})\right\|<(1+\tau)\left\|w-w^{\prime}\right\|.$

Taking the supremum over $\mathcal{D}^{t}(w)\cap
B\left((y,u),\dfrac{r}{3}\right)$ yields

$e\left(\mathcal{D}^{t}(w)\cap
B\left((y,u),\frac{r}{3}\right),\;\mathcal{D}^{t}(w^{\prime})\right)\leq(1+\tau)\left\|w-w^{\prime}\right\|\;\;\mbox{
for all }\;\;t\in(0,\alpha).$

Finally, for (iii), consider $\varepsilon>0$ and $\gamma>0$ arbitrarily such
that $\gamma<\dfrac{\varepsilon}{3}$. Since $\mathcal{S}_{p}$ is inner
semicontinuous at $(\bar{x},(\bar{y},\bar{u}))$ with
$(\bar{y},\bar{u})\in\mathcal{S}_{p}(\bar{x})$, there exists $r_{1}>0$ such
that

$d\left((\bar{y},\bar{u}),\;\mathcal{S}_{p}(x)\right)<\gamma\;\;\mbox{ for all
}\;\;x\in B(\bar{x},r_{1}).$

From the lower semicontinuity of $\mathcal{S}_{p}^{t}(x)$ at $0^{+}$ for any
$x$ in $B(\bar{x},r_{2})$ ($r_{2}>0$), we have

$e(\mathcal{S}_{p}(x),\mathcal{S}_{p}^{t}(x))<\gamma.$

Fix now $x\in B(\bar{x},r)$ with $0<r<\min(r_{1},r_{2})$ and $(y,u)\in
V\cap\mathcal{S}_{p}^{t}(x)$ where $V:=B((\bar{y},\bar{u}),\gamma)$. Let
$x^{\prime}\in B(x,r^{\prime})$ with $0<r^{\prime}<r-\left\|x-\bar{x}\right\|$
so that $x^{\prime}\in B(\bar{x},r)$ and thus

$d\left((y,u),\mathcal{S}_{p}^{t}(x^{\prime})\right)\;\,\leq\;\,\left\|(y,u)-(\bar{y},\bar{u})\right\|+d((\bar{y},\bar{u}),\mathcal{S}_{p}(x^{\prime}))+e(\mathcal{S}_{p}(x^{\prime}),\mathcal{S}_{p}^{t}(x^{\prime}))\;<\;3\;\gamma\;<\;\varepsilon$

and the conclusion follows. ∎

Note that sufficient conditions for Lipschitz-likeness specifically tailored
to the set-valued mapping $\mathcal{D(\cdot)}$ are obtained in [14, Theorem
3.6] by rewriting this mapping as

$\mathcal{D(}x\mathcal{)}=\left\\{(y,u)\in\mathbb{R}^{m+q}|\;\;0\in
h(x,(y,u))+C\right\\}$

with

$h:(x,(y,u))\longmapsto h(x,(y,u)):=\begin{pmatrix}\mathcal{L}(x,y,u)\\\ u\\\
-g(x,y)\\\ \mathrm{diag}(u)g(x,y)\end{pmatrix}\;\;\mbox{ and
}\;\;C:=\left\\{0_{\mathbb{R}^{m}}\right\\}\mathbb{\times R}_{-}^{3q},$

where $\mathrm{diag}(u)$ denotes the diagonal matrix with the diagonal
elements being $u_{1},\ldots,u_{q}$.

We conclude this section with two illustrative examples.

###### Example 3.12

Consider an example of the pessimistic bilevel problem ($P_{p}$) with

$F(x,y):=y,\;\;X:=[0,\,1],\;\;K(x):=[0,\,1],\;\;\mbox{ and }\;\;f(x,y):=xy.$
(3.6)

Then for any $x\in\left]0,1\right],$ $S(x)=\left\\{0\right\\}$ and
$S(0)=\left[0,1\right]$ so that

$\varphi_{p}(x)=\left\\{\begin{array}[c]{l}0\text{ \ if }0<x\leq 1,\\\ 1\text{
\ if }x=0.\end{array}\right.$

Observe that any $\bar{x}\in\left]0,1\right]$ is optimal for (3.6).

The lower-level problem from (3.6) is convex, SCQ is clearly satisfied, and
therefore, the corresponding version of problem (KKT) is obtained with

$\mathcal{D}(x)=\left\\{\begin{array}[]{lll}\left\\{(0,(x,0))\right\\}&\text{if}&0<x\leq
1\\\
\left[0,1\right]\times\left\\{(0,0)\right\\}&\text{if}&x=0\end{array}\right.\;\;\mbox{
and
}\;\;\mathcal{S}_{p}(x)=\left\\{\begin{array}[]{lll}\left\\{(0,(x,0))\right\\}&\text{if}&0<x\leq
1,\\\ \left\\{(1,(0,0))\right\\}&\text{if}&x=0\end{array}\right.$

The regularized version of the pessimistic bilevel program (3.6) is given by

$\underset{\text{ \ \ \ }}{\underset{0\,\leq x\,\leq\,1\text{ }}{\min}\text{
}\psi^{t}_{p}(x):=}\underset{(y,u)\in\mathcal{D}^{t}(x)}{\max}y$

with the set-valued mapping $\mathcal{D}^{t}$ obtained as

$\mathcal{D}^{t}(x)=\left\\{(y,(u_{1},u_{1}-x))\in\left[0,1\right]\mathbb{\times
R}^{2}\;\;\left|\begin{array}[c]{l}u_{1}\geq x,\;\;u_{1}y\leq
t,\;\;-(u_{1}-x)(y-1)\leq t\end{array}\right.\right\\}$

for any $t\in(0,1]$ and $x\in\left[0,1\right]$. Thus, for $0<t<x\leq 1$,

$\mathcal{D}^{t}(x)=\left\\{(y,(u_{1},u_{1}-x))\;\;\;\left|\begin{array}[c]{c}\left(x\leq
u_{1}<t+x\wedge 0\leq y\leq\dfrac{t}{u_{1}}\right)\\\ \vee\\\ \left(t+x\leq
u_{1}\leq u_{1}^{\ast}(x)\wedge-\dfrac{t}{u_{1}-x}+1\leq
y\leq\dfrac{t}{u_{1}}\right)\end{array}\right.\right\\}$ (3.7)

while for $0<x\leq t\leq 1,$ we get

$\mathcal{D}^{t}(x)=\left\\{(y,(u_{1},u_{1}-x))\;\;\;\left|\begin{array}[c]{c}\left(x\leq
u_{1}\leq t\wedge 0\leq y\leq 1\right)\\\ \vee\\\ \left(t<u_{1}\leq t+x\wedge
0\leq y\leq\dfrac{t}{u_{1}}\right)\\\ \vee\\\ \left(t+x\leq u_{1}\leq
u_{1}^{\ast}(x)\wedge-\dfrac{t}{u_{1}-x}+1\leq
y\leq\dfrac{t}{u_{1}}\right)\end{array}\right.\right\\},$ (3.8)

where $u_{1}^{\ast}(x)=\dfrac{2t+x+\sqrt{4t^{2}+x^{2}}}{2}$ and thus

$\psi^{t}_{p}(x)=\left\\{\begin{array}[c]{c}\dfrac{t}{x}\text{ \ \ if }t\leq
x,\\\\[4.30554pt] 1\text{ \ \ if }x\leq t.\end{array}\right.$

As for $x=0$, we have
$\psi^{t}_{p}(0):=\underset{(y,u)\in\mathcal{D}^{t}(0)}{\max}y=1$ given that

$\mathcal{D}^{t}(0)=\left\\{(y,(u_{1},u_{1}))\;\;\;\left|\begin{array}[c]{c}\left(0\leq
u_{1}<t\wedge 0\leq y\leq 1\right)\\\ \vee\\\ \left(t\leq
u_{1}<2t\wedge-\dfrac{t}{u_{1}}+1\leq
y\leq\dfrac{t}{u_{1}}\right)\end{array}\right.\right\\}.$

Clearly, the regularized function $\psi^{t}_{p}$ is continuous everywhere on
the feasible set, in contrary to the function $\psi_{p}=\varphi_{p}$, which is
continuous only on $\left]0,1\right]$.

On the other hand, as we have

$\mathcal{S}^{t}_{p}(x)=\left\\{\begin{array}[]{lll}\left\\{(1,(u_{1},u_{1}))\left|\;\;0\leq
u_{1}\leq t\right.\right\\}&\mbox{ if }&x=0,\\\
\left\\{(y,u)\in\mathcal{D}^{t}(x)\left|\;\;\;y\geq\dfrac{t}{x}\right.\right\\}=\left\\{(\dfrac{t}{x},(x,0))\right\\}&\mbox{
if }&0<t\leq x\leq 1,\\\ \left\\{(y,u)\in\mathcal{D}^{t}(x)\left|\;\;y\geq
1\right.\right\\}=\left\\{(1,(u_{1},u_{1}-x))|\;\;x\leq u_{1}\leq
t\right\\}&\mbox{ if }&0<x\leq t\leq 1,\end{array}\right.$ (3.9)

let us show that all the assumptions in Theorem 3.10 hold. Fix
$\bar{x}\in\left]0,\,1\right]$. Obviously, the set-valued mapping
$\mathcal{D}(\cdot)$ (resp. $\mathcal{S}_{p}(\cdot)$) is Lipschitz-continuous
around $\bar{x}$, and hence, it is then lower (resp. inner) semicontinuous at
$\bar{x}$ (resp. any
($\bar{x},(\bar{y},\bar{u}))\in\mbox{gph}\mathcal{S}_{p}$). Given now
$\varepsilon>0$ and choose $0<\delta<\dfrac{\varepsilon}{2}$ for $0<\bar{x}<1$
(resp. $\bar{x}=1$) such that
$U:=\left]\bar{x}-\delta,\bar{x}+\delta\right[\subset\left]0,1\right[$ (resp.
$\left]1-\delta,1\right]\subset\left]0,1\right][$). Taking $x\in U$ and
$(y,u)\in\mathcal{D}_{x}(t)$ with $0<t<\bar{x}-\varepsilon$, we have

$(y,u):=(y,(u_{1},u_{1}-x))=(0,(\bar{x},0))+(y,(u_{1}-\bar{x},u_{1}-x))$

with the string of conditions

$\left(0\leq u_{1}-x<t\wedge 0\leq y\leq\dfrac{t}{u_{1}}\right)\vee\left(t\leq
u_{1}-x\leq u_{1}^{\ast}(x)-x\wedge-\dfrac{t}{u_{1}-x}+1\leq
y\leq\dfrac{t}{u_{1}}\right).$

Since $u_{1}^{\ast}(x)-x\leq 2t$ and $u_{1}^{\ast}(x)-\bar{x}\leq 2t+\delta$
(resp. $2t$) for $0<\bar{x}<1$ (resp. $\bar{x}=1$), it follows that

$\left|u_{1}-\bar{x}\right|\leq
2t+\delta\,\,(\text{resp.}\,\,2t)\,\,\wedge\,\,0\leq u_{1}-x\leq
2t\,\,\wedge\,\,0\leq y\leq\dfrac{t}{\bar{x}-\delta}.$

Hence, for
$0<t<\min\,\left(\bar{x}-\varepsilon,(\bar{x}-\delta)\varepsilon,\;\dfrac{\varepsilon}{4}\right)$
, we get $(y,(u_{1}-\bar{x},u_{1}-x))\in\varepsilon B_{\mathbb{R}^{3}}$ and so

$(y,(u_{1},u_{1}-x))\in\mathcal{D}(\bar{x})+\varepsilon B_{\mathbb{R}^{3}}$

such that for any $t$ in a neighborhood of $0^{+}$ and any $x\in U$,

$\mathcal{D}^{t}(x)\subset\mathcal{D}(\bar{x})+\varepsilon
B_{\mathbb{R}^{3}}.$

This means that
$\mathcal{D}(\cdot,\cdot):t\rightrightarrows\mathcal{D}(t,x):=\mathcal{D}^{t}(x)$
is upper semicontinuous at $(0^{+},\bar{x})$. Similarly, we can show that the
set-valued mapping
$\mathcal{D}_{x}(\cdot):t\rightrightarrows\mathcal{D}_{x}(t)\,:=\mathcal{D}^{t}(x)$
is upper semicontinuous at $0^{+}$ for any $x\in\left[0,1\right]$. That is,
for any $x\in\left[0,1\right]$, $\varepsilon>0$, and $t$ in a neighborhood of
$0^{+}$, it holds that

$\mathcal{D}^{t}(x)\subset\mathcal{D}(x)+\varepsilon B_{\mathbb{R}^{3}}.$

Finally, let us show that the set-valued mapping
$t\rightrightarrows\mathcal{S}^{t}_{p}(x)$ is lower semicontinuous at $0^{+}$
for any $x$ close to $\bar{x}$. Indeed, since for any $x\in\left]0,1\right]$
and $0<t<x$, we have

$(0,(x,0))=\left(\frac{t}{x},(x,0)\right)-\left(\frac{t}{x},(0,0)\right)\in\mathcal{S}^{t}_{p}(x)+\frac{t}{x}B_{\mathbb{R}^{3}},$

it follows that for all $\varepsilon>0$ and $t$ in a neighborhood of $0^{+}$,
$\mathcal{S}_{p}(x)\subset\mathcal{S}^{t}_{p}(x)+\varepsilon
B_{\mathbb{R}^{3}}$. ∎

###### Example 3.13

Here, we slightly modify the problem from the previous example so that

$F(x,y):=x+y,\;\;X:=[-1,\,1],\;\;f(x,y):=xy,\;\mbox{ and }\;K(x):=[0,\,1].$
(3.10)

We can easily check that

$S(x)=\left\\{\begin{array}[c]{l}\left\\{0\right\\}\text{ \ \ if }0<x\leq
1,\\\ \left\\{1\right\\}\text{ \ \ if }-1\leq x<0,\\\ \left[0,1\right]\text{ \
if }x=0,\end{array}\right.\;\;\mbox{ and
}\;\;\varphi_{p}(x)=\left\\{\begin{array}[c]{l}x\text{ \ \ \ \ \ \ \ if
}\,\,0<x\leq 1,\\\ x+1\text{\ \ \ if }-1\leq x\leq 0.\end{array}\right.$

and the point $\bar{x}=-1$ is the global optimal solution for the problem
(3.10). The coresponding version of problem (KKT) can be obtained with

$\mathcal{D}(0)=\left[0,\,1\right]\times\left\\{(0,0)\right\\}\;\,\mbox{ and
}\;\,\mathcal{D}(x)=\left\\{\begin{array}[]{lll}\left\\{(0,x,0)\right\\}&\text{if}&0<x\leq
1,\\\\[4.30554pt] \left\\{(1,\,0,\,-x)\right\\}&\text{if}&-1\leq
x<0,\end{array}\right.$

that is, $\psi_{p}=\varphi_{p}$ while
$\mathcal{S}_{p}(x)=\left\\{(1,0,0)\right\\}$ if $x=0$ and
$\mathcal{S}_{p}(x)=\mathcal{D}(x)$ for $x\in X\setminus\\{0\\}$.

The regularized version (KKTt) of the problem can be written with
$\mathcal{D}^{t}(x)$ as in (3.7)–(3.8) for any $x\in\left[0,1\right]$ while
for $-1\leq x\leq-t<0$, we have

$\mathcal{D}^{t}(x)=\left\\{(y,(u_{1},u_{1}-x))\;\;\;\left|\begin{array}[c]{c}\left(0\leq
u_{1}<t\wedge-\dfrac{t}{u_{1}-x}+1\leq y\leq 1\right)\\\ \vee\\\ \left(t\leq
u_{1}\leq u_{1}^{\ast}(x)\wedge-\dfrac{t}{u_{1}-x}+1\leq
y\leq\dfrac{t}{u_{1}}\right)\end{array}\right.\right\\}$

and for $-1\leq-t\leq x<0$, we get

$\mathcal{D}^{t}(x)=\left\\{(y,(u_{1},u_{1}-x))\;\;\;\left|\begin{array}[c]{c}\left(0\leq
u_{1}\leq t+x\wedge 0\leq y\leq 1\right)\\\ \vee\\\ \left(t+x<u_{1}\leq
t\wedge-\dfrac{t}{u_{1}-x}+1\leq y\leq 1\right)\\\ \vee\\\ \left(t\leq
u_{1}\leq u_{1}^{\ast}(x)\wedge-\dfrac{t}{u_{1}-x}+1\leq
y\leq\dfrac{t}{u_{1}}\right)\end{array}\right.\right\\}.$

And subsequently, we have

$\psi^{t}_{p}(x)=\left\\{\begin{array}[c]{c}x+\dfrac{t}{x}\text{ \ \ if }t\leq
x,\\\\[4.30554pt] x+1\text{ \ \ if }x<t,\end{array}\right.\;\;\mbox{ and
}\;\;\mathcal{S}^{t}_{p}(x)=\left\\{\begin{array}[]{lll}\left\\{(1,(u_{1},u_{1}-x))\left|\;\,0\leq
u_{1}\leq t\right.\right\\}&\text{if}&x\in\left[-1,0\right[,\\\\[4.30554pt]
\left\\{(1,(u_{1},u_{1}))\left|\;\,0\leq u_{1}\leq
t\right.\right\\}&\text{if}&x=0,\\\\[4.30554pt] \mbox{same as in
}\;\;\eqref{tS}&\text{if}&0<x\leq 1.\end{array}\right.$

Clearly, the regularized function $\psi^{t}_{p}$ is continuous everywhere on
the feasible set, for $t>0$. ∎

##  4 Computing C-stationary points.

Our basic assumption in this section is that at Step 1 of Algorithm 1, we are
computing stationary points of (KKTt) for $t:=t_{k}$, with the aim to
construct a framework ensuring that the resulting sequence converges to a
C-stationary point of problem (KKT). To proceed, we first introduce the
C-stationarity concept of the latter problem.

###### Definition 4.1

A point $\bar{x}$ will be said to be C-stationary point for ($P_{p}$) if there
exists a vector $\left(\bar{y},\bar{u},\alpha,\beta,\gamma\right)$ such that
we have the relationships

$\displaystyle(\bar{x},\bar{y},\bar{u})\in\mbox{gph}\,\mathcal{S}_{p},$ (4.1)
$\displaystyle\nabla_{x}F(\bar{x},\bar{y})+\sum\limits_{i=1}^{p}\alpha_{i}\nabla
G_{i}(\bar{x})+\sum\limits_{l=1}^{m}\beta_{l}\nabla_{x}\mathcal{L}_{l}(\bar{x},\bar{y},\bar{u})+\sum\limits_{i=1}^{q}\gamma_{i}\nabla_{x}g_{i}(\bar{x},\bar{y})=0,$
(4.2)
$\displaystyle\nabla_{y}F(\bar{x},\bar{y})+\sum\limits_{l=1}^{m}\beta_{l}\nabla_{y}\mathcal{L}_{l}(\bar{x},\bar{y},\bar{u})+\sum\limits_{i=1}^{q}\gamma_{i}\nabla_{y}g_{i}(\bar{x},\bar{y})=0,$
(4.3) $\displaystyle\alpha\geq 0,\;\;G(\bar{x})\leq
0,\;\;\alpha^{T}G(\bar{x})=0,$ (4.4)
$\displaystyle\nabla_{y}g_{\nu}(\bar{x},\bar{y})\beta=0,\;\;\gamma_{\eta}=0,$
(4.5) $\displaystyle\forall
i\in\theta:\;\;\,\gamma_{i}\sum\limits_{l=1}^{m}\beta_{l}\nabla_{y_{l}}g_{i}(\bar{x},\bar{y})\geq
0,$ (4.6)

where $\gamma_{\eta}:=(\gamma_{i})_{i\in\eta}$,
$\nabla_{y}g_{\nu}(\bar{x},\bar{y})\beta$ denotes the vector with components
$\sum\limits_{l=1}^{m}\beta_{l}\nabla_{y_{l}}g_{i}(\bar{x},\bar{y})$ with
$i\in\nu$, and the index sets $\eta$, $\theta$, and $\nu$ are respectively
defined as follows:

$\begin{array}[]{rlrll}\eta&:=&\eta(\bar{x},\bar{y},\bar{u})&:=&\left\\{i\in\left\\{1,...,q\right\\}\left|\;\;\bar{u}_{i}=0,\text{
}g_{i}(\bar{x},\bar{y})<0\right.\right\\},\\\
\theta&:=&\theta(\bar{x},\bar{y},\bar{u})&:=&\left\\{i\in\left\\{1,...,q\right\\}\left|\;\;\bar{u}_{i}=0,\text{
}g_{i}(\bar{x},\bar{y})=0\right.\right\\},\\\
\nu&:=&\nu(\bar{x},\bar{y},\bar{u})&:=&\left\\{i\in\left\\{1,...,q\right\\}\left|\;\;\bar{u}_{i}>0,\text{
}g_{i}(\bar{x},\bar{y})=0\right.\right\\}.\end{array}$

Similarly, we can define the M- and S-stationarity by replacing condition
(4.6) by

$\begin{array}[]{c}\forall
i\in\theta:\;\;\,(\gamma_{i}<0\wedge\sum\limits_{l=1}^{m}\beta_{l}\nabla_{y_{l}}g_{i}(\bar{x},\bar{y})<0)\vee\gamma_{i}\sum\limits_{l=1}^{m}\beta_{l}\nabla_{y_{l}}g_{i}(\bar{x},\bar{y})=0\\\
\left(\mbox{resp. }\;\,\forall i\in\theta:\;\;\,\gamma_{i}\leq
0\wedge\sum\limits_{l=1}^{m}\beta_{l}\nabla_{y_{l}}g_{i}(\bar{x},\bar{y})\leq
0\right).\end{array}$

Obviously, the following string of implications is obtained directly from
these definitions:

$S\text{-stationarity }\Longrightarrow\text{ }M\text{-stationarity
}\Longrightarrow\text{ }C\text{-stationarity.}$

These concepts were introduced in [8] in the context of ($P_{p}$). Further
stationarity concepts for pessimistic bilevel optimization and relevant
details can be found in the latter reference. As for optimistic bilevel
programs and the closely related MPCCs, see [11, 12, 18] and references
therein.

Next, we recall a result, which provides a framework ensuring that a local
optimal solution of problem ($P_{p}$) satisfies the C-stationarity conditions.
To proceed, we need to introduce some assumptions. First, the upper-level
regularity condition will be said to hold at $\bar{x}$ if

$\left[\nabla G(\bar{x})^{\top}\alpha=0,\;\;\alpha\geq
0,\;\;\alpha^{\top}G(\bar{x})=0\right]\;\;\Longrightarrow\;\;\alpha=0.$ (4.7)

Obviously, this regularity concept corresponds to the Mangasarian–Fromovitz
constraint qualification for the upper-level constraint. For the remaining
qualification conditions, we introduce the C-qualification conditions at
$(\bar{x},\bar{y},\bar{u})$ are defined by

$\displaystyle(A_{1}^{c})\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ }(\beta,\gamma)$
$\displaystyle\in\Lambda^{ec}(\bar{x},\bar{y},\bar{u},0)\implies\beta=0,\gamma=0,\vskip
6.0pt plus 2.0pt minus 2.0pt$ $\displaystyle(A_{2}^{c})\text{ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }(\beta,\gamma)$
$\displaystyle\in\Lambda_{y}^{ec}(\bar{x},\bar{y},\bar{u},0)\implies\nabla_{x}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{T}\beta+\nabla_{x}g(\bar{x},\bar{y})^{T}\gamma=0,\vskip
6.0pt plus 2.0pt minus 2.0pt$ $\displaystyle(A_{3}^{c})\text{ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }(\beta,\gamma)$
$\displaystyle\in\Lambda_{y}^{ec}(\bar{x},\bar{y},\bar{u},0)\implies\beta=0,\gamma=0,\text{
}$

with the C-multiplier set $\Lambda^{ec}(\bar{x},\bar{y},\bar{u},0)$ resulting
from setting $v=0$ in

$\Lambda^{ec}(\bar{x},\bar{y},\bar{u},v):=\left\\{(\beta,\gamma)\in\mathbb{R}^{m+q}\left|\;\;\begin{array}[]{l}\nabla_{y}g_{\nu}(\bar{x},\bar{y})\beta=0,\;\;\gamma_{\eta}=0\\\
\forall
i\in\theta:\;\;\gamma_{i}\left(\nabla_{y}g_{i}(\bar{x},\bar{y})\right)\beta\geq
0\\\ v+\nabla_{x,y}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{\top}\beta+\nabla
g(\bar{x},\bar{y})^{\top}\gamma=0\end{array}\right.\right\\},$ (4.8)

while $\Lambda_{y}^{ec}(\bar{x},\bar{y},\bar{u},0)$ can be obtained by
replacing the derivatives w.r.t. $(x,y)$ is the last equation in the set (4.8)
by the derivatives of the same functions w.r.t. $y$ only. Obviously,

$(A_{1}^{c})\impliedby(A_{3}^{c})\implies(A_{2}^{c}).$

Similarly to the $M$\- and $S$-stationarity concepts introduced at the
beginning of this section, we can define $M$\- and $S$-qualification
conditions.

######  Theorem 4.2 ([8])

Let $\bar{x}$ be a local optimal solution to ($P_{p}$), where the lower-level
problem is convex. Suppose that $\bar{x}$ is upper-level regular and
$\mathcal{S}_{p}$ is inner semicontinuous at $(\bar{x},\bar{y},\bar{u})$,
where $(A_{1}^{c})$ and $(A_{2}^{c})$ are also assumed to hold. Then there
exists $\left(\alpha,\beta,\gamma\right)$ such that (4.1)–(4.6).

Note that (SCQ) is needed here to ensure that the result holds. However, it is
assumed that this regularity condition is satisfied throughout the paper.
Hence, it is not explicitly stated in the result.

Next, we introduce the necessary optimality conditions for the regularized
problem (KKTt). For a fixed number $t>0$, a point $x^{t}$ will be said to
_satisfy the necessary optimality conditions_ (or _be a stationary point_) for
problem (KKTt) if there exists a vector
$(y^{t},u^{t},\alpha^{t},\beta^{t},\gamma^{t},\mu^{t},\delta^{t})$ such that
the following relationships are satisfied:

$\displaystyle(x^{t},y^{t},u^{t})\in\mbox{gph }\mathcal{S}^{t}_{p},$ (4.9)
$\displaystyle\nabla_{x}F(x^{t},y^{t})+\nabla
G(x^{t})^{\top}\alpha^{t}-\nabla_{x}\mathcal{L}(x^{t},y^{t},u^{t})^{\top}\beta^{t}-\sum\limits_{i=1}^{q}\left(\gamma_{i}^{t}-\delta_{i}^{t}u_{i}^{t}\right)\nabla_{x}g_{i}(x^{t},y^{t})=0,$
(4.10)
$\displaystyle\nabla_{y}F(x^{t},y^{t})-\nabla_{y}\mathcal{L}(x^{t},y^{t},u^{t})^{\top}\beta^{t}-\sum\limits_{i=1}^{q}\left(\gamma_{i}^{t}-\delta_{i}^{t}u_{i}^{t}\right)\nabla_{y}g_{i}(x^{t},y^{t})=0,$
(4.11) $\displaystyle\forall
i=1,\ldots,q:\;\,-\nabla_{y}g_{i}(x^{t},y^{t})\beta^{t}+\mu_{i}^{t}+\delta_{i}^{t}g_{i}(x^{t},y^{t})=0,$
(4.12) $\displaystyle\forall j=1,\ldots,p:\;\;\alpha_{j}^{t}\geq
0,\;\;G_{j}(x^{t})\leq 0,\;\;\alpha_{j}^{t}G_{j}(x^{t})=0,$ (4.13)
$\displaystyle\forall i=1,\ldots,q:\;\;\gamma^{t}_{i}\geq
0,\;\;g_{i}(x^{t},y^{t})\leq 0,\;\;\gamma^{t}_{i}g_{i}(x^{t},y^{t})=0,$ (4.14)
$\displaystyle\forall i=1,\ldots,q:\;\;\mu^{t}_{i}\geq 0,\;\;u^{t}_{i}\geq
0,\;\;\mu^{t}_{i}u^{t}_{i}=0,$ (4.15) $\displaystyle\forall
i=1,\ldots,q:\;\;\delta^{t}_{i}\geq 0,\;\;-u^{t}_{i}g_{i}(x^{t},y^{t})\leq
t,\;\;\delta^{t}_{i}\left(u^{t}_{i}g_{i}(x^{t},y^{t})+t\right)=0.$ (4.16)

######  Theorem 4.3 ([37])

For a given $t>0,$ let $x^{t}$ be an upper-level regular local optimal
solution for (KKTt). Assume that the set-valued map $\mathcal{S}^{t}_{p}$ is
inner semicontinous at
$(x^{t},y^{t},u^{t})\in\mathrm{gph}\,\mathcal{S}^{t}_{p}$ and the following
qualification condition holds at $(x^{t},y^{t},u^{t})$:

$\left.\begin{array}[c]{r}\nabla_{y}\mathcal{L}(x^{t},y^{t},u^{t})^{\top}\beta^{t}+\sum\limits_{i=1}^{q}\nabla_{y}g_{i}(x^{t},y^{t})\left(\gamma_{i}^{t}-\delta_{i}^{t}u_{i}^{t}\right)=0\\\
\nabla_{y}g_{i}(x^{t},y^{t})\beta^{t}-\mu_{i}^{t}-\delta_{i}^{t}g_{i}(x^{t},y^{t})=0\\\
\gamma^{t}\geq 0,\text{ }\delta^{t}\geq 0,\text{ }\mu^{t}\geq 0\\\
\mu_{i}^{t}u_{i}^{t}=0,\text{ \ }\gamma_{i}^{t}g_{i}(x^{t},y^{t})=0,\text{\
}\delta_{i}^{t}\left(u_{i}^{t}g_{i}(x^{t},y^{t})+t\right)=0\end{array}\right\\}\Longrightarrow\left\\{\begin{array}[c]{l}\beta=0_{m},\\\
\\\ \delta=\gamma=\mu=0_{q}.\end{array}\right.$ (4.17)

Then $x^{t}$ is a stationary point for problem (KKTt); i.e., there exists a
vector $(y^{t},u^{t},\alpha^{t},\beta^{t},\gamma^{t},\mu^{t},\delta^{t})$ such
that the optimality conditions (4.9)–(4.16) are satisfied.

To establish the convergence result of Algorithm 1 in this context, the
following index sets, defined for $(x,(y,u))\in X\times\mathcal{D}^{t}(x)$
with $t>0$, are needed:

$\begin{array}[]{rll}I_{G}(x)&:=&\left\\{i\in\\{1,...,p\\}|\;\;G_{i}(x)=0\right\\},\\\
I_{u}(x,y,u)&:=&\left\\{i\in\\{1,...,q\\}|\;\;u_{i}=0\right\\},\\\
I_{g}(x,y,u)&:=&\left\\{i\in\\{1,...,q\\}|\;\;g_{i}(x,y)=0\right\\},\\\
I_{ug}(x,y,u)&:=&\left\\{i\in\\{1,...,q\\}|\;\;u_{i}g_{i}(x,y)+t=0\right\\}.\end{array}$

Clearly, $I_{g}(x,y,u)\cap I_{ug}(x,y,u)=\emptyset$ and $I_{u}(x,y,u)\cap
I_{ug}(x,y,u)=\emptyset$. Also, for the convergence result, we will use the
$m$–counterparts, $(A_{1}^{m})$ and $(A_{2}^{m})$, of assumptions
$(A_{1}^{c})$ and $(A_{2}^{c})$, which can be obtained by simply replacing the
C-multipliers set (4.8) by the corresponding M-multipliers set. One can easily
check that $(A_{1}^{m})$ and $(A_{2}^{m})$ are weaker than $(A_{1}^{c})$ and
$(A_{2}^{c})$, respectively.

###### Theorem 4.4

Let $t_{k}\downarrow 0$ and $(x^{k})$ be a sequence such that $x^{k}$ is a
stationary point of problem (KKTt) for $t:=t^{k}$ with
$x^{k}\underset{k\rightarrow\infty}{\longrightarrow}\bar{x}$ such that
$\mathcal{S}_{p}(\bar{x})$ is nonempty and compact. Assume that $\bar{x}$ is
upper-level regular, and $(A_{1}^{m})$ and $(A_{2}^{m})$ hold at all
$(\bar{x},y,u)$ with $(y,u)\in\mathcal{S}_{p}(\bar{x})$. Furthermore, let

$e\left(\mathcal{S}^{t_{k}}_{p}(x^{k}),\;\mathcal{S}_{p}(\bar{x})\right)\underset{k\rightarrow\infty}{\longrightarrow}0.$
(4.18)

Then $\bar{x}$ is a C-stationary point.

###### Proof 4.5

_Proof._ Since $x^{k}$ is a stationary point of (KKTt) for $t:=t_{k}$, there
exist a vector $(y^{k},u^{k})\in\mathcal{S}^{t_{k}}(x^{k})$ and multipliers
$(\alpha^{k},\beta^{k},\mu^{k},\gamma^{k},\delta^{k})$ such that the
relationships

$\left\\{\begin{array}[]{l}\nabla_{x}F(x^{k},y^{k})+\nabla
G^{T}(x^{k})\alpha^{k}-\nabla_{x}\mathcal{L}(x^{k},y^{k},u^{k})^{T}\beta^{k}-\sum\limits_{i=1}^{q}(\gamma_{i}^{k}-\delta_{i}^{k}u_{i}^{k})\nabla_{x}g_{i}(x^{k},y^{k})=0,\\\\[4.30554pt]
\lx<EMAIL_ADDRESS>\lx<EMAIL_ADDRESS>(4.19)

hold together with the following complementarity conditions:

$\left\\{\begin{array}[]{l}\alpha_{i}^{k}\geq 0,\;\,G_{i}(x^{k})\leq
0,\;\,\alpha_{i}^{k}G_{i}(x^{k})=0,\;,i=1,...,p,\\\\[4.30554pt]
\mu_{i}^{k}\geq 0,\;\,\gamma_{i}^{k}\geq 0,\;\,\delta_{i}^{k}\geq
0,\;\,i=1,...,q,\\\\[4.30554pt]
\mu_{i}^{k}u_{i}^{k}=0,\;\;\gamma_{i}^{k}g_{i}(x^{k},y^{k})=0,\;\;\delta_{i}^{k}(u_{i}^{k}g_{i}(x^{k},y^{k})+t_{k})=0,\;\,i=1,...,q.\end{array}\right.$

Hence, it follows that

$\left\\{\begin{array}[]{lll}\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k}=\mu_{i}^{k}&\mbox{
for }&i\in\mathrm{supp}\mu^{k},\\\\[4.30554pt]
\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k}=g_{i}(x^{k},y^{k})\delta_{i}^{k}&\mbox{
for }&i\in\mathrm{supp}\delta^{k},\\\\[4.30554pt]
\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k}=0&\mbox{ for
}&i\notin(\mathrm{supp}\mu^{k}\cup\mathrm{supp}\delta^{k}),\end{array}\right.$

and

$\displaystyle\alpha_{i}^{k}$ $\displaystyle\geq 0,\text{ \
}\mathrm{supp}\alpha^{k}\subset I_{G}(x^{k}),\vskip 6.0pt plus 2.0pt minus
2.0pt$ (4.20) $\displaystyle\mu_{i}^{k}$ $\displaystyle\geq 0,\text{ \
}\mathrm{supp}\mu^{k}\subset I_{u}(x^{k},y^{k},u^{k}),\vskip 6.0pt plus 2.0pt
minus 2.0pt$ (4.21) $\displaystyle\gamma_{i}^{k}$ $\displaystyle\geq 0,\text{
\ }\mathrm{supp}\gamma^{k}\subset I_{g}(x^{k},y^{k},u^{k}),\vskip 6.0pt plus
2.0pt minus 2.0pt$ (4.22) $\displaystyle\delta_{i}^{k}$ $\displaystyle\geq
0,\text{ \ }\mathrm{supp}\delta^{k}\subset I_{ug}(x^{k},y^{k},u^{k}),$ (4.23)

where $\mathrm{supp}(z):=\left\\{i|\,\,z_{i}=0\right\\}$ is the support of a
vector $z\in\mathbb{R}^{n}$.

Next, observe that the continuity of the constraint functions $G$ and $g$
leads to

$I_{G}(x^{k})\subseteq I_{G},\text{
}I_{u}(x^{k},y^{k},u^{k})\subseteq\theta\cup\eta,\
I_{g}(x^{k},y^{k},u^{k})\subseteq\theta\cup\nu,$ (4.24)

for $k$ sufficiently large; here
$I_{G}:=\left\\{i\in\left\\{1,...,p\right\\}|\;\;G_{i}(\bar{x})=0\right\\}.$
Now, we can introduce some new Lagrange multipliers by setting
$\tilde{\beta}^{k}:=-\beta^{k}$,

$\tilde{\gamma}_{i}^{k}:=\left\\{\begin{array}[]{lll}-\gamma_{i}^{k}&\mbox{ if
}&i\in\mathrm{supp}\gamma^{k},\\\ \delta_{i}^{k}u_{i}^{k}&\mbox{ if
}&i\in\mathrm{supp}\delta^{k}\backslash\eta,\\\ 0&\mbox{ if
}&i\in\eta,\end{array}\right.\;\,\mbox{ and
}\;\,\tilde{\mu}_{i}^{k}:=\left\\{\begin{array}[]{lll}\mu_{i}^{k}&\mbox{ if
}&i\in\mathrm{supp}\mu^{k},\\\ \delta_{i}^{k}g_{i}(x^{k},y^{k})&\mbox{ if
}&i\in\mathrm{supp}\delta^{k}\backslash\nu,\\\ 0&\mbox{ if
}&i\in\nu.\end{array}\right.$ (4.25)

Hence, from the optimality conditions in (4.19), we have the system of
equations

$\left\\{\begin{array}[]{l}\nabla_{x}F(x^{k},y^{k})+\nabla
G(x^{k})^{T}\alpha^{k}+\nabla_{x}\mathcal{L}(x^{k},y^{k},u^{k})^{T}\tilde{\beta}^{k}\\\\[2.15277pt]
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\;\;\;+\,\sum\limits_{i=1}^{q}\tilde{\gamma}_{i}^{k}\nabla_{x}g_{i}(x^{k},y^{k})-\sum\limits_{i\in\eta}\delta_{i}^{k}u_{i}^{k}\nabla_{x}g_{i}(x^{k},y^{k})=0,\\\\[4.30554pt]
\lx<EMAIL_ADDRESS>(4.26)

which is accompanied by the conditions

$\left\\{\begin{array}[]{lll}\nabla_{y}g_{i}(x^{k},y^{k})\tilde{\beta}^{k}=-\tilde{\mu}_{i}^{k}&\mbox{
for }&i\in\mathrm{supp}\mu^{k}\cup\mathrm{\ supp}\delta^{k}\backslash\nu,\\\
\nabla_{y}g_{i}(x^{k},y^{k})\tilde{\beta}^{k}=-\delta_{i}^{k}g_{i}(x^{k},y^{k})&\mbox{
for }&i\in\nu,\\\ \nabla_{y}g_{i}(x^{k},y^{k})\tilde{\beta}^{k}=0&\mbox{ for
}&i\notin(\mathrm{supp}\mu^{k}\cup\mathrm{supp}\delta^{k}).\end{array}\right.$
(4.27)

On the other hand, from (4.18), there exists
$(z^{k},w^{k})\in\mathcal{S}_{p}(\bar{x})$ such that

$\left\|y^{k}-z^{k}\right\|\underset{k\rightarrow\infty}{\rightarrow}0\text{
and }\left\|u^{k}-w^{k}\right\|\underset{k\rightarrow\infty}{\rightarrow}0$

and since $\mathcal{S}_{p}(\bar{x})$ is compact, the sequence
$(y^{k},u^{k})_{k}$ (up to a subsequence) converges to some point
$(\bar{y},\bar{u})\in\mathcal{S}_{p}(\bar{x})$. Next, we are going to show
that the sequence
$(\chi_{k}):=\begin{pmatrix}\alpha^{k},\tilde{\beta}^{k},\tilde{\mu}^{k},\tilde{\gamma}^{k},\delta_{\eta\cup\nu}^{k}\end{pmatrix}_{k}$
is bounded. Assume that this is not the case and consider the sequence
$\left(\dfrac{\chi_{k}}{\left\|\chi_{k}\right\|}\right)_{k}$ converging to a
nonvanishing vector
$\chi:=(\alpha,\tilde{\beta},\tilde{\mu},\tilde{\gamma},\delta_{\eta\cup\nu})$
(otherwise, a suitable subsequence is chosen). Dividing (4.26) by
$\left\|\chi_{k}\right\|$ and taking the limit $k\rightarrow\infty$ while
taking into account the continuous differentiability of all involved functions
and the fact that $\bar{u}_{i}=0$ for $i\in\eta,$, we come up with

$\nabla
G(\bar{x})^{T}\alpha+\nabla_{x}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{T}\tilde{\beta}+\nabla_{x}g^{T}(\bar{x},\bar{y})\tilde{\gamma}=0\mbox{
and
}\nabla_{y}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{T}\tilde{\beta}+\nabla_{y}g^{T}(\bar{x},\bar{y})\tilde{\gamma}=0.$
(4.28)

Let us show now that we have the following inclusions for any $k$ sufficiently
large:

$\mathrm{supp}\alpha\subset I_{G}(x^{k})\subset I_{G},$ (4.29)
$\mathrm{supp}\tilde{\mu}\subset I_{u}(x^{k},y^{k},u^{k})\cup
I_{ug}(x^{k},y^{k},u^{k})\backslash\nu\subset\theta\cup\eta,$ (4.30)
$\mathrm{supp}\tilde{\gamma}\subset I_{g}(x^{k},y^{k},u^{k})\cup
I_{ug}(x^{k},y^{k},u^{k})\backslash\eta\subset\theta\cup\nu.$ (4.31)

Indeed, for (4.29), let $i\in\mathrm{supp}\alpha$ such that $\alpha_{i}>0$.
Hence, for any $k$ large enough, $\alpha_{i}^{k}>0$ that is,
$i\in\mathrm{supp}\alpha^{k}\subset I_{G}(x^{k})$ by (4.20). Given now $i\in
I_{G}(x^{k})$ for any $k$ sufficiently large so that, there exists
$k_{0}\in\mathbb{N}$ such that for any $k\geq k_{0},$ $G_{i}(x^{k})=0.$
Passing to the limit as $k\rightarrow\infty$, we get $G_{i}(\bar{x})=0$
($G_{i}$ being continuous) and so $i\in I_{G}(\bar{x}).$ For (4.30): take
$i\in\mathrm{supp}\tilde{\mu}$ thus for any $k$ sufficiently large,
$\tilde{\mu}_{i}^{k}>0$ i.e., $i\in\mathrm{supp}\tilde{\mu}^{k}.$ Then for all
$k$ sufficiently large,
$i\in\mathrm{supp}\mu^{k}\cup\mathrm{supp}\delta^{k}\backslash\nu.$ Hence by
properties (4.21) and (4.23), $i\in I_{u}(x^{k},y^{k},u^{k})\cup
I_{ug}(x^{k},y^{k},u^{k})\backslash\nu.$ And from (4.24),
$I_{u}(x^{k},y^{k},u^{k})\subset\theta\cup\eta$. Now if
$u_{i}^{k}g_{i}(x^{k},y^{k})+t_{k}=0$ for $k$ large enough, with $i\notin\nu.$
Taking the limit, it follows that $\bar{u}_{i}g_{i}(\bar{x},\bar{y})=0$ so
$i\in\theta\cup\eta.$ Similarly, we get (4.31). On the other hand, we have

$\displaystyle\alpha_{j}\geq 0,\text{ \ }G_{j}(\bar{x})\leq 0,$
$\displaystyle\;\;\alpha_{j}G_{j}(\bar{x})=0\;\,\mbox{ for
}\;\,j=1,...,p,\vskip 6.0pt plus 2.0pt minus 2.0pt$
$\displaystyle\delta_{\eta\cup\nu}$
$\displaystyle=\lim\delta_{\eta\cup\nu}^{k}\geq 0,\vskip 6.0pt plus 2.0pt
minus 2.0pt$ $\displaystyle\tilde{\gamma}_{i}$
$\displaystyle=\lim\tilde{\gamma}_{i}^{k}=0\text{ \ \ }\forall i\in\eta,\vskip
6.0pt plus 2.0pt minus 2.0pt$
$\displaystyle\nabla_{y}g_{\nu}(\bar{x},\bar{y})\tilde{\beta}$
$\displaystyle=\lim\nabla_{y}g_{\nu}(x^{k},y^{k})\tilde{\beta}^{k}=-\lim\delta_{\nu}^{k}g_{\nu}(x^{k},y^{k})=-\delta_{v}g_{v}(\bar{x},\bar{y})=0.$

Let us now prove that

$(\tilde{\gamma}_{i}<0\wedge\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}<0)\vee\tilde{\gamma}_{i}\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}=0$

for all $i\in\theta.$ Assume that $\tilde{\gamma}_{i}>0$ or
$\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}>0$ for some $i\in\theta$ with
$\tilde{\gamma}_{i}\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}\neq 0.$ If
$\tilde{\gamma}_{i}>0$ then for all $k$ large enough,
$\tilde{\gamma}_{i}^{k}>0$ and so from (4.25), $i\in\mathrm{supp}\delta^{k}$.
Moreover, as $\mathrm{supp}\mu^{k}\cap$ supp$\delta^{k}=\emptyset,$
$i\notin\mathrm{supp}\mu^{k}$ and from (4.27) and (4.25),

$\nabla_{y}g_{i}(x^{k},y^{k})\frac{\tilde{\beta}^{k}}{\left\|\chi_{k}\right\|}=-\frac{\delta_{i}^{k}}{\left\|\chi_{k}\right\|}g_{i}(x^{k},y^{k})$

and by taking the limit, we get
$\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}=0$ since $g_{i}(x^{k},y^{k})$
converges to $g_{i}(\bar{x},\bar{y})=0$ ($i\in\theta$) and the sequence
$\left(\dfrac{\delta_{i}^{k}}{\left\|\chi_{k}\right\|}\right)$ is bounded.
This leads to a contradiction since
$\tilde{\gamma}_{i}\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}\neq 0$ by
assumption. Similarly, if $\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}>0$ so
for all $k$ large enough, $\nabla_{y}g_{i}(x^{k},y^{k})\tilde{\beta}^{k}>0$
and from (4.27), $i\in\mathrm{supp}\delta^{k}.$ Then
$\dfrac{\tilde{\gamma}_{i}^{k}}{\left\|\chi_{k}\right\|}=\dfrac{\delta_{i}^{k}}{\left\|\chi_{k}\right\|}u_{i}^{k}$
converges to $\tilde{\gamma}_{i}=0$ ($\bar{u}_{i}=0$), which leads to a
contradiction too. Consequently, we have

$\left\\{\begin{array}[]{l}\nabla_{y}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{T}\tilde{\beta}+\nabla_{y}g^{T}(\bar{x},\bar{y})\tilde{\gamma}=0,\\\
\nabla_{y}g_{\nu}(\bar{x},\bar{y})\tilde{\beta}=0,\text{ \
}\tilde{\gamma}_{\eta}=0,\\\
(\tilde{\gamma}_{i}<0\wedge\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}<0)\vee\tilde{\gamma}_{i}\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}=0\;\mbox{
for }\;i\in\theta,\end{array}\right.$

so that
$(-\tilde{\beta},-\tilde{\gamma})\in\Lambda_{y}^{em}(\bar{x},\bar{y},\bar{u},0)$
and by condition $(A_{2}^{m})$, we get

$\nabla_{x}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{T}\tilde{\beta}+\nabla_{x}g^{T}(\bar{x},\bar{y})\tilde{\gamma}=0$

using (4.28), it yields $\nabla G(\bar{x})^{T}\alpha=0$; this implies that
$\alpha=0$ ($\bar{x}$ being upper-level regular). Thus,

$\left\\{\begin{array}[]{l}\nabla_{x,y}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{T}\tilde{\beta}+\nabla
g^{T}(\bar{x},\bar{y})\tilde{\gamma}=0,\\\
\nabla_{y}g_{\nu}(\bar{x},\bar{y})\tilde{\beta}=0,\text{ \
}\tilde{\gamma}_{\eta}=0,\\\
(\tilde{\gamma}_{i}<0\wedge\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}<0)\vee\tilde{\gamma}_{i}\nabla_{y}g_{i}(\bar{x},\bar{y})\tilde{\beta}=0\;\mbox{
for }\;i\in\theta;\end{array}\right.$

that is,
$(-\tilde{\beta},-\tilde{\gamma})\in\Lambda^{em}(\bar{x},\bar{y},\bar{u},0)$
and by the condition $(A_{1}^{m}),$ we get $(\tilde{\beta},\tilde{\gamma})=0.$
Hence $(\alpha,\tilde{\beta},\tilde{\mu},\tilde{\gamma})=0$ (observe that
$\tilde{\mu}=0$ from (4.27)) and we conclude that $\delta_{\eta\cup\nu}\neq
0.$ Assume without loss of generality that there exists $i\in\eta$ such that
$\delta_{i}>0.$ Thus for $k$ large enough,
$i\in\mathrm{supp}\delta_{i}^{k}\backslash\nu$ and from (4.25),
$\tilde{\mu}_{i}^{k}:=\delta_{i}^{k}g_{i}(x^{k},y^{k})$ so
$\dfrac{\tilde{\mu}_{i}^{k}}{\left\|\chi_{k}\right\|}$ converges to
$\tilde{\mu}_{i}=\delta_{i}g_{i}(\bar{x},\bar{y})<0$ (since $i\in\eta$) and
the contradiction follows (with the fact that $\tilde{\mu}_{i}=0$). Similary,
if $\delta_{\nu}\neq 0$ we get a contradiction.

Consequently, the sequence
$(\alpha^{k},\tilde{\beta}^{k},\tilde{\mu}^{k},\tilde{\gamma}^{k},\delta_{\eta\cup\nu}^{k})_{k}$
is bounded. Consider
$(\bar{\alpha},\overline{\beta},\overline{\tilde{\mu}},\overline{\tilde{\gamma}},\bar{\delta}_{\eta\cup\nu})$
its limit (up to a subsequence) so that we have clearly have

$\mathrm{supp}\bar{\alpha}\subset I_{G},\text{
}\mathrm{supp}\overline{\tilde{\mu}}\subset\theta\cup\eta,\
\mathrm{supp}\overline{\tilde{\gamma}}\subset\theta\cup\nu.$

Taking the limit in (4.26), we obtain

$\left\\{\begin{array}[]{l}\nabla_{x}F(\bar{x},\bar{y})+\nabla
G(\bar{x})^{T}\bar{\alpha}+\nabla_{x}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{T}\overline{\beta}+\sum\limits_{i=1}^{q}\overline{\tilde{\gamma}}_{i}\nabla_{x}g_{i}(\bar{x},\bar{y})=0,\\\\[4.30554pt]
\lx<EMAIL_ADDRESS>
with $\bar{\alpha}\geq 0$, $\bar{\alpha}^{\top}G(\bar{x})=0$,
$\overline{\tilde{\gamma}}_{\eta}=0$, and
$\nabla_{y}g_{\nu}(\bar{x},\bar{y})\overline{\beta}=0$.

It remains to prove that
$\overline{\tilde{\gamma}}_{i}\nabla_{y}g_{i}(\bar{x},\bar{y})\overline{\beta}\geq
0$ for $i\in\theta.$ Let us assume that for some $i\in\theta$,

$\overline{\tilde{\gamma}}_{i}<0\;\;\mbox{ and
}\;\;\nabla_{y}g_{i}(\bar{x},\bar{y})\overline{\beta}>0.$

From (4.25) and the fact that $\overline{\tilde{\gamma}}_{i}<0,$
$i\in\mathrm{supp}\gamma^{k}$ and $g_{i}(x^{k},y^{k})=0$ for all $k$ large
enough so that,

$\left\\{\begin{array}[]{lll}\nabla_{y}g_{i}(x^{k},y^{k})\tilde{\beta}^{k}=-\mu_{i}^{k}&\mbox{for
}i\in\mathrm{supp}\mu^{k},\vskip 6.0pt plus 2.0pt minus 2.0pt\\\
\nabla_{y}g_{i}(x^{k},y^{k})\tilde{\beta}^{k}=0&\mbox{otherwise.}\end{array}\right.$

Thus, $\nabla_{y}g_{i}(\bar{x},\bar{y})\overline{\beta}\leq 0,$ which is a
contradiction to our assumption that
$\nabla_{y}g_{i}(\bar{x},\bar{y})\overline{\beta}>0.$ Similarly, if
$\overline{\tilde{\gamma}}_{i}>0$ and
$\nabla_{y}g_{i}(\bar{x},\bar{y})\overline{\beta}<0.$ Thus,
$\tilde{\gamma}^{k}>0$ for all $k$ large enough and by (4.25),
$i\in\mathrm{supp}\delta^{k}\backslash\eta$ for all $k$ large enough and
$i\notin\mathrm{supp}\mu^{k}$. Hence, for all $k$ large enough,

$\nabla_{y}g_{i}(x^{k},y^{k})\tilde{\beta}^{k}=-\delta_{i}^{k}g_{i}(x^{k},y^{k})>0,$

and the limit leads to the inequality
$\nabla_{y}g_{i}(\bar{x},\bar{y})\overline{\beta}\geq 0$, which is a
contradiction. Hence, we have the inequality
$\overline{\tilde{\gamma}}_{i}(\nabla_{y}g_{i}(\bar{x},\bar{y})\bar{\beta})\geq
0$ for $i\in\theta$ and the conclusion follows. ∎

To illustrate this result, we apply it to the problems from Examples 3.12 and
3.13.

###### Example 4.6

Observe that for any $\bar{x},$ $\mathcal{S}_{p}(\bar{x})$ is nonempty and
compact and the conditions $(A_{1}^{m})$ and $(A_{2}^{m})$ are satisfied for
both examples. For the problem from (3.6), consider $t_{k}\downarrow 0$ and
$(x_{k})$ in $\left]0,1\right]$ such that
$x_{k}\rightarrow\bar{x}\in\left]0,1\right]$. Hence, for all $k$ large enough
such that $0<t_{k}\leq x_{k}$,

$\mathcal{S}^{t_{k}}_{p}(x_{k})=\left\\{\left(\frac{t_{k}}{x_{k}},(x_{k},0)\right)\right\\}$

and

$e\left(\mathcal{S}^{t_{k}}_{p}(x_{k}),\;\mathcal{S}_{p}(\bar{x})\right)=\left\|\left(\frac{t_{k}}{x_{k}},(x_{k},0)\right)-(0,(\bar{x},0))\right\|=\frac{t_{k}}{x_{k}}+\left|x_{k}-\bar{x}\right|.$

Thus, it clearly follows that
$e(\mathcal{S}^{t_{k}}_{p}(x_{k}),\;\mathcal{S}_{p}(\bar{x}))\underset{k\rightarrow\infty}{\longrightarrow}0$.

Now, considering the problem from (3.10), $t_{k}\downarrow 0$ and a sequence
$(x_{k})$ in $\left[-1,0\right[$ such that we have
$x_{k}\rightarrow\bar{x}=-1$,

$\mathcal{S}^{t_{k}}_{p}(x_{k})=\left\\{(1,(u_{k},u_{k}-x_{k}))\left|\;0\leq
u_{k}\leq t_{k}\right.\right\\}\;\;\mbox{ for all }\;\;k$

so that, for any $(u_{k})$ such that $0\leq u_{k}\leq t_{k}$, we have

$d((1,(u_{k},u_{k}-x_{k})),\;\mathcal{S}_{p}(\bar{x}))\,=\,\left\|(1,(u_{k},u_{k}-x_{k}))-(1,\,(0,1))\right\|\,\leq\,2u_{k}+\left|x_{k}+1\right|\longrightarrow
0$

and thus
$e\left(\mathcal{S}^{t_{k}}_{p}(x_{k}),\;\mathcal{S}_{p}(\bar{x})\right)\longrightarrow
0$ as $k\longrightarrow\infty$. ∎

Note that condition (4.18) is satisfied if
$(t,x)\rightrightarrows\mathcal{S}^{t}_{p}(x)$ is upper semicontinuous at
$(0,\bar{x})$ (in the Hausdorff sense); i.e.,
$e(\mathcal{S}^{t}_{p}(x),\;\mathcal{S}^{0}_{p}(\bar{x}))\longrightarrow 0$ as
$(t,x)\longrightarrow(0,\bar{x})$, taking into account the equality
$\mathcal{S}^{0}_{p}(\bar{x})=\mathcal{S}_{p}(\bar{x})$. The next result gives
a framework that instead relies on semicontinuity properties of the set-valued
mapping $\mathcal{D}$ and $\mathcal{D}^{t}$ to ensure that condition (4.18) is
satisfied.

###### Proposition 4.7

Let $(t_{k})\downarrow 0$ and let
$(x^{k})\underset{k\rightarrow\infty}{\longrightarrow}\bar{x}$ such that
$\mathcal{D}(\bar{x})$ is nonempty and compact. Assume that the set-valued
mapping $x\rightrightarrows\mathcal{D}(x)$ $($resp.
$(t,x)\rightrightarrows\mathcal{D}^{t}(x)$$)$ is lower semicontinuous at any
$(\bar{x},y,u)\in\mbox{gph}\,\mathcal{D}$ $($resp. upper semicontinuous at
$(0,\bar{x})$$)$. Then the property (4.18) holds.

###### Proof 4.8

_Proof._ Assuming that the statement is not true, that is, (4.18) does not
hold, then there exist $\delta>0$ and a sequence $(y^{k},u^{k})_{k}$ such that
$(y^{k},u^{k})\in\mathcal{S}^{t_{k}}_{p}(x^{k})$ and

$d((y^{k},u^{k}),\mathcal{S}_{p}(\bar{x}))\geq\delta\;\mbox{ for all }\;k.$
(4.32)

Therefore, since $(y^{k},u^{k})\in\mathcal{D}^{t_{k}}(x^{k})$, it holds that

$d((y^{k},u^{k}),\mathcal{D}(\bar{x}))\leq
e(\mathcal{D}^{t_{k}}(x^{k}),\mathcal{D}(\bar{x}))$

with $e(\mathcal{D}^{t_{k}}(x^{k}),\mathcal{D}(\bar{x}))\longrightarrow 0$ as
$k\longrightarrow\infty$, by the fact the set-valued mapping
$(t,x)\rightrightarrows\mathcal{D}^{t}(x)$ is upper semicontinuous at
$(0,\bar{x})$. Hence, there exists a sequence $(z^{k},w^{k})$ in
$\mathcal{D}(\bar{x})$ such that

$\left\|y^{k}-z^{k}\right\|\longrightarrow 0\;\,\text{ and
}\;\,\left\|u^{k}-w^{k}\right\|\longrightarrow 0$

and due to the compactness of $\mathcal{D}(\bar{x})$, the sequence
$(z^{k},w^{k})$ (up to a subsequence) converges to a point
$(\bar{y},\bar{u})\in\mathcal{D}(\bar{x})$ and so does the (sub)sequence
$(y^{k},u^{k})$.

Let us prove now that $(\bar{y},\bar{u})\in\mathcal{S}_{p}(\bar{x})$. Indeed,
from assertion 3 in Proposition 2.2, we get

$F(x^{k},y^{k})-\psi_{p}(x^{k})\geq F(x^{k},y^{k})-\psi_{p}^{t_{k}}(x^{k})\geq
0$

by the fact that $(y^{k},u^{k})\in\mathcal{S}^{t_{k}}_{p}(x^{k})$. On the
other hand, since $F(\cdot,\cdot)$ is continuous and $\mathcal{D}(\cdot)$ is
lower semicontinuous, the function $\psi_{p}(\cdot)$ is lower semicontinuous
at $\bar{x}$. Hence,

$F(\bar{x},\bar{y})-\psi_{p}(\bar{x})\geq
F(\bar{x},\bar{y})-\underset{k\rightarrow\infty}{\text{
}\lim\inf}\psi_{p}(x^{k})=\underset{k\rightarrow\infty}{\text{
}\lim\sup}(F(x^{k},y^{k})-\psi_{p}^{t_{k}}(x^{k}))\geq 0.$

Consequently, $(\bar{y},\bar{u})\in\mathcal{S}_{p}(\bar{x})$ and from the
following equality

$d((y^{k},u^{k}),\mathcal{S}_{p}(\bar{x}))\leq\left\|(y^{k},u^{k})-(\bar{y},\bar{u})\right\|$

we get
$\underset{k\longrightarrow\infty}{\lim}d((y^{k},u^{k}),\;\mathcal{S}_{p}(\bar{x}))=0$,
which is a contradiction to (4.32). ∎

In Theorem 4.4, the requirement that the sequence $(x^{k})$ be such that each
point $x^{k}$ is a stationary point of problem (KKTt) for $t:=t^{k}$ assumes
the existence of a vector
$(y^{t},u^{t},\alpha^{t},\beta^{t},\gamma^{t},\mu^{t},\delta^{t})$ such that
the optimality conditions (4.9)–(4.16) are satisfied. A priori, it is not
clear whether such a vector actually exists. According to Theorem 4.3, such a
vector can exist if the point $x^{k}$ is upper-level regular, the set-valued
mapping $\mathcal{S}^{t_{k}}_{p}$ is inner semicontinuous at
$(x^{k},y^{k},u^{k})$ for some
$(y^{k},u^{k})\in\mathcal{S}^{t_{k}}_{p}(x^{k})$, and the qualification
condition (4.17) holds at $(x^{k},y^{k},u^{k})$. The question is, how can we
ensure that these three conditions are automatically satisfied as our sequence
get close to the point of interest. Theorem 3.10(iii) has already given some
conditions ensuring that we can find a neighborhood $U\times V$ of some
reference point $(\bar{x},(\bar{y},\bar{u}))$ such that for all $t\downarrow
0$, $\mathcal{S}_{p}^{t}$ is inner semicontinuous at all points $(x,(y,u))$
with $x\in U$ and $(y,u)\in V\cap\mathcal{S}_{p}^{t}(x)$.

Theorem 4.11 below, which is a variant of [31, Proposition 2.2], establishes
sufficient conditions for conditions (4.7) and (4.17) to hold at all points in
a neighborhood of our reference point. Since the challenging part of this
result relies on the satisfaction of the qualification conditions
$(A_{1}^{m})$ and $(A_{2}^{m})$ at our reference point, we first show that
$(A_{1}^{m})$ and $(A_{2}^{m})$ are stable conditions, in the sense that if
they hold at a given point, they also hold at all points in some neighborhood
of the point.

###### Proposition 4.9

Assume that conditions $(A_{1}^{m})$ and $(A_{2}^{m})$ hold at
$(\bar{x},\bar{y},\bar{u})$. Then there exists a neighborhood $U\times V$ of
$(\bar{x},(\bar{y},\bar{u}))$ such that $(A_{1}^{m})$ and $(A_{2}^{m})$ hold
at any $(x,(y,u))\in U\times V$.

###### Proof 4.10

_Proof._ If such a neighborhood does not exist, then we can find a convergent
sequence $(x^{k},(y^{k},u^{k}))$ to $(\bar{x},(\bar{y},\bar{u}))$ as
$k\rightarrow\infty$ such that $(A_{1}^{m})$ or $(A_{2}^{m})$ does not hold at
$(x^{k},(y^{k},u^{k}))$. Assuming that $(A_{1}^{m})$ is not satisfied, there
exists a sequence $(\beta^{k},\gamma^{k})_{k}$ with
$\left\|(\beta^{k},\gamma^{k})\right\|=1$ such that we have the inclusion
$(\beta^{k},\gamma^{k})\in\Lambda^{em}(x^{k},y^{k},u^{k},0)$; i.e.,

$\left\\{\begin{array}[c]{l}\nabla_{x,y}\mathcal{L}(x^{k},y^{k},u^{k})^{\top}\beta^{k}+\nabla
g(x^{k},y^{k})^{\top}\gamma^{k}=0,\vskip 6.0pt plus 2.0pt minus 2.0pt\\\
\nabla_{y}g_{\nu^{k}}(x^{k},y^{k})\beta^{k}=0,\;\;\gamma_{\eta^{k}}^{k}=0,\vskip
6.0pt plus 2.0pt minus 2.0pt\\\
\left(\gamma_{i}^{k}>0\wedge\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k}>0\right)\vee\gamma_{i}^{k}\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k}=0\;\mbox{
for all }i\in\theta^{k},\end{array}\right.$ (4.33)

where $\theta^{k}:=\theta(x^{k},y^{k},u^{k}),$
$\eta^{k}:=\eta(x^{k},y^{k},u^{k})$, and $\nu^{k}:=\nu(x^{k},y^{k},u^{k})$.
Clearly,

$\theta^{k}\subset\theta,\text{ }\eta^{k}\subset\theta\cup\eta,\text{ and
}\nu^{k}\subset\theta\cup\nu\;\,\mbox{ for all }\;\,k\;\,\mbox{ sufficiently
large.}$ (4.34)

Taking into account that $i\in\eta^{k}$ for all $i\in\eta$ and $i\in\nu^{k}$
for all $i\in\nu$ whenever $k$ is sufficiently large, and by setting

$\bar{\gamma}_{i}^{k}:=\left\\{\begin{array}[c]{l}\gamma_{i}^{k}\text{\ \ if\
\ \ }i\in\theta\cup\nu,\vskip 6.0pt plus 2.0pt minus 2.0pt\\\ 0\text{ \ \ \
otherwise},\end{array}\right.$ (4.35)

the system of equations (4.33) becomes the following one:

$\left\\{\begin{array}[c]{l}\nabla_{x,y}\mathcal{L}(x^{k},y^{k},u^{k})^{\top}\beta^{k}+\nabla
g(x^{k},y^{k})^{\top}\bar{\gamma}^{k}=0,\vskip 6.0pt plus 2.0pt minus 2.0pt\\\
\nabla_{y}g_{\nu}(x^{k},y^{k})\beta^{k}=0,\text{ \ \
}\bar{\gamma}_{\eta}^{k}=0,\vskip 6.0pt plus 2.0pt minus 2.0pt\\\
(\bar{\gamma}_{i}^{k}>0\wedge\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k}>0)\vee\bar{\gamma}_{i}^{k}(\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k})=0\;\mbox{
for all }i\in\theta.\end{array}\right.$ (4.36)

Now without loss of generality, we may assume that the sequence
$(\beta^{k},\bar{\gamma}^{k})$ converges to $(\beta,\bar{\gamma})$ as
$k\rightarrow+\infty$ with $\left\|(\beta,\bar{\gamma})\right\|=1.$
Consequently, as all functions in (4.36) are continuous, we get

$\left\\{\begin{array}[c]{l}\nabla_{x,y}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{\top}\beta+\nabla
g(\bar{x},\bar{y})^{\top}\bar{\gamma}=0,\\\
\nabla_{y}g_{\nu}(\bar{x},\bar{y})\beta=0,\text{ \ }\bar{\gamma}_{\eta}=0,\\\
(\bar{\gamma}_{i}\geq 0\wedge\nabla_{y}g_{i}(\bar{x},\bar{y})\beta\geq
0)\vee\bar{\gamma}_{i}(\nabla_{y}g_{i}(\bar{x},\bar{y})\beta)=0\;\mbox{ for
all }i\in\theta.\end{array}\right.$

Now if for some $i\in\theta,$
$\bar{\gamma}_{i}(\nabla_{y}g_{i}(\bar{x},\bar{y})\beta)\neq 0$ then
$\bar{\gamma}_{i}>0$ and $\nabla_{y}g_{i}(\bar{x},\bar{y})\beta>0$ and so

$(\bar{\gamma}_{i}>0\wedge\nabla_{y}g_{i}(\bar{x},\bar{y})\beta>0)\vee\bar{\gamma}_{i}(\nabla_{y}g_{i}(\bar{x},\bar{y})\beta)=0\;\mbox{
for all }i\in\theta.$

Hence $(A_{1}^{m})$ is not satisfied at $(\bar{x},\bar{y},\bar{u})$ since
$0\neq(\beta,\bar{\gamma})\in\Lambda^{em}(\bar{x},\bar{y},\bar{u},0).$

Similarly if $(A_{2}^{m})$ is not satisfied, we can find a nonvanishing
sequence $(\beta^{k},\gamma^{k})$ such that

$\nabla_{x}\mathcal{L}(x^{k},y^{k},u^{k})^{\top}\beta^{k}+\nabla_{x}g(x^{k},y^{k})^{\top}\gamma^{k}\neq
0$

and $(\beta^{k},\gamma^{k})\in\Lambda_{y}^{em}(x^{k},y^{k},u^{k},0)$ so that,

$\left\\{\begin{array}[c]{l}\nabla_{y}\mathcal{L}(x^{k},y^{k},u^{k})^{\top}\beta^{k}+\nabla_{y}g(x^{k},y^{k})^{\top}\gamma^{k}=0,\vskip
6.0pt plus 2.0pt minus 2.0pt\\\
\nabla_{y}g_{v^{k}}(x^{k},y^{k})\beta^{k}=0,\;\;\gamma_{\eta^{k}}^{k}=0,\vskip
6.0pt plus 2.0pt minus 2.0pt\\\
\left(\gamma_{i}^{k}>0\wedge\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k}>0\right)\vee\gamma_{i}^{k}\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k}=0\;\mbox{
for all }i\in\theta^{k}.\end{array}\right.$

Taking the sequence $(\bar{\gamma}^{k})$ as in (4.35), we obtain

$\left\\{\begin{array}[c]{l}\nabla_{y}\mathcal{L}(x^{k},y^{k},u^{k})^{\top}\beta^{k}+\nabla_{y}g(x^{k},y^{k})^{\top}\bar{\gamma}^{k}=0,\vskip
6.0pt plus 2.0pt minus 2.0pt\\\
\nabla_{y}g_{\nu}(x^{k},y^{k})\beta^{k}=0,\text{ \ \
}\bar{\gamma}_{\eta}^{k}=0,\vskip 6.0pt plus 2.0pt minus 2.0pt\\\
(\bar{\gamma}_{i}^{k}>0\wedge\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k}>0)\vee\bar{\gamma}_{i}^{k}(\nabla_{y}g_{i}(x^{k},y^{k})\beta^{k})=0\;\mbox{
for all }i\in\theta,\end{array}\right.$

and assuming that the sequence $(\beta^{k},\bar{\gamma}^{k})$ (up to a
subsequence) converges to $(\beta,\bar{\gamma})$ as $k\rightarrow+\infty$ with
$\left\|(\beta,\bar{\gamma})\right\|=1,$ we clearly arrive at

$\left\\{\begin{array}[c]{l}\nabla_{y}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{\top}\beta+\nabla_{y}g(\bar{x},\bar{y})^{\top}\bar{\gamma}=0,\\\
\nabla_{y}g_{\nu}(\bar{x},\bar{y})\beta=0,\text{ \ }\bar{\gamma}_{\eta}=0,\\\
(\bar{\gamma}_{i}\geq 0\wedge\nabla_{y}g_{i}(\bar{x},\bar{y})\beta\geq
0)\vee\bar{\gamma}_{i}(\nabla_{y}g_{i}(\bar{x},\bar{y})\beta)=0\;\mbox{ for
all }i\in\theta,\end{array}\right.$

so that $(\beta,\bar{\gamma})\in\Lambda_{y}^{em}(\bar{x},\bar{y},\bar{u},0)$;
this implies, by $(A_{2}^{m})$, that

$\nabla_{x}\mathcal{L}(\bar{x},\bar{y},\bar{u})^{T}\beta+\nabla_{x}g(\bar{x},\bar{y})^{T}\bar{\gamma}=0.$

Hence $(\beta,\bar{\gamma})\in\Lambda^{em}(\bar{x},\bar{y},\bar{u},0),$
leading to $(\beta,\bar{\gamma})=0$, by $(A_{1}^{m})$ at
$(\bar{x},\bar{y},\bar{u})$. ∎

###### Theorem 4.11

Let $\bar{x}$ be an upper-regular point and suppose that the conditions
$(A_{1}^{m})$ and $(A_{2}^{m})$ hold at $(\bar{x},\bar{y},\bar{u})$ with
$(\bar{y},\bar{u})\in\mathcal{D}(\bar{x})$. Then there exists a neighborhood
$U\times V$ of $(\bar{x},(\bar{y},\bar{u}))$ such that for all $t$ close to
$0$, the constraint qualifications (4.7) and (4.17) for (KKTt) are satisfied
at all points $(x,(y,u))$ with $x\in U\cap X$ and $(y,u)\in
V\cap\mathcal{D}^{t}(x)$.

###### Proof 4.12

_Proof._ Since $\bar{x}$ is upper-regular, by continuity of $G$, the upper-
level regularity condition (4.7) is satisfied at all points $x\in X$, which
are sufficiently close to $\bar{x}$. Now from Proposition 4.9, there is a
neighborhood $U\times V$ of $(\bar{x},(\bar{y},\bar{u}))$ such that
$(A_{1}^{m})$ and $(A_{2}^{m})$ hold at any $(x,(y,u))\in U\times V$. Consider
now $t$ close to $0$ and $(x,(y,u))$ sufficiently close to
$(\bar{x},(\bar{y},\bar{u})),$ namely, $x\in U\cap X$ and $(y,u)\in
V\cap\mathcal{D}^{t}(x).$ Let $(\beta,\gamma,\delta,\mu)\in\mathbb{R}^{m+3q}$
such that

$\left\\{\begin{array}[c]{l}\nabla_{y}\mathcal{L}^{T}(x,y,u)\beta+\sum\limits_{i=1}^{q}(\gamma_{i}-\delta_{i}u_{i})\nabla_{y}g_{i}(x,y)=0,\\\
\nabla_{y}g_{i}(x,y)\beta-\mu_{i}-\delta_{i}g_{i}(x,y)=0,\;\,i=1,...,q,\\\\[4.30554pt]
\gamma_{i}\geq 0,\text{ }\delta_{i}\geq 0,\text{ }\mu_{i}\geq
0,\;\,i=1,...,q,\\\\[4.30554pt] \mu_{i}u_{i}=0,\text{ \
}\gamma_{i}g_{i}(x,y)=0,\text{ \
}\delta_{i}(u_{i}g_{i}(x,y)+t)=0,\;\,i=1,...,q.\end{array}\right.$

Hence, it follows that we have

$\nabla_{y}g_{i}(x,y)\beta=0\,\mbox{ for
}\,i\in\nu(x,y,u),\,\gamma_{i}=0\,\mbox{ for }\,i\in\eta(x,y,u),\,\mbox{ and
}\,\nabla_{y}g_{i}(x,y)\beta=\mu_{i}\,\mbox{ for }\,i\in\theta(x,y,u).$

Now setting

$\tilde{\gamma}_{i}:=\left\\{\begin{array}[]{lll}\gamma_{i}&\;\;\mbox{ if
}&i\in\mathrm{supp}\gamma,\\\ -\delta_{i}u_{i}&\;\;\mbox{ if
}&i\in\mathrm{supp}\delta,\\\ 0&\;\;\mbox{ if
}&\mbox{otherwise},\end{array}\right.$

leads to the conditions

$\nabla_{y}\mathcal{L}^{T}(x,y,u)\beta+\sum\limits_{i=1}^{q}\tilde{\gamma}i\nabla_{y}g_{i}(x,y)=0\;\;\mbox{
and }\;\;\left\\{\begin{array}[]{lll}\nabla_{y}g_{i}(x,y)\beta=0&\mbox{ for
}&i\in\nu(x,y,u),\\\ \tilde{\gamma}_{i}=0&\mbox{ for }&i\in\eta(x,y,u),\\\
\tilde{\gamma}_{i}\nabla_{y}g_{i}(x,y)\beta=\tilde{\gamma}_{i}\mu_{i}&\mbox{
for }&i\in\theta(x,y,u),\end{array}\right.$

and as $i\notin\mathrm{supp}\delta$ whenever $i\in\theta(x,y,u)$ so that for
all $i\in\theta(x,y,u)$,

$0\leq\tilde{\gamma}_{i}\nabla_{y}g_{i}(x,y)\beta\;\;=\;\;\left\\{\begin{array}[]{lll}\gamma_{i}\mu_{i}&\mbox{
if }&i\in\mathrm{supp}\gamma\cap\mathrm{supp}\mu,\\\
0&&\mbox{otherwise}.\end{array}\right.$

Thus, for any $i\in\theta(x,y,u)$, we have

$(\tilde{\gamma}_{i}=\gamma_{i}>0\wedge\nabla_{y}g_{i}(x,y)\beta=\mu_{i}>0)\vee\tilde{\gamma}_{i}\nabla_{y}g_{i}(x,y)\beta=0$

so that $(\beta,\tilde{\gamma})\in\Lambda_{y}^{em}(x,y,u,0)$. Applying
$(A_{2}^{m})$, we get
$\nabla_{x}\mathcal{L}(x,y,u)^{T}\beta+\nabla_{x}g(x,y)^{T}\tilde{\gamma}=0$
and thus $(\beta,\tilde{\gamma})\in\Lambda^{em}(x,y,u,0)$, which implies, by
$(A_{1}^{m})$, that $\beta=0$ and $\tilde{\gamma}=0.$ ∎

##  5 Conclusion and topics for future work.

We have considered the KKT reformulation of the pessimistic bilevel
optimization problem (KKT) and built a theoretical framework to solve it by
iteratively computing a sequence of solutions of the relaxation problem (KKTt)
for $t:=t^{k}$ as $t^{k}\downarrow 0$. Then, considering the fact that problem
($P_{p}$) is globally/local equivalent to problem (KKT), under mild
assumptions, solving the corresponding class of the pessimistic bilevel
program boils down to solving min-max optimization problems. Solving min-max
optimization problems of the type in (KKTt) is not an easy task, especially as
the inner constraints there are parameterized by $(y,u)$ even as we fix $t>0$;
a detailed analysis of the complexity of solving such problems is conducted in
the recent paper [5]. Hence, our immediate next goal will be to conduct a
detailed study on the most tractable approach to compute global and local
optimal solutions for problem (KKTt) for fixed $t>0$. Secondly, we will pay
attention on designing an algorithm to directly compute C-stationary points by
means of solving the optimality conditions in (4.9)–(4.16). There is a wide
range of techniques to transform (4.13)–(4.16) into an equivalent system of
nonsmooth equations. Thus, the challenge in solving (4.9)–(4.16) with
approaches such as Newton-type methods resides in finding tractable
transformations for inclusion (4.9). Possible approaches to tackle this could
include the application of generalized equations transformations (see, e.g.,
[26]) or relaxation techniques based on optimal value functions such as the
ones used in [16, 17, 34, 39]. All these questions will form the basis of
future works, building from results of this paper, which have the potential to
enable tractable algorithms for the pessimistic bilevel optimization problem
($P_{p}$).

## Acknowledgments.

The work of AZ is supported by the EPSRC grant EP/V049038/1 and the Alan
Turing Institute under the EPSRC grant EP/N510129/1.

## References

  * [1] Aragón Artacho FJ, Mordukhovich BS (2011) Enhanced metric regularity and Lipschitzian properties of variational systems. _J. Global Optim._ 50(1):145-167.
  * [2] Aussel D, Svensson A (2019) Is Pessimistic bilevel programming a special case of a mathematical program with complementarity constraints? _J. Optim. Theory Appl._ 181:504-520.
  * [3] Bank B, Guddat J, Klatte D, Kummer B, Tammer K (1982) _Non-linear Parametric Optimization_ (Akademie-Verlag, Berlin).
  * [4] Červinka M, Matonoha C, Outrata JV (2013) On the computation of relaxed pessimistic solutions to MPECs. _Optim. Methods Softw._ 28(1):186-206.
  * [5] Daskalakis C, Skoulakis S, Zampetakis M (2021) The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 1466-1478.
  * [6] Dempe S (2002) _Foundations of Bilevel Programming_ (Kluwer Academic Publishers, London).
  * [7] Dempe S, Dutta J, (2012) Is bilevel programming a special case of a mathematical program with complementarity constraints? _Math. Program._ 131(1):37-48.
  * [8] Dempe S, Mordukhovich BS, Zemkoho AB (2014) Necessary optimality conditions in pessimistic bilevel programming. _Optimization_ 63(4):505-533.
  * [9] Dempe S, Mordukhovich BS, Zemkoho AB (2012) Sensitivity analysis for two-level value functions with applications to bilevel programming. _SIAM J. Optim._ 22(4):1309-1343.
  * [10] Dempe S, Mordukhovich BS, Zemkoho AB (2019) Two-level value function approach to non-smooth optimistic and pessimistic bilevel programs. _Optimization_ 68(2-3):433–455.
  * [11] Dempe S, Zemkoho AB (2014) KKT reformulation and necessary conditions for optimality in nonsmooth bilevel optimization. _SIAM J. Optim._ 24(4):1639-1669.
  * [12] Dempe S, Zemkoho AB (2012) On the Karush–Kuhn–Tucker reformulation of the bilevel optimization problem. _Nonlinear Anal._ 75(3):1202-1218.
  * [13] Dempe S, Zemkoho AB, eds. (2020) _Bilevel Optimization: Advances and Next Challenges_ (Springer, Cham).
  * [14] Durea M, Strugariu R (2012) Openness stability and implicit multifunction theorems, applications to variational systems. _SIAM J. Optim._ 22:899-913.
  * [15] Fischer A (1992) A special newton-type optimization method. _Optimization_ 24(3-4):269-284.
  * [16] Fischer A, Zemkoho AB, Zhou S (2021) Semismooth Newton-type method for bilevel optimization: Global convergence and extensive numerical experiments. _Optim. Methods Softw._ DOI:10.1080/10556788.2021.1977810
  * [17] Fliege J, Tin A, Zemkoho AB (2021) Gauss Newton-type methods for bilevel optimization. _Comput. Optim. Appl._ 78:793–824.
  * [18] Hoheisel T, Kanzow C, Schwartz A (2013) Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. _Math. Prog. Ser. A_ 137:257-288.
  * [19] Lampariello L, Sagratella S, Stein O (2019) The standard pessimistic bilevel problem. _SIAM J. Optim._ 29(2):1634-1656.
  * [20] Lin GH, Fukushima M (2005) A modified relaxation scheme for mathematical programs with complementarity contraints. _Ann. Oper. Res._ 133:63-84.
  * [21] Loridan P, Morgan J (1989) $\varepsilon$–regularized two-level optimization problems: approximation and existence results. Dolecki S, ed._Optimization. Lecture Notes in Mathematics_ (Springer, Berlin, Heidelberg) 99-113.
  * [22] Loridan P, Morgan J (1996) Weak via strong Stackelberg problem: new results. _J. Global Optim._ 8(3):263-287.
  * [23] Mordukhovich BS (1993) Complete characterization of openness, meric regularity, and Lipschitzian properties of multifunctions. _Trans. Amer. Math. Soc._ 340(1):1-35.
  * [24] Mordukhovich BS (1980) Metric approximations and necessary optimality conditions for general classes of extremal problems. _Dokl. Akad. Nauk SSSR_ 254(5):1072–1076.
  * [25] Mordukhovich BS (2006) _Variational Analysis and Generalized Differentiation. I: Basic Theory. II: Applications_ (Springer, Berlin).
  * [26] Mordukhovich BS, Outrata JV (2007) Coderivative analysis of quasi-variational inequalities with applications to stability and optimization. _SIAM J. Optim._ 18(2):389–412.
  * [27] Mordukhovich BS, Nam NM (2005) Variational stability and marginal function via generalized differentiation. _Math. Oper. Res._ 30:800-816.
  * [28] Mordukhovich BS, Nam NM, Phan HM (2012) Variational analysis of marginal functions with applications to bilevel programming. _J. Optim. Theory Appl._ 152:557-586.
  * [29] Mordukhovich BS, Nam MN, Yen ND (2009) Subgradients of marginal functions in parametrics mathematical programming. _Math. Program._ 116:369-396.
  * [30] Outrata J, Kocvara M, Zowe J (2013) _Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results_ (Kluwer Academic Publishers, Dordrecht).
  * [31] Qi L, Wei Z (2000) On the constraint positive linear dependence condition and its application to SQP methods. _SIAM J. Optim._ 10(4):963-981.
  * [32] Rockafellar RT, Wets RJ (1998) _Variational Analysis_ (Springer-Verlag, Berlin, Heidelberg).
  * [33] Scholtes S (2001) Convergence properties of a regularisation scheme for mathematical programs with complementarity constraints. _SIAM J. Optim._ 11:918-936.
  * [34] Tin A, Zemkoho AB (2021) Levenberg-Marquardt method and partial exact penalty parameter selection in bilevel optimization. arXiv preprint arXiv:2101.09521
  * [35] Wiesemann W, Tsoukalas A, Kleniati PM, Rustem B (2013) Pessimistic bilevel optimization. _SIAM J. Optim._ 23(1):353-380.
  * [36] Ye JJ (2000) Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints, _SIAM J. Optim._ 10(4):943-962.
  * [37] Zemkoho AB (2014) A simple approach to optimality conditions in minmax programming. _Optimization_ 63(3):385-401.
  * [38] Zemkoho AB (2016) Solving ill-posed bilevel programs. _Set-Valued Var. Anal._ 24(3):423-48.
  * [39] Zemkoho AB, Zhou S (2021) Theoretical and numerical comparison of the Karush-Kuhn-Tucker and value function reformulations in bilevel optimization. _Comp. Optim. Appl._ 78(2):625-674.
  * [40] Zhou S, Zemkoho AB, Tin A (2020) BOLIB: Bilevel Optimization LIBrary of test problems. Dempe S, Zemkoho AB, eds. _Bilevel Optimization: Advances and Next Challenges_ (Springer, Cham), 563-580.