# Optimality conditions for bilevel programs via Moreau envelope reformulation

Kuang Bai Department of Applied Mathematics, The Hong Kong Polytechnic
University, Hong Kong, People’s Republic of China. The research of this author
was partially supported by the NSFC Grant 12201531 and the Hong Kong Research
Grants Council PolyU153036/22p. Email<EMAIL_ADDRESS> Jane J. Ye
Corresponding author. Department of Mathematics and Statistics, University of
Victoria, Canada. The research of this author was partially supported by
NSERC. Email<EMAIL_ADDRESS>Shangzhi Zeng Department of Mathematics and
Statistics, University of Victoria, Canada. Email<EMAIL_ADDRESS>
###### Abstract

For bilevel programs with a convex lower level program, the classical approach
replaces the lower level program with its Karush-Kuhn-Tucker condition and
solve the resulting mathematical program with complementarity constraint
(MPCC). It is known that when the set of lower level multipliers is not
unique, MPCC may not be equivalent to the original bilevel problem, and many
MPCC-tailored constraint qualifications do not hold. In this paper, we study
bilevel programs where the lower level is generalized convex. Applying the
equivalent reformulation via Moreau envelope, we derive new directional
optimality conditions. Even in the nondirectional case, the new optimality
condition is stronger than the strong stationarity for the corresponding MPCC.

Key words. bilevel programs, Moreau envelope, constraint qualifications,
sensitivity analysis, directional metric subregularity, necessary optimality
conditions

AMS subject classification: 90C26, 90C30, 90C31, 90C46.

##  1 Introduction

In this paper, we consider the standard bilevel program:

$\displaystyle\mbox{(BP)}\quad\min_{x,y}\quad F(x,y)\ s.t.\ \ y\in S(x),\
G(x,y)\leq 0,$

where for any given $x$, $S(x)$ denotes the solution set of the lower level
program

$(P_{x})\quad\min_{y}f(x,y)\ \ \mbox{s.t. }g(x,y)\leq 0.$

In this paper unless otherwise specified we assume that and
$F,f:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R},\
G:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}^{q}$,
$g:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}^{p}$ are
continuously differentiable and the lower level program is generalized convex
in the following sense.

######  Assumption 1.1 (Generalized convexity of the lower level program)

For each $x$, $f$ is convex in $y$ and $g$ is quasi-convex in variable $y$,
i.e., the level set $\left\\{y|g(x,y)\leq r\right\\}$ is convex for all real
number $r$.

Under the lower level generalized convexity if a certain constraint
qualification for (Px) holds at $y$, then $y\in S(x)$ if any only if there
exists a Lagrange multiplier $\lambda$ satisfying the Karush-Kuhn-Tucker (KKT)
condition, i.e.,

$\nabla_{y}f(x,y)+\nabla_{y}g(x,y)^{T}\lambda=0,\ 0\leq\lambda\perp g(x,y)\leq
0.$

Denote the set of all Lagrange multipliers of (Px) at $y$ by $\Lambda(x,y)$.
If the lower level program is generalized convex and a certain constraint
qualification holds, then (BP) is equivalent to the following single-level
problem

$\displaystyle\quad\begin{array}[]{ll}\min_{x,y}{}&F(x,y)\\\ s.t.{}&G(x,y)\leq
0,\mbox{ there exists }\lambda\in\Lambda(x,y).\end{array}$

However the above problem is not track-able. Hence instead of considering the
above equivalent problem, it became popular to study the following related
problem

$\displaystyle{\rm(MPCC)}\quad\begin{array}[]{ll}\min_{x,y,\lambda}{}&F(x,y)\\\
s.t.{}&G(x,y)\leq 0,\ \nabla_{y}f(x,y)+\nabla g(x,y)^{T}\lambda=0,\
0\leq\lambda\perp g(x,y)\leq 0,\end{array}$

which is a mathematical program with complementarity constraint (MPCC). This
approach is the so-called first-order approach or the KKT approach, which was
popularly studied over the last three decades; see e.g. [27, 34, 10] for the
general theory and [39, 41, 44, 21, 12] for the optimality conditions derived
by using this approach. Now in addition, we assume the functions $f,g$ are
twice continuously differentiable and recall the S-stationarity condition for
(MPCC):

###### Definition 1.1

[41, Definition 2.7] A vector $(\bar{x},\bar{y},\bar{\lambda})$ is said to be
strong (S-)stationary of (MPCC) if there exists
$(\mu_{G},\mu_{g},\mu_{e},\mu_{\lambda})\in\mathbb{R}^{q+p+m+q}$ such that

$\displaystyle\nabla F(\bar{x},\bar{y})+\nabla
G(\bar{x},\bar{y})^{T}\mu_{G}+\nabla
g(\bar{x},\bar{y})^{T}\mu_{g}+\nabla_{x,y}l(\bar{x},\bar{y},\bar{\lambda})^{T}\mu_{e}=0,$
(3)
$\displaystyle\nabla_{\lambda}l(\bar{x},\bar{y},\bar{\lambda})^{T}\mu_{e}-\mu_{\lambda}=0,$
$\displaystyle 0\leq\mu_{G}\perp G(\bar{x},\bar{y})\leq 0,\
\mu_{\lambda}\perp\bar{\lambda},\ \mu_{g}\perp g(\bar{x},\bar{y})\leq 0,$
$\displaystyle\nabla_{y}f(\bar{x},\bar{y})+\nabla
g(\bar{x},\bar{y})^{T}\bar{\lambda}=0,\ 0\leq\bar{\lambda}\perp
g(\bar{x},\bar{y})\leq 0,$ $\displaystyle(\mu_{g})_{j}\geq 0\ \mbox{and}\
(\mu_{\lambda})_{j}\geq 0,\ \forall j\in
I_{0}(\bar{x},\bar{y}):=\\{j|\bar{\lambda}_{j}=0,g_{j}(\bar{x},\bar{y})=0\\},$

where $l(x,y,\lambda):=\nabla_{y}f(x,y)+\nabla_{y}g(x,y)^{T}\lambda.$

It is well-known that if $(\bar{x},\bar{y},\bar{\lambda})$ is a local optimal
solution of (MPCC) satisfying the MPCC linear independent constraint
qualification (MPCC-LICQ) [41, Definition 2.8], then it must be S-stationary.

Although (MPCC) is more track-able than the original bilevel program, there
are two major drawbacks of using the KKT approach. First, when the set of
multipliers $\Lambda(x,y)$ is not a singleton for certain feasible solution
$(x,y)$, (MPCC) is usually not equivalent to (BP) if local optimality is
considered. Specifically, if $(\bar{x},\bar{y},\bar{\lambda})$ is a local
minimizer of (MPCC), $(\bar{x},\bar{y})$ may not be a local minimizer of (BP);
see the details in Dempe and Dutta [11]. Secondly, MPCC variant of
Mangasarian-Fromovitz constraint qualification (MPCC-MFCQ) may not hold at
feasible points of (MPCC). In fact for the case where $g(x,y)$ is independent
of $x$, Gfrerer and Ye [20] showed that when $\Lambda(x,y)$ is not a singleton
for all feasible $(x,y)$, MPCC-MFCQ is never satisfied by any feasible
solution of (MPCC). Furthermore, in this case even the MPCC Guignard
constraint qualification (MPCC-GCQ), one of the weakest MPCC-tailored
constraint qualifications may not be valid.

Another way to reformulate (BP) as a single level problem is the value
function approach, which was first proposed in [33] for numerical purpose.
Using the optimal value function $v(x):=\inf_{y}\\{f(x,y)|g(x,y)\leq 0\\}$ of
the lower level program, the constraint $y\in S(x)$ can always be equivalently
replaced by inequalities $f(x,y)-v(x)\leq 0,g(x,y)\leq 0$. Ye and Zhu [46]
studied the optimality condition of the resulting single-level program

(VP) $\displaystyle\min_{x,y}\quad F(x,y)$ $\displaystyle s.t.\quad
f(x,y)-v(x)\leq 0,\ g(x,y)\leq 0,\ G(x,y)\leq 0.$

Under the Lipschitz continuity of the value function and a certain constraint
qualification, at a feasible solution $(\bar{x},\bar{y})$, the nonsmooth
stationary condition in terms of Clarke subdifferential can be written as
follows: there exist
$(\alpha,\lambda_{g},\lambda_{G})\in\mathbb{R}_{+}\times\mathbb{R}^{p+q}$ such
that

$\displaystyle 0\in\nabla F(\bar{x},\bar{y})+\alpha(\nabla
f(\bar{x},\bar{y})-\partial^{c}v(\bar{x})\times\\{0\\})+\nabla
g(\bar{x},\bar{y})^{T}\lambda_{g}+\nabla G(\bar{x},\bar{y})^{T}\lambda_{G},$
(4) $\displaystyle 0\leq\lambda_{g}\perp g(\bar{x},\bar{y})\leq 0,\
0\leq\lambda_{G}\perp G(\bar{x},\bar{y})\leq 0,$

where $\partial^{c}v$ denotes the Clarke subdifferential of the value function
$v$. However, the value function is implicitly defined, and to develop a
verifiable optimality condition, there are two major challenges. First, it is
known that KKT conditions may not hold at a local minimizer unless a certain
constraint qualification holds. Since the strict inequality $f(x,y)-v(x)<0$ is
nowhere satisfied in the feasible region, the no nonzero abnormal multiplier
constraint qualification (NNAMCQ) fails at any feasible point of (VP). This
means constraint qualifications weaker than NNAMCQ need to be employed.
Secondly, $\partial^{c}v$ is implicitly defined. Under appropriate conditions,
say the restricted inf-compactness condition (see e.g. [23, Definition 3.8])
plus the MFCQ at each optimal point, one has the Lipschitz continuity of the
value function and an upper estimate can be stated as follows:

$\partial^{c}v(\bar{x})\subseteq{\rm co}\bigcup_{y\in
S(\bar{x})}\bigcup_{\lambda\in\Lambda(\bar{x},y)}\\{\nabla_{x}f(\bar{x},y)+\nabla_{x}g(\bar{x},y)^{T}\lambda\\},$

where ${\rm co}C$ denotes the convex hull of set $C$. In the literature (see
e.g., [46]), to get an explicit optimality condition, one would replace the
set $\partial^{c}v(\bar{x})$ by its upper estimates. Hence, to verify the
optimality condition, one has to check each point in $S(\bar{x})$. Moreover,
the resulting stationary system is not computable by any algorithms if
$S(\bar{x})$ is not a singleton. A natural question is: in application, can we
find all elements in $S(\bar{x})$? The answer is yes when bilevel polynomial
programs are considered, see e.g., [31, 32]. But for general (BP), it is hard
to calculate the set $S(\bar{x})$. A natural idea is to replace $S(\bar{x})$
by a smaller set. If either the functions $f,g$ are convex in both variables
$x$ and $y$ or the inner semicontinuity (see e.g., [29]) of $S(x)$ at
$(\bar{x},\bar{y})$ holds, then $S(\bar{x})$ in the union is replaced by
$\\{\bar{y}\\}$, i.e.,

$\displaystyle\partial^{c}v(\bar{x})\subseteq\bigcup_{\lambda\in\Lambda(\bar{x},\bar{y})}\\{\nabla_{x}f(\bar{x},\bar{y})+\nabla_{x}g(\bar{x},\bar{y})^{T}\lambda\\}.$

By replacing $\partial^{c}v(\bar{x})$ in (LABEL:KKTVP) with an element in the
above upper estimate, the following KKT stationary condition can be obtained:
there exist
$(\alpha,\lambda_{g},\lambda_{G})\in\mathbb{R}_{+}\times\mathbb{R}^{p+q}$ and
$\bar{\lambda}\in\Lambda(\bar{x},\bar{y})$ such that

$\displaystyle 0=\nabla F(\bar{x},\bar{y})+\nabla
g(\bar{x},\bar{y})^{T}(\lambda_{g}-\alpha\bar{\lambda})+\nabla
G(\bar{x},\bar{y})^{T}\lambda_{G},$ (5) $\displaystyle 0\leq\lambda_{g}\perp
g(\bar{x},\bar{y})\leq 0,\ 0\leq\lambda_{G}\perp G(\bar{x},\bar{y})\leq 0.$

Let $\mu_{g}:=\lambda_{g}-\alpha\bar{\lambda},.$ Then $(\mu_{g})_{j}\geq 0$ if
$\bar{\lambda}_{j}=0$. Hence
$(\mu_{G},\mu_{g},\mu_{e},\mu_{\lambda}):=(\lambda_{G},\lambda_{g}-\alpha\bar{\lambda},0,0)$
satisfies the stationary condition (3). Therefore the stationary condition (5)
is stronger than the S-stationary condition (3) for problem (MPCC). Moreover
unlike in the MPCC reformulation, the multiplier $\bar{\lambda}$ is not
arbitrarily given, it is selected from the set of multipliers
$\Lambda(\bar{x},\bar{y})$. The optimality condition in the form (5) was first
derived in [40, Theorem 4.2] (see also [42, Theorem 4.1 and Corollary 4.1] and
[43, Theorem 8.8.3], [24, Lemma 5.1(c)]) under the joint convexity assumption
on the lower level program (i.e., $f,g$ convex in both variables $x,y$), or
under the semicontinuity of the solution set (see e.g. [30, Theorem 6.21]) and
is used in some recent work on semismooth Newton method for solving bilevel
programs [24, 37, 14].

However, the joint convexity of the lower level program or the inner
semicontinuity property of the solution map is quite strictive. So the problem
is left to be solved: are there other conditions that also allow us to derive
the KKT condition as the simple system (5).

Recently, Gao et al. [15] proposed a modified value function reformulation for
(BP). For any given $x,y,\gamma>0$, we define the Moreau envelope function of
the lower level program as

$\displaystyle v_{\gamma}(x,y)$
$\displaystyle:=\inf_{w}\left\\{\left.f(x,w)+\frac{1}{2\gamma}\|w-y\|^{2}\right|g(x,w)\leq
0\right\\}.$

When the lower level program $(P_{x})$ is generalized convex, the constraint
$y\in S(x)$ can be equivalently replaced by $f(x,y)-v_{\gamma}(x,y)\leq
0,g(x,y)\leq 0$. Hence, (BP) can be equivalently reformulated as:

${\rm(VP)}_{\gamma}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\begin{aligned}
\min_{(x,y)}~{}~{}&F(x,y)\\\ s.t.~{}~{}~{}~{}&f(x,y)-v_{\gamma}(x,y)\leq 0,\
g(x,y)\leq 0,\ G(x,y)\leq 0.\end{aligned}$

Provided that $v_{\gamma}$ is Lipschitz continuous, one can immediately write
out the KKT stationary condition for (VP)γ: there exist
$(\alpha,\lambda_{g},\lambda_{G})\in\mathbb{R}_{+}\times\mathbb{R}^{p+q}$ such
that

$\displaystyle 0\in\nabla F(\bar{x},\bar{y})+\alpha(\nabla
f(\bar{x},\bar{y})-\partial^{c}v_{\gamma}(\bar{x},\bar{y}))+\nabla
g(\bar{x},\bar{y})^{T}\lambda_{g}+\nabla G(\bar{x},\bar{y})^{T}\lambda_{G},$
(6) $\displaystyle 0\leq\lambda_{g}\perp g(\bar{x},\bar{y})\leq 0,\
0\leq\lambda_{G}\perp G(\bar{x},\bar{y})\leq 0.$

Generally, it is easier to study KKT condition (6) than (LABEL:KKTVP). Indeed,
when $\gamma$ is sufficiently small, the objective function
$f(x,w)+\frac{1}{2\gamma}\|w-y\|^{2}$ is coercive. As a result, many
regularity conditions for sensitivity analysis of $v_{\gamma}$ hold
automatically, and under relatively weak assumptions, say the MFCQ of the
system $g(\bar{x},y)\leq 0$ at $\bar{y}\in S(\bar{x})$, we have the upper
estimate:

$\partial^{c}v_{\gamma}(\bar{x},\bar{y})\subseteq\bigcup_{\lambda\in\Lambda(\bar{x},\bar{y})}\left\\{(\nabla_{x}f(\bar{x},\bar{y})+\nabla_{x}g(\bar{x},\bar{y})^{T}\lambda,0)\right\\}.$

It is interesting that replacing $\partial^{c}v_{\gamma}(\bar{x},\bar{y})$ by
the above upper estimate still results in the KKT stationary system (5).
Besides, the above upper estimate for $v_{\gamma}$ is sharper than that for
the value function $v(x)$ in the absence of full convexity; see e.g., [16, 2].
Hence, the resulting optimality condition is stronger than classical
optimality conditions for (VP).

Another direction to improve the value function approach is to consider the
directional constraint qualifications and KKT conditions. Recently, Bai and Ye
[1] derived directional KKT condition for (VP) under the directional calmness
condition, where the value function $v(x)$ is assumed to be directionally
Lipschitz continuous and directionally differentiable along a certain
direction, and the solution set $S(x)$ is replaced by the solution along
certain critical direction which is in general is a smaller subset of $S(x)$.
Since these directional conditions are usually weaker than their non-
directional counterparts, the resulting directional KKT condition is in
general sharper and the directional constraint qualification is weaker than
the nondirectional counterpart.

In this paper, by using the Moreau envelope reformulation, we derive a
directional version of the KKT system (5) under the directional calmness
condition. We also derive some verifiable directional quasi-normality
condition as sufficient conditions for the directional calmness condition.
Note that the directional version of the KKT system is in general stronger
than the nondirectional KKT system while the directional calmness condition is
in general weaker than the nondirectional calmness condition. A direct
consequence of our result gives some new conditions under which the KKT system
(5) holds without assuming either full convexity of the lower level problem or
the inner semicontinuity of the solution map $S(x)$.

We organize the paper as follows. In the next section, we provide notations,
preliminaries and preliminary results. In Section 3 we derive the directional
KKT condition under the directional calmness condition for a nonsmooth
nonlinear optimization problem. In Section 4, we study directional sensitivity
analysis of the Moreau envelope function. In Section 5, we apply the results
of previous sections to (VP)γ and derive a verifiable necessary optimality
condition. We conclude the paper in Section 6.

##  2 Preliminaries and preliminary results

We first give notations that will be used in the paper. We denote by
$\overline{\mathbb{R}}:=\mathbb{R}\cup\\{\pm\infty\\}$, while
$\mathbb{R}:=(-\infty,+\infty)$. $\|\cdot\|$ denotes the Euclidean norm.
$\langle a,b\rangle$ denotes the inner product of vectors $a,b$, and $a\perp
b$ means the inner product $\langle a,b\rangle=0$. Let $\Omega$ be a set. By
$x^{k}\xrightarrow{\Omega}\bar{x}$ we mean $x^{k}\rightarrow\bar{x}$ and for
each $k$, $x^{k}\in\Omega$. By $x^{k}\xrightarrow{u}\bar{x}$ where $u$ is a
vector, we mean that the sequence $\\{x^{k}\\}$ approaches $\bar{x}$ in
direction $u$, i.e., there exist $t_{k}\downarrow 0,u^{k}\rightarrow u$ such
that $x^{k}=\bar{x}+t_{k}u^{k}$. By $o(t)$, we mean $\lim_{t\rightarrow
0}\frac{o(t)}{t}=0$. We denote by $\mathbb{B}$, $\bar{\mathbb{B}}$,
$\mathbb{S}$ the open unit ball, the closed unit ball and the unit sphere,
respectively. $\mathbb{B}_{\delta}(\bar{z})$ denotes the open unit ball
centered at $\bar{z}$ with radius $\delta$. We denote by ${\rm ri}\Omega$,
${\rm int}\Omega$, ${\rm co}\Omega$ and $cl\Omega$ the relative interior, the
interior, the convex hull and the closure of a set $\Omega$, respectively. The
distance from a point $x$ to a set $\Omega$ is denoted by ${\rm
dist}(x,\Omega):=\inf\\{\|x-y\||y\in\Omega\\}$, the indicator function of the
set $\Omega$ is denoted by $\delta_{\Omega}(x)$, and the support function of
set $\Omega$ is denoted by $\sigma_{\Omega}(x):=\sup\\{\langle
x,y\rangle|y\in\Omega\\}$. For a single-valued map
$\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$, we denote by
$\nabla\phi(x)\in\mathbb{R}^{m\times n}$ the Jacobian matrix of $\phi$ at $x$
and for a function $\varphi:\mathbb{R}^{n}\rightarrow\mathbb{R}$, we denote by
$\nabla\varphi(x)$ the gradient of $\varphi$ at $x$. Denote the pre-image of
set $\Omega\subseteq\mathbb{R}^{m}$ under map $\phi$ by
$\phi^{-1}(\Omega):=\\{x\in\mathbb{R}^{n}|\phi(x)\in\Omega\\}$. For a set-
valued map $\Phi:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ the graph of
$\Phi$ is defined by gph$\Phi:=\\{(x,y)|y\in\Phi(x)\\}$. For an extended-
valued function $\varphi:\mathbb{R}^{n}\rightarrow\overline{\mathbb{R}}$, we
define its domain by $dom\varphi:=\\{x\in\mathbb{R}^{n}|\varphi(x)<\infty\\}$,
and its epigraph by
$epi\varphi:=\\{(x,\alpha)\in\mathbb{R}^{n+1}|\alpha\geq\varphi(x)\\}$. For a
function $g:\mathbb{R}^{n}\rightarrow\mathbb{R}$, we denote
$g_{+}(x):=\max\\{0,g(x)\\}$ and if it is vector-valued then the maximum is
taken componentwise.

In the following, we gather some basic concepts and prove some results in
variational analysis, which will be used later on. For more details see e.g.
[7, 8, 9, 13, 26, 29, 36].

######  Definition 2.1 (Tangent Cone and Normal Cone)

(see, e.g., [36, Definitions 6.1 and 6.3]) Given a set
$\Omega\subseteq\mathbb{R}^{n}$ and a point $\bar{x}\in\Omega$, the tangent
cone to $\Omega$ at $\bar{x}$ is defined as

$T_{\Omega}(\bar{x}):=\left\\{d\in\mathbb{R}^{n}|\exists t_{k}\downarrow
0,d_{k}\rightarrow d\ \mbox{ s.t. }\bar{x}+t_{k}d_{k}\in\Omega\ \forall
k\right\\}.$

The regular normal cone and the limiting normal cone to $\Omega$ at $\bar{x}$
are defined as

$\displaystyle\widehat{N}_{\Omega}(\bar{x})$ $\displaystyle:=$
$\displaystyle\left\\{\zeta\in\mathbb{R}^{n}\bigg{|}\langle\zeta,x-\bar{x}\rangle\leq
o(\|x-\bar{x}\|)\quad\forall x\in\Omega\right\\},$ $\displaystyle
N_{\Omega}(\bar{x})$ $\displaystyle:=$
$\displaystyle\left\\{\zeta\in\mathbb{R}^{n}\bigg{|}\exists\
x_{k}\xrightarrow{\Omega}\bar{x},\ \zeta_{k}{\rightarrow}\zeta\ \text{such
that}\ \zeta_{k}\in\widehat{N}_{\Omega}(x_{k})\ \forall k\right\\},$

respectively.

######  Definition 2.2 (Directional Normal Cone)

([22, Definition 2.3] or [17, Definition 2]). Given a set
$\Omega\subseteq\mathbb{R}^{n}$, a point $\bar{x}\in\Omega$ and a direction
$u\in\mathbb{R}^{n}$, the limiting normal cone to $\Omega$ at $\bar{x}$ in
direction $u$ is defined by

$N_{\Omega}(\bar{x};u):=\left\\{\zeta\in\mathbb{R}^{n}\bigg{|}\exists\
t_{k}\downarrow 0,u_{k}\rightarrow u,\zeta_{k}\rightarrow\zeta\mbox{ s.t.
}\zeta_{k}\in\widehat{N}_{\Omega}(\bar{x}+t_{k}u_{k})\ \forall k\right\\}.$

It is obvious that $N_{\Omega}(\bar{x};0)=N_{\Omega}(\bar{x})$,
$N_{\Omega}(\bar{x};u)=\emptyset$ if $u\not\in T_{\Omega}(\bar{x})$ and
$N_{\Omega}(\bar{x};u)\subseteq N_{\Omega}(\bar{x})$. Moreover when $\Omega$
is convex, by [18, Lemma 2.1] the directional and the classical normal cone
have the following relationship

$N_{\Omega}(\bar{x};u)=N_{\Omega}(\bar{x})\cap\\{u\\}^{\perp}\qquad\forall
u\in T_{\Omega}(\bar{x}).$ (7)

When $u=0$ the following definition coincides with the Painlevé-Kuratowski
inner/lower and outer/upper limit of $\Phi$ as $x\rightarrow\bar{x}$
respectively; see e.g., [29].

###### Definition 2.3

Given a set-valued map $\Phi:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$
and a direction $u\in\mathbb{R}^{n}$, the inner/lower and outer/upper limit of
$\Phi$ as $x\xrightarrow{u}\bar{x}$ respectively is defined by

$\displaystyle\liminf_{x\xrightarrow{u}\bar{x}}\Phi(x)$
$\displaystyle:=\\{y\in\mathbb{R}^{m}|\forall\ \mbox{sequence}\
t_{k}\downarrow 0,u^{k}\rightarrow u,\exists y^{k}\rightarrow y\mbox{ s.t.
}y^{k}\in\Phi(\bar{x}+t_{k}u^{k})\\},$
$\displaystyle\limsup_{x\xrightarrow{u}\bar{x}}\Phi(x)$
$\displaystyle:=\\{y\in\mathbb{R}^{m}|\exists\ \mbox{sequence}\
t_{k}\downarrow 0,u^{k}\rightarrow u,y^{k}\rightarrow y\mbox{ s.t.
}y^{k}\in\Phi(\bar{x}+t_{k}u^{k})\\},$

respectively.

######  Definition 2.4 (Graphical and Directional Derivatives)

[36, Page 199]Let $\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ and
$x,u\in\mathbb{R}^{n}$. The graphical derivative of $\phi$ at $x$ is

$D\phi(x)(u):=\left\\{v\left|\exists t_{k}\downarrow 0,u_{k}\rightarrow u\
s.t.~{}v=\lim_{k\rightarrow+\infty}\frac{\phi(x+t_{k}u_{k})-\phi(x)}{t_{k}}\right.\right\\}.$

When $m=1$, the upper-/lower-Dini derivative of $\phi$ at $x$ in direction $u$
is

$\displaystyle\phi^{\prime}_{+}(x;u):=\limsup_{t\downarrow
0}\frac{\phi(x+tu)-\phi(x)}{t},$
$\displaystyle\phi^{\prime}_{-}(x;u):=\liminf_{t\downarrow
0}\frac{\phi(x+tu)-\phi(x)}{t}.$

The usual directional derivative of $\phi$ at $x$ in the direction $u$ is

$\phi^{\prime}(x;u):=\lim_{t\downarrow 0}\frac{\phi(x+tu)-\phi(x)}{t}$

when this limit exists.

Below we review the concept of directional neighborhood introduced by Gfrerer
in [17]. Given a direction $u\in\mathbb{R}^{n}$, and positive numbers
$\epsilon,\delta>0$, the directional neighborhood of direction $u$ is a set
defined by

${\cal
V}_{\epsilon,\delta}(u):=\\{x\in\epsilon\mathbb{B}|\big{\|}\|u\|x-\|x\|u\big{\|}\leq\delta\|x\|\|u\|\\}.$

Clearly, the directional neighborhood of direction $u=0$ is just the open ball
$\epsilon\mathbb{B}$ and the directional neighborhood of a nonzero direction
$u\not=0$ is a smaller subset of $\epsilon\mathbb{B}$. Hence many regularity
conditions can be extended to a directional version which is weaker than the
original nondirectional one.

We say that $\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ is directionally
Lipschitz continuous at $\bar{x}$ in direction $u$ if there are positive
numbers $L,\epsilon,\delta$ such that

$\|\phi(x)-\phi(x^{\prime})\|\leq L\|x-x^{\prime}\|\quad\forall
x,x^{\prime}\in\bar{x}+{\cal V}_{\epsilon,\delta}(u).$

It is easy to see that if $\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ is
directionally Lipschitz continuous at $\bar{x}$ in direction $u$, then
$D\phi(\bar{x})(u)\neq\emptyset$ and both $\phi^{\prime}_{+}(\bar{x};u)$ and
$\phi^{\prime}_{-}(\bar{x};u)$ are finite and belong to $D\phi(\bar{x})(u)$.
Futhermore, if $\phi$ is directionally differentiable at $\bar{x}$ in
direction $u$ then for any sequence $\\{u^{k}\\}$ which converges to $u$, we
have

$\phi^{\prime}(\bar{x};u)=\lim_{k\rightarrow\infty}\frac{\phi(\bar{x}+t_{k}u^{k})-\phi(\bar{x})}{t_{k}}.$

We now recall the definition of some subdifferentials below.

######  Definition 2.5 (Subdifferentials)

([36, Definition 8.3]) Let
$\varphi:\mathbb{R}^{n}\rightarrow\overline{\mathbb{R}}$ and
$\varphi(\bar{x})$ be finite. The Fréchet (regular) subdifferential of
$\varphi$ at $\bar{x}$ is the set

$\displaystyle\widehat{\partial}\varphi(\bar{x}):=\left\\{\xi\in\mathbb{R}^{n}|\varphi(x)\geq\varphi(\bar{x})+\langle\xi,x-\bar{x}\rangle+{o(\|x-\bar{x}\|)}\right\\},$

the limiting (Mordukhovich or basic) subdifferential of $\varphi$ at $\bar{x}$
is the set

$\displaystyle\partial\varphi(\bar{x}):=\\{\xi\in\mathbb{R}^{n}|\exists
x^{k}\rightarrow\bar{x},\ \xi^{k}\rightarrow\xi\ \mbox{ s.t.
}\varphi(x^{k})\rightarrow\varphi(\bar{x}),\xi^{k}\in\widehat{\partial}\varphi(x^{k})\\}.$

Recently a directional version of the subdifferential was introduced [17, 22]
and further studies and related results can be found in [26, 7, 2].

######  Definition 2.6 (Directional Subdifferentials)

Let $\varphi:\mathbb{R}^{n}\rightarrow\overline{\mathbb{R}}$ and
$\varphi(\bar{x})$ be finite. The limiting subdifferential of $\varphi$ at
$\bar{x}$ in direction $u\in\mathbb{R}^{n}$ is defined as

$\displaystyle\partial\varphi(\bar{x};u):=\\{\xi\in\mathbb{R}^{n}|\exists
t_{k}\downarrow 0,u^{k}\rightarrow u,\xi^{k}\rightarrow\xi\mbox{ s.t.
}\varphi(\bar{x}+t_{k}u^{k})\rightarrow\varphi(\bar{x}),\
\xi^{k}\in\widehat{\partial}\varphi(\bar{x}+t_{k}u^{k})\\}.$

It is easy to see that if $u\notin T_{dom\varphi}(\bar{x})$, then
$\partial\varphi(\bar{x};u)=\emptyset$ and
$\partial\varphi(\bar{x};0)=\partial\varphi(\bar{x})$. When $u\not=0$,
$\partial\varphi(\bar{x};u)\subseteq\partial\varphi(\bar{x})$ and when
$\varphi$ is continuously differentiable at $\bar{x}$,
$\partial\varphi(\bar{x};u)=\\{\nabla\varphi(\bar{x})\\}$ for any direction
$u$.

By [7, Corollary 4.1] directional subdifferentials can be equivalently defined
by the directional normal cone to its epigraph.

###### Proposition 2.1

Let $\varphi:\mathbb{R}^{n}\rightarrow\overline{\mathbb{R}}$ and
$\varphi(\bar{x})$ be finite. Suppose $\varphi$ is Lipschitz continuous and
directionally differentiable at $\bar{x}$ in direction $u$. Then

$\displaystyle\partial\varphi(\bar{x};u)$
$\displaystyle=\\{\xi\in\mathbb{R}^{n}|(\xi,-1)\in
N_{epi\varphi}(\bar{x},\varphi(\bar{x});(u,\varphi^{\prime}(\bar{x};u)))\\}.$

######  Definition 2.7 (Directional Clarke Subdifferential)

[1, Definition 2.7] Let $\varphi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be
directionally Lipschitz continuous at $\bar{x}$ in direction
$u\in\mathbb{R}^{n}$. The directional Clarke subdifferential of $\varphi$ at
$\bar{x}$ in direction $u$ is defined as

$\partial^{c}\varphi(\bar{x};u):=co(\partial\varphi(\bar{x};u)).$

It is clear that the directional Clarke subdifferential in direction $u=0$
coincides with the Clarke subdifferential $\partial^{c}\varphi(\bar{x})$. By
[1, Proposition 2.1], one has
$\partial^{c}(-\varphi)(\bar{x};u)=-\partial^{c}\varphi(\bar{x};u).$

A function $\varphi(x):\mathbb{R}^{n}\rightarrow\overline{\mathbb{R}}$ is said
to be weakly convex if there exists a modulus $\rho\geq 0$ such that the
function $\varphi(x)+\frac{\rho}{2}\|x\|^{2}$ is convex. The class of weakly
convex functions is large and it includes the class of functions with a
bounded Lipschitz gradient, i.e., dom$\varphi$ is open, $\varphi(x)$ is
differentiable at all $x\in{\rm dom}\varphi$ and there exists $L>0$ such that
$\|\nabla\varphi(x)-\nabla\varphi(y)\|\leq L\|x-y\|$ for $\forall x,y\in{\rm
dom}\varphi$. It turns out that like convex functions, weakly convex functions
are directionally differentiable and Lipschitz continuous in the interior of
its domain. Moreover the directional limiting subdifferential and the
directional Clarke subdifferential coincide as shown below.

###### Proposition 2.2

Let $\varphi:\mathbb{R}^{n}\rightarrow\overline{\mathbb{R}}$ be weakly convex
and $\bar{x}\in{\rm ri}(dom\varphi)$. Then one has

$\displaystyle\varphi^{\prime}(\bar{x};u)=\sup\left\\{\langle\xi,u\rangle|\xi\in\partial\varphi(\bar{x})\right\\}.$
(8)

Moreover if $\bar{x}\in{\rm int}(dom\varphi)$, then $\varphi$ is directionally
differentiable at $\bar{x}$ and Lipschitz continuous around $\bar{x}$, (8)
holds with “sup” replaced with “max” and

$\displaystyle\partial^{c}\varphi(\bar{x};u)=\partial\varphi(\bar{x};u)=\partial\varphi(\bar{x})\cap\\{\xi|\xi^{T}u=\varphi^{\prime}(\bar{x};u)\\}.$
(9)

Proof. By the weak convexity, $\tilde{\varphi}(x):=\varphi(x)+\rho\|x\|^{2}$
is convex for some $\rho>0$. Hence the limiting and regular subdifferential
coincide with the one in the sense of convex analysis and we have

$\partial\varphi(\bar{x})=\partial\tilde{\varphi}(\bar{x})-2\rho\bar{x}.$

By [35, Theorem 23.4], we have

$\varphi^{\prime}(\bar{x};u)=\tilde{\varphi}^{\prime}(\bar{x};u)-2\rho\bar{x}^{T}u=\sup\left\\{\langle\xi,u\rangle|\xi\in\partial\tilde{\varphi}(\bar{x})\right\\}-2\rho\bar{x}^{T}u$

from which (8) follows. Now suppose $\bar{x}\in{\rm int}(dom\varphi)$. Then by
[35, Theorem 23.4], $\tilde{\varphi}(x)$ is directionally differentiable and
hence $\varphi$ is directionally differentiable. And the convex function
$\tilde{\varphi}(x)$ is Lipschitz continuous around $\bar{x}$ and so is
$\varphi(x)$.

We now prove (9). By sum rule of directional subdifferential [26, Theorem
5.6],

$\partial\varphi(\bar{x};u)=\partial\tilde{\varphi}(\bar{x};u)-2\rho\bar{x}.$

By Proposition 2.1, $\partial\tilde{\varphi}(\bar{x};u)=\\{\xi|(\xi,-1)\in
N_{{\rm
epi}\tilde{\varphi}}((\bar{x},\tilde{\varphi}(\bar{x}));(u,\tilde{\varphi}^{\prime}(\bar{x};u))\\}$.
By the convexity of $\tilde{\varphi}$, ${\rm epi}\tilde{\varphi}$ is convex,
so by (7)

$N_{{\rm
epi}\tilde{\varphi}}((\bar{x},\tilde{\varphi}(\bar{x}));(u,\tilde{\varphi}^{\prime}(\bar{x};u))=N_{{\rm
epi}\tilde{\varphi}}((\bar{x},\tilde{\varphi}(\bar{x}))\cap\\{(u,\tilde{\varphi}^{\prime}(\bar{x};u))\\}^{\perp}.$

Then $\xi\in\partial\tilde{\varphi}(\bar{x};u)$ if and only if

$(\xi,-1)\in N_{{\rm
epi}\tilde{\varphi}}((\bar{x},\tilde{\varphi}(\bar{x}))\cap\\{(u,\tilde{\varphi}^{\prime}(\bar{x};u))\\}^{\perp}$

which means $\xi\in\partial\tilde{\varphi}(\bar{x};u)$ if and only if
$\xi\in\partial\tilde{\varphi}(\bar{x})$ and
$\xi^{T}u=\tilde{\varphi}^{\prime}(\bar{x};u)$. Note that

$\tilde{\varphi}^{\prime}(\bar{x};u)=\varphi^{\prime}(\bar{x};u)+2\rho{\bar{x}}^{T}u.$

Consequently, $\xi\in\partial\tilde{\varphi}(\bar{x};u)$ if and only if
$\xi-2\rho\bar{x}\in\partial\varphi(\bar{x})$ and
$(\xi-2\rho{\bar{x}})^{T}u=\varphi^{\prime}(\bar{x};u)$. This proves the
second equality of (9). $\partial\varphi(\bar{x})$ is a closed convex set, and
so is $\partial\varphi(\bar{x};u)$. By Definition 2.7,
$\partial^{c}\varphi(\bar{x};u)=\partial\varphi(\bar{x};u)$.

We now give the definition of directional metric subregularity constraint
qualification.

######  Definition 2.8 (Directional MSCQ)

[17, Definition 2.1]Let $\bar{z}$ be a solution to the system $\phi(z)\leq 0$,
where $\phi:\mathbb{R}^{a}\rightarrow\mathbb{R}^{b}$. Given a direction
$u\in\mathbb{R}^{a}$, the system $\phi(z)\leq 0$ is said to satisfy the metric
subregularity constraint qualification (MSCQ) at $\bar{z}$ in direction $u$,
or the set-valued map $\Phi(z):=\phi(z)-\mathbb{R}^{b}_{-}$ is metrically
subregular at ($\bar{z},0$) in direction $u$, if there are positive reals
$\epsilon>0,\delta>0$ and $\kappa>0$ such that

${{\rm
dist}}(z,\phi^{-1}(\mathbb{R}^{b}_{-}))\leq\kappa\|\phi_{+}(z)\|\qquad\quad\forall
z\in\bar{z}+{\cal V}_{\epsilon,\delta}(u).$

If $u=0$ in the above definition, then we say that the system $\phi(z)\leq 0$
satisfies MSCQ at $\bar{z}$.

It is known that MSCQ holds when MFCQ holds or $\phi(z)$ is affine. In the
following, we list some sufficient conditions for the directional MSCQ. The
reader can refer to [1, 4, 7, 6] for more details.

###### Definition 2.9

Let $\bar{z}$ be a solution to the system $\phi(z)\leq 0$, where
$\phi:\mathbb{R}^{a}\rightarrow\mathbb{R}^{b}$. Given a direction
$u\in\mathbb{R}^{a}$.

  * •

Suppose that $\phi$ is Lipschitz at $\bar{z}$. We say that the no-nonzero
abnormal multiplier constraint qualification (NNAMCQ) holds at $\bar{z}$ if

$0\in\partial\langle\zeta,\phi\rangle(\bar{z})\mbox{ and
}0\leq\zeta\perp\phi(\bar{z})\Longrightarrow\zeta=0.$

  * •

Suppose that $\phi$ is directionally Lipschitz at $\bar{z}$ in direction $u$.
We say that the first order sufficient condition for metric subregularity
(FOSCMS) holds at $\bar{z}$ in direction $\xi$ where $\xi\in
D\phi(\bar{z})(u)$ if there exists no $\zeta\neq 0$ satisfying

$0\in\partial\langle\zeta,\phi\rangle(\bar{z};u),0\leq\zeta\perp\phi(\bar{z}),\zeta\perp\xi.$

  * •

Suppose that $\phi$ is directionally Lipschitz at $\bar{z}$ in direction $u$.
We say that the directional quasi-normality holds at $\bar{z}$ in direction
$u$ if there exists no $\zeta\neq 0$ satisfying

$0\in\partial\langle\zeta,\phi\rangle(\bar{z};u),0\leq\zeta\perp\phi(\bar{z}),\zeta\perp\xi\mbox{
for some }\xi\in D\phi(\bar{z})(u)$

and there exist sequences $t_{k}\downarrow 0,\ u^{k}\rightarrow u$ satisfying

$\phi_{j}(\bar{z}+t_{k}u_{k})>0,\ \mbox{ if
}j\in\\{j=1,\ldots,b|\phi_{j}(\bar{z})=0\mbox{ and }\zeta_{j}>0\\}.$

It is known that in the smooth setting, NNAMCQ is equivalent to the MFCQ.
FOSCMS holding in a nonzero direction is in general weaker than MFCQ.

Throughout this paper, for any parametric inequality system $\phi(x,y)\leq 0$
where $\phi(x,y):\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}^{s}$
and $(\bar{x},\bar{y})\in\\{(x,y)\mid\phi(x,y)\leq 0\\}$, we denote the active
set of the inequality at $(\bar{x},\bar{y})$ as

$I_{\phi}(\bar{x},\bar{y}):=\\{i=1,\dots,s\mid\phi_{i}(\bar{x},\bar{y})=0\\}.$

The following regularity condition will be useful in this paper.

######  Definition 2.10 (RCR Regularity)

([28, Definition 1]). We say that the feasible map ${\cal
F}(x):=\\{y|g(x,y)\leq 0\\}$ is relaxed constant rank (RCR) regular at
$(\bar{x},\bar{y})\in{\rm gph}{\cal F}$ if there exists $\delta>0$ such that
for any index subset $K\subseteq I_{g}(\bar{x},\bar{y})$, the family of
gradient vectors $\nabla_{y}g_{j}(x,y),j\in K$, has the same rank at all
points $(x,y)\in\mathbb{B}_{\delta}(\bar{x},\bar{y})$.

Recall the directional Robinson Stability [1, Definition 4.7]).

######  Definition 2.11 (Directional Robinson Stability)

We say that the feasible map ${\cal F}(x)$ satisfies Robinson stability
${\rm(RS)}$ property at $(\bar{x},\bar{y})\in{\rm gph}{\cal F}$ in direction
$u\in\mathbb{R}^{n}$ if there exist positive scalars $\kappa,\epsilon,\delta$
such that

${\rm dist}(y,{\cal F}(x))\leq\kappa\|g_{+}(x,y)\|\quad\forall
x\in\bar{x}+{\cal V}_{\epsilon,\delta}(u),y\in\mathbb{B}_{\epsilon}(\bar{y}).$

If RS holds at $(\bar{x},\bar{y})$ in direction $u=0$, we say that RS holds at
$(\bar{x},\bar{y})$ ([19, Definition 1.1]). RS means that the MSCQ holds at
$\bar{y}$ uniformly in a directional neighborhood of $\bar{x}$ in direction
$u$.

Define the image directional derivative of $g$ with respect to $x$ at
$(\bar{x},\bar{y})$ in direction $u$ as the closed cone

${\rm Im}D_{x}g(\bar{x},\bar{y};u):=\left\\{\alpha v\left|\alpha\geq 0,\exists
t_{k}\downarrow 0,u^{k}\rightarrow u\ s.t.\
v=\lim_{k\rightarrow\infty}\frac{g(\bar{x}+t_{k}u^{k},\bar{y})-g(\bar{x},\bar{y})}{\|g(\bar{x}+t_{k}u^{k},\bar{y})-g(\bar{x},\bar{y})\|}\right.\right\\}.$

We always have

$\\{\alpha\nabla_{x}g(\bar{x},\bar{y})u|\alpha\geq 0\\}\subseteq{\rm
Im}D_{x}g(\bar{x},\bar{y};u)$

and the equality holds if $\nabla_{x}g(\bar{x},\bar{y})u\neq 0$.

The following proposition lists some sufficient conditions for directional RS.
The reader is referred to [3] for more sufficient conditions for directional
RS. And for any $\tilde{u}\in\mathbb{R}^{n}$, we need the following cone

$\mathbb{L}(\bar{x},\bar{y};\tilde{u}):=\left\\{v|\nabla
g_{i}(\bar{x},\bar{y})(\tilde{u},v)\leq 0,\ i\in
I_{g}(\bar{x},\bar{y})\right\\}.$ (10)

###### Proposition 2.3

[1, Proposition 4.1], [3, Proposition 3.2, Corollaries 3.1 and 3.2]. If the
system $g(x,y)\leq 0$ satisfies one of the following conditions at
$(\bar{x},\bar{y})$, then RS holds at $(\bar{x},\bar{y})$ in direction $u$.

  * 1.

$g(x,y)=h(x)+By+c$, where $h:\mathbb{R}^{n}\rightarrow\mathbb{R}^{p}$ and $B$
is an $m\times p$ matrix, and the feasible region $\mathcal{F}(x)$ is nonempty
for all $x\in\mathcal{V}_{\epsilon,\delta}(u)$ for some $\epsilon,\delta>0$.

  * 2.

For any direction $d\in{\rm Im}D_{x}g(\bar{x},\bar{y};u)$, there exists
$v\in\mathbb{R}^{m}$ satisfying

$d_{i}+\nabla_{y}g_{i}(\bar{x},\bar{y})v\leq 0,\ i\in I_{g}(\bar{x},\bar{y}).$
(11)

FOSCMS for the system $g(\bar{x},y)\leq 0$ at $y=\bar{y}$ holds in direction
$d+\nabla_{y}g(\bar{x},\bar{y})v$, i.e.,

$\displaystyle\left\\{\begin{array}[]{ll}\nabla_{y}g(\bar{x},\bar{y})^{T}\lambda=0,\\\
0\leq\lambda\perp g(\bar{x},\bar{y}),\
\lambda\perp(d+\nabla_{y}g(\bar{x},\bar{y})v)\end{array}\right.\implies\lambda=0,$

for each $(d,v)\not=0$ satisfying (11) and $d\in{\rm
Im}D_{x}g(\bar{x},\bar{y};u)$.

  * 3.

$\nabla_{x}g(\bar{x},\bar{y})u\not=0$. For any $\alpha\geq 0$,
$\mathbb{L}(\bar{x},\bar{y};\alpha u)$ defined in (10) is nonempty and FOSCMS
for the system $g(\bar{x},y)\leq 0$ at $y=\bar{y}$ holds in all directions in
$\mathbb{L}(\bar{x},\bar{y};\alpha u)$ for $\alpha\geq 0$.

  * 4.

MFCQ for the system $g(\bar{x},y)\leq 0$ holds at $y=\bar{y}$.

##  3 Directional KKT conditions

In this section we derive directional KKT condition for the optimization
problem

$\displaystyle{\rm(P)}~{}~{}~{}\min_{z}$ $\displaystyle\varphi(z)\quad\mbox{
s.t. }\phi(z)\leq 0,$

where $\varphi:\mathbb{R}^{a}\rightarrow\mathbb{R}$ and
$\phi:\mathbb{R}^{a}\rightarrow\mathbb{R}^{b}$. In [1, Section 3], Bai and Ye
obtained the directional optimality condition for (P) under the assumption
that all constraint functions $\phi_{j}$ are directionally Lipschitz
continuous and directionally differentiable. In this section we extend the
result to allow at most one of the active constraint functions, say $\phi_{1}$
to be not directionally differentiable.

Let $\bar{z}$ be a feasible solution to problem (P). Assume $1\in
I_{\phi}(\bar{z})$ throughout this section. Now suppose that $\varphi$ is
continuously differentiable at $\bar{z}$ and $\phi_{j}$ is directionally
Lipschitz continuous for all $j$, and directionally differentiable for all
$j\neq 1$ at $\bar{z}$. Then treating the inequality constraint $\phi(z)\leq
0$ as the inclusion $\phi(z)\in\mathbb{R}^{b}_{-}$, we can define the
linearized cone of (P) at $\bar{z}$ by

$\mathbb{L}(\bar{z}):=\\{u\in\mathbb{R}^{a}|D\phi(\bar{z})(u)\cap
T_{\mathbb{R}^{b}_{-}}(\phi(\bar{z}))\neq\emptyset\\}$

and the critical cone of (P) at $\bar{z}$ by

$C(\bar{z}):=\\{u\in\mathbb{L}(\bar{z})|\nabla\varphi(z)u\leq
0\\}=\\{u\in\mathbb{R}^{a}|D\phi(\bar{z})(u)\cap
T_{\mathbb{R}^{b}_{-}}(\phi(\bar{z}))\neq\emptyset,\nabla\varphi(\bar{z})u\leq
0\\}.$

By the directional differentiability of $\phi_{j}(1<j\leq b)$, one can easily
obtain

$D\phi(\bar{z})(u)=D\phi_{1}(\bar{z})(u)\times\Pi_{j=2}^{b}\phi^{\prime}_{j}(\bar{z};u),$

and by the directional Lipschitz continuity of $\phi_{1}$ at $\bar{z}$ in
direction $u$,

$D\phi_{1}(\bar{z})(u)\cap\mathbb{R}_{-}\neq\emptyset\Leftrightarrow\phi^{\prime}_{-}(\bar{z};u)\leq
0.$

Hence the following equivalent definitions of $\mathbb{L}(\bar{z})$ and
$C(\bar{z})$ hold:

$\displaystyle\mathbb{L}(\bar{z})=\\{u\in\mathbb{R}^{a}|(\phi_{j})_{-}^{\prime}(\bar{z};u)\leq
0,j\in I_{\phi}(\bar{z})\\},$ $\displaystyle C(\bar{z})=\\{u\in
L(\bar{z})|\nabla\varphi(\bar{z})u\leq
0\\}=\\{u\in\mathbb{R}^{a}|(\phi_{j})^{\prime}_{-}(\bar{z};u)\leq 0,j\in
I_{\phi}(\bar{z}),\nabla\varphi(\bar{z})u\leq 0\\}.$

The concept of (Clarke) calmness for a mathematical program is first defined
by Clarke [9, Definition 6.41] and extended to a directional version by Bai
and Ye [1].

######  Definition 3.1 (Directional Clarke Calmness)

[1, Definition 3.1] Suppose $\bar{z}$ is a local solution of (P). We say that
(P) is (Clarke) calm at $\bar{z}$ in direction $u$ if there exist positive
scalars $\epsilon,\delta,\rho$, such that for any
$\alpha\in\epsilon\mathbb{B}$ and any $z\in\bar{z}+{\cal
V}_{\epsilon,\delta}(u)$ satisfying $\phi(z)+\alpha\leq 0$ one has,

$\varphi(z)-\varphi(\bar{z})+\rho\|\alpha\|\geq 0.$

Similar to its nondirectional version, provided the objective function is
directionally Lipschitz continuous, the directional calmness of problem (P)
holds under the directional MSCQ, hence can be verified by directional
constraint qualifications listed in Definition 2.9.

###### Lemma 3.1

[1, Lemma 3.1] Let $\bar{z}$ solve $({\rm P})$ and $\varphi(z)$ be Lipschitz
continuous at $\bar{z}$ in direction $u$. Suppose that the system $\phi(z)\leq
0$ satisfies MSCQ at $\bar{z}$ in direction $u$. Then $({\rm P})$ is calm at
$\bar{z}$ in direction $u$.

###### Proposition 3.1

Let $\phi(\bar{z})\leq 0$ and suppose that $\phi$ is directionally Lipschitz
at $\bar{z}$ in direction $u\in\mathbb{L}(\bar{z})$. If the directional quasi-
normality holds at $\bar{z}$ in direction $u$ for the inequality system
$\phi(z)\leq 0$. Then the system $\phi(z)\leq 0$ satisfies the directional
MSCQ at $\bar{z}$ in direction $u$.

Proof. The proof can be completed by following a similar process of the proof
of [1, Proposition 3.1].

We now summerize our discussions by the following implications under the
Lipschitz continuity of the objective function in direction $u$:

Quasi-normality in direction $u$

$\Downarrow$

MSCQ in direction $u$

$\Downarrow$

Calmness in direction $u$.

The following theorem shows that under the directional calmness of (P), a
directional KKT condition holds at a local minimizer. This theorem generalizes
[1, Theorem 3.1] to allow one of the constraint functions to be not
directionally differentiable.

###### Theorem 3.1

Let $\bar{z}$ be a local minimizer of (P) and $u\in C(\bar{z})$. Suppose that
$\varphi(z)$ is continuously differentiable at $\bar{z}$, $\phi(z)$ is
directionally Lipschitz continuous and $\phi_{i}(z)$ for $i=2,\ldots,b$ are
directionally differentiable at $\bar{z}$ in direction $u$. Suppose that
Problem (P) is calm at $\bar{z}$ in direction $u$. Then there exist a
multiplier $\lambda\in\mathbb{R}^{b}$ and $\xi\in D\phi_{1}(\bar{z})(u)$ such
that $0\leq\lambda\perp\phi(\bar{z}),\ \lambda\perp
d:=(\xi,\phi_{2}^{\prime}(\bar{z};u),\ldots,\phi_{b}^{\prime}(\bar{z};u))$ and

$\displaystyle
0\in\nabla\varphi(\bar{z})+\partial\langle\lambda,\phi\rangle(\bar{z};u).$

Proof. Since (P) is calm at $\bar{z}$ in direction $u$, there exist positive
scalars $\epsilon,\delta,\rho$ such that

$\varphi(z)+\rho\|\phi_{+}(z)\|\geq\varphi(\bar{z})\qquad\forall
z\in\bar{z}+{\cal V}_{2\epsilon,\delta}(u).$ (13)

Since $u\in C(\bar{z})$, there exist $\xi\in D\phi_{1}(\bar{z})(u)$ and
sequences $t_{k}\downarrow 0,u^{k}\rightarrow u$ such that
$\lim_{k}(\phi_{1}(\bar{z}+t_{k}u^{k})-\phi_{1}(\bar{z}))/t_{k}=\xi\leq 0$.
Then for sufficiently large $k$ we have

$\phi(\bar{z})+t_{k}(\xi,\phi_{2}^{\prime}(\bar{z};u),\ldots,\phi_{b}^{\prime}(\bar{z};u))\leq
0$

and hence

$0\leq\frac{\|\phi_{+}(\bar{z}+t_{k}u^{k})\|}{t_{k}}\leq\frac{\|\phi(\bar{z}+t_{k}u^{k})-\phi(\bar{z})-t_{k}(\xi,\phi_{2}^{\prime}(\bar{z};u),\ldots,\phi_{b}^{\prime}(\bar{z};u))\|}{t_{k}}.$

It follows that
$\lim_{k\downarrow\infty}(\|\phi_{+}(\bar{z}+t_{k}u^{k})\|)/t_{k}=0$.

Since $\bar{z}+t_{k}u^{k}\in\bar{z}+cl({\cal V}_{\epsilon,\delta}(u))$ for $k$
sufficiently large, by (13),

$\varphi(\bar{z}+t_{k}u^{k})+\rho\|\phi_{+}(\bar{z}+t_{k}u^{k})\|\geq\varphi(\bar{z}).$

Together with $\nabla\varphi(\bar{z})u\leq 0$ we have

$\lim_{k\downarrow\infty}\frac{\varphi(\bar{z}+t_{k}u^{k})+\rho\|\phi_{+}(\bar{z}+t_{k}u^{k})\|-\varphi(\bar{z})}{t_{k}}=0.$
(14)

The rest of the proof then follows from that of [1, Theorem 3.1] by replacing
$\frac{u}{k}$ and $\phi^{\prime}(\bar{z};u)$ with $t_{k}u^{k}$ and
$(\xi,\phi_{2}^{\prime}(\bar{z};u),\ldots,\phi_{b}^{\prime}(\bar{z};u))$,
respectively. For completeness we sketch the proof. For each $k=0,1,\ldots$,
define
$\sigma_{k}:=2(\varphi(\bar{z}+t_{k}u^{k})+\rho\|\phi_{+}(\bar{z}+t_{k}u^{k})\|-\varphi(\bar{z}))$.
If $\sigma_{k}\equiv 0$, then for each large enough $k$, by (13),
$\bar{z}+t_{k}u^{k}$ is a global minimizer of the function
$\varphi(z)+\rho\|\phi_{+}(z)\|+\delta_{\bar{z}+cl({\cal
V}_{\epsilon,\delta}(u))}(z)$. Since for each large enough $k$,
$\bar{z}+t_{k}u^{k}$ is an interior point of $\bar{z}+cl({\cal
V}_{\epsilon,\delta}(u))$, by the well-known Fermat’s rule and the calculus
rule (see e.g., [36, Corollary 10.9]),

$0\in\nabla\varphi(\bar{z}+t_{k}u^{k})+\rho\partial(\|\phi_{+}{(\cdot)}\|)(\bar{z}+t_{k}u^{k}).$
(15)

Otherwise, without loss of generality, we assume that for all $k$,
$\sigma_{k}>0$. Then by definition of $\sigma_{k}$, the equality (14), we have
for $k$ sufficiently large,

$\varphi(\bar{z}+t_{k}u^{k})+\rho\|\phi_{+}(\bar{z}+t_{k}u^{k})\|+\delta_{\bar{z}+cl({\cal
V}_{\epsilon,\delta}(u))}(\bar{z}+t_{k}u^{k})<\varphi(\bar{z})+\sigma_{k}.$

Define
$\lambda_{k}:=\frac{2\|u^{k}\|rt_{k}}{\epsilon}\sqrt{\frac{\sigma_{k}\epsilon}{2\|u^{k}\|rt_{k}}}$
with $r>0$. Then by Ekeland’s variation principle (see e.g., [29, Theorem
2.26]), there exists

$\tilde{z}^{k}\in\mathrm{argmin}_{z}\left\\{\varphi(z)+\rho\|\phi_{+}(z)\|+\delta_{\bar{z}+cl({\cal
V}_{\epsilon,\delta}(u))}(z)+\frac{\sigma_{k}}{\lambda_{k}}\|z-(\bar{z}+t_{k}u^{k})\|\right\\}$

satisfying that $\|\tilde{z}^{k}-(\bar{z}+t_{k}u^{k})\|\leq\lambda_{k}$. By
(14), we can show that for sufficiently small $r$, $\tilde{z}^{k}$ is in the
interior of $\bar{z}+cl({\cal V}_{\epsilon,\delta}(u))$. Then by the well-
known Fermat’s rule, we obtain

$0\in\nabla\varphi(\tilde{z}^{k})+\rho\partial(\|\phi_{+}(\cdot)\|)(\tilde{z}^{k})+\frac{\sigma_{k}}{\lambda_{k}}\bar{\mathbb{B}}.$
(16)

Using the directionally Lipschitz continuity of $\phi$ at $\bar{z}$ in
direction $u$, by applying the chain rule for limiting subdifferential [29,
Corollary 3.43], we have

$\partial(\|\phi_{+}(\cdot)\|)(\tilde{z}^{k})\subseteq\bigcup_{\zeta^{\prime}\in\partial\|(\cdot)_{+}\|(\phi(\tilde{z}^{k}))}\partial\langle\zeta^{\prime},\phi\rangle(\tilde{z}^{k}).$

Therefore by $(\ref{opk1})$ or $(\ref{opk2})$,
$\exists\zeta^{k}\in\partial\|(\cdot)_{+}\|(\phi(\bar{z}+t_{k}u^{k}))$ or
$\exists\zeta^{k}\in\partial\|(\cdot)_{+}\|(\phi(\tilde{z}^{k}))$ such that

$0\in\nabla\varphi(\bar{z}+t_{k}u^{k})+\rho\partial\langle\zeta^{k},\phi\rangle(\bar{z}+t_{k}u^{k}),\
\mbox{or}\
0\in\nabla\varphi(\tilde{z}^{k})+\rho\partial\langle\zeta^{k},\phi\rangle(\tilde{z}^{k})+\frac{\sigma_{k}}{\lambda_{k}}\bar{\mathbb{B}}.$
(17)

By the Lipschitz continuity of the function $\|x_{+}\|$, $\\{\zeta^{k}\\}$ is
bounded. Without loss of generality, assume $\zeta:=\lim_{k}\zeta^{k}$. We
also have
$\lim_{k}(\bar{z}+t_{k}u^{k}-\bar{z})/t_{k}=\lim_{k}(\tilde{z}^{k}-\bar{z})/t_{k}=u$.
Since $\sigma_{k}=o(t_{k}),\ \lim_{k}\frac{\sigma_{k}}{\lambda_{k}}=0$. Taking
the limit of $(\ref{opk})$ as $k\rightarrow\infty$, by [26, Theorem 5.4] we
have

$0\in\nabla\varphi(\bar{z})+\rho\partial\langle\zeta,\phi\rangle(\bar{z};u).$

Moreover by [7, Corollary 4.2],

$\zeta\in\partial(\|(\cdot)_{+}\|)(\phi(\bar{z});(\xi,\phi_{2}^{\prime}(\bar{z};u),\ldots,\phi_{b}^{\prime}(\bar{z};u)))\subseteq
N_{\mathbb{R}^{b}_{-}}(\phi(\bar{z});(\xi,\phi_{2}^{\prime}(\bar{z};u),\ldots,\phi_{b}^{\prime}(\bar{z};u))).$

The desired result holds by taking
$d:=(\xi,\phi_{2}^{\prime}(\bar{z};u),\ldots,\phi_{b}^{\prime}(\bar{z};u))$
and

$\lambda_{\phi}:=\rho\zeta\in
N_{\mathbb{R}^{b}_{-}}(\phi(\bar{z});d)=\\{\eta\in\mathbb{R}^{b}|0\leq\eta\perp\phi(\bar{z}),\eta\perp
d\\}.$

##  4 Directional sensitivity analysis of the Moreau envelope function

Since the Moreau envelope function $v_{\gamma}(x,y)$ is the optimal value
function for the following parametric mathematical program with parameter
$(x,y)$:

$\displaystyle\mbox{(P${}^{\gamma}_{x,y}$)}~{}~{}~{}~{}\quad\min_{w}~{}$
$\displaystyle\nu(x,y,w):=f(x,w)+\frac{1}{2\gamma}\|w-y\|^{2}$ $\displaystyle
s.t.~{}$ $\displaystyle g(x,w)\leq 0,$

in this section we study the sensitivity analysis of the Moreau envelope
function from the perspective that it is the optimal value function for the
above parametric program. Note that the feasible map of the problem
${\rm(P^{\gamma}_{x,y})}$ is the same as the one for problem $(P_{x})$:

$\mathcal{F}(x):=\\{w\in\mathbb{R}^{m}|g(x,w)\leq 0\\}.$

We define the optimal solution map/the proximal map by

$\displaystyle S_{\gamma}(x,y)$
$\displaystyle:=\mathrm{argmin}_{w}\left\\{\left.f(x,w)+\frac{1}{2\gamma}\|w-y\|^{2}\right|g(x,w)\leq
0\right\\},$

the Lagrange function of ${\rm(P^{\gamma}_{x,y})}$ by

${\cal
L}(x,y,w;\lambda):=f(x,w)+\frac{1}{2\gamma}\|w-y\|^{2}+g(x,w)^{T}\lambda,$

and the set of Lagrange multipliers of ${\rm(P^{\gamma}_{x,y})}$ associated
with $w\in{\cal F}(x)$ by

$\Lambda(x,y,w):=\\{\lambda\in\mathbb{R}^{p}|\nabla_{w}{\cal
L}(x,y,w;\lambda)=0,\ g(x,w)^{T}\lambda=0,\ \lambda\geq 0\\}.$

Let $(u,v)$ satisfy $\nabla g(x,w)(u,v)\in
T_{\mathbb{R}^{p}_{-}}(g(x,w))=\\{(\xi,\zeta)\mid\nabla
g_{i}(x,w)(\xi,\zeta)\leq 0\ \ i\in I_{g}(x,w)\\}$. We denote the set of
directional Lagrange multipliers of ${\rm(P^{\gamma}_{x,y})}$ associated with
$w\in{\cal F}(x)$ in direction $(u,v)$ by

$\Lambda(x,y,w;u,v):=\\{\lambda\in\mathbb{R}^{p}_{+}|\nabla_{w}{\cal
L}(x,y,w;\lambda)=0,\ g(x,w)^{T}\lambda=0,\ \lambda^{T}\nabla
g(x,w)(u,v)=0\\}.$

We divide our discussion into three cases: first, we show that sensitivity
analysis of value functions in convex analysis can be extended to the case
when $v_{\gamma}$ is weakly convex. In the second and third subsections,
without weak convexity of $v_{\gamma}$, we obtain sensitivity analysis under
FOSCMS and RCR regularity+RS, respectively.

###  4.1 Sensitivity analysis under weak convexity

Recently, Gao et al. [23] studied weak convexity and sensitivity analysis of
$v_{\gamma}$. Particularly, in [23, Theorems 1-3], they show that $v_{\gamma}$
is weakly convex when $f$ is weakly convex and $g$ is convex. And from their
proof, one can easily find that convexity of $g$ can be weakened to
quasiconvexity. Moreover, in this paper we only need the local Lipschitz
continuity of the function $v_{\gamma}(x,y)$.

###### Proposition 4.1

Assume that $g(x,y)$ is quasiconvex on $\mathbb{R}^{n}\times\mathbb{R}^{m}$,
$f$ is $\rho_{f}$-weakly convex with $\rho_{f}>0$ on ${\rm gph}\mathcal{F}$.
Then the Moreau envelope function $v_{\gamma}(x,y)$ is $\rho_{v}$-weakly
convex for any $\gamma\in(0,1/\rho_{f})$ satisfying
$\rho_{v}\geq\frac{\rho_{f}}{1-\gamma\rho_{f}}$. If
$\mathcal{F}(x)\neq\emptyset$ for all $x$ in a neighborhood of
$\bar{x}\in\mathbb{R}^{n}$, then $v_{\gamma}(x,y)$ is Lipschitz continuous
around $(\bar{x},y)$ for any $y\in\mathbb{R}^{m}$.

Under the assumptions in Proposition 4.1, Gao et al. [23] presented lower
estimates for the subdifferential of $v_{\gamma}$. We now extend their results
to directional subdifferential defined in Definition 2.6.

###### Proposition 4.2

Assume that $g(x,y)$ is quasiconvex on $\mathbb{R}^{n}\times\mathbb{R}^{m}$,
$f$ is $\rho_{f}$-weakly convex with $\rho_{f}>0$ on ${\rm gph}\mathcal{F}$.
Let $\bar{w}\in S_{\gamma}(\bar{x},\bar{y})$ with $\gamma\in(0,1/\rho_{f})$
and suppose that $\mathcal{F}(x)\neq\emptyset$ for all $x$ in a neighborhood
of $\bar{x}$. Then $v_{\gamma}(x,y)$ is Lipschitz continuous and directionally
differentiable at $(\bar{x},\bar{y})$. One has

$\partial
v_{\gamma}(\bar{x},\bar{y})\supseteq\bigcup_{\lambda\in\Lambda(\bar{x},\bar{y},\bar{w})}\left(\left\\{\nabla_{x}f(\bar{x},\bar{w})+\nabla_{x}g(\bar{x},\bar{w})^{T}\lambda\right\\}\times\\{(\bar{y}-\bar{w})/\gamma\\}\right),$
(18)

and the equality holds if Guignard constraint qualification (Guignard CQ) for
the system $g(x,w)\leq 0$ holds at $(\bar{x},\bar{w})$, i.e.,

$N_{{\rm
gph}\mathcal{F}}(\bar{x},\bar{w})=\left\\{\sum_{i=1}^{l}\lambda_{i}\nabla
g_{i}(\bar{x},\bar{w})|\lambda\geq
0,\sum_{i=1}^{l}\lambda_{i}g_{i}(\bar{x},\bar{w})=0\right\\}.$ (19)

If Guignard CQ (19) holds, then for any direction
$(u,v)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ satisfying $\nabla
g(\bar{x},\bar{w})(u,v)\in T_{\mathbb{R}^{p}_{-}}(g(\bar{x},\bar{w}))$, we
have

$\partial
v_{\gamma}(\bar{x},\bar{y};u,v)=\bigcup_{\lambda\in{\Lambda(\bar{x},\bar{y},\bar{w};u,v)}}\left(\left\\{\nabla_{x}f(\bar{x},\bar{w})+\nabla_{x}g(\bar{x},\bar{w})^{T}\lambda\right\\}\times\\{(\bar{y}-\bar{w})/\gamma\\}\right).$
(20)

$v^{\prime}_{\gamma}(\bar{x},\bar{y};u,v)=\max_{\lambda\in{\Lambda(\bar{x},\bar{y},\bar{w};u,v)}}\nabla\mathcal{L}(\bar{x},\bar{y},\bar{w};\lambda)(u,v).$
(21)

Proof. Since $\mathcal{F}(x)\neq\emptyset$ for all $x$ in a neighborhood of
$\bar{x}$, by Proposition 4.1, $v_{\gamma}$ is weakly convex and Lipschitz
continuous around $(\bar{x},\bar{y})$. The first estimate (18) follows by [23,
Theorem 5]. We now prove formula (20). By Proposition 2.2,
$(\xi,\zeta)\in\partial v_{\gamma}(\bar{x},\bar{y};u,v)$ if
$(\xi,\zeta)\in\partial v_{\gamma}(\bar{x},\bar{y})$ and
$\langle(\xi,\zeta),(u,v)\rangle=\sigma_{\partial
v_{\gamma}(\bar{x},\bar{y})}(u,v)$ where $\sigma_{C}$ denotes the support
function of set $C$. When the equality in (18) holds, we have

$\displaystyle\sigma_{\partial v_{\gamma}(\bar{x},\bar{y})}(u,v)$
$\displaystyle=\max_{\lambda\in\Lambda(\bar{x},\bar{y},\bar{w})}\left(\nabla_{x}f(\bar{x},\bar{w})u+\sum^{l}_{i=1}\lambda_{i}\nabla_{x}g_{i}(\bar{x},\bar{w})u+v^{T}(\bar{y}-\bar{w})/\gamma\right).$

Now suppose $\nabla g(\bar{x},\bar{w})(u,v)\in
T_{\mathbb{R}^{p}_{-}}(g(\bar{x},\bar{w}))$ and Guignard CQ (19) holds. Then
for any vector $\lambda\in\Lambda(\bar{x},\bar{y},\bar{w})$ we have
$\lambda\in N_{\mathbb{R}^{p}_{-}}(g(\bar{x},\bar{w}))$. Therefore
$\lambda^{T}\nabla g(\bar{x},\bar{w})(u,v)\leq 0$. This means
$\langle(\xi,\zeta),(u,v)\rangle=\sigma_{\partial
v_{\gamma}(\bar{x},\bar{y})}(u,v)$ if and only if
$\xi=\nabla_{x}f(\bar{x},\bar{w})+\sum^{l}_{i=1}\lambda_{i}\nabla_{x}g_{i}(\bar{x},\bar{w}),\lambda\in\Lambda(\bar{x},\bar{y},\bar{w})$
and $\lambda^{T}\nabla_{x}g(\bar{x},\bar{w})(u,v)=0$, that is,
$\lambda\in\Lambda(\bar{x},\bar{y},\bar{w};u,v)$. Hence, when Guignard CQ
holds, one has the formula (20). (21) follows by applying Proposition 2.2.

It is known that Guignard CQ holds under MSCQ. The reader can refer to [45,
Proposition 5] for more sufficient conditions for Guignard CQ.

###  4.2 Sensitivity analysis without weak convexity

Since $v_{\gamma}(x,y)=\inf_{w}\\{\nu(x,y,w)\mid g(x,w)\leq 0\\},$ under the
lower level generalized convexity assumption, for each fixed $(x,y)$, the
minimization problem (P${}^{\gamma}_{x,y}$) is strongly convex and so there
always exists a unique solution for each $(x,y)$. This implies that the
proximal map $S_{\gamma}$ is always single-valued. Besides, the objective
function $\nu(x,y,w)$ is coercive with respect to $w$, and hence it is level-
bounded. It follows that the restricted inf-compactness (see e.g., [23,
Definition 3.8]) always holds. And the directional Lipschitz continuity of
$v_{\gamma}(x,y)$ follows if $\mathcal{F}$ satisfies the directional RS.

###### Proposition 4.3

[1, Theorem 4.1] Let $\bar{w}\in S_{\gamma}(\bar{x},\bar{y})$. Suppose that
the feasible map ${\cal F}$ satisfies RS at $(\bar{x},\bar{w})$ in direction
$u$. Then $v_{\gamma}(x,y)$ is Lipschitz continuous at $(\bar{x},\bar{y})$ in
direction $(u,v)$ for any $v$.

Proof. Define $\widetilde{\mathcal{F}}(x,y):=\\{w|g(x,w)\leq 0\\}$. By
Definition 2.11 ${\cal F}(x)$ satisfying RS at $(\bar{x},\bar{w})$ in
direction $u$ is equivalent to $\widetilde{\cal F}(x,y)$ satisfying RS at
$(\bar{x},\bar{y},\bar{w})$ in direction $(u,v)$ for any $v$. By [1, Theorem
4.1] $v_{\gamma}(x,y)$ is Lipschitz continuous at $(\bar{x},\bar{y})$ in
direction $(u,v)$ for any $v$.

Observe that $\nu(x,y,w)=f(x,w)+\frac{1}{2\gamma}\|w-y\|^{2}$ is smooth with
the gradient equal to

$\nabla\nu(x,y,w)=(\nabla_{x}f(x,w),(y-w)/\gamma,\nabla_{w}f(x,w)+(w-y)/\gamma).$

So by the directional Danskin’s theorem [2, Proposition 4.4], we conclude that
the Clarke subdifferential of $v_{\gamma}(x,y)$ with respect to variable $y$
is a singleton and hence $v_{\gamma}(x,y)$ is continuously differentiable in
variable $y$ and
$\nabla_{y}v_{\gamma}(\bar{x},\bar{y})=(\bar{y}-\bar{w})/\gamma$ with
$\bar{w}\in S_{\gamma}(\bar{x},\bar{y})$. We have

$\displaystyle(v_{\gamma})_{+}^{\prime}(\bar{x},\bar{y};u,v)$
$\displaystyle=(v_{\gamma})_{+}^{\prime}(\bar{x},\bar{y};u,0)+v^{T}(\bar{y}-\bar{w})/\gamma,$
$\displaystyle(v_{\gamma})_{-}^{\prime}(\bar{x},\bar{y};u,v)$
$\displaystyle=(v_{\gamma})_{-}^{\prime}(\bar{x},\bar{y};u,0)+v^{T}(\bar{y}-\bar{w})/\gamma,$
$\displaystyle v_{\gamma}^{\prime}(\bar{x},\bar{y};u,v)$
$\displaystyle=v_{\gamma}^{\prime}(\bar{x},\bar{y};u,0)+v^{T}(\bar{y}-\bar{w})/\gamma,$

where $\bar{w}\in S_{\gamma}(\bar{x},\bar{y})$.

To obtain directional differentiability and subdifferentiability of
$v_{\gamma}$ with respect to variable $x$, we need to assume some regularity
conditions. In the following subsections, we study the sensitivity analysis of
$v_{\gamma}$ under FOSCMS, and RCR regularity$+$RS, respectively.

####  4.2.1 Sensitivity analysis under FOSCMS

Since the solution map $S_{\gamma}(x,y)$ is always uniformly compact around
$(\bar{x},\bar{y})$, by [3, Theorem 4.3 and Corollaries 4.7 and 4.8], under
MFCQ or FOSCMS we have the following estimates for Dini directional
derivatives of $v_{\gamma}(x,y)$.

###### Proposition 4.4

Let $\bar{w}\in S_{\gamma}(\bar{x},\bar{y})$ and $u\in\mathbb{R}^{n}$. Suppose
either MFCQ holds for the system $g(\bar{x},w)\leq 0$ at $w=\bar{w}$ or one of
the following FOSCMS holds:

  * •

Suppose for any direction $d\in{\rm Im}D_{x}g(\bar{x},\bar{w};u)$, there
exists $v\in\mathbb{R}^{m}$ satisfying

$d_{i}+\nabla_{y}g_{i}(\bar{x},\bar{w})v\leq 0,\ i\in I_{g}(\bar{x},\bar{w}).$
(22)

Suppose that FOSCMS for the system $g(\bar{x},w)\leq 0$ at $w=\bar{w}$ holds
in direction $d+\nabla_{y}g(\bar{x},\bar{w})v$, i.e.,

$\displaystyle\left\\{\begin{array}[]{ll}\nabla_{y}g(\bar{x},\bar{w})^{T}\lambda=0,\\\
0\leq\lambda\perp g(\bar{x},\bar{w}),\
\lambda\perp(d+\nabla_{y}g(\bar{x},\bar{w})v)\end{array}\right.\implies\lambda=0,$

for each $(d,v)\not=0$ satisfying (22) and $d\in{\rm
Im}D_{x}g(\bar{x},\bar{w};u)$. Moreover suppose
$\mathbb{L}(\bar{x},\bar{w};\pm u)$ is nonempty and FOSCMS holds at $\bar{w}$
in direction $\nabla g(\bar{x},\bar{w})(\pm u,v)$ for any
$v\in\mathbb{L}(\bar{x},\bar{w};\pm u)$.

  * •

$\nabla_{x}g(\bar{x},\bar{y})u\not=0$, $\mathbb{L}(\bar{x},\bar{w};\alpha u)$
is nonempty for any $\alpha\in\mathbb{R}$ and FOSCMS holds at $\bar{w}$ in
direction $\nabla g(\bar{x},\bar{w})(\alpha u,v)$ for any
$(\alpha,v)\not=(0,0)$ with $v\in\mathbb{L}(\bar{x},\bar{w};\alpha u)$.

Then for any direction $v\in\mathbb{R}^{m}$,

$\displaystyle\min_{\lambda\in\Lambda(\bar{x},\bar{y},\bar{w})}\nabla_{x}\mathcal{L}(\bar{x},\bar{y},\bar{w};\lambda)u+v^{T}(\bar{y}-\bar{w})/\gamma\leq$
$\displaystyle(v_{\gamma})_{-}^{\prime}(\bar{x},\bar{y};u,v)\leq(v_{\gamma})_{+}^{\prime}(\bar{x},\bar{y};u,v)$
(24)
$\displaystyle\leq{\max_{\lambda\in\Lambda(\bar{x},\bar{y},\bar{w})}}\nabla_{x}\mathcal{L}(\bar{x},\bar{y},\bar{w};\lambda)u+v^{T}(\bar{y}-\bar{w})/\gamma.$

Furthermore if $\Lambda(\bar{x},\bar{y},\bar{w})=\\{\bar{\lambda}\\}$ is a
singleton, then $v_{\gamma}(x,y)$ is Hadamard directionally differentiable and

$(v_{\gamma})^{\prime}(\bar{x},\bar{y};u,v)=\nabla_{x}\mathcal{L}(\bar{x},\bar{y},\bar{w};\bar{\lambda})u+v^{T}(\bar{y}-\bar{w})/\gamma.$

Proof. When MFCQ holds, the proof is complete from [3, Corollary 4.7]. Next,
we prove the results under FOSCMS. As discussed at the beginning of Section
4.2, with generalized convexity, the restricted inf-compactness condition
holds automatically. By Proposition 2.3, under the assumed conditions
$\mathcal{F}$ satisfies RS in direction $(u,v)$. The estimate (24) follows
from [3, Theorem 4.3].

We now study the subdifferentiability of $v_{\gamma}$. Let $w\in{\cal F}(x)$.
For direction $(u,d)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$, define

$\displaystyle
W(x,y,w;u,d):=\bigcup_{\lambda\in\Lambda(x,y,w;u,d)}\left\\{(\nabla_{x}f(x,w)+\nabla_{x}g(x,w)^{T}\lambda)\right\\}\times\\{(y-w)/\gamma\\}.$

The following inner calmness* property will be used in this section to obtain
simplified estimates for directional subdifferentials of $v_{\gamma}$.

######  Definition 4.1 (Directional Inner Calmness*)

(Benko et al. [5]) The optimal solution map $S_{\gamma}(x,y)$ is said to be
inner calm* at $(\bar{x},\bar{y},\bar{w})$ in direction $(u,v)$ if there
exists $\kappa>0$ such that for every sequence
$(x^{k},y^{k})\xrightarrow{(u,v)}(\bar{x},\bar{y})$, there exist a subsequence
$K$ of the set of nonnegative integers $\mathbb{N}$, together with a sequence
$w^{k}\in S_{\gamma}(x^{k},y^{k})$ for $k\in K$ and $\bar{w}\in\mathbb{R}^{m}$
such that

$\|w^{k}-\bar{w}\|\leq\kappa\|(x^{k},y^{k})-(\bar{x},\bar{y})\|.$

Particularly, we say $S_{\gamma}(x,y)$ is inner calm* at
$(\bar{x},\bar{y},\bar{w})$ if $(u,v)=(0,0)$.

Based on [2, Proposition 4.2] we can obtain the following results.

###### Proposition 4.5

Let $\bar{w}\in S_{\gamma}(\bar{x},\bar{y})$ and $u\in\mathbb{R}^{n}$. Suppose
that the system $g(x,w)\leq 0$ satisfies MSCQ at $(\bar{x},\bar{w})$ and
$\mathcal{F}$ satisfies RS at $(\bar{x},\bar{w})$ in direction $u$. Then
$v_{\gamma}(x,y)$ is Lipschitz around $(\bar{x},\bar{y})$ in direction
$(u,v)$, and

$\displaystyle\emptyset\not=$ $\displaystyle\partial
v_{\gamma}(\bar{x},\bar{y};u,v)\subseteq\bigcup_{d\in\mathcal{C}(\bar{x},\bar{y},\bar{w};u)\cup(\mathcal{C}(\bar{x},\bar{y},\bar{w};0)\cap\mathbb{S})}W(\bar{x},\bar{y},\bar{w};u,d),$
(25)

where

$\displaystyle\mathcal{C}(x,y,w;u)$ $\displaystyle:=$
$\displaystyle\left\\{d~{}\Bigg{|}\begin{array}[]{l}(v_{\gamma})_{-}^{\prime}(x,y;u,0)\leq\nabla
f(x,w)(u,d)+{d^{T}(w-y)/\gamma}\leq(v_{\gamma})_{+}^{\prime}(x,y;u,0)\\\
\nabla g_{i}(x,w)(u,d)\leq 0,\ \ \forall i\in I_{g}(x,w)\end{array}\right\\}.$

Moreover if $S_{\gamma}(x,y)$ is inner calm* at $(\bar{x},\bar{y},\bar{w})$ in
direction $(u,v)$, then the upper estimate (25) can be replaced by the smaller
set
$\bigcup_{d\in\mathcal{C}(\bar{x},\bar{y},\bar{w};u)}W(\bar{x},\bar{y},\bar{w};u,d)$.

Proof. Since $f$ is convex and $g$ is quasiconvex in $y$ for each fixed $x$,
as discussed before, the restricted inf-compactness condition holds
automatically. As $S_{\gamma}(\bar{x},\bar{y})=\\{\bar{w}\\}$ and the system
$g(x,w)\leq 0$ satisfies MSCQ at $(\bar{x},\bar{w})$, by [2, Theorem 3.1] the
upper estimate (25) holds. Besides, since $\mathcal{F}$ satisfies RS at
$(\bar{x},\bar{w})$ in direction $u$, the directional Lipschitz continuity of
$v_{\gamma}$ along direction $(u,v)$ follows directly from Proposition 4.3. It
follows that $\partial v_{\gamma}(\bar{x},\bar{y};u,v)$ is nonempty.

Since by Proposition 2.3, FOSCMS in certain directions or MFCQ for the system
$g(\bar{x},w)\leq 0$ holding at $\bar{w}$ implies RS, we can replace RS by
FOSCMS/MFCQ and obtain the following corollary from Propositions 4.4 and 4.5.

###### Corollary 4.1

Let $\bar{w}\in S_{\gamma}(\bar{x},\bar{y})$ and $u\in\mathbb{R}^{n}$. Then
under one of the following conditions, $v_{\gamma}(x,y)$ is directionally
differentiable and Lipschitz around $(\bar{x},\bar{y})$ in direction $(u,v)$
for any $v\in\mathbb{R}^{m}$, and (24), (25) hold.

  * (a)

Suppose $\nabla_{x}g(\bar{x},\bar{w})u\not=0$ and
$\mathbb{L}(\bar{x},\bar{w};\alpha u)\not=\emptyset$ for any
$\alpha\in\mathbb{R}$. Suppose that the system $g(x,w)\leq 0$ satisfies MSCQ
at $(\bar{x},\bar{w})$ and FOSCMS for the system $g(\bar{x},w)\leq 0$ at
$w=\bar{w}$ holds in direction $\nabla g(\bar{x},\bar{w})(\alpha u,v)$ for any
$(\alpha,v)\neq 0$ with $v\in\mathbb{L}(\bar{x},\bar{w};\alpha u)$.

  * (b)

Suppose that the system $g(x,w)\leq 0$ satisfies MFCQ at $(\bar{x},\bar{w})$

Proof. (a) When $\nabla_{x}g(\bar{x},\bar{w})u\neq 0$,
$\\{\alpha\nabla_{x}g(\bar{x},\bar{w})u|\alpha\geq 0\\}={\rm
Im}D_{x}g(\bar{x},\bar{w};u)$. Then $d\in{\rm Im}D_{x}g(\bar{x},\bar{w};u)$ if
and only if $d=\nabla g(\bar{x},\bar{w})(\alpha u)$ for some $\alpha\geq 0$.
Hence condition (22) reduces to the nonemptyness of
$\mathbb{L}(\bar{x},\bar{w};\alpha u)$ for all $\alpha\geq 0$. And FOSCMS at
$\bar{w}$ in direction $d+\nabla_{y}g(\bar{x},\bar{w})v$ for each
$(d,v)\not=0$ satisfying (22) and $d\in{\rm Im}D_{x}g(\bar{x},\bar{w};u)$ is
equivalent to FOSCMS at $\bar{w}$ in direction $\nabla
g(\bar{x},\bar{w})(\alpha u,v)$ for any $(\alpha,v)\not=(0,0)$ satisfying
$v\in\mathbb{L}(\bar{x},\bar{w};\alpha u)$. Estimate (24) follows from
applying Proposition 4.4 immediately. And (25) holds because the directional
RS follows from Proposition 2.3 and MSCQ for the system $g(x,w)\leq 0$ is
assumed.

Now we prove (b). By Proposition 4.4, estimate (24) holds under MFCQ.
Furthermore, MFCQ implies RS of $\mathcal{F}$ at $(\bar{x},\bar{w})$ by
Proposition 2.3, hence implies MSCQ of system $g(x,w)\leq 0$ and directional
RS of $\mathcal{F}$. Then by Proposition 4.5, the estimate (25) holds.

###  4.3 Sensitivity analysis under RCRCQ+RS

It is well-known in nonlinear optimization that RCR-regularity is not
comparable to MFCQ. Now we apply directional sensitivity analysis from [1] and
obtain the following directional differentiability results of
$v_{\gamma}(x,y)$.

###### Proposition 4.6

Suppose $f$ is convex and $g$ is quasiconvex in $y$ for fixed $x$. Let
$\bar{w}\in S_{\gamma}(\bar{x},\bar{y})$. Assume that ${\cal F}$ is RCR-
regular at $(\bar{x},\bar{w})$ and RS is satisfied at $(\bar{x},\bar{w})$ in
direction $u$. Then the function $v_{\gamma}(x,y)$ is directionally Lipschitz
and directionally differentiable at $(\bar{x},\bar{y})$ in direction $(u,v)$
for any $v$ and

$\displaystyle
v_{\gamma}^{\prime}(\bar{x},\bar{y};u,v)=\max_{\lambda\in\Lambda(\bar{x},\bar{y},\bar{w})}\nabla_{x}{\cal
L}(\bar{x},\bar{y},\bar{w};\lambda)u+v^{T}(\bar{y}-\bar{w})/\gamma,$ (26)
$\displaystyle\emptyset\not=\partial
v_{\gamma}(\bar{x},\bar{y};u,v)\subseteq\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v)\subseteq
W(\bar{x},\bar{y},\bar{w};u,d)\quad\forall
d\in\mathcal{C}(\bar{x},\bar{y},\bar{w};u),$ (27)

where

$\displaystyle\mathcal{C}(\bar{x},\bar{y},\bar{w};u)=\left\\{d~{}\Bigg{|}\begin{array}[]{l}\max_{\lambda\in\Lambda(\bar{x},\bar{y},\bar{w})}\nabla_{x}{\cal
L}(\bar{x},\bar{y},\bar{w};\lambda)u=\nabla
f(\bar{x},\bar{w})(u,d)+{d^{T}(\bar{w}-\bar{y})/\gamma}\\\ \nabla
g_{i}(\bar{x},\bar{w})(u,d)\leq 0,\ \ \forall i\in
I_{g}(\bar{x},\bar{w})\end{array}\right\\}.$

Proof. As discussed in the beginning of this section, the restricted inf-
compactness always holds for problem $(P^{\gamma}_{x,y})$ at any point
$(\bar{x},\bar{y})$ and in any direction $(u,0)$. Since ${\cal F}(x)$ is
independent of variable $y$, ${\cal F}$ satisfying RS at $(\bar{x},\bar{w})$
in direction $u$ is equivalent to saying that ${\cal F}$ satisfies RS at
$(\bar{x},\bar{y},\bar{w})$ in direction $(u,0)$. Hence by [3, Corollary 4.1],
$v_{\gamma}(x,y)$ is continuous in direction $(u,0)$ and
$S_{\gamma}(\bar{x},\bar{y};u,0)\not=\emptyset$, where
$S_{\gamma}(\bar{x},\bar{y};u,0)$ denotes the directional solution in
direction $(u,0)$ (see [1, Definition 4.5]). Hence
$S_{\gamma}(\bar{x},\bar{y};u,0)=\\{\bar{w}\\}$. By [1, Proposition 4.3],

$v_{\gamma}^{\prime}(\bar{x},\bar{y};u,0)=\max_{\lambda\in\Lambda(\bar{x},\bar{y},\bar{w})}\nabla_{x}{\cal
L}(\bar{x},\bar{y},\bar{w};\lambda)u.$

Noting that

$v_{\gamma}^{\prime}(\bar{x},\bar{y};u,v)=v_{\gamma}^{\prime}(\bar{x},\bar{y};u,0)+\nabla_{y}v_{\gamma}(\bar{x},\bar{y})v\mbox{
and }\nabla_{y}v_{\gamma}(\bar{x},\bar{y})=(\bar{y}-\bar{w})/\gamma,$

the proof of (26) is completed. By [1, Theorem 4.3], since
$S_{\gamma}(\bar{x},\bar{y};u,v)=\\{\bar{w}\\}$ is a singleton, we have
$\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v)\subseteq{\rm
co}W(\bar{x},\bar{y},\bar{w};u,d)\quad\forall d\in
d\in\mathcal{C}(\bar{x},\bar{y},\bar{w};u)$. Since
$W(\bar{x},\bar{y},\bar{w};u,d)$ is convex, the second inclusion in (27)
follows.

##  5 Necessary optimality conditions for bilevel programs

The main purpose of this section is to apply Theorem 3.1 to problem (VP)γ and
the result of the directional sensitivity analysis of the Moreau envelope
function in Section 4 to derive a verifiable necessary optimality condition
for (VP)γ under a weak and verifiable constraint qualification.

By the generalized convexity of the lower level program, it is easy to show
that $\bar{y}\in S(\bar{x})$ if and only if
$S_{\gamma}(\bar{x},\bar{y})=\\{\bar{y}\\}$.

Since for $\bar{y}\in S(\bar{x})$,

$(f-v_{\gamma})^{\prime}_{-}(\bar{x},\bar{y};u,v)=\nabla
f(\bar{x},\bar{y})(u,v)-(v_{\gamma})^{\prime}_{+}(\bar{x},\bar{y};u,v)=\nabla
f(\bar{x},\bar{y})(u,v)-(v_{\gamma})^{\prime}_{+}(\bar{x},\bar{y};u,0),$

we can define the linearized cone of (VP)γ at a feasible solution
$(\bar{x},\bar{y})$ by

$\mathbb{L}(\bar{x},\bar{y}):=\left\\{(u,v)\Bigg{|}\begin{array}[]{l}\nabla
f(\bar{x},\bar{y})(u,v)\leq(v_{\gamma})_{+}^{\prime}(\bar{x},\bar{y};u,0),\\\
\nabla g_{i}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall i\in
I_{g}(\bar{x},\bar{y}),{\nabla G_{i}}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall
i\in I_{G}(\bar{x},\bar{y})\end{array}\right\\}.$

Let $(\bar{x},\bar{y})$ be a feasible solution of (VP)γ. Then for all
$y\in{\cal F}(x)$,

$0=f(\bar{x},\bar{y})-v_{\gamma}(\bar{x},\bar{y})\leq f(x,y)-v_{\gamma}(x,y).$

Hence under the Abadie constraint qualification, one always has $\nabla
f(\bar{x},\bar{y})(u,v)\geq(v_{\gamma})^{\prime}_{-}(\bar{x},\bar{y};u,0)$ for
all $(u,v)$ satisfying $\nabla g_{i}(\bar{x},\bar{y})(u,v)\leq 0,\ i\in
I_{g}(\bar{x},\bar{y})$. The Abadie constraint qualification is very weak and
it would satisfy under the constraint qualifications we impose. We may denote
the critical cone of (VP)γ at $(\bar{x},\bar{y})$ by

$\displaystyle C(\bar{x},\bar{y}):=$
$\displaystyle\\{(u,v)\in\mathbb{L}(\bar{x},\bar{y})~{}|~{}\nabla
F(\bar{x},\bar{y})(u,v)\leq 0\\}$ $\displaystyle=$
$\displaystyle\left\\{(u,v)~{}\Bigg{|}~{}\begin{array}[]{l}(v_{\gamma})^{\prime}_{-}(x,y;u,0)\leq\nabla
f(\bar{x},\bar{y})(u,v)\leq(v_{\gamma})_{+}^{\prime}(\bar{x},\bar{y};u,0),\\\
\nabla F(\bar{x},\bar{y})(u,v)\leq 0,\\\ \nabla
g_{i}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall i\in
I_{g}(\bar{x},\bar{y}),{\nabla G_{i}}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall
i\in I_{G}(\bar{x},\bar{y})\end{array}\right\\}.$ (31)

For $(\bar{x},\bar{y})\in{\rm gph}{\cal F}$ and $u\in\mathbb{R}^{n}$, define

$\displaystyle\mathcal{C}(\bar{x},\bar{y};u)=\left\\{v~{}\Bigg{|}\begin{array}[]{l}(v_{\gamma})^{\prime}_{-}(\bar{x},\bar{y};u,0)\leq\nabla
f(\bar{x},\bar{y})(u,v)\leq(v_{\gamma})_{+}^{\prime}(\bar{x},\bar{y};u,0)\\\
\nabla g_{i}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall i\in
I_{g}(\bar{x},\bar{y})\end{array}\right\\}.$

Define the Lagrange function of $(P_{x})$ associated with $y\in{\cal F}(x)$ by

${\cal L}(x,y;\lambda):={\cal L}(x,y,y;\lambda)=f(x,y)+g(x,y)^{T}\lambda,$

the set of Lagrange multipliers of $(P_{x})$ by

$\Lambda(x,y):=\Lambda(x,y,y)=\\{\lambda\in\mathbb{R}^{p}|\nabla_{y}{\cal
L}(x,y;\lambda)=0,\ g(x,y)^{T}\lambda=0,\ \lambda\geq 0\\}$

and the set of directional multipliers associated with direction $(u,v)$ with
$\nabla g(x,y)(u,v)\in T_{\mathbb{R}^{p}_{-}}(g(x,y))$ by

$\Lambda(x,y;u,v):=\\{\lambda\in\mathbb{R}^{p}_{+}|\nabla_{y}{\cal
L}(x,y;\lambda)=0,\ g(x,y)^{T}\lambda=0,\ \lambda^{T}\nabla g(x,y)(u,v)=0\\}.$

It is known [46] that classical constraint qualifications such as the NNAMCQ
fails at each feasible point of (VP). Recently, it is proved in [1] that the
FOSCMS also fails at any feasible point of (VP) along any critical direction.
Similar to [1, Proposition 5.1] we can show that even the weaker constraint
qualification FOSCMS fails at any feasible point of (VP)γ along any critical
direction. As discussed in Section 3, one can obtain a necessary optimality
condition under the calmness condition.

In [46, Definition 3.1], the partial calmness condition was introduced for
(VP). We now define a directional version of the partial calmness for our
problem (VP)γ.

######  Definition 5.1 (Directional partial calmness)

Suppose $(\bar{x},\bar{y})$ is a local solution of (VP)γ. We say that (VP)γ is
partially calm at $(\bar{x},\bar{y})$ in direction $(u,v)$ if there exist
positive scalars $\epsilon,\delta,\rho$, such that for any
$(\alpha,\beta)\in\epsilon\mathbb{B}$ and any $(x,y)\in{\rm
gph}\mathcal{F}\cap((\bar{x},\bar{y})+{\cal V}_{\epsilon,\delta}(u,v))$
satisfying $f(x,y)-v_{\gamma}(x,y)+\alpha\leq 0,G(x,y)+\beta\leq 0$ one has,

$F(x,y)-F(\bar{x},\bar{y})+\rho\|(\alpha,\beta)\|\geq 0.$

It is easy to see that the partial calmness condition above is equivalent to
exact penalization of the constraints $f(x,y)-v_{\gamma}(x,y)\leq 0$ and
$G(x,y)\leq 0$ in a directional neighborhood of $(u,v)$. It is easy to see
that the combination of the directional partial calmness and directional MSCQ
of the system $g(x,y)\leq 0$ in direction $(u,v)$ can imply the directional
calmness condition of (VP)γ in direction $(u,v)$. Now we apply Theorem 3.1 to
(VP)γ to obtain the necessary optimalitys condition for the bilevel program
(BP) under the partial calmness condition.

###### Theorem 5.1

Let $(\bar{x},\bar{y})$ be a local minimizer of (BP) with a generalized convex
lower level program. Suppose the value function $v_{\gamma}$ is directionally
Lipschitz continuous at $(\bar{x},\bar{y})$ in direction $(u,v)\in
C(\bar{x},\bar{y})$, defined in (5). Moreover suppose (VP)γ is either calm or
partially calm at $(\bar{x},\bar{y})$ in direction $(u,v)$ and MSCQ for the
system $g(x,y)\leq 0$ at $(\bar{x},\bar{y})$ in direction $(u,v)$. Then there
exists $(\alpha,\lambda_{g},\lambda_{G})\in\mathbb{R}^{1+p+q}$ such that

$\displaystyle 0\in\nabla F(\bar{x},\bar{y})+\alpha\nabla
f(\bar{x},\bar{y})-\alpha\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v)+\nabla
g(\bar{x},\bar{y})^{T}\lambda_{g}+\nabla G(\bar{x},\bar{y})^{T}\lambda_{G},$
$\displaystyle\alpha\geq 0,\ 0\leq\lambda_{g}\perp g(\bar{x},\bar{y}),\
\lambda_{g}\perp\nabla g(\bar{x},\bar{y})(u,v),\ 0\leq\lambda_{G}\perp
G(\bar{x},\bar{y}),\ \lambda_{G}\perp\nabla G(\bar{x},\bar{y})(u,v).$

By Propositions 2.2 and 4.1, in case $f$ is weakly convex and $g$ is
quasiconvex in variables $(x,y)$, we have the
$\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v)=\partial
v_{\gamma}(\bar{x},\bar{y};u,v)$ for sufficiently small $\gamma$. Hence by
Proposition 4.2 and Theorem 5.1, we obtain the following optimality conditions
for this case immediately.

###### Theorem 5.2

Let $(\bar{x},\bar{y})$ be a local minimizer of (BP) for which $g(x,y)$ is
quasi-convex in variables $(x,y)$ on $\mathbb{R}^{n}\times\mathbb{R}^{m}$, and
$f$ is convex in $y$ and $\rho_{f}$-weakly convex on gph${\cal F}$ with
$\rho_{f}>0$. Suppose that the $\mathcal{F}(x)\neq\emptyset$ for all $x$ in a
neighborhood of $\bar{x}$ and MSCQ for system $g(x,y)\leq 0$ holds at
$(\bar{x},\bar{y})$. Then

$C(\bar{x},\bar{y})=\left\\{(u,v)~{}\Bigg{|}~{}\begin{array}[]{l}\nabla
f(\bar{x},\bar{y})(u,v)=\max_{\lambda\in\Lambda(\bar{x},\bar{y})}\nabla_{x}{\cal
L}(\bar{x},\bar{y};\lambda)u,\quad\nabla F(\bar{x},\bar{y})(u,v)\leq 0,\\\
\nabla g_{i}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall i\in
I_{g}(\bar{x},\bar{y}),{\nabla G_{i}}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall
i\in I_{G}(\bar{x},\bar{y})\end{array}\right\\}.$

If (VP)γ for some $\gamma\in(0,1/\rho_{f})$ is partially calm at
$(\bar{x},\bar{y})$ in a direction $(u,v)\in C(\bar{x},\bar{y})$. Then there
exists a vector $(\alpha,\lambda_{g},\lambda_{G})\in\mathbb{R}^{1+p+q}$ and
$\bar{\lambda}\in\Lambda(\bar{x},\bar{y};u,v)$ satisfying

$\displaystyle 0=\nabla F(\bar{x},\bar{y})+\nabla
g(\bar{x},\bar{y})^{T}(\lambda_{g}-\alpha\bar{\lambda})+\nabla
G(\bar{x},\bar{y})^{T}\lambda_{G},$ (32) $\displaystyle\alpha\geq
0,0\leq\lambda_{g}\perp g(\bar{x},\bar{y}),\lambda_{g}\perp\nabla
g(\bar{x},\bar{y})(u,v),0\leq\lambda_{G}\perp
G(\bar{x},\bar{y}),\lambda_{G}\perp\nabla G(\bar{x},\bar{y})(u,v).$

Similarly, by Proposition 4.6 under the RCR-regularity, one can obtain the
following result. Note that RCR-regularity implies MSCQ for the system
$g(x,y)\leq 0$.

###### Theorem 5.3

Let $(\bar{x},\bar{y})$ be a local minimizer of (BP) with a generalized convex
lower level program. Suppose that the feasible map $\mathcal{F}$ satisfies
RCR-regularity and RS at $(\bar{x},\bar{y})$ in a direction
$u\in\mathbb{R}^{n}$. Then

$C(\bar{x},\bar{y})=\left\\{(u,v)~{}\Bigg{|}~{}\begin{array}[]{l}\nabla
f(\bar{x},\bar{y})(u,v)=\max_{\lambda\in\Lambda(\bar{x},\bar{y})}\nabla_{x}{\cal
L}(\bar{x},\bar{y};\lambda)u,\quad\nabla F(\bar{x},\bar{y})(u,v)\leq 0,\\\
\nabla g_{i}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall i\in
I_{g}(\bar{x},\bar{y}),{\nabla G_{i}}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall
i\in I_{G}(\bar{x},\bar{y})\end{array}\right\\}.$

Furthermore, suppose that (VP)γ for some $\gamma>0$ is partially calm at
$(\bar{x},\bar{y})$ in direction $(u,v)\in C(\bar{x},\bar{y})$. Then there
exists a vector $(\alpha,\lambda_{g},\lambda_{G})\in\mathbb{R}^{1+p+q}$ and
$\bar{\lambda}\in\Lambda(\bar{x},\bar{y};u,v)$ satisfying (32).

Proof. The proof follows from Theorem 5.1, Proposition 4.6 and the implication

$(u,v)\in C(\bar{x},\bar{y})\implies v\in\mathcal{C}(\bar{x},\bar{y};u),$

where

$\displaystyle\mathcal{C}(\bar{x},\bar{y};u)=\left\\{d~{}\Bigg{|}\begin{array}[]{l}\max_{\lambda\in\Lambda(\bar{x},\bar{y},\bar{w})}\nabla_{x}{\cal
L}(\bar{x},\bar{y};\lambda)u=\nabla f(\bar{x},\bar{w})(u,d)\\\ \nabla
g_{i}(\bar{x},\bar{y})(u,d)\leq 0,\ \ \forall i\in
I_{g}(\bar{x},\bar{y})\end{array}\right\\}.$

By Corollary 4.1 and Theorem 5.1, we obtain the following optimality
conditions for this case immediately. Note that MFCQ for the system
$g(\bar{x},y)\leq 0$ at $\bar{y}$ implies MSCQ for the system $g(x,y)\leq 0$
at $(\bar{x},\bar{y})$.

###### Theorem 5.4

Let $(\bar{x},\bar{y})$ be a local minimizer of (BP) with a generalized convex
lower level program. Suppose that either MFCQ for the system $g(\bar{x},y)$
holds at $y=\bar{y}$ or condition (a) in Corollary 4.1 holds. Furthermore,
suppose that (VP)γ for some $\gamma>0$ is partially calm at
$(\bar{x},\bar{y})$ in direction $(u,v)\in C(\bar{x},\bar{y})$. Then there
exists a vector $(\alpha,\lambda_{g},\lambda_{G})\in\mathbb{R}^{1+p+q}$
together with $\bar{\lambda}\in\Lambda(\bar{x},\bar{y})$ satisfying (32).

Proof. By Corollary 4.1, (25) holds. Meanwhile, for any direction $(u,d)$,
$W(\bar{x},\bar{y},\bar{y};u,d)\subseteq W(\bar{x},\bar{y},\bar{y};0,0)$,
which is convex. This together with (25) and Definition 2.7 imply that
$\partial^{c}v_{\gamma}(\bar{x},\bar{y};0,0)\subseteq
W(\bar{x},\bar{y},\bar{w};0,0)$. Then the proof is complete noticing that
$\Lambda(\bar{x},\bar{y};0,0)=\Lambda(\bar{x},\bar{y})$.

In particular if we take $(u,v)=(0,0)$ in (32), then by Theorems 5.2, 5.3 and
5.4 we have the following corollary.

###### Corollary 5.1

Let $(\bar{x},\bar{y})$ be a local minimizer of (BP) with a generalized convex
lower level program. Suppose one of the following conditions holds:

  * (i)

$g(x,y)$ is quasi-convex, $f$ is $\rho_{f}$-weakly convex with $\rho_{f}>0$ on
gph${\cal F}$. ${\cal F}(x)\not=\emptyset$ for all $x$ in a neighborhood of
$\bar{x}$. MSCQ holds for the system $g(x,y)\leq 0$ at $(\bar{x},\bar{y})$.

  * (ii)

the feasible map $\mathcal{F}$ satisfies RCR-regularity and RS at
$(\bar{x},\bar{y})$.

  * (iii)

MFCQ holds for the system $g(\bar{x},y)\leq 0$ at $\bar{y}$.

Suppose that (VP)γ for some $\gamma>0$ ($\gamma\in(0,1/\rho_{f})$ when
condition (i) holds) is partially calm at $(\bar{x},\bar{y})$ in certain
direction $(u,v)\in C(\bar{x},\bar{y})$. Then there exists a vector
$(\alpha,\lambda_{g},\lambda_{G})\in\mathbb{R}_{+}\times\mathbb{R}^{p+q}$ and
$\bar{\lambda}\in\Lambda(\bar{x},\bar{y})$ satisfying

$\displaystyle\begin{aligned} &0=\nabla F(\bar{x},\bar{y})+\nabla
g(\bar{x},\bar{y})^{T}(\lambda_{g}-\alpha\bar{\lambda})+\nabla
G(\bar{x},\bar{y})^{T}\lambda_{G},\\\ &0\leq\lambda_{g}\perp
g(\bar{x},\bar{y}),\quad 0\leq\lambda_{G}\perp G(\bar{x},\bar{y}).\
\end{aligned}$ (33)

In Theorem 5.4 and Corollary 5.1(iii), we need a direction $(u,v)\in
C(\bar{x},\bar{y})$. Such a direction can be obtained for example if the
multiplier set $\Lambda(\bar{x},\bar{y})=\\{\bar{\lambda}\\}$ is a singleton
since in this case the critical cone is equal to

$C(\bar{x},\bar{y})=\left\\{(u,v)~{}\Bigg{|}~{}\begin{array}[]{l}\nabla
f(\bar{x},\bar{y})(u,v)=\nabla_{x}{\cal
L}(\bar{x},\bar{y};\bar{\lambda})u,\quad\nabla F(\bar{x},\bar{y})(u,v)\leq
0,\\\ \nabla g_{i}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall i\in
I_{g}(\bar{x},\bar{y}),{\nabla G_{i}}(\bar{x},\bar{y})(u,v)\leq 0,\ \forall
i\in I_{G}(\bar{x},\bar{y})\end{array}\right\\}.$

###### Remark 5.1

The stationary condition (33) is in fact the stationary condition (5). Hence
Corollary 5.1 has provided sufficient conditions under which the stationary
system (5) is a necessary optimality condition. In fact the stationary system
(5) was proved to be a necessary optimality condition for the class of jointly
convex lower level program under the nondifferentiable Abadie CQ in [40,
Theorem 4.2], the extended Abadie CQ in [42, Theorem 4.1 and Corollary 4.1]
and the calmness of the partially perturbed feasible region of $(VP)$ (see
[24, Lemma 5.1(c)]). The directional version (32) is sharper than the
nondirectional one (33), and the directional S-stationary conditions for the
MPCC approach, see e.g., [25, Definition 4.4]. Note that unlike the KKT
approach where $\bar{\lambda}$ in Definition 1.1 is arbitrary, our optimality
conditions come with a lower level multiplier $\bar{\lambda}$ which is
selected and not given a priori.

It is known that the directional quasi-normality and the relaxed constant
positively linear dependence (RCPLD) condition (see [38]) can hold at feasible
points of (VP). Since RCPLD or the quasi-normality implies MSCQ, according to
the discussion in Section 3, the MSCQ of the constraint system for problem
(VP)γ in a direction implies the calmness of the problem in the same
direction. Consequently, the directional partial calmness assumed in Theorems
5.2 5.3 and 5.4 can be replaced by the directional quasi-normality condition,
or the RCPLD condition.

In the rest of this section, we will propose some verifiable sufficient
conditions for the directional quasi-normality. For the sake of simplicity, we
only give the definition of directional quasi-normality condition for (VP)γ.

###### Definition 5.2

Let $(\bar{x},\bar{y})$ be a feasible point of (BP) with a generalized convex
lower level program. Assume that $v_{\gamma}(x,y)$ is directionally Lipschitz
continuous at $(\bar{x},\bar{y})$ in direction $(u,v)$. We say that the
directional quasi-normality holds at $(\bar{x},\bar{y})$ in direction $(u,v)$
if there exists no nonzero vector
$(\alpha,\nu_{g},\nu_{G})\in\mathbb{R}^{1+p+q}_{+}$ satisfying that

$\displaystyle 0\in\alpha\nabla
f(\bar{x},\bar{y})-\alpha\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v)+\nabla
g(\bar{x},\bar{y})^{T}\nu_{g}+\nabla G(\bar{x},\bar{y})^{T}\nu_{G},$ (34)
$\displaystyle\nu_{g}\perp g(\bar{x},\bar{y}),\ \nu_{g}\perp\nabla
g(\bar{x},\bar{y})(u,v),\ \nu_{G}\perp G(\bar{x},\bar{y}),\ \nu_{G}\perp\nabla
G(\bar{x},\bar{y})(u,v),$ $\displaystyle\alpha\perp\xi\mbox{ for some
}\xi\in\nabla f(\bar{x},\bar{y})(u,v)-Dv_{\gamma}(\bar{x},\bar{y})(u,v)$

and there exist sequences $t_{k}\downarrow 0,\ (u^{k},v^{k})\rightarrow(u,v)$
such that

$\displaystyle\begin{aligned}
\alpha(f(\bar{x}+t_{k}u^{k},\bar{y}+t_{k}v^{k})-v_{\gamma}(\bar{x}+t_{k}u^{k},\bar{y}+t_{k}v^{k}))>0,\
&\mbox{if}\ \alpha>0,\\\ g_{i}(\bar{x}+t_{k}u^{k},\bar{y}+t_{k}v^{k})>0,\
&\mbox{if}\ (\nu_{g})_{i}>0,i\in I_{g}(\bar{x},\bar{y}),\\\
G_{i}(\bar{x}+t_{k}u^{k},\bar{y}+t_{k}v^{k})>0,\ &\mbox{if}\
(\nu_{G})_{i}>0,i\in I_{G}(\bar{x},\bar{y}).\end{aligned}$ (35)

###### Remark 5.2

Define $\phi(x,y):=(f(x,y)-v_{\gamma}(x,y),g(x,y),G(x,y))$ and
$\lambda:=(\alpha,\nu_{g},\nu_{G})$. We can show that the directional quasi-
normality defined in Definition 5.2 is equivalent to the one defined in 2.9
for the system $\phi(x,y)\leq 0$. By assumption, $\phi(x,y)$ is directionally
Lipschitz continuous at $(\bar{x},\bar{y})$ in direction $(u,v)$. Then since
$f(\bar{x},\bar{y})-v_{\gamma}(\bar{x},\bar{y})=0,g(\bar{x},\bar{y})\leq
0,G(\bar{x},\bar{y})\leq 0$, $(\ref{KKT1})$ means
$0\leq\lambda\perp\phi(\bar{x},\bar{y})$ and

$\lambda\perp(\xi,\nabla g(\bar{x},\bar{y})(u,v),\nabla
G(\bar{x},\bar{y})(u,v)),$

where $(\xi,\nabla g(\bar{x},\bar{y})(u,v),\nabla G(\bar{x},\bar{y})(u,v))\in
D\phi(\bar{x},\bar{y})(u,v).$ Since by the calculus rule in [26, Theorem 5.6],
we have

$\displaystyle\partial(f-v_{\gamma})(\bar{x},\bar{y};u,v)=\nabla
f(\bar{x},\bar{y})+\partial(-v_{\gamma})(\bar{x},\bar{y};u,v)$
$\displaystyle\subseteq\nabla
f(\bar{x},\bar{y})+\partial^{c}(-v_{\gamma})(\bar{x},\bar{y};u,v)=\nabla
f(\bar{x},\bar{y})-\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v).$

we conclude that (34)-(35) is stronger than the directional quasi-normality
defined in Definition 2.9.

Applying the formulas of the directional derivatives and the upper estimates
for the directional subdifferentials for the function $v_{\gamma}(x,y)$
obtained in Section 4, we derive several sufficient conditions for the
directional quasi-normality below.

###### Theorem 5.5

Let $(\bar{x},\bar{y})$ be a feasible point of (BP) with a generalized convex
lower level program and $u\in\mathbb{R}^{n}$.

  * (i)

Suppose either MFCQ holds for the system $g(\bar{x},y)\leq 0$ at $\bar{y}$, or
the following conditions hold:

    * –

The system $g(x,y)\leq 0$ satisfies MSCQ at $(\bar{x},\bar{y})$ and
$\mathcal{F}$ satisfies RS at $(\bar{x},\bar{y})$ in direction $u$.
$\mathbb{L}(\bar{x},\bar{y};\pm u)$ is nonempty and FOSCMS holds at $\bar{y}$
in direction $\nabla g(\bar{x},\bar{y})(\pm u,v)$ for any
$v\in\mathbb{L}(\bar{x},\bar{y};\pm u)$.

Suppose there exists no nonzero vector
$(\alpha,\nu_{g},\nu_{G})\in\mathbb{R}^{1+p+q}_{+}$ satisfying conditions
(34)-(35) with $\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v)$ replaced by

$co\left(\bigcup_{\lambda\in\Lambda(\bar{x},\bar{y};u,d)\atop
d\in\widetilde{\mathcal{C}}(\bar{x},\bar{y};u)\cup(\widetilde{\mathcal{C}}(\bar{x},\bar{y};0)\cap\mathbb{S})}\left\\{(\nabla_{x}f(\bar{x},\bar{y})+\nabla_{x}g(\bar{x},\bar{y})^{T}\lambda)\right\\}\times\\{0\\}\right),$

where

$\displaystyle\widetilde{\mathcal{C}}(\bar{x},\bar{y};u)$ $\displaystyle:=$
$\displaystyle\left\\{d~{}\Bigg{|}\begin{array}[]{l}\min_{\lambda\in\Lambda(\bar{x},\bar{y})}\nabla_{x}{\cal
L}(\bar{x},\bar{y};\lambda)u\leq\nabla
f(\bar{x},\bar{y})(u,v)\leq\max_{\lambda\in\Lambda(\bar{x},\bar{y})}\nabla_{x}{\cal
L}(\bar{x},\bar{y};\lambda)u\\\ \nabla g_{i}(\bar{x},\bar{y})(u,d)\leq 0,\ \
\forall i\in I_{g}(\bar{x},\bar{y})\end{array}\right\\}.$

Moreover if $S_{\gamma}(x,y)$ is inner calm* at $(\bar{x},\bar{y})$ in
direction $(u,v)$ then $\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v)$ is
replaced by

$co\left(\bigcup_{\lambda\in\Lambda(\bar{x},\bar{y};u,d)\atop
d\in\widetilde{\mathcal{C}}(\bar{x},\bar{y};u)}\left\\{(\nabla_{x}f(\bar{x},\bar{y})+\nabla_{x}g(\bar{x},\bar{y})^{T}\lambda)\right\\}\times\\{0\\}\right).$

Then the directional quasi-normality holds at $(\bar{x},\bar{y})$ in direction
$(u,v)$.

  * (ii)

Suppose $f$ is $\rho_{f}$-weakly convex on gph${\cal F}$ with $\rho_{f}>0$.
Suppose that $\mathcal{F}(x)\neq\emptyset$ for all $x$ in a neighborhood of
$\bar{x}$ and MSCQ for the system $g(x,y)\leq 0$ holds at $(\bar{x},\bar{y})$.
Suppose there exists no nonzero vector
$(\alpha,\nu_{g},\nu_{G})\in\mathbb{R}^{1+p+q}_{+}$ satisfying conditions
(34)-(35) with $\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v)$ replaced by

$\bigcup_{\lambda_{g}\in\Lambda(\bar{x},\bar{y};u,v)}(\nabla_{x}f(\bar{x},\bar{y})+\nabla_{x}g(\bar{x},\bar{y})^{T}\lambda_{g},0).$

Then the directional quasi-normality holds at $(\bar{x},\bar{y})$ in direction
$(u,v)$.

  * (iii)

Suppose that $\bar{y}\in S(\bar{x})$ and ${\mathcal{F}}$ is RCR-regular and
satisfies RS at $(\bar{x},\bar{y})$ in direction $u$. Suppose there exists no
nonzero vector $(\alpha,\nu_{g},\nu_{G})\in\mathbb{R}^{1+p+q}_{+}$ satisfying
conditions (34)-(35) with $\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v)$
replaced by

$\bigcup_{\lambda_{g}\in\Lambda(\bar{x},\bar{y};u,d)}(\nabla_{x}f(\bar{x},\bar{y})+\nabla_{x}g(\bar{x},\bar{y})^{T}\lambda_{g},0),$

where $d\in\mathcal{C}(\bar{x},\bar{y};u)$. Then the directional quasi-
normality holds at $(\bar{x},\bar{y})$ in direction $(u,v)$.

Proof. By Proposition 4.4, $\widetilde{C}(\bar{x},\bar{y};u)$ contains
$C(\bar{x},\bar{y};u)$ in case (i). The rest of the proof follows from
Definition 5.2 and upper estimates for
$\partial^{c}v_{\gamma}(\bar{x},\bar{y};u,v)$ in Propositions 4.2, 4.5 and
4.6.

##  6 Conclusion

The classical approach of solving a bilevel program by its MPCC reformulation
is known to be problematic when the lower level program has non-unique
multipliers. In particular a local optimal solution
$(\bar{x},\bar{y},\bar{\lambda})$ for MPCC may not imply that
$(\bar{x},\bar{y})$ is a local optimal solution of the bilevel program.
Recently using the value function reformulation, some optimality conditions
such as system (5) which does not depend on an arbitrarily chosen multiplier
of the lower level program, have been derived and used as a basis for
numerical computation. However the validity of system (5) as an optimality
condition for bilevel program requires very strong assumptions such as the
joint convexity of the function $f$ and $g$, as well as others. In this paper
by using Moreau envelope reformulation, we are able to obtain sufficient
conditions under which system (5) is an optimality condition.

## References

  * [1] K. Bai and J.J. Ye, Directional necessary optimality conditions for bilevel programs, Math. Oper. Res., 47(2022), pp. 1169-1191.
  * [2] K. Bai and J.J. Ye, Directional subdifferential of the value function, Commun. Optim. Theory, 35(2023), pp. 1-36.
  * [3] K. Bai and J.J. Ye, Directional derivative of the value function for parametric set-constrained optimization problems, preprint, arXiv:2311.03604.
  * [4] K. Bai, J.J. Ye and J. Zhang, Directional quasi-/pseudo-normality as sufficient conditions for metric subregularity, SIAM J. Optim., 29 (2019), pp. 2625-2649.
  * [5] M. Benko, On inner calmness*, generalized calculus, and derivatives of the normal cone mapping, J. Nonsmooth Anal. Optim., 2(2021), pp. 1-27.
  * [6] M. Benko, M. Červinka and T. Hoheisel, Sufficient conditions for metric subregularity of constraint systems with applications to disjunctive and ortho-disjunctive programs, Set-Valued Var. Anal., 30 (2022), pp. 143–177.
  * [7] M. Benko, H. Gfrerer and J.V. Outrata, Calculus for directional limiting normal cones and subdifferentials, Set-Valued Var. Anal., 27 (2019), pp. 713–745.
  * [8] J.F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer, New York, 2000.
  * [9] F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley-Interscience, New York, 1983.
  * [10] S. Dempe, Foundations of Bilevel Programming, Kluwer Academic, Dordrecht, 2002.
  * [11] S. Dempe and J. Dutta, Is bilevel programming a special case of mathematical program with equlibrium constraints? Math. Program., 131 (2012), pp. 37-48.
  * [12] S. Dempe and A.B. Zemkoho, On the Karush-Kuhn-Tucker reformulation of the bilevel optimization problem, Nonlinear Anal., 75 (2012), pp. 1202 - 1218.
  * [13] A.L. Dontchev, R.T. Rockafellar, Implicit Functions and Solution Mappings, Springer, New York, 2009.
  * [14] A. Fischer, A.B. Zemkoho and S. Zhou, Semismooth Newton-type method for bilevel optimization: global convergence and extensive numerical experiments, Optim. Methods and Softw., 37(2022), pp. 1770-1804.
  * [15] L.L. Gao, J.J. Ye, H. Yin, S. Zeng and J. Zhang, Moreau envelope based difference-of-weakly-convex reformulation and algorithm for bilevel programs, preprint, 2023, ArXiv:2306.16761.
  * [16] J. Gauvin and F. Dubeau, Differential properties of the marginal function in mathematical programming. Math. Program. Stud., 19 (1982), pp. 101-119.
  * [17] H. Gfrerer, On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs. Set-Valued Var. Anal., 21 (2013), pp. 151-176.
  * [18] H. Gfrerer, Optimality conditions for disjunctive programs based on generalized differentiation with application to mathematical programs with equilibrium constraints, SIAM J. Optim., 24 (2014), pp. 898-931.
  * [19] H. Gfrerer and B. Mordukhovich, Robinson stability of parametric constraint systems via variational analysis, SIAM J. Optim. 27 (2017), pp. 438–465.
  * [20] H. Gfrerer and J.J. Ye, New constraint qualifications for mathematical programs with equilibrium constraints via variational analysis, SIAM J. Optim., 27 (2017), pp. 842-865.
  * [21] H. Gfrerer and J.J. Ye, New sharp necessary optimality conditions for mathematical programs with equilibrium constraints, Set-Valued Var. Anal., 28 (2020), pp. 395-426.
  * [22] I. Ginchev and B.S. Mordukhovich, On directionally dependent subdifferentials, C.R. Bulg. Acad. Sci., 64 (2011), pp. 497-508.
  * [23] L. Guo, G-H. Lin, J.J. Ye, and J. Zhang, Sensitivity analysis of the value function for parametric mathematical programs with equlibrium constraints, SIAM J. Optim. 24 (2014), pp. 1206-1237.
  * [24] L. O. Jolaoso, P. Mehlitz and A.B. Zemkoho, A fresh look at nonsmooth Levenberg–Marquardt methods with applications to bilevel optimization, preprint, ArXiv: 2305.19870.
  * [25] Y.C. Liang and J.J. Ye, Optimality conditions and exact penalty for mathematical programs with switching constraints, J. Optim. Theory Appl., 190 (2021), pp. 1-31.
  * [26] P. Long, B. Wang and X. Yang, Calculus of directional subdifferentials and coderivatives in Banach spaces, Positivity, 21 (2017), pp. 223-254.
  * [27] Z.Q. Luo, J-S. Pang and D. Ralph, Mathematical Programs with Equlibrium Constriants, Cambridge University Press, 1996.
  * [28] L. Minchenko and S. Stakhovski, Parametric nonlinear programming problems under the relaxed constant rank condition, SIAM J. Optim. 21 (2011), pp. 314-332.
  * [29] B.S. Mordukhovich,Variational Analysis and Generalized Differentiation I. Basic Theory. Ser. Comprehensive Stud. Math. 330, Springer, Berlin, 2006.
  * [30] B.S. Mordukhovich,Variational Analysis and Applications. Springer Monographs in Mathematics, Berlin, 2018.
  * [31] J.W. Nie and J.J. Ye, Bilevel polynomial programs and semidefinite relaxation methods, SIAM J. Optim., 27(2017), pp. 1728-1757.
  * [32] J.W. Nie, J.J. Ye and S.H. Zhong, A Lagrange multiplier expression method for bilevel polynomial optimization, SIAM J. Optim. , 31(2021), pp. 2368-2395.
  * [33] J.V. Outrata, On the numerical solution of a class of Stackelberg problems, Z. Oper. Res. 34 (1990), pp. 255-277.
  * [34] J.V. Outrata, M. Kočvara and J. Zowe, Nonsmooth Approach to Optimization Problems with Equlibrium Constraints: Theory, Applications and Numerical Results, Kluwer, Dordrecht, The Netherlands, 1998.
  * [35] R.T. Rockafellar, Convex Anlysis, Princeton University Press, Princeton, 1970.
  * [36] R.T. Rockafellar and R. J-B. Wets, Variational Analysis, Springer, Berlin, 1998.
  * [37] A. Tin and A.B. Zemkoho, Levenberg-Marquardt method and partial exact penalty parameter selection in bilevel optimization, Optim. Eng., 24 (2022), pp. 1343-1385.
  * [38] M. Xu and J.J. Ye, Relaxed constant positive linear dependence constraint qualification and its application to bilevel programs, J. Global Optim., 78 (2020), pp. 181-205.
  * [39] J.J. Ye, Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints, SIAM J. Optim.,10 (2000), pp. 943-962.
  * [40] J.J. Ye, Nondifferentiable multiplier rules for optimization and bilevel optimization problems, SIAM J. Optim.,15 (2004), pp. 252-274.
  * [41] J.J. Ye, Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints, J. Math. Anal. Appl., 307(2005), pp. 350-369.
  * [42] J.J. Ye, Constraint qualifications and KKT conditions for bilevel programming problems, Math. Oper. Res., 31 (2006), pp. 811-824.
  * [43] J.J. Ye, Constraint qualifications and optimality conditions in bilevel optimization, Bilevel Optimization: Advances and Next Challenges, ch. 8, Springer Optimization and its Applications, vol. 161, 2020.
  * [44] J.J. Ye and X.Y. Ye, Necessary optimality conditions for optimization problems with variational inequality constraints, Math. Oper. Res., 22 (1997), pp. 977-997.
  * [45] J.J. Ye, X.M. Yuan, S.Z. Zeng and J. Zhang, Difference of convex algorithms for bilevel programs with applications in hyperparameter selection, Math. Program., 198 (2023), pp. 1583-1616.
  * [46] J.J. Ye and D.L. Zhu, Optimality conditions for bilevel programming problems, Optimization, 33 (1995), pp. 9-27.