2021-02-24 2021-08-05 2 7215 2021 10.46298/jnsao-2021-7215

###### Acknowledgements.

The research of the first author was supported by the Austrian Science Fund
(FWF) under grants P29190-N32 and P32832-N. Moreover, the first author would
like to thank the Institute of Computational Mathematics, Johannes Kepler
University Linz, for access to the infrastructure of the institute.

# On implicit variables in optimization theory

Matúš Benko  Applied Mathematics and Optimization. University of Vienna,
Austria. . ORCID: 0000-0003-3307-7939<EMAIL_ADDRESS>Patrick
Mehlitz  Institute of Mathematics, Chair of Optimal Control. Brandenburgische
Technische Universität Cottbus–Senftenberg, Germany. . ORCID:
0000-0002-9355-850X<EMAIL_ADDRESS>
###### Abstract

Implicit variables of a mathematical program are variables which do not need
to be optimized but are used to model feasibility conditions. They frequently
appear in several different problem classes of optimization theory comprising
bilevel programming, evaluated multiobjective optimization, or nonlinear
optimization problems with slack variables. In order to deal with implicit
variables, they are often interpreted as explicit ones. Here, we first point
out that this is a light-headed approach which induces artificial locally
optimal solutions. Afterwards, we derive various Mordukhovich-stationarity-
type necessary optimality conditions which correspond to treating the implicit
variables as explicit ones on the one hand, or using them only implicitly to
model the constraints on the other. A detailed comparison of the obtained
stationarity conditions as well as the associated underlying constraint
qualifications will be provided. Overall, we proceed in a fairly general
setting relying on modern tools of variational analysis. Finally, we apply our
findings to different well-known problem classes of mathematical optimization
in order to visualize the obtained theory.
_Keywords:_ Implicit variables, Local minimizers, Metric subregularity,
M-stationarity, Variational analysis
_MSC (2010):_ 49J53, 90C30, 90C33

##  1 Introduction

In this paper, we consider the mathematical program

(P) $\begin{split}f(z)&\,\to\,\min\limits_{z}\\\ 0&\,\in\,H(z)\\\
z&\,\in\,M\end{split}$

where $f\colon\mathbb{R}^{n}\to\mathbb{R}$ is a given locally Lipschitz
continuous objective function and the set-valued mapping
$H\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{s}$ attains the form

$H(z):=\bigcup\limits_{\lambda\in F(z)}G(z,\lambda)$

for set-valued mappings $F\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$
and $G\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{s}$
which possess a closed graph, respectively. Furthermore,
$M\subset\mathbb{R}^{n}$ is a nonempty and closed set of simple structure,
e.g., a typical constraint set defined via standard inequality and equality
constraints satisfying a suitable constraint qualification. The feasible set
of (P) will be denoted by $Z\subset\mathbb{R}^{n}$. We emphasize that the
objective in (P) is only minimized w.r.t. $z$ and _not_ w.r.t. $\lambda$
although the latter variable is used implicitly in order to model $Z$. That is
why we call $\lambda$ an _implicit_ variable. Let us note that the rather
general model (P) covers several problem classes from optimization theory,
which are modeled with the aid of implicit variables, e.g., bilevel
programming problems, evaluated multiobjective programs, or programs with
slack variables, see Section 2 as well. In these examples, the implicit
variables are given by means of the lower level Lagrange multipliers,
scalarization parameters, or the introduced slack variables, respectively.

The main difficulty in (P) is the appearing union of image sets associated
with the given set-valued mappings $F$ and $G$. An easy approach which can be
used to handle this issue is to interpret $\lambda$ as a meaningful variable.
This leads to the consideration of

(Q) $\begin{split}f(z)&\,\to\,\min\limits_{z,\lambda}\\\
\lambda&\,\in\,F(z)\\\ 0&\,\in\,G(z,\lambda)\\\ z&\,\in\,M\end{split}$

where $\lambda$ now takes the role of an _explicit_ variable. We denote the
feasible set of this program by
$\tilde{Z}\subset\mathbb{R}^{n}\times\mathbb{R}^{m}$. As we will see in
Section 4.1, there is a one-to-one correspondence between the global
minimizers of (P) and (Q). However, the relationship between local minimizers
is far more delicate. Particularly, there may exist local minimizers of (Q)
which do not correspond to local minimizers of (P). Similar issues are pointed
out in the context of bilevel programming, see [2, 20, 22, 23, 43], w.r.t. the
use of slack variables in logical programming, see [44, 46], or cardinality-
constrained optimization, see [17], and will be generalized in this paper.

Let us briefly mention that the concept of implicit variables can be extended
to related areas of optimization theory like the numerical solution of
generalized equations resulting from optimality conditions of convex
optimization programs. Here, it is also common to introduce intermediate or
slack variables in order to state the convex chain rule for compositions, see
e.g. [15, Section 4], or to decompose the inclusion to make it more tractable,
see [35, Section 5]. It sometimes may be beneficial, however, to formulate the
assumptions ensuring convergence in the implicit-variable-free setting.

Observing that the computation of local minimizers of (Q) does not generally
yield local minimizers of (P) while noting that (Q) is likely to be a
nonconvex program due to the underlying applications we have in mind, a direct
treatment of (P) seems to be reasonable. With the aid of modern variational
analysis, in particular limiting coderivatives of set-valued mappings, see
[48, 53], we will infer necessary optimality conditions of Mordukhovich-
stationarity-type (subsequently, we will use the term M-stationarity for
brevity) for (P) under mild constraint qualifications. More precisely, we
first derive optimality conditions comprising the implicitly known
coderivative of the mapping $H$ under metric subregularity of $H$. Afterwards,
we study assumptions which allow us to state these optimality conditions in
terms of the coderivatives associated with $F$ and $G$. Clearly, this makes
the utilization of a coderivative _chain rule_ necessary, so we discuss weak
conditions ensuring its applicability. Therefore, we make use of the recent
results from [6, 9] which are mainly based on the presence of _metric
subregularity_ for so-called “feasibility” mappings and _inner
semicompactness_ for so-called “intermediate” mappings. Interestingly, these
assumptions are mainly inherent for the example problems from Section 2 which
underlines the power of this approach. On the other hand, using problem (Q) as
the starting point enables us to avoid the (coderivative of) the mapping $H$.
A similar role is then played by an auxiliary mapping, which depends on both,
$z$ and $\lambda$. As it will turn out, the procedures sketched above lead to
three stationarity systems and diverse constraint qualifications which differ
from each other w.r.t. their _degree of explicitness_. We will provide a
detailed comparison of all these stationarity conditions and constraint
qualifications, and we will comment on their respective relation to the
problem (Q). In [1], the authors discuss related issues by means of an
equilibrium-constrained mathematical problem with lower level inequality
constraints. It turns out that there is a significant difference between the
M-stationarity conditions for problem (P), which are formulated without taking
into account the special structure of $H$ and, hence, without the variable
$\lambda$, and the M-stationarity conditions of (Q). Moreover, the difference
between the corresponding constraint qualifications, i.e., the conditions that
guarantee the validity of the two types of M-stationarity at local minimizers,
is even more striking. Here, we generalize and deepen the approach from [1].
Let us briefly note that the theory of this paper can be extended directly to
the situation where $\mathbb{R}^{n}$, $\mathbb{R}^{m}$, and $\mathbb{R}^{s}$
are replaced by arbitrary Euclidean spaces. For simplicity, however, we focus
on the most elementary setting.

The remaining parts of this paper are organized as follows: In Section 2, we
present three prototypical example classes of optimization problems where
implicit variables are used to model the feasible set, namely bilevel
optimization problems, evaluated multiobjective optimization problems, and
mathematical programs with cardinality constraints. We provide an overview of
the notation used in this manuscript before recalling the definitions and some
background information about the fundamental tools of variational analysis we
are going to exploit here in Section 3. Furthermore, we motivate a rather
abstract notion of M-stationarity for mathematical problems with generalized
equation constraints and provide some calculus rules for the coderivative of
compositions and products of set-valued mappings. Afterwards, Section 4 is
dedicated to the abstract analysis of the program (P) via (Q). First, we study
the relationship between the solutions of (P) and (Q) in Section 4.1. Second,
we derive three potentially distinct notions of M-stationarity for (P) as well
as associated constraint qualifications in Section 4.2. Furthermore, we
clarify how to obtain explicit M-stationarity conditions in terms of initial
problem data from the abstract M-stationarity conditions of (P). As we will
demonstrate in Section 4.3, the necessary assumptions are inherently satisfied
in many practically relevant settings. Finally, we briefly comment on the
sufficiency of the introduced M-stationarity notions in the presence of
convexity in Section 4.4. In Section 5, we apply some of our findings to the
aforementioned example problems. As it will turn out, we recover or even
enhance available results from the literature with our approach. Finally, we
present some concluding remarks in Section 6.

##  2 Motivating examples

In this section, we present three prototypical classes of optimization
problems whose respective feasible sets can be modeled with the aid of
implicit variables.

###  2.1 Bilevel programming

Quite often, hierarchical decision making appears naturally in real world
problems raising in economics, logistics, natural sciences, or engineering. In
case where two decision makers are involved, so-called bilevel optimization
problems can be used to model and study the underlying applications
theoretically and numerically, see [4, 19, 21, 48, 54]. For given parameters
$x\in\mathbb{R}^{n_{1}}$, let us consider the parametric optimization problem

(LL) $\begin{split}j(x,y)&\,\to\,\min\limits_{y}\\\ g(y)&\,\in\,C\end{split}$

where $j\colon\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}\to\mathbb{R}$ is
twice continuously differentiable and convex w.r.t. $y$ for each
$x\in\mathbb{R}^{n_{1}}$ while $g\colon\mathbb{R}^{n_{2}}\to\mathbb{R}^{m}$ is
twice continuously differentiable and convex w.r.t. the closed, convex cone
$C\subset\mathbb{R}^{m}$. Let us set
$\Gamma:=\\{y\in\mathbb{R}^{n_{2}}\,|\,g(y)\in C\\}$. One generally refers to
(LL) as the _lower level_ or _follower’s problem_. It is well known that due
to the convexity of $j(x,\cdot)$ and $\Gamma$, the set of optimal solutions
associated with (LL) is equivalently characterized by

$-\nabla_{y}j(x,y)\in\widehat{\mathcal{N}}_{\Gamma}(y).$

Under a suitable constraint qualification, we can characterize the set of
optimal solutions associated with (LL) equivalently by the generalized
equation

$-\nabla_{y}j(x,y)\in\nabla g(y)^{\top}\widehat{\mathcal{N}}_{C}(g(y)).$

Above, we exploited the notion of the regular normal cone which coincides with
the normal cone of convex analysis due to convexity of $\Gamma$ and $C$, see
Section 3.

The superordinate so-called _upper level_ or _leader’s problem_ , given by

$\begin{split}f(x,y)&\,\to\,\min\limits_{x,y}\\\ x&\,\in\,S\\\
y&\,\in\,\Psi(x),\end{split}$

where $S\subset\mathbb{R}^{n_{1}}$ is a closed set and
$\Psi\colon\mathbb{R}^{n_{1}}\rightrightarrows\mathbb{R}^{n_{2}}$ is the
solution mapping associated with (LL), is equivalent to

(BPP) $\begin{split}f(x,y)&\,\to\min\limits_{x,y}\\\ x&\,\in\,S\\\
0&\,\in\,\bigcup_{\lambda\in\widehat{\mathcal{N}}_{C}(g(y))}\left\\{\nabla_{y}j(x,y)+\nabla
g(y)^{\top}\lambda\right\\}\end{split}$

whenever the aforementioned assumptions are valid. The latter is a program of
type (P) in the sense

(2.1) $F(z):=\widehat{\mathcal{N}}_{C}(g(y)),\quad
G(z,\lambda):=\nabla_{y}j(x,y)+\nabla g(y)^{\top}\lambda,\quad
M:=S\times\mathbb{R}^{n_{2}}$

where we used $z:=(x,y)$ and $n:=n_{1}+n_{2}$. Particularly, the implicit
variable $\lambda$ is the Lagrange multiplier associated with the constraints
in (LL). It is well known that interpreting $\lambda$ as a variable in (BPP)
may cause difficulties w.r.t. local minimizers, see e.g. [2, 20, 22, 43]. The
authors in [1], where the particular setting $C:=\mathbb{R}^{m}_{-}$ is
discussed, focused on a qualitative comparison of the reformulation

$\begin{split}f(x,y)&\,\to\min\limits_{x,y}\\\ x&\,\in\,S\\\
-\nabla_{y}j(x,y)&\,\in\,\widehat{\mathcal{N}}_{\Gamma}(y),\end{split}$

which is fully equivalent to the original bilevel programming problem, and the
problem (Q) associated with (BPP) regarding constraint qualifications and
M-stationarity-type optimality conditions. They came up with the observation
that the respective stationarity systems as well as constraint qualifications
differ significantly. The analysis in this paper will put their results into a
more general context.

###  2.2 Evaluating weakly efficient points in multicriteria optimization

For a twice continuously differentiable componentwise convex function
$j\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ with $m\geq 2$ components and a
nonempty, closed, convex set $\Gamma\subset\mathbb{R}^{n}$, we consider the
following multicriteria optimization problem which is a standard model from
vector optimization, see [26, 41]:

(MOP) $\begin{split}j(z)&\,\rightarrow\,\text{``}\min\text{''}\\\
z&\,\in\,\Gamma.\end{split}$

The quotation marks emphasize that classical minimization is not possible
since the componentwise natural ordering in $\mathbb{R}^{m}$ only provides a
partial order which is not total. In order to overcome this problem, several
different notions of so-called _efficiency_ have been derived in order to
characterize reasonable feasible points of (MOP). In this context, a point
$\bar{z}\in\Gamma$ is called _weakly efficient_ for (MOP) if the condition

$\bigl{(}j(\bar{z})-\mathbb{R}^{m}_{++}\bigr{)}\cap j(\Gamma)=\varnothing$

holds where we used $\mathbb{R}^{m}_{++}:=\\{y\in\mathbb{R}^{m}\,|\,\forall
i\in\\{1,\ldots,m\\}\colon\,y_{i}>0\\}$. Let
$\Gamma_{\textup{we}}\subset\mathbb{R}^{n}$ be the set of weakly efficient
points associated with (MOP). Using a classical linear scalarization approach,
see [26], one obtains the characterization

$\bar{z}\in\Gamma_{\textup{we}}\quad\Longleftrightarrow\quad\exists\lambda\in\Delta\,\forall
z\in\Gamma\colon\,\lambda^{\top}j(\bar{z})\leq\lambda^{\top}j(z)$

of weak efficiency since the problem data in (MOP) is convex. Above,
$\Delta\subset\mathbb{R}^{m}$ given by

$\Delta:=\bigl{\\{}\lambda\in\mathbb{R}^{m}\,|\,\lambda\geq
0,\,\sum\nolimits_{i=1}^{m}\lambda_{i}=1\bigr{\\}}$

denotes the standard simplex. In practice, the set $\Gamma_{\textup{we}}$ will
be quite large in general which is why it is desirable to shrink it for
applicability purposes using another decision criterion given in form of a
scalar function, see e.g. [10, 12, 13, 39]. Here, we investigate the
_evaluated multiobjective optimization problem_

$\begin{split}f(z)&\,\to\,\min\\\ z&\,\in\,\Gamma_{\textup{we}}.\end{split}$

Invoking the above arguments, this is equivalent to

(EMOP) $\begin{split}f(z)&\,\to\,\min\\\
0&\,\in\,\bigcup\limits_{\lambda\in\Delta}\Psi(\lambda)-z\end{split}$

where $\Psi\colon\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$ is the set-
valued mapping defined by

$\Psi(\lambda):=\begin{cases}\operatorname*{\operatorname{argmin}}\limits_{z}\\{\lambda^{\top}j(z)\,|\,z\in\Gamma\\}&\lambda\in\Delta,\\\
\varnothing&\lambda\notin\Delta.\end{cases}$

Obviously, this is a program of type (P) where the scalarization parameter
takes the role of the implicit variable. Particularly, the data from (P) takes
the form

(2.2) $F(z):=\Delta,\qquad G(z,\lambda):=\Psi(\lambda)-z,\qquad
M:=\mathbb{R}^{n}.$

It has been reported in [23] that interpreting scalarization parameters as
variables is generally delicate in multiobjective bilevel programming, and
this observation clearly extends to (EMOP) as well.

###  2.3 Cardinality-constrained programming

For some vector $z\in\mathbb{R}^{n}$, let $\left\|z\right\|_{0}$ denote the
number of non-zero entries of $z$. In order to guarantee _sparsity_ of
solutions to optimization problems, one may consider the so-called
_cardinality-constrained mathematical program_

(CCMP) $\begin{split}f(z)&\,\to\,\min\\\ z&\,\in\,M\\\
\left\|z\right\|_{0}&\,\leq\,\kappa\end{split}$

where $\kappa\in\mathbb{N}$ satisfies $1\leq\kappa\leq n-1$, see e.g. [11, 16,
17, 18, 45, 50, 51] for an overview of existing reformulations, optimality
conditions, solution algorithms, and further references.

Let us rewrite the cardinality constraint $\left\|z\right\|_{0}\leq\kappa$ as
a constraint of type $q(z)\in D$ where
$q\colon\mathbb{R}^{n}\to\mathbb{R}^{\ell}$ is continuously differentiable and
$D\subset\mathbb{R}^{\ell}$ is the union of finitely many convex polyhedral
sets, allowing us to interpret (CCMP) as a so-called _disjunctive_
optimization problem, see e.g. [7, 28, 45]. Therefore, we introduce
$\mathcal{J}_{\kappa}:=\\{\alpha\in\\{0,1\\}^{n}\,|\,\sum_{i=1}^{n}\alpha_{i}=\kappa\\}$.
Furthermore, for each $\alpha\in\\{0,1\\}^{n}$, we set

$\mathbb{R}^{n}_{\alpha}:=\operatorname{span}\\{\mathtt{e}_{i}\,|\,i=1,\ldots,n,\,\alpha_{i}=1\\}$

where $\mathtt{e}_{i}\in\mathbb{R}^{n}$ denotes the $i$-th unit vector in
$\mathbb{R}^{n}$. Finally, we set
$D_{\kappa}:=\bigcup_{\alpha\in\mathcal{J}_{\kappa}}\mathbb{R}^{n}_{\alpha}$.
Then we easily see

(2.3) $\forall
z\in\mathbb{R}^{n}\colon\quad\left\|z\right\|_{0}\leq\kappa\,\Longleftrightarrow\,z\in
D_{\kappa}.$

The variational geometry of $D_{\kappa}$ has been explored in [50, 51].
Particularly, exploiting the limiting and regular normal cone to $D_{\kappa}$,
reasonable notions of M- and strong stationarity are available for (CCMP).

It has been observed in [17, Theorem 3.2] that we have

$\forall
z\in\mathbb{R}^{n}\colon\quad\left\|z\right\|_{0}\leq\kappa\,\Longleftrightarrow\,\exists\lambda\in\mathbb{R}^{n}\colon\,\mathtt{e}^{\top}\lambda\geq
n-\kappa,\,(z_{i},\lambda_{i})\in\mathcal{C}\;\forall i\in\\{1,\ldots,n\\}$

where we used

$\mathcal{C}:=\\{(a,b)\in\mathbb{R}^{2}\,|\,ab=0,\,b\in[0,1]\\},$

and that gave rise to the reformulation of (CCMP) as

(2.4) $\displaystyle f(z)$ $\displaystyle\,\to\,\min\limits_{z,\lambda}$
$\displaystyle z$ $\displaystyle\,\in\,M$
$\displaystyle\mathtt{e}^{\top}\lambda$ $\displaystyle\,\geq\,n-\kappa$
$\displaystyle(z_{i},\lambda_{i})$ $\displaystyle\,\in\,\mathcal{C}$
$\displaystyle i=1,\ldots,n.$

Above, $\mathtt{e}\in\mathbb{R}^{n}$ denotes the all-ones vector. Clearly, the
variable $\lambda$ plays the role of an explicit variable in (2.4) although it
is not relevant for the purpose of minimization. In order to state (2.4) in
the form (P), one may choose

(2.5)
$F(z)\equiv\bigl{\\{}\lambda\in\mathbb{R}^{n}\,\big{|}\,\mathtt{e}^{\top}\lambda\geq
n-\kappa\bigr{\\}},\qquad
G(z,\lambda):=\prod_{i=1}^{n}(\mathcal{C}-(z_{i},\lambda_{i})),$

i.e., $s=2n$ holds in this particular case.

It has been reported in [17] that (CCMP) and (2.4) are equivalent w.r.t.
global minimizers, that the local minimizers of (CCMP) can be found among the
local minimizers of (2.4), and that for a local minimizer
$(\bar{z},\bar{\lambda})\in\mathbb{R}^{n}\times\mathbb{R}^{n}$ of (2.4), which
satisfies $\left\|\bar{z}\right\|_{0}=\kappa$, $\bar{z}$ is a local minimizer
of (CCMP). The situation where $\left\|\bar{z}\right\|_{0}<\kappa$ holds,
however, has been shown to be crucial since, in this case, $\bar{z}$ does not
need to be locally optimal for (CCMP). First- and second-order optimality
conditions for (CCMP) via its surrogate (2.4) have been derived in [16, 17,
18] while the authors in [45, 50, 51] exploited (2.3) in order to infer
optimality conditions for (CCMP) without relying on implicit variables. To the
best of our knowledge, a detailed comparison of both approaches does not exist
in the literature. Some regarding remarks, however, can be found in the papers
[16, 45]. We also refer the interested reader to [5] where yet another
approach to cardinality-constrained optimization is discussed which also
avoids the appearance of implicit variables.

##  3 Notation and preliminaries

###  3.1 Notation

Throughout the manuscript, we make use of the standard concepts of variational
analysis, see [48, 53].

#### Basic notation

In this manuscript, we equip $\mathbb{R}^{n}$ with the common Euclidean inner
product and the common Euclidean norm $\left\|\cdot\right\|$. In order to
extend the notion of norms to product spaces, we use the sum of the underlying
Euclidean norms to induce a norm in the product space. Due to notational
purposes, for arbitrary $z\in\mathbb{R}^{n}$ and $w\in\mathbb{R}^{m}$, we use
both notations

$\begin{pmatrix}z\\\ w\end{pmatrix}\qquad\text{and}\qquad(z,w)$

in order to represent elements of $\mathbb{R}^{n}\times\mathbb{R}^{m}$. We use
$\mathbb{B}$ in order to denote the closed unit ball around $0$. For a set
$A\subset\mathbb{R}^{n}$ and $z\in\mathbb{R}^{n}$, we exploit
$z+A=A+z:=\\{z+a\,|\,a\in A\\}$ for brevity. Furthermore, we use

$A^{\circ}:=\bigl{\\{}\xi\in\mathbb{R}^{n}\,\bigl{|}\,\forall a\in
A\colon\,\xi^{\top}a\leq 0\\},\qquad
A^{\perp}:=\bigl{\\{}\xi\in\mathbb{R}^{n}\,\bigl{|}\,\forall a\in
A\colon\,\xi^{\top}a=0\\}$

in order to represent the polar cone and the annihilator of $A$. We make use
of $z^{\perp}:=\\{z\\}^{\perp}$. We set

$\operatorname{dist}(z,A):=\inf\\{\left\|a-z\right\|\,|\,a\in A\\}$

in order to denote the distance of $z$ to $A$. Throughout the manuscript, we
exploit $\mathbb{R}_{+}:=\\{s\in\mathbb{R}\,|\,s\geq 0\\}$ and
$\mathbb{R}_{-}:=\\{s\in\mathbb{R}\,|\,s\leq 0\\}$.

#### Set-valued mappings

For a set-valued mapping
$\Upsilon\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$, the sets
$\operatorname{gph}\Upsilon:=\\{(z,w)\in\mathbb{R}^{n}\times\mathbb{R}^{m}\,|\,w\in\Upsilon(z)\\}$,
$\operatorname{dom}\Upsilon:=\\{z\in\mathbb{R}^{n}\,|\,\Upsilon(z)\neq\varnothing\\}$,
$\operatorname{rge}\Upsilon:=\\{w\in\mathbb{R}^{m}\,|\,\exists
z\in\mathbb{R}^{n}\colon\,w\in\Upsilon(z)\\}$, and
$\ker\Upsilon:=\\{z\in\mathbb{R}^{n}\,|\,0\in\Upsilon(z)\\}$ are called graph,
domain, range, and kernel of $\Upsilon$, respectively. The set-valued mapping
$\Upsilon^{-1}\colon\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$, given by
$\Upsilon^{-1}(w):=\\{z\in\mathbb{R}^{n}\,|\,w\in\Upsilon(z)\\}$ for all
$w\in\mathbb{R}^{m}$, is referred to as the inverse of $\Upsilon$.

The mapping $\Upsilon$ is called locally bounded at
$\bar{z}\in\operatorname{dom}\Upsilon$ whenever we find a neighborhood
$U\subset\mathbb{R}^{n}$ of $\bar{z}$ and a bounded set
$B\subset\mathbb{R}^{m}$ such that $\Upsilon(z)\subset B$ holds for all $z\in
U$. Furthermore, $\Upsilon$ is said to be inner semicompact at $\bar{z}$
w.r.t. $\Omega\subset\mathbb{R}^{n}$ if for each sequence
$\\{z_{k}\\}_{k\in\mathbb{N}}\subset\Omega$ such that $z_{k}\to\bar{z}$, there
is a convergent sequence $\\{w_{l}\\}_{l\in\mathbb{N}}\subset\mathbb{R}^{m}$
and a subsequence $\\{z_{k_{l}}\\}_{l\in\mathbb{N}}$ such that
$w_{l}\in\Upsilon(z_{k_{l}})$ holds for all $l\in\mathbb{N}$. Clearly,
whenever $\Upsilon$ is locally bounded at $\bar{z}$, it is inner semicompact
w.r.t. $\operatorname{dom}\Upsilon$ at this point. Similarly, $\Upsilon$ is
called inner semicontinuous at
$(\bar{z},\bar{w})\in\operatorname{gph}\Upsilon$ w.r.t. $\Omega$ if for each
sequence $\\{z_{k}\\}_{k\in\mathbb{N}}\subset\Omega$ satisfying
$z_{k}\to\bar{z}$, there exists a sequence
$\\{w_{k}\\}_{k\in\mathbb{N}}\subset\mathbb{R}^{m}$ such that
$w_{k}\to\bar{w}$ and $w_{k}\in\Upsilon(z_{k})$ for all sufficiently large
$k\in\mathbb{N}$.

We call $\Upsilon$ convex whenever the property

$\forall
z_{1},z_{2}\in\mathbb{R}^{n},\,\forall\alpha\in[0,1]\colon\quad\alpha\Upsilon(z_{1})+(1-\alpha)\Upsilon(z_{2})\subset\Upsilon(\alpha
z_{1}+(1-\alpha)z_{2})$

holds, i.e., whenever $\operatorname{gph}\Upsilon$ is convex. This property
particularly holds for set-valued mappings of the form $\Upsilon(z):=g(z)-C$,
$z\in\mathbb{R}^{n}$, where $C\subset\mathbb{R}^{m}$ is a closed, convex cone
and the single-valued mapping $g\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ is
convex w.r.t. $C$, i.e.,

$\forall z_{1},z_{2}\in\mathbb{R}^{n},\,\forall\alpha\in[0,1]\colon\quad
g(\alpha z_{1}+(1-\alpha)z_{2})-\alpha g(z_{1})-(1-\alpha)g(z_{2})\in C.$

Let us recall some essential Lipschitzian properties of set-valued mappings.
Therefore, we fix a point $(\bar{z},\bar{y})\in\operatorname{gph}\Upsilon$.
Recall that $\Upsilon$ possesses the _Aubin property_ at $(\bar{z},\bar{w})$
whenever there are a constant $\kappa>0$ and neighborhoods $U$ of $\bar{z}$
and $V$ of $\bar{w}$ such that

$\forall z_{1},z_{2}\in U\,\forall w\in\Upsilon(z_{1})\cap
V\colon\quad\operatorname{dist}(w,\Upsilon(z_{2}))\leq\kappa\left\|z_{1}-z_{2}\right\|.$

Furthermore, $\Upsilon$ is called _metrically regular_ at $(\bar{z},\bar{w})$
whenever there are $\kappa>0$ as well as neighborhoods $U$ and $V$ of
$\bar{z}$ and $\bar{w}$, respectively, such that

$\forall z\in U,\,\forall w\in
V\colon\quad\operatorname{dist}(z,\Upsilon^{-1}(w))\leq\kappa\operatorname{dist}(w,\Upsilon(z)).$

It is well known that $\Upsilon$ is metrically regular at $(\bar{z},\bar{w})$
if and only if $\Upsilon^{-1}$ possesses the Aubin property at
$(\bar{w},\bar{z})$. Finally, recall that $\Upsilon$ is referred to as
_metrically subregular_ at $(\bar{z},\bar{w})$ whenever there exist a constant
$\kappa>0$ and a neighborhood $U$ of $\bar{z}$ satisfying

$\forall z\in
U\colon\quad\operatorname{dist}(z,\Upsilon^{-1}(\bar{w}))\leq\kappa\operatorname{dist}(\bar{w},\Upsilon(z)).$

The infimum of all such constants $\kappa$ is referred to as the modulus of
metric subregularity. Let us mention that $\Upsilon$ is metrically subregular
at $(\bar{z},\bar{w})$ if and only if the inverse $\Upsilon^{-1}$ is so-called
_calm_ at $(\bar{w},\bar{z})$, see [37, 38] for a definition and further
details. It has turned out that metric subregularity is of essential
importance in order to guarantee applicability of the prominent calculus for
the limiting constructions of generalized differentiation. This is one of the
reasons why sufficient conditions for its presence were studied, see e.g. [3,
7, 27, 30, 40, 60] and the references therein as well as the aforementioned
papers dealing with calmness. We would like to mention that each polyhedral
set-valued mapping, i.e., a set-valued mapping whose graph is the union of
finitely many convex polyhedral sets, is metrically subregular at each point
of its graph. This result dates back to [52].

#### Variational analysis

For a closed set $A\subset\mathbb{R}^{n}$ and some point $\bar{z}\in A$, we
refer to

$\mathcal{T}_{A}(\bar{z}):=\left\\{d\in\mathbb{R}^{n}\,\middle|\,\exists\\{z_{k}\\}_{k\in\mathbb{N}}\subset
A,\,\exists\\{t_{k}\\}_{k\in\mathbb{N}}\subset\mathbb{R}_{+}\colon\,z_{k}\to\bar{z},\,t_{k}\downarrow
0,\,(z_{k}-\bar{z})/t_{k}\to d\right\\}$

as the (Bouligand) tangent cone to $A$ at $\bar{z}$. Based on that, let us
introduce

$\displaystyle\widehat{\mathcal{N}}_{A}(\bar{z})$
$\displaystyle:=\mathcal{T}_{A}(\bar{z})^{\circ},$
$\displaystyle\mathcal{N}_{A}(\bar{z})$
$\displaystyle:=\left\\{\xi\in\mathbb{R}^{n}\,\middle|\,\begin{aligned}
&\exists\\{z_{k}\\}_{k\in\mathbb{N}}\subset
A,\,\exists\\{\xi_{k}\\}_{k\in\mathbb{N}}\subset\mathbb{R}^{n}\colon\\\
&\qquad
z_{k}\to\bar{z},\,\xi_{k}\to\xi,\,\xi_{k}\in\widehat{\mathcal{N}}_{A}(z_{k})\,\forall
k\in\mathbb{N}\end{aligned}\right\\},$

the so-called regular (or Fréchet) and limiting (or Mordukhovich) normal cone
to $A$ at $\bar{z}$, respectively. In case where $A$ is convex, these normal
cones correspond to the normal cone in the sense of convex analysis, i.e.,
$\widehat{\mathcal{N}}_{A}(\bar{z})=\mathcal{N}_{A}(\bar{z})=(A-\bar{z})^{\circ}$.

For a locally Lipschitz continuous function
$\varphi\colon\mathbb{R}^{n}\to\mathbb{R}$, we define its limiting
subdifferential at some point $\bar{z}\in\mathbb{R}^{n}$ by means of

$\partial\varphi(\bar{z}):=\left\\{\xi\in\mathbb{R}^{n}\,\middle|\,(\xi,-1)\in\mathcal{N}_{\operatorname{epi}\varphi}(\bar{z},\varphi(\bar{z}))\right\\}$

where
$\operatorname{epi}\varphi:=\\{(z,s)\in\mathbb{R}^{n}\times\mathbb{R}\,|\,s\geq\varphi(z)\\}$
denotes the epigraph of $\varphi$. In case where $\varphi$ is convex, the
above arguments yield that $\partial\varphi(\bar{z})$ coincides with the
subdifferential in the sense of convex analysis, i.e.,

$\partial\varphi(\bar{z})=\bigl{\\{}\xi\in\mathbb{R}^{n}\,\big{|}\,\forall
z\in\mathbb{R}^{n}\colon\,\varphi(z)\geq\varphi(\bar{z})+\xi^{\top}(z-\bar{z})\bigr{\\}}$

holds in this case.

For a set-valued mapping
$\Upsilon\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ with closed
graph and some point $(\bar{z},\bar{w})\in\operatorname{gph}\Upsilon$, the
set-valued mapping
$D^{*}\Upsilon(\bar{z},\bar{w})\colon\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$
given by

$\forall\eta\in\mathbb{R}^{m}\colon\quad
D^{*}\Upsilon(\bar{z},\bar{w})(\eta):=\left\\{\xi\in\mathbb{R}^{n}\,\middle|\,(\xi,-\eta)\in\mathcal{N}_{\operatorname{gph}\Upsilon}(\bar{z},\bar{w})\right\\}$

is referred to as the (limiting) coderivative of $\Upsilon$ at
$(\bar{z},\bar{w})$. For a single-valued mapping
$\upsilon\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$, we exploit the notation
$D^{*}\upsilon(\bar{z}):=D^{*}\upsilon(\bar{z},\upsilon(\bar{z}))$. Whenever
$\upsilon$ is continuously differentiable at $\bar{z}$, then
$D^{*}\upsilon(\bar{z})(\eta)=\nabla\upsilon(\bar{z})^{\top}\eta$ holds for
all $\eta\in\mathbb{R}^{m}$ where $\nabla\upsilon(\bar{z})$ denotes the
Jacobian of $\upsilon$ at $\bar{z}$.

Let us recall that $\Upsilon$ possesses the Aubin property at
$(\bar{z},\bar{w})$ if and only if the condition

$D^{*}\Upsilon(\bar{z},\bar{w})(0)=\\{0\\}$

holds. Thus, $\Upsilon$ is metrically regular at $(\bar{z},\bar{w})$ if and
only if we have

$\ker D^{*}\Upsilon(\bar{z},\bar{w})=\\{0\\}.$

Both criteria are referred to as _Mordukhovich criterion_ in the literature,
see [48, Theorem 3.3].

###  3.2 M-stationarity for optimization problem with generalized equation
constraints

The following result can be found in [37, Theorem 4.1] and [33, Proposition
4.1]. It provides a calculus rule for the computation of the limiting normal
cone to the pre-image associated with a set-valued mapping which is metrically
subregular at a certain point of interest.

######  Proposition 3.1.

Let $\Upsilon\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ be a set-
valued mapping having locally closed graph around
$(\bar{z},\bar{w})\in\operatorname{gph}\Upsilon$ and assume that $\Upsilon$ is
metrically subregular at $(\bar{z},\bar{w})$ with modulus $\bar{\kappa}$. Then
the following estimate is valid for each $\kappa>\bar{\kappa}$:

(3.1)
$\mathcal{N}_{\Upsilon^{-1}(\bar{w})}(\bar{z})\subset\left\\{\xi\in\mathbb{R}^{n}\,\middle|\,\exists\eta\in\kappa\left\|\xi\right\|\mathbb{B}\colon\,\xi\in
D^{*}\Upsilon(\bar{z},\bar{w})(\eta)\right\\}.$

This motivates the subsequently stated extension of the definition of
M-stationarity to abstract optimization programs of the form

(G) $\begin{split}\varphi(z)&\,\to\,\min\\\ 0&\,\in\,\Upsilon(z),\end{split}$

where $\varphi\colon\mathbb{R}^{n}\to\mathbb{R}$ is a locally Lipschitz
continuous function and
$\Upsilon\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is a set-valued
mapping with closed graph, observing that $\Upsilon^{-1}(0)$ is the feasible
set of (G). A similar stationarity condition has been studied in the
literature, see [57, Section 3].

######  Definition 3.2.

We say that a feasible point $\bar{z}\in\Upsilon^{-1}(0)$ of the program (G)
is M-stationary provided there exists $\eta\in\mathbb{R}^{m}$ such that

$0\in\partial\varphi(\bar{z})+D^{*}\Upsilon(\bar{z},0)(\eta).$

In case where the constraint mapping $\Upsilon$ is given in the form of a so-
called “feasibility” mapping, i.e., $\Upsilon(z):=\Phi(z)-\Omega$ for all
$z\in\mathbb{R}^{n}$, where, for simplicity,
$\Phi\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ is a continuously differentiable
mapping and $\Omega\subset\mathbb{R}^{m}$ is a closed set, Proposition 3.1
yields the standard pre-image calculus rule

$\mathcal{N}_{\Phi^{-1}(\Omega)}(z)\subset\nabla\Phi(z)^{\top}\mathcal{N}_{\Omega}(\Phi(z))$

for each $z\in\mathbb{R}^{n}$ such that $\Upsilon$ is metrically subregular at
$(z,0)\in\operatorname{gph}\Upsilon$. This also justifies the M-stationarity
terminology in Definition 3.2. Moreover, the additional bound
$\left\|\eta\right\|\leq\kappa\left\|\xi\right\|$ in (3.1) implies that for
every $\xi\in\mathcal{N}_{\Phi^{-1}(\Omega)}(z)$, there exists a multiplier
$\eta\in\mathcal{N}_{\Omega}(\Phi(z))\cap\kappa\left\|\xi\right\|\mathbb{B}$
with $\xi=\nabla\Phi(z)^{\top}\eta$. This observation, however, brings forth
the following important property of the associated multiplier mapping which
has been discussed in [6, Theorem 3.9] recently.

######  Proposition 3.3.

Let $\Phi\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ be continuously differentiable
and let $\Omega\subset\mathbb{R}^{m}$ be closed. We consider
$\Upsilon\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ given by
$\Upsilon(z):=\Phi(z)-\Omega$ for each $z\in\mathbb{R}^{n}$. Let
$(\bar{z},\bar{z}^{*})\in\operatorname{gph}\mathcal{N}_{C}$ for
$C:=\Phi^{-1}(\Omega)$ be fixed and assume that the feasibility mapping
$\Upsilon$ is metrically subregular at $(\bar{z},0)$. Then the multiplier
mapping
$\Lambda\colon\mathbb{R}^{n}\times\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$,
given by

$\forall(z,z^{*})\in\mathbb{R}^{n}\times\mathbb{R}^{n}\colon\quad\Lambda(z,z^{*}):=\bigl{\\{}\eta\in\mathcal{N}_{\Omega}(\Phi(z))\,\big{|}\,\nabla\Phi(z)^{\top}\eta=z^{*}\bigr{\\}},$

is inner semicompact at $(\bar{z},\bar{z}^{*})$ w.r.t.
$\operatorname{gph}\mathcal{N}_{C}$. Moreover,
$\operatorname{gph}\mathcal{N}_{C}=\operatorname{dom}\Lambda$ holds provided
$\Omega$ is convex.

For comparison, it is well known that the stronger assumption of metric
regularity yields local boundedness of the multiplier mapping $\Lambda$, and
this has indeed been often used to guarantee its inner semicompactness, see
Section 5.1 as well. While it may seem that local boundedness is not much
stronger than inner semicompactness, when the underlying assumptions are
compared, the gap is noteworthy. In case of standard nonlinear programs,
metric regularity equals the prominent _Mangasarian–Fromovitz constraint
qualification_ (MFCQ), while in case of the more general class of geometric
constraints as discussed in Proposition 3.3, metric regularity of the
feasibility mapping $\Upsilon$ at $(\bar{z},0)\in\operatorname{gph}\Upsilon$
boils down to

$\nabla\Phi(\bar{z})^{\top}\eta=0,\,\eta\in\mathcal{N}_{\Omega}(\Phi(\bar{z}))\quad\Longrightarrow\quad\eta=0,$

which is called _generalized Mangasarian–Fromovitz constraint qualification_
(GMFCQ) or _no nonzero abnormal multiplier constraint qualification_ (NNAMCQ).
The above propositions often enable us to relax the metric regularity
requirement to the so-called _metric subregularity constraint qualification_
(MSCQ) demanding $\Upsilon$ to be metrically subregular at $(\bar{z},0)$.

###  3.3 Calculus of set-valued mappings

Throughout this section, we assume that all considered set-valued mappings
possess closed graphs.

We first review the chain rule for the computation of coderivatives of
compositions. Therefore, let us consider set-valued mappings
$S_{1}\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ and
$S_{2}\colon\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{s}$ as well as their
composition $S_{2}\circ
S_{1}\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{s}$ given by

$\forall z\in\mathbb{R}^{n}\colon\quad(S_{2}\circ
S_{1})(z):=\bigcup\limits_{y\in S_{1}(z)}S_{2}(y).$

In order to estimate the coderivative of $S_{2}\circ S_{1}$, we introduce the
standard “intermediate” mapping
$\Xi\colon\mathbb{R}^{n}\times\mathbb{R}^{s}\rightrightarrows\mathbb{R}^{m}$
given by

(3.2) $\forall z\in\mathbb{R}^{n},\,\forall
w\in\mathbb{R}^{s}\colon\quad\Xi(z,w):=S_{1}(z)\cap S_{2}^{-1}(w)=\\{y\in
S_{1}(z)\,|\,w\in S_{2}(y)\\},$

together with the “feasibility” mapping
$\Upsilon\colon\mathbb{R}^{n}\times\mathbb{R}^{s}\times\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{m}\times\mathbb{R}^{s}$
in the following form:

$\forall z\in\mathbb{R}^{n},\,\forall w\in\mathbb{R}^{s},\,\forall
y\in\mathbb{R}^{m}\colon\quad\Upsilon(z,w,y):=\begin{pmatrix}S_{1}(z)-y\\\
S_{2}(y)-w\end{pmatrix}.$

The following chain rule is taken from [9, Theorem 5.2].

######  Lemma 3.4.

Fix $(\bar{z},\bar{w})\in\operatorname{gph}(S_{2}\circ S_{1})$. Let $\Xi$ be
inner semicompact w.r.t. $\operatorname{dom}\Xi$ at $(\bar{z},\bar{w})$ and
let $\Upsilon$ be metrically subregular at all points
$((\bar{z},\bar{w},\bar{y}),(0,0))$ such that
$\bar{y}\in\Xi(\bar{z},\bar{w})$. Then we have

$\forall w^{*}\in\mathbb{R}^{s}\colon\quad D^{*}(S_{2}\circ
S_{1})(\bar{z},\bar{w})(w^{*})\subset\bigcup\limits_{\bar{y}\in\Xi(\bar{z},\bar{w})}\bigl{(}D^{*}S_{1}(\bar{z},\bar{y})\circ
D^{*}S_{2}(\bar{y},\bar{w})\bigr{)}(w^{*}).$

In [9, Theorem 5.2], the subregularity assumption is replaced by the
equivalent calmness assumption associated with the inverse mapping of
$\Upsilon$ given by

$\Upsilon^{-1}(a,b)=\\{(z,w,y)\,\mid\,y+a\in S_{1}(z),w+b\in S_{2}(y)\\}.$

Furthermore, note that $\Upsilon$ is slightly different from the typical
feasibility mapping used in the chain rule, see e.g. [53, proof of Theorem
10.37]. However, it is worth to mention that the respective metric
subregularity assumptions, which need to be postulated on these maps in order
to infer the chain rule, are actually equivalent due to [9, Proposition 2.6].

The proof of Lemma 3.4 is based on the essential relations

(3.3) $\operatorname{gph}(S_{2}\circ
S_{1})=\operatorname{dom}\Xi,\qquad\qquad\operatorname{gph}\Xi=\Upsilon^{-1}(0,0).$

Roughly speaking, the inner semicompactness of $\Xi$ provides a connection
between the graph of $S_{2}\circ S_{1}$ and the graph of $\Xi$ while the
metric subregularity of $\Upsilon$ connects the graph of $\Xi$ with the graph
of $\Upsilon$ via Proposition 3.1, see [9, Sections 3 and 5.3] for details.
The combination of these two assumptions, hence, yields a way to estimate the
coderivative of $S_{2}\circ S_{1}$ via the coderivative of $\Upsilon$, namely

$\displaystyle z^{*}\in D^{*}(S_{2}\circ S_{1})(\bar{z},\bar{w})(w^{*})$
$\displaystyle\quad\Longrightarrow\exists\bar{y}\in\Xi(\bar{z},\bar{w}),\,\exists\xi_{1}\in\mathbb{R}^{m},\,\exists\xi_{2}\in\mathbb{R}^{s}\colon\,(z^{*},-w^{*},0)\in
D^{*}\Upsilon((\bar{z},\bar{w},\bar{y}),(0,0))(\xi_{1},\xi_{2}).$

Finally, the coderivative of $\Upsilon$ can be expressed via its components as

$D^{*}\Upsilon((\bar{z},\bar{w},\bar{y}),(0,0))(\xi_{1},\xi_{2})=D^{*}S_{1}(\bar{z},\bar{y})(\xi_{1})\times\\{0\\}\times
D^{*}S_{2}(\bar{y},\bar{w})(\xi_{2})\ -\ (0,\xi_{2},\xi_{1}).$

This can be seen from Lemma 3.7 (b) (whose proof does not depend on the chain
rule) where one can split $(z,w,y)$ either as $((z,w),y)$ or as $(z,(w,y))$.
The above formulas now readily yield the desired chain rule via the
coderivatives of $S_{1}$ and $S_{2}$.

Naturally, in specific situations, one may prefer to use different
intermediate and feasibility mappings satisfying (3.3). The question then
remains whether one can handle the coderivative of the chosen feasibility
mapping to derive the chain rule without additional assumptions.

For set-valued mappings
$\Gamma_{1}\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m_{1}}$ and
$\Gamma_{2}\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m_{2}}$, we
consider the product mapping
$\Gamma\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m_{1}}\times\mathbb{R}^{m_{2}}$
given by

$\forall
z\in\mathbb{R}^{n}\colon\quad\Gamma(z):=\Gamma_{1}(z)\times\Gamma_{2}(z).$

For later use, we need to compute or at least estimate the coderivative of
this mapping. From [9, Section 5.4], we obtain the next result.

######  Lemma 3.5.

Fix $(\bar{z},(\bar{w}_{1},\bar{w}_{2}))\in\operatorname{gph}\Gamma$. Assume
that
$\widetilde{\Upsilon}\colon\mathbb{R}^{n}\times\mathbb{R}^{m_{1}}\times\mathbb{R}^{m_{2}}\times\mathbb{R}^{n}\times\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{m_{1}}\times\mathbb{R}^{m_{2}}$,
given by

$\forall z,q_{1},q_{2}\in\mathbb{R}^{n},\,\forall
w_{1}\in\mathbb{R}^{m_{1}},\,\forall
w_{2}\in\mathbb{R}^{m_{2}}\colon\quad\widetilde{\Upsilon}(z,w_{1},w_{2},q_{1},q_{2}):=\begin{pmatrix}z-q_{1}\\\
z-q_{2}\\\ \Gamma_{1}(q_{1})-w_{1}\\\ \Gamma_{2}(q_{2})-w_{2}\end{pmatrix},$

is metrically subregular at
$((\bar{z},\bar{w}_{1},\bar{w}_{2},\bar{z},\bar{z}),(0,0,0,0))$. Then we have

(3.4) $D^{*}\Gamma(\bar{z},(\bar{w}_{1},\bar{w}_{2}))(\xi_{1},\xi_{2})\subset
D^{*}\Gamma_{1}(\bar{z},\bar{w}_{1})(\xi_{1})+D^{*}\Gamma_{2}(\bar{z},\bar{w}_{2})(\xi_{2}).$

Moreover, $\widetilde{\Upsilon}$ is metrically subregular at
$((\bar{z},\bar{w}_{1},\bar{w}_{2},\bar{z},\bar{z}),(0,0,0,0))$ whenever
$\Gamma_{1}$ and $\Gamma_{2}$ are polyhedral or if the qualification condition

(3.5)
$D^{*}\Gamma_{1}(\bar{z},\bar{w}_{1})(0)\cap\bigl{(}-D^{*}\Gamma_{2}(\bar{z},\bar{w}_{2})(0)\bigr{)}=\\{0\\}$

holds, in which case $\widetilde{\Upsilon}$ is even metrically regular at the
point of interest.

The qualification condition (3.5) is clearly satisfied if one of the mappings
$\Gamma_{i}$, $i=1,2$, possesses the Aubin property at
$(\bar{z},\bar{w}_{i})$. In the following lemmas, we review more results from
[9, Section 5.4] concerning some exemplary settings where (3.5) holds
naturally.

######  Lemma 3.6.

Fix $(\bar{z},(\bar{w}_{1},\bar{w}_{2}))\in\operatorname{gph}\Gamma$ and
assume that one of the following conditions holds. Then (3.5) is satisfied
and, thus, the estimate (3.4) is valid.

  1. (a)

There are a locally Lipschitz continuous function
$\gamma\colon\mathbb{R}^{n}\to\mathbb{R}^{m_{2}}$ as well as a closed set
$\Omega\subset\mathbb{R}^{m_{2}}$ such that $\Gamma_{2}$ is given by
$\Gamma_{2}(z):=\gamma(z)-\Omega$ for all $z\in\mathbb{R}^{n}$ (an analogous
statements holds if $\,\Gamma_{1}$ admits such a representation).

  2. (b)

The variables $z$ can be decomposed as
$z=(z_{1},z_{2})\in\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}$. Furthermore,
there are set-valued mappings
$\widetilde{\Gamma}_{1}\colon\mathbb{R}^{n_{1}}\rightrightarrows\mathbb{R}^{m_{1}}$
and
$\widetilde{\Gamma}_{2}\colon\mathbb{R}^{n_{2}}\rightrightarrows\mathbb{R}^{m_{2}}$
as well as locally Lipschitz continuous functions
$\gamma_{1}\colon\mathbb{R}^{n_{2}}\to\mathbb{R}^{m_{1}}$ and
$\gamma_{2}\colon\mathbb{R}^{n_{1}}\to\mathbb{R}^{m_{2}}$ such that

$\forall
z=(z_{1},z_{2})\in\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}\colon\quad\Gamma_{1}(z):=\widetilde{\Gamma}_{1}(z_{1})+\gamma_{1}(z_{2}),\quad\Gamma_{2}(z):=\widetilde{\Gamma}_{2}(z_{2})+\gamma_{2}(z_{1}).$

We note that, in principle, the setting (a) can be viewed as an extreme case
of setting (b) with $n_{1}=n$ and $n_{2}=0$. Naturally, this does not fit
formally, but one could regard a set as a set-valued mapping from a zero-
dimensional space and propose a suitable relation for its coderivative via the
normal cone to the set.

In the specific settings outlined above, we can, in fact, get equality in
(3.4) instead of inclusion if we strengthen the Lipschitzness of the single-
valued parts to continuous differentiability, see [9, Lemma 5.7].

######  Lemma 3.7.

Fix $(\bar{z},(\bar{w}_{1},\bar{w}_{2}))\in\operatorname{gph}\Gamma$. Then the
following statements hold.

  1. (a)

Consider the setting (a) from Lemma 3.6 and assume that the function $\gamma$
is continuously differentiable. Then we have

$D^{*}\Gamma(\bar{z},(\bar{w}_{1},\bar{w}_{2}))(\xi_{1},\xi_{2})=\begin{cases}D^{*}\Gamma_{1}(\bar{z},\bar{w}_{1})(\xi_{1})+\nabla\gamma(\bar{z})^{\top}\xi_{2}&\text{if
}\xi_{2}\in\mathcal{N}_{\Omega}(\gamma(\bar{z})-\bar{w}_{2}),\\\
\varnothing&\text{otherwise.}\end{cases}$

  2. (b)

Consider the setting (b) from Lemma 3.6 and assume that the functions
$\gamma_{1}$ and $\gamma_{2}$ are continuously differentiable. Then we have

$D^{*}\Gamma(\bar{z},(\bar{w}_{1},\bar{w}_{2}))(\xi_{1},\xi_{2})=\begin{pmatrix}D^{*}\widetilde{\Gamma}_{1}(\bar{z}_{1},\bar{w}_{1}-\gamma_{1}(\bar{z}_{2}))(\xi_{1})+\nabla\gamma_{2}(\bar{z}_{1})^{\top}\xi_{2}\\\
D^{*}\widetilde{\Gamma}_{2}(\bar{z}_{2},\bar{w}_{2}-\gamma_{2}(\bar{z}_{1}))(\xi_{2})+\nabla\gamma_{1}(\bar{z}_{2})^{\top}\xi_{1}\end{pmatrix}.$

Up to now, we discussed the auxiliary issue of how to guarantee metric
subregularity of $\widetilde{\Upsilon}$, while the main target is to justify
the upper estimate for the coderivative of $\Gamma$. Later, we will also
employ metric subregularity of the product mapping $\Gamma$ itself, which is,
however, often a more difficult issue. We conclude the preliminary part by a
simple result regarding how to ensure metric subregularity of $\Gamma$ from
metric subregularity of its factors $\Gamma_{1}$ and $\Gamma_{2}$. Let us
mention that there exists a much deeper result by Klatte and Kummer, see [42,
Theorem 3.6], on calmness of an intersection of mappings, which can be
equivalently stated in terms of metric subregularity of a product of mappings,
and which has several very interesting applications. In particular, since
$\widetilde{\Upsilon}$ also has the structure of a product, it can be utilized
even in situations when (3.5) fails to hold. Moreover, as demonstrated in [1],
it applies quite nicely to the setting discussed in Section 2.1. Nevertheless,
for the purposes of this paper, we will only need the following result.

######  Lemma 3.8.

Fix $(\bar{z},(\bar{w}_{1},\bar{w}_{2}))\in\operatorname{gph}\Gamma$ and
assume that $\Gamma_{i}$ is metrically subregular at $(\bar{z},\bar{w}_{i})$
for $i=1,2$ and, moreover, that the mapping
$\Sigma\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}\times\mathbb{R}^{n}$
given by

(3.6) $\forall
z\in\mathbb{R}^{n}\colon\quad\Sigma(z):=(z-\Gamma_{1}^{-1}(\bar{w}_{1}))\times(z-\Gamma_{2}^{-1}(\bar{w}_{2}))$

is metrically subregular at $(\bar{z},(0,0))$. Then $\Gamma$ is metrically
subregular at $(\bar{z},(\bar{w}_{1},\bar{w}_{2}))$.

######  Proof 3.9.

By assumption, we find neighborhoods $U,U_{1},U_{2}\subset\mathbb{R}^{n}$ of
$\bar{z}$ and reals $\kappa,\kappa_{1},\kappa_{2}>0$ satisfying

$\forall z\in
U\colon\quad\operatorname{dist}(z,\Sigma^{-1}(0,0))\leq\kappa\operatorname{dist}((0,0),\Sigma(z))$

as well as

$\forall z\in
U_{i}\colon\quad\operatorname{dist}(z,\Gamma_{i}^{-1}(\bar{w}_{i}))\leq\kappa_{i}\operatorname{dist}(\bar{w}_{i},\Gamma_{i}(z))$

for $i=1,2$. Due to $\Gamma^{-1}(\bar{w}_{1},\bar{w}_{2})=\Sigma^{-1}(0,0)$,
we obtain

$\displaystyle\operatorname{dist}(z,\Gamma^{-1}(\bar{w}_{1},\bar{w}_{2}))$
$\displaystyle\leq\kappa\big{(}\operatorname{dist}(z,\Gamma_{1}^{-1}(\bar{w}_{1}))+\operatorname{dist}(z,\Gamma_{2}^{-1}(\bar{w}_{2}))\big{)}$
$\displaystyle\leq\kappa\max\\{\kappa_{1},\kappa_{2}\\}\operatorname{dist}((\bar{w}_{1},\bar{w}_{2}),\Gamma(z))$

for each $z\in U\cap U_{1}\cap U_{2}$, and this shows the claim.

Since $\Sigma$ from (3.6) has a simpler structure than $\Gamma$, its
coderivative can be readily computed by Lemma 3.7. Particularly, we note that
metric regularity of $\Sigma$ at $(\bar{z},(0,0))$ reads

$\mathcal{N}_{\Gamma^{-1}_{1}(\bar{w}_{1})}(\bar{z})\cap\left(-\mathcal{N}_{\Gamma^{-1}_{2}(\bar{w}_{2})}(\bar{z})\right)=\\{0\\},$

and, by metric subregularity of $\Gamma_{i}$ at $(\bar{z},\bar{w}_{i})$,
$i=1,2$, as well as the pre-image rule from Proposition 3.1, the condition

$\operatorname{rge}D^{*}\Gamma_{1}(\bar{z},\bar{w}_{1})\cap\left(-\operatorname{rge}D^{*}\Gamma_{2}(\bar{z},\bar{w}_{2})\right)=\\{0\\}$

is sufficient to guarantee its validity.

##  4 Abstract analysis with and without implicit variables

In this section, we first address the relationship between the minimizers of
(P) and (Q), respectively. Afterwards, we will deal with the derivation of
necessary optimality conditions and constraint qualifications for (P) with the
aid of limiting variational analysis. In order to infer optimality conditions
in terms of initial problem data (particularly, in terms of the generalized
derivatives of $F$ and $G$), we use the chain and product rule of coderivative
calculus from Section 3.3. As we will see, the associated assumptions for
their respective application are valid in several practically relevant
settings, which shows that the essential constraint qualification boils down
to one subregularity assumption. We close the section with some brief remarks
regarding sufficiency of the derived optimality conditions for convex problems
of type (P).

###  4.1 Solution behavior

Here, we want to study the relationship between the local and global
minimizers of (P) and (Q), respectively. To this end, the intermediate mapping
$K\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ given by

$\forall z\in\mathbb{R}^{n}\colon\quad K(z):=\\{\lambda\in F(z)\,|\,0\in
G(z,\lambda)\\}$

will be of essential importance. Note that we have
$Z=M\cap\operatorname{dom}K$ by definition.

######  Lemma 4.1.

If $F$ is a locally bounded set-valued mapping, then $H$ possesses a closed
graph.

######  Proof 4.2.

Let $\\{(z_{k},w_{k})\\}_{k\in\mathbb{N}}\subset\operatorname{gph}H$ be a
sequence converging to some
$(\bar{z},\bar{w})\in\mathbb{R}^{n}\times\mathbb{R}^{s}$. Then, by definition
of $H$, for each $k\in\mathbb{N}$, we find $\lambda_{k}\in F(z_{k})$ such that
$w_{k}\in G(z_{k},\lambda_{k})$ holds. Since $F$ is locally bounded at
$\bar{z}$, $\\{\lambda_{k}\\}_{k\in\mathbb{N}}$ must be bounded. Thus, along a
subsequence (without relabeling) it converges to some
$\bar{\lambda}\in\mathbb{R}^{m}$. Recalling that $F$ and $G$ are set-valued
mappings with a closed graph, $\bar{\lambda}\in F(\bar{z})$ and $\bar{w}\in
G(\bar{z},\bar{\lambda})$ follow, i.e., $\bar{w}\in H(\bar{z})$ is obtained.
This shows the closedness of $\operatorname{gph}H$.

Exemplary, let us mention that in the setting of Section 2.1, the mapping $F$
is cone-valued and not likely to be locally bounded. However, one can check
that the associated mapping $H$ still possesses a closed graph by closedness
of the normal cone mapping associated with a convex set.

Subsequently, we discuss some properties of the mapping $K$.

######  Lemma 4.3.

The following assertions hold.

  1. (a)

The mapping $K$ possesses a closed graph.

  2. (b)

Fix $\bar{z}\in\operatorname{dom}K$. If $F$ is locally bounded at $\bar{z}$,
then $K$ is inner semicompact at $\bar{z}$ w.r.t. $\operatorname{dom}K$.

######  Proof 4.4.

Let us start with the proof of assertion (a). Let
$\\{(z_{k},\lambda_{k})\\}_{k\in\mathbb{N}}\subset\operatorname{gph}K$ be
chosen such that $z_{k}\to\bar{z}$ and $\lambda_{k}\to\bar{\lambda}$ hold. By
definition, we have $\lambda_{k}\in F(z_{k})$ and $0\in G(z_{k},\lambda_{k})$
for each $k\in\mathbb{N}$. The closedness of $\operatorname{gph}F$ and
$\operatorname{gph}G$ yields $\bar{\lambda}\in F(\bar{z})$ and $0\in
G(\bar{z},\bar{\lambda})$, respectively. Hence, we have $\bar{\lambda}\in
K(\bar{z})$, i.e., $\operatorname{gph}K$ is closed.
In order to show (b), let
$\\{z_{k}\\}_{k\in\mathbb{N}}\subset\operatorname{dom}K$ be chosen such that
$z_{k}\to\bar{z}$ holds. Then we find a sequence
$\\{\lambda_{k}\\}_{k\in\mathbb{N}}\subset\mathbb{R}^{m}$ such that
$\lambda_{k}\in K(z_{k})$ holds for all $k\in\mathbb{N}$. Noting that $K$ is
locally bounded at $\bar{z}$ since $F$ enjoys this property by assumption,
$\\{\lambda_{k}\\}_{k\in\mathbb{N}}$ is bounded and possesses a convergent
subsequence. Thus, $K$ is inner semicompact at $\bar{z}$ w.r.t.
$\operatorname{dom}K$.

In the upcoming theorem, we take a look at the global minimizers of (P) and
(Q).

######  Theorem 4.5.

  1. (a)

Let $\bar{z}\in\mathbb{R}^{n}$ be a global minimizer of (P). Then, for each
$\lambda\in K(\bar{z})$, $(\bar{z},\lambda)$ is a global minimizer of (Q).

  2. (b)

Let $(\bar{z},\bar{\lambda})\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ be a global
minimizer of (Q). Then $\bar{z}$ is a global minimizer of (P).

######  Proof 4.6.

Both statements of the theorem follow from the observation that for given
$z\in\mathbb{R}^{n}$, we have the equivalences

$z\in Z\,\Longleftrightarrow\,z\in
M\cap\operatorname{dom}K\,\Longleftrightarrow\,\exists\lambda\in\mathbb{R}^{m}\colon\,(z,\lambda)\in\tilde{Z},$

while the objective function of (Q) does not depend on the variable $\lambda$.

The above theorem shows that the relationship between (P) and (Q) is straight
whenever global minimizers are under consideration. Thus, whenever these
problems actually do not possess local minimizers which are not globally
optimal, then (P) and (Q) are _equivalent_ w.r.t. their minimizers in the
sense of Theorem 4.5.

######  Corollary 4.7.

Consider the situation where $F$ and $G$ are convex set-valued mappings. One
can easily check that this implies convexity of $H$. Particularly, whenever
$f$ is a convex function and $M$ is a convex set, then (P) and (Q) are both
convex optimization problems (i.e., their objective function and feasible set
are convex, respectively) whose minimizers correspond to each other in the
sense of Theorem 4.5.

A quite popular and nearby situation which is addressed by Corollary 4.7
arises in the context of (conic) linear programming where slack variables are
used to transfer a given problem instance into standard normal form. It is
well known that the original problem and its surrogate are equivalent w.r.t.
their minimizers.

Next, we investigate the relationship between local minimizers of (P) and (Q).
As we will see, this issue is much more delicate in comparison with the
situation where globally optimal solutions of these programs are under
consideration.

######  Theorem 4.8.

  1. (a)

Let $\bar{z}\in\mathbb{R}^{n}$ be a local minimizer of (P). Then, for each
$\lambda\in K(\bar{z})$, $(\bar{z},\lambda)$ is a local minimizer of (Q).

  2. (b)

Let $(\bar{z},\lambda)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ be a local
minimizer of (Q) for each $\lambda\in K(\bar{z})$. Furthermore, let $K$ be
inner semicompact at $\bar{z}$ w.r.t. $\operatorname{dom}K$. Then $\bar{z}$ is
a local minimizer of (P).

######  Proof 4.9.

For the proof of (a), suppose that, for some local minimizer $\bar{z}\in Z$ of
(P), there is some $\bar{\lambda}\in K(\bar{z})$ such that
$(\bar{z},\bar{\lambda})$ is not a local minimizer of (Q). Then there is a
sequence $\\{(z_{k},\lambda_{k})\\}_{k\in\mathbb{N}}\subset\tilde{Z}$ such
that $z_{k}\to\bar{z}$, $\lambda_{k}\to\bar{\lambda}$, and
$f(z_{k})<f(\bar{z})$ holds for each $k\in\mathbb{N}$. Since we have $z_{k}\in
M\cap\operatorname{dom}K$ by definition of $K$, $z_{k}$ is feasible to (P) for
each $k\in\mathbb{N}$. Thus, $\bar{z}$ cannot be a local minimizer of (P)
which is a contradiction. This shows (a).
For the proof of (b), let
$(\bar{z},\lambda)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ be a local minimizer
of (Q) for each $\lambda\in K(\bar{z})$ and let $K$ be inner semicompact at
$\bar{z}$ w.r.t. $\operatorname{dom}K$. From $\bar{z}\in
M\cap\operatorname{dom}K$ we infer the feasibility of $\bar{z}$ to (P).
Suppose now that $\bar{z}$ is not a local minimizer of (P). Then we find a
sequence $\\{z_{k}\\}_{k\in\mathbb{N}}\subset Z$ such that $z_{k}\to\bar{z}$
while $f(z_{k})<f(\bar{z})$ is satisfied for all $k\in\mathbb{N}$. From
$z_{k}\in Z$ we deduce $z_{k}\in M\cap\operatorname{dom}K$ for each
$k\in\mathbb{N}$. Due to the inner semicompactness of $K$ at $\bar{z}$ w.r.t.
$\operatorname{dom}K$, there are a subsequence
$\\{z_{k_{l}}\\}_{l\in\mathbb{N}}$ and a sequence
$\\{\lambda_{l}\\}_{l\in\mathbb{N}}\subset\mathbb{R}^{m}$ converging to some
$\bar{\lambda}\in\mathbb{R}^{m}$ such that $\lambda_{l}\in K(z_{k_{l}})$ holds
for all $l\in\mathbb{N}$ . Since we have $z_{k_{l}}\to\bar{z}$, we can deduce
$\bar{\lambda}\in K(\bar{z})$ from the closedness of $\operatorname{gph}K$,
see Lemma 4.3. Thus, the points from
$\\{(z_{k_{l}},\lambda_{l})\\}_{l\in\mathbb{N}}$ as well as
$(\bar{z},\bar{\lambda})$ are feasible to (Q). Since we have
$f(z_{k_{l}})<f(\bar{z})$ for all $l\in\mathbb{N}$, $(\bar{z},\bar{\lambda})$
cannot be a local minimizer of (Q). This, however, contradicts our
assumptions.

Naturally, when dealing with the reformulated problem (Q), one can hardly
expect to find $\bar{z}$ such that $(\bar{z},\lambda)$ is a local minimizer
for all $\lambda\in K(\bar{z})$. Typically, one simply finds a point
$(\bar{z},\bar{\lambda})$ which is locally optimal (even this is often too
optimistic and one only gets a stationary point instead). This underlines that
the approach via problem (Q) is indeed quite far from ideal. The proof of the
previous theorem yields that the situation can be saved if the stronger inner
semicontinuity of $K$ is assumed.

######  Corollary 4.10.

Let $(\bar{z},\bar{\lambda})\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ be a local
minimizer of (Q) and let $K$ be inner semicontinuous at
$(\bar{z},\bar{\lambda})$ w.r.t. $\operatorname{dom}K$. Then $\bar{z}$ is a
local minimizer of (P).

Due to Lemma 4.3, the inner semicompactness of $K$ can be guaranteed via local
boundedness of $F$. In the context of bilevel programming, see Section 2.1, we
already mentioned that the mapping $F$ does not enjoy this property. However,
$K$ is the Lagrange multiplier mapping associated with the lower level problem
in this context, and the latter is known to be locally bounded under validity
of the Mangasarian–Fromovitz constraint qualification which, thus, implies its
inner semicompactness as well. Hence, Theorem 4.8 recovers the popular result
[20, Theorem 3.2]. However, exploiting Proposition 3.3, we are in position to
weaken this constraint qualification such that the resulting multiplier
mapping still possesses the necessary inner semicompactness, i.e., we will
keep the essential result of Theorem 4.8 in this case, see Section 5.1 for
details.

######  Remark 4.11.

We point out that, in several exemplary cases, the inner semicompactness
assumption will be automatically fulfilled (or will be a consequence of some
initial assumption on the data, such as validity of a constraint qualification
for the lower level program in bilevel programming). In fact, even a stronger
form of inner semicompactness considered in Section 4.2 (i.e., inner
semicompactness w.r.t. another intermediate mapping) will hold true, see
Section 5.1 as well.

Below, we illustrate that none of the assumptions which are necessary in order
to identify a local minimizer of (P) via local minimizers of (Q) can be
dropped in Theorem 4.8.

######  Example 4.12.

  1. (a)

Let us consider the setting $n=m=s=1$ with $f:=\operatorname{id}$,

$\forall z,\lambda\in\mathbb{R}\colon\quad F(z):=\begin{cases}\\{0\\}&z>0,\\\
\\{0,1\\}&z=0,\\\ \\{1\\}&z<0,\end{cases}\qquad
G(z,\lambda):=[-z-\lambda,\infty),$

as well as $M:=\mathbb{R}$. Obviously, we have $Z=[-1,\infty)$, i.e.,
$\bar{z}:=-1$ is the uniquely determined local and global minimizer of the
associated problem (P). It holds

$\forall z\in\mathbb{R}\colon\quad K(z)=\begin{cases}\\{0\\}&z>0,\\\
\\{0,1\\}&z=0,\\\ \\{1\\}&z\in[-1,0),\\\ \varnothing&z<-1.\end{cases}$

At $\tilde{z}:=0$, $K$ is inner semicompact w.r.t. $\operatorname{dom}K=Z$. It
can be easily checked that $(\tilde{z},0)$ is a local minimizer of (Q) while
$(\tilde{z},1)$ is not. Thus, assertion (b) of Theorem 4.8 does not generally
hold whenever the local optimality for (Q) cannot be guaranteed for all
realizations of the implicit variables in question.

  2. (b)

For $n=m=s=1$, we set $f:=\operatorname{id}$,

$\forall z,\lambda\in\mathbb{R}\colon\quad F(z):=\begin{cases}\\{0\\}&z\geq
0,\\\ \\{-1/z\\}&z<0,\end{cases}\qquad G(z,\lambda):=[-1,1+z],$

as well as $M:=\mathbb{R}$. Again, we find $Z=[-1,\infty)$, and $\bar{z}:=-1$
is the uniquely determined local and global minimizer of the associated
problem (P). One easily computes

$\forall z\in\mathbb{R}\colon\quad K(z)=\begin{cases}\\{0\\}&z\geq 0,\\\
\\{-1/z\\}&z\in[-1,0),\\\ \varnothing&z<-1.\end{cases}$

Let us consider $\tilde{z}:=0$. At $\tilde{z}$, $K$ is not inner semicompact
w.r.t. $\operatorname{dom}K$. On the other hand, $(\tilde{z},0)$ is a local
minimizer of (Q) since for $z\uparrow 0$, we have $\lambda\to\infty$ for any
$\lambda\in K(z)$. Consequently, we cannot abstain from postulating inner
semicompactness of $K$ in order to guarantee validity of assertion (b) of
Theorem 4.8.

The issues regarding the relationship between local minimizers of (P) and (Q)
result from the fact that the variable $\lambda$ is equipped with a metric
structure in (Q). This is quite natural when treating (Q) as an optimization
problem and forms the base for the derivation of necessary optimality
conditions, constraint qualifications, and solution algorithms. In the context
of bilevel optimization, the authors of [58] used a different approach by
disregarding the metric structure w.r.t. the lower level Lagrange multipliers
in a reformulation of the bilevel programming problem which exploits the
optimal value function as well as the Karush–Kuhn–Tucker-conditions of the
lower level problem simultaneously, see [58, Proposition 3.1]. In the more
general setting considered here, this amounts to saying that a feasible point
$(\bar{z},\bar{\lambda})\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ of (Q) is a
local minimizer whenever there is a neighborhood $U\subset\mathbb{R}^{n}$ of
$\bar{z}$ such that

(4.1) $\forall(z,\lambda)\in\tilde{Z}\cap(U\times\mathbb{R}^{m})\colon\quad
f(\bar{z})\leq f(z)$

holds. One can easily check that whenever $\bar{z}\in\mathbb{R}^{n}$ is a
local minimizer of (P), then, for each $\lambda\in K(\bar{z})$,
$(\bar{z},\lambda)$ is a local minimizer of (Q) in the sense of (4.1).
Conversely, if $(\bar{z},\bar{\lambda})\in\mathbb{R}^{n}\times\mathbb{R}^{m}$
is a local minimizer of (Q) in the sense of (4.1), then $\bar{z}$ is a local
minimizer of (P). At the first glance, this approach seems to solve all the
issues observed in Theorem 4.8. However, it is completely unclear how local
minimizers of (Q) in the sense of (4.1) can be characterized or numerically
identified. In [58], the authors do not comment on this shortcoming at all.
Thus, although faced with the disadvantages carved out in Theorem 4.8, we will
stick to the classical notion of local optimality in (Q), i.e., we impose a
metric structure on $\lambda$ there.

We conclude this section with a brief remark regarding sufficient optimality
conditions.

######  Remark 4.13.

In optimization theory, sufficient optimality conditions generally imply local
linear or quadratic growth, i.e., they impose local isolatedness of the
characterized minimizer. Now, consider a local minimizer $\bar{z}\in Z$ of
(P). Even if it is a locally isolated minimizer of (P), this property fails to
hold for the respective local minimizer $(\bar{z},\bar{\lambda})$ for each
$\bar{\lambda}\in K(\bar{z})$ as soon as $K(\bar{z})$ is a connected set which
is not a singleton since the objective of (Q) does not depend on the variable
$\lambda$. As a consequence, one cannot rely on classical first- or second-
order sufficient optimality conditions in order to characterize the minimizers
of (Q) as soon as $K$ is multivalued. In the light of Theorem 4.8, it is,
thus, difficult to infer local optimality of a feasible point of (P) via (Q).
In the context of bilevel and cardinality-constrained programming, this
phenomenon has been mentioned recently in [47, Remark 4.21] and [16, Section
3.2], respectively.

###  4.2 Necessary optimality conditions

Here, we are going to investigate three notions of necessary optimality
conditions of M-stationarity-type for program (P). Two of them correspond to
(standard) M-stationarity defined in Definition 3.2 applied either directly to
(P) or to its reformulation (Q), while the third notion offers conditions in a
completely explicit form. Without mentioning it again, we assume throughout
the section that $\operatorname{gph}H$ is (locally) closed. As we have seen in
Lemma 4.1 this is inherent if $F$ is locally bounded, but it also holds in far
more general but practically relevant situations. In particular,
$\operatorname{gph}H$ is locally closed around
$(\bar{z},0)\in\operatorname{gph}H$ if the mapping $\widehat{K}$ from (4.3)
below is inner semicompact at $(\bar{z},0)$ w.r.t.
$\operatorname{dom}\widehat{K}=\operatorname{gph}H$. For later use, let us
define set-valued mappings
$\mathcal{H}\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{m}\times\mathbb{R}^{s}$
and
$\mathfrak{H}\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n+m}\times\mathbb{R}^{n+m+s}$
by means of

$\displaystyle\forall
z\in\mathbb{R}^{n},\,\forall\lambda\in\mathbb{R}^{m}\colon\quad\mathcal{H}(z,\lambda)$
$\displaystyle:=\begin{pmatrix}F(z)-\lambda\\\
G(z,\lambda)\end{pmatrix},\;\;\mathfrak{H}(z,\lambda):=\begin{pmatrix}(z,\lambda)-\operatorname{gph}F\\\
(z,\lambda,0)-\operatorname{gph}G\end{pmatrix}.$

In order to incorporate the constraints $z\in M$, we will exploit the mappings
$H_{M}\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{s}\times\mathbb{R}^{n}$,
$\mathcal{H}_{M}\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{m}\times\mathbb{R}^{s}\times\mathbb{R}^{n}$,
as well as
$\mathfrak{H}_{M}\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n+m}\times\mathbb{R}^{n+m+s}\times\mathbb{R}^{n}$
obtained from $H$, $\mathcal{H}$, and $\mathfrak{H}$ by adding $(z-M)$ as a
component, i.e., we exemplary have $H_{M}(z):=H(z)\times(z-M)$ for all
$z\in\mathbb{R}^{n}$. Observe that we have $z\in Z$ if and only if $(0,0)\in
H_{M}(z)$ and $(z,\lambda)\in\tilde{Z}$ if and only if
$(0,0,0)\in\mathcal{H}_{M}(z,\lambda)$ if and only if
$((0,0),(0,0,0),0)\in\mathfrak{H}_{M}(z,\lambda)$.

######  Definition 4.14.

Let $\bar{z}\in\mathbb{R}^{n}$ be a feasible point of (P). Then $\bar{z}$ is
said to be

  1. (i)

_implicitly M-stationary_ if there exists $\nu\in\mathbb{R}^{s}$ such that

$0\in\partial f(\bar{z})+D^{*}H(\bar{z},0)(\nu)+\mathcal{N}_{M}(\bar{z}),$

  2. (ii)

_fuzzily M-stationary_ (or _fuzzily M-stationary w.r.t. $\bar{\lambda}$_) if
there exist $\bar{\lambda}\in K(\bar{z})$, $\mu\in\mathbb{R}^{m}$, and
$\nu\in\mathbb{R}^{s}$ such that

$(0,0)\in\partial
f(\bar{z})\times\\{0\\}+D^{*}\mathcal{H}((\bar{z},\bar{\lambda}),(0,0))(\mu,\nu)+\mathcal{N}_{M}(\bar{z})\times\\{0\\}$

holds, i.e., if $(\bar{z},\bar{\lambda})$ is M-stationary for (Q),

  3. (iii)

_explicitly M-stationary_ (or _explicitly M-stationary w.r.t.
$\bar{\lambda}$_) if there exist $\bar{\lambda}\in K(\bar{z})$,
$\mu\in\mathbb{R}^{m}$, and $\nu\in\mathbb{R}^{s}$ such that

$0\in\partial
f(\bar{z})+D^{*}F(\bar{z},\bar{\lambda})(\mu)+\\{\xi\in\mathbb{R}^{n}\,|\,(\xi,\mu)\in
D^{*}G((\bar{z},\bar{\lambda}),0)(\nu)\\}+\mathcal{N}_{M}(\bar{z}).$

Proposition 3.1 now immediately provides constraint qualifications for the
above M-stationarity notions.

######  Proposition 4.15.

Let $\bar{z}\in\mathbb{R}^{n}$ be a local minimizer of (P). Then the following
assertions hold.

  1. (a)

If $H_{M}$ is metrically subregular at $(\bar{z},(0,0))$, then $\bar{z}$ is
implicitly M-stationary.

  2. (b)

If $\mathcal{H}_{M}$ is metrically subregular at
$((\bar{z},\bar{\lambda}),(0,0,0))$ for some $\bar{\lambda}\in K(\bar{z})$,
then $\bar{z}$ is fuzzily M-stationary w.r.t. $\bar{\lambda}$.

  3. (c)

If $\mathfrak{H}_{M}$ is metrically subregular at
$((\bar{z},\bar{\lambda}),((0,0),(0,0,0),0))$ for some $\bar{\lambda}\in
K(\bar{z})$, then $\bar{z}$ is explicitly M-stationary w.r.t. $\bar{\lambda}$.

######  Proof 4.16.

Since $\bar{z}$ is a local minimizer of (P), [48, Theorem 6.1] guarantees
validity of

$0\in\partial f(\bar{z})+\mathcal{N}_{H_{M}^{-1}(0,0)}(\bar{z}).$

Noting that for each $\lambda\in K(\bar{z})$, $(\bar{z},\lambda)$ is a local
minimizer of (Q), see Theorem 4.8, [48, Theorem 6.1] furthermore implies

(4.2a) $\displaystyle(0,0)$ $\displaystyle\in\partial
f(\bar{z})\times\\{0\\}+\mathcal{N}_{\mathcal{H}_{M}^{-1}(0,0,0)}(\bar{z},\bar{\lambda}),$
(4.2b) $\displaystyle(0,0)$ $\displaystyle\in\partial
f(\bar{z})\times\\{0\\}+\mathcal{N}_{\mathfrak{H}_{M}^{-1}((0,0),(0,0,0),0)}(\bar{z},\bar{\lambda}).$

For the proof of (a), we exploit the metric subregularity of $H_{M}$ at
$(\bar{z},(0,0))$ and Proposition 3.1 in order to find $0\in\partial
f(\bar{z})+D^{*}H_{M}(\bar{z},(0,0))(\nu,\xi)$ for some $\nu\in\mathbb{R}^{s}$
and $\xi\in\mathbb{R}^{n}$. Now, we can exploit assertion (a) of Lemma 3.7 in
order to find

$D^{*}H_{M}(\bar{z},(0,0))(\nu,\xi)=\begin{cases}D^{*}H(\bar{z},0)(\nu)+\xi&\xi\in\mathcal{N}_{M}(\bar{z}),\\\
\varnothing&\text{otherwise,}\end{cases}$

and this shows that $\bar{z}$ is implicitly M-stationary.
The proof for (b) works in analogous way exploiting (4.2a).
In order to verify statement (c), we first introduce a continuously
differentiable single-valued mapping
$\mathfrak{h}_{M}\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}^{n+m}\times\mathbb{R}^{n+m+s}\times\mathbb{R}^{n}$
and a set
$\Omega\subset\mathbb{R}^{n+m}\times\mathbb{R}^{n+m+s}\times\mathbb{R}^{n}$ by
means of

$\forall
z\in\mathbb{R}^{n},\,\forall\lambda\in\mathbb{R}^{m}\colon\quad\mathfrak{h}_{M}(z,\lambda):=((z,\lambda),(z,\lambda,0),z),\qquad\Omega:=\operatorname{gph}F\times\operatorname{gph}G\times
M$

and observe that
$\mathfrak{H}_{M}(z,\lambda)=\mathfrak{h}_{M}(z,\lambda)-\Omega$ holds for all
$z\in\mathbb{R}^{n}$ and $\lambda\in\mathbb{R}^{m}$. Thus, the metric
subregularity of the feasibility mapping $\mathfrak{H}_{M}$ at the reference
point guarantees applicability of the pre-image rule, see Section 3.2.
Together with the product rule for the limiting normal cone, see [53,
Proposition 6.41], we obtain

$\displaystyle\mathcal{N}_{\mathfrak{H}_{M}^{-1}((0,0),(0,0,0),0)}(\bar{z},\bar{\lambda})$
$\displaystyle\qquad\subset\nabla\mathfrak{h}_{M}(\bar{z},\bar{\lambda})^{\top}\mathcal{N}_{\Omega}(\mathfrak{h}_{M}(\bar{z},\bar{\lambda}))$
$\displaystyle\qquad=\nabla\mathfrak{h}_{M}(\bar{z},\bar{\lambda})^{\top}\left(\mathcal{N}_{\operatorname{gph}F}(\bar{z},\bar{\lambda})\times\mathcal{N}_{\operatorname{gph}G}(\bar{z},\bar{\lambda},0)\times\mathcal{N}_{M}(\bar{z})\right)$
$\displaystyle\qquad=\left\\{(\xi_{1}+\xi_{2}+\xi_{3},\mu_{1}+\mu_{2})\middle|\,\begin{aligned}
&\exists\nu\in\mathbb{R}^{s}\colon\,\xi_{1}\in
D^{*}F(\bar{z},\bar{\lambda})(-\mu_{1}),\\\ &\qquad(\xi_{2},\mu_{2})\in
D^{*}G((\bar{z},\bar{\lambda}),0)(\nu),\,\xi_{3}\in\mathcal{N}_{M}(\bar{z})\end{aligned}\right\\}.$

Now, the claim follows from (4.2b).

######  Remark 4.17.

Taking into account Lemma 3.8 as well as the fact that the simple mapping
$z\rightrightarrows z-M$ is trivially metrically subregular at all points of
its graph, metric subregularity of $H_{M}$ at $(\bar{z},(0,0))$ can be ensured
by metric subregularity of $H$ at $(\bar{z},0)$ and metric subregularity of
$z\rightrightarrows(z-H^{-1}(0))\times(z-M)$ at $(\bar{z},(0,0))$. Note that
the latter implies applicability of the intersection rule for the set
$Z=H_{M}^{-1}(0,0)=H^{-1}(0)\cap M$, namely

$\mathcal{N}_{H_{M}^{-1}(0,0)}(\bar{z})\subset\mathcal{N}_{H^{-1}(0)}(\bar{z})+\mathcal{N}_{M}(\bar{z})$

and, hence, combined with the metric subregularity of $H$, also provides a
constraint qualification for implicit M-stationarity, see Proposition 3.1.

Let us briefly comment on how to ensure the above metric subregularity
assumptions via sufficient conditions in terms of coderivatives. Let
$\bar{z}\in\mathbb{R}^{n}$ be a feasible point for (P) and let
$\bar{\lambda}\in K(\bar{z})$ be chosen arbitrarily.

  1. (i)

If, for all $\nu\in\mathbb{R}^{s}$ and $\xi\in\mathbb{R}^{n}$, the implication

$-\xi\in D^{*}H(\bar{z},0)(\nu)\cap\big{(}-\mathcal{N}_{M}(\bar{z})\big{)}\
\Longrightarrow\ \xi,\nu=0$

holds, then $H_{M}$ is metrically subregular at $(\bar{z},(0,0))$.

  2. (ii)

If, for all $\mu\in\mathbb{R}^{m}$, $\nu\in\mathbb{R}^{s}$, and
$\xi\in\mathbb{R}^{n}$, the implication

$(-\xi,0)\in D^{*}\mathcal{H}((\bar{z},\bar{\lambda}),(0,0))(\mu,\nu),\
\xi\in\mathcal{N}_{M}(\bar{z})\ \Longrightarrow\ \xi,\mu,\nu=0$

holds, then $\mathcal{H}_{M}$ is metrically subregular at
$((\bar{z},\bar{\lambda}),(0,0,0))$.

  3. (iii)

If, for all $\zeta\in\mathbb{R}^{n}$, $\mu\in\mathbb{R}^{m}$,
$\nu\in\mathbb{R}^{s}$, and $\xi\in\mathbb{R}^{n}$, the implication

$\zeta\in D^{*}F(\bar{z},\bar{\lambda})(\mu),\ (-\zeta-\xi,\mu)\in
D^{*}G((\bar{z},\bar{\lambda}),0)(\nu),\ \xi\in\mathcal{N}_{M}(\bar{z})\
\Longrightarrow\ \xi,\zeta,\mu,\nu=0$

holds, then $\mathfrak{H}_{M}$ is metrically subregular at
$((\bar{z},\bar{\lambda}),((0,0),(0,0,0),0))$.

Observe that the above conditions correspond to the famous Mordukhovich
criterion applied to the respective situation at hand. This can be seen from
statement (a) of Lemma 3.7, the sum rule for coderivative calculus, see e.g.
[48, Theorem 3.9], and the product rule for limiting normals, see [53,
Proposition 6.41]. Thus, the above conditions already imply metric regularity
of the mappings $H_{M}$, $\mathcal{H}_{M}$, and $\mathfrak{H}_{M}$ at the
respective point of interest. Weaker sufficient conditions for the presence of
metric subregularity in terms of limiting normal cones and coderivatives can
exemplary be found in [37, 38, 40, 60]. Even finer sufficient conditions can
be obtained using the directional limiting approach, namely the _first-order
sufficient condition for metric subregularity_ from [30] or the directional
pseudo- and quasi-normality conditions from [3, 7]. For more details on the
directional limiting approach in variational analysis, we exemplary refer to
[8, 33] and the references therein.

Next, we are going to compare the three approaches on how to come up with
necessary optimality conditions for (P). First, we look at the qualification
conditions and, afterwards, we deal with the stationarity conditions. For that
purpose, let us define another intermediate mapping
$\widehat{K}\colon\mathbb{R}^{n}\times\mathbb{R}^{s}\rightrightarrows\mathbb{R}^{m}$,
closely related to $K$, given by

(4.3) $\forall z\in\mathbb{R}^{n},\,\forall
w\in\mathbb{R}^{s}\colon\quad\widehat{K}(z,w):=\\{\lambda\in F(z)\,|\,w\in
G(z,\lambda)\\}.$

######  Proposition 4.18.

Let $\bar{z}\in\mathbb{R}^{n}$ be a feasible point of (P). Consider the
following two assumptions:

  1. (a)

$\mathcal{H}_{M}$ is metrically subregular at $((\bar{z},\lambda),(0,0,0))$
for each $\lambda\in K(\bar{z})$ and $\widehat{K}$ is inner semicompact at
$(\bar{z},0)$ w.r.t. $\operatorname{dom}\widehat{K}$,

  2. (b)

$\mathcal{H}_{M}$ is metrically subregular at
$((\bar{z},\bar{\lambda}),(0,0,0))$ for some $\bar{\lambda}\in K(\bar{z})$ and
$\widehat{K}$ is inner semicontinuous at $((\bar{z},0),\bar{\lambda})$ w.r.t.
$\operatorname{dom}\widehat{K}$.

Then each of the conditions (a) and (b) implies that $H_{M}$ is metrically
subregular at $(\bar{z},(0,0))$.

######  Proof 4.19.

Let us first show the statement under validity of (a). Suppose that $H_{M}$ is
not metrically subregular at $(\bar{z},(0,0))$. Hence, for each
$k\in\mathbb{N}$, we find $z_{k}\in\mathbb{R}^{n}$ and some $w_{k}\in
H(z_{k})$ satisfying

$\operatorname{dist}(z_{k},Z)=\operatorname{dist}(z_{k},H^{-1}_{M}(0,0))>k\,\operatorname{dist}((0,0),H_{M}(z_{k}))=k(\left\|w_{k}\right\|+\operatorname{dist}(z_{k},M))$

such that $z_{k}\to\bar{z}$. Particularly, $w_{k}\to 0$ follows. By definition
of $H$ and $\widehat{K}$, we have
$(z_{k},w_{k})\in\operatorname{dom}\widehat{K}$ for each $k\in\mathbb{N}$. The
assumed inner semicompactness of $\widehat{K}$ at $(\bar{z},0)$ w.r.t.
$\operatorname{dom}\widehat{K}$ yields the existence of a sequence
$\\{\lambda_{k}\\}_{k\in\mathbb{N}}$ and some $\lambda\in\mathbb{R}^{m}$ such
that $\lambda_{k}\to\lambda$ and $\lambda_{k}\in\widehat{K}(z_{k},w_{k})$ hold
along a subsequence (without relabeling). Recalling that $F$ and $G$ are
mappings with closed graphs, the above convergences yield $\lambda\in
F(\bar{z})$ and $0\in G(\bar{z},\lambda)$, i.e.,
$\lambda\in\widehat{K}(\bar{z},0)=K(\bar{z})$. Consequently, we obtain

$\displaystyle\operatorname{dist}((z_{k},\lambda_{k}),\mathcal{H}^{-1}_{M}(0,0,0))=\operatorname{dist}((z_{k},\lambda_{k}),\tilde{Z})\geq\operatorname{dist}(z_{k},Z)$
$\displaystyle\qquad>k\bigl{(}\left\|w_{k}\right\|+\operatorname{dist}(z_{k},M)\bigr{)}\geq
k\bigl{(}\operatorname{dist}(0,G(z_{k},\lambda_{k}))+\operatorname{dist}(z_{k},M)\bigr{)}$
$\displaystyle\qquad=k\bigl{(}\operatorname{dist}(0,F(z_{k})-\lambda_{k})+\operatorname{dist}(0,G(z_{k},\lambda_{k}))+\operatorname{dist}(z_{k},M)\bigr{)}$
$\displaystyle\qquad=k\operatorname{dist}((0,0,0),\mathcal{H}_{M}(z_{k},\lambda_{k})),$

showing that $\mathcal{H}_{M}$ is not metrically subregular at
$((\bar{z},\lambda),(0,0,0))$. This, however, contradicts the proposition’s
assumptions from (a).
The proof works similarly under validity of (b) observing that the sequence
$\\{\lambda_{k}\\}_{k\in\mathbb{N}}$ can be chosen to be convergent to the
fixed implicit variable $\bar{\lambda}\in\widehat{K}(\bar{z},0)$ by inner
semicontinuity of $\widehat{K}$ w.r.t. $\operatorname{dom}\widehat{K}$ at
$((\bar{z},0),\bar{\lambda})$.

######  Proposition 4.20.

Let $\bar{z}\in\mathbb{R}^{n}$ be a feasible point of (P) and fix
$\bar{\lambda}\in K(\bar{z})$. Assume that $\mathfrak{H}_{M}$ is metrically
subregular at $((\bar{z},\bar{\lambda}),((0,0),(0,0,0),0))$. Then
$\mathcal{H}_{M}$ is metrically subregular at
$((\bar{z},\bar{\lambda}),(0,0,0))$.

######  Proof 4.21.

The proof follows easily from
$\mathcal{H}^{-1}_{M}(0,0,0)=\mathfrak{H}^{-1}_{M}((0,0),(0,0,0),0)=\tilde{Z}$,
together with the simple estimates

$\displaystyle\forall\,(z,\lambda^{\prime})\in\operatorname{gph}F,\,\forall\lambda\in\mathbb{R}^{m}\colon\quad$
$\displaystyle\operatorname{dist}((z,\lambda),\operatorname{gph}F)$
$\displaystyle\leq\left\|\lambda-\lambda^{\prime}\right\|,$
$\displaystyle\forall\,((z,\lambda),w)\in\operatorname{gph}G\colon\quad$
$\displaystyle\operatorname{dist}(((z,\lambda),0),\operatorname{gph}G)$
$\displaystyle\leq\left\|w\right\|$

which yield that
$\operatorname{dist}(((0,0),(0,0,0),0),\mathfrak{H}_{M}(z,\lambda))\leq\operatorname{dist}((0,0,0),\mathcal{H}_{M}(z,\lambda))$
holds.

Next, we investigate the relationship between the three stationarity notions
from Definition 4.14 in more detail. Let us first address the relationship
between fuzzy and explicit M-stationarity.

######  Remark 4.22.

Lemmas 3.5, 3.6 and 3.7 yield that, under suitable conditions, the
coderivative of $\mathcal{H}$ at some point $((\bar{z},\lambda),(0,0))$ of its
graph can be estimated or computed via its components, i.e.,

(Inc$(\lambda)$) $D^{*}\mathcal{H}((\bar{z},\lambda),(0,0))(\mu,\nu)\subset
D^{*}F(\bar{z},\lambda)(\mu)\times\\{-\mu\\}\,+\,D^{*}G((\bar{z},\lambda),0)(\nu)$

for all $\mu\in\mathbb{R}^{m}$ and $\nu\in\mathbb{R}^{s}$. A sufficient
condition for validity of (Inc$(\lambda)$) is given by

$\xi\in D^{*}F(\bar{z},\lambda)(0),\,(-\xi,0)\in
D^{*}G((\bar{z},\lambda),0)(0)\quad\Longrightarrow\quad\xi=0,$

see Lemma 3.5, and this is inherent if either $F$ possesses the Aubin property
at $(\bar{z},\lambda)$ or $G$ possesses the Aubin property at
$((\bar{z},\lambda),0)$. Another situation where (Inc$(\lambda)$) naturally
holds is given in the case where $F$ and $G$ are polyhedral set-valued
mappings. Note that (Inc$(\lambda)$) does not hold for free in general due to
fact that the variable $z$ enters both set-valued parts $F$ and $G$. Combining
validity of (Inc$(\lambda)$) with simple computations provides conditions that
guarantee that fuzzy M-stationarity implies or even coincides with explicit
M-stationarity. We will show in Section 4.3 that the latter is automatically
fulfilled for all of our example problems from Section 2, so we skip further
details and consider these two notions to be basically identical.

Let us now tackle the more interesting question when an implicitly
M-stationary point is fuzzily or explicitly M-stationary as well. The latter
question can be easily answered by the chain rule since
$H(z)=(G\circ\tilde{F})(z)$ holds for all $z\in\mathbb{R}^{n}$ where
$\tilde{F}\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}\times\mathbb{R}^{m}$
is the set-valued mapping given by $\tilde{F}(z):=\\{z\\}\times F(z)$ for all
$z\in\mathbb{R}^{n}$. Taking into account that

$D^{*}\tilde{F}(z,(z,\lambda))(\xi,\mu)=\xi+D^{*}F(z,\lambda)(\mu)$

holds by Lemma 3.7 (a), Lemma 3.4 immediately yields the following result.

######  Proposition 4.23.

Let $\bar{z}\in\mathbb{R}^{n}$ be an implicitly M-stationary point for (P).
Then $\bar{z}$ is explicitly M-stationary provided the mapping

(4.4) $(z,w)\rightrightarrows\tilde{F}(z)\cap
G^{-1}(w)=\\{(z,\lambda)\,|\,\lambda\in F(z),\,w\in G(z,\lambda)\\}$

is inner semicompact at $(\bar{z},0)$ w.r.t. its domain while the mapping

(4.5)
$(z,w,q,\lambda)\rightrightarrows\bigl{(}z-q,F(z)-\lambda,G(q,\lambda)-w\bigr{)}$

is metrically subregular at $((\bar{z},0,\bar{z},\lambda),(0,0,0))$ for each
$\lambda\in K(\bar{z})$.

On the other hand, using the intermediate mapping $\widehat{K}$ from (4.3),
one obtains

$\operatorname{gph}H=\operatorname{dom}\widehat{K},\qquad\qquad\operatorname{gph}\widehat{K}=\widehat{\mathcal{H}}^{-1}(0,0)$

for the feasibility mapping
$\widehat{\mathcal{H}}\colon\mathbb{R}^{n}\times\mathbb{R}^{s}\times\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{m}\times\mathbb{R}^{s}$
given by

(4.6) $\forall z\in\mathbb{R}^{n},\,\forall
w\in\mathbb{R}^{s},\,\forall\lambda\in\mathbb{R}^{m}\colon\quad\widehat{\mathcal{H}}(z,w,\lambda):=\begin{pmatrix}F(z)-\lambda\\\
G(z,\lambda)-w\end{pmatrix}=\mathcal{H}(z,\lambda)-\begin{pmatrix}0\\\
w\end{pmatrix}.$

Keeping Lemma 3.4 and the subsequently stated remarks in mind, the
coderivative of $H$ can be estimated via the coderivative of
$\widehat{\mathcal{H}}$ under suitable assumptions. More precisely, for
$(a,b)$ satisfying $a\in D^{*}H(\bar{z},0)(b)$, the above approach yields the
existence of $\bar{\lambda}\in K(\bar{z})$ together with
$\mu\in\mathbb{R}^{m}$ and $\nu\in\mathbb{R}^{s}$ such that

$(a,-b,0)\in
D^{*}\widehat{\mathcal{H}}((\bar{z},0,\bar{\lambda}),(0,0))(\mu,\nu).$

Consequently, the decoupled sum rule from [9, Section 5.4] implies that the
relations $\nu=b$ and $(a,0)\in
D^{*}\mathcal{H}((\bar{z},\bar{\lambda}),(0,0))(\mu,\nu)$ need to hold, and
for the particular choice $a\in-\partial f(\bar{z})-\mathcal{N}_{M}(\bar{z})$,
we end up with fuzzy M-stationarity.

We summarize these observations in the subsequent proposition.

######  Proposition 4.24.

Let $\bar{z}\in\mathbb{R}^{n}$ be an implicitly M-stationary point of (P).
Assume that $\widehat{K}$ is inner semicompact at $(\bar{z},0)$ w.r.t.
$\operatorname{dom}\widehat{K}$, and let $\widehat{\mathcal{H}}$ be metrically
subregular at $((\bar{z},0,\lambda),(0,0))$ for each $\lambda\in K(\bar{z})$.
Then $\bar{z}$ is fuzzily M-stationary. Moreover, $\bar{z}$ is also explicitly
M-stationary if (Inc$(\lambda)$) holds for each $\lambda\in K(\bar{z})$.

The metric subregularity assumption in Proposition 4.24 can again be replaced
by the stronger Mordukhovich criterion.

######  Corollary 4.25.

Let $\bar{z}\in\mathbb{R}^{n}$ be an implicitly M-stationary point for (P).
Let $\widehat{K}$ be inner semicompact at $(\bar{z},0)$ w.r.t.
$\operatorname{dom}\widehat{K}$.

  1. (a)

Assume that, for each $\lambda\in K(\bar{z})$, the constraint qualification

(4.7) $(0,0)\in
D^{*}\mathcal{H}((\bar{z},\lambda),(0,0))(\mu,0)\quad\Longrightarrow\quad\mu=0$

holds, which is inherent whenever $\mathcal{H}$ is metrically regular at
$((\bar{z},\lambda),(0,0))$. Then $\bar{z}$ is fuzzily M-stationary. If,
additionally, (Inc$(\lambda)$) holds for each $\lambda\in K(\bar{z})$, then
$\bar{z}$ is explicitly M-stationary.

  2. (b)

Assume that (Inc$(\lambda)$) holds for each $\lambda\in K(\bar{z})$ and let

(4.8) $\xi\in D^{*}F(\bar{z},\lambda)(\mu),\,(-\xi,\mu)\in
D^{*}G((\bar{z},\lambda),0)(0)\quad\Longrightarrow\quad\mu=0$

be valid for each $\lambda\in K(\bar{z})$ which is inherent whenever $G$
posseses the Aubin property at $((\bar{z},\lambda),0)$ for each $\lambda\in
K(\bar{z})$. Then $\bar{z}$ is explicitly M-stationary.

  3. (c)

Assume that

(4.9) $\xi\in D^{*}F(\bar{z},\lambda)(\mu),\,(-\xi,\mu)\in
D^{*}G((\bar{z},\lambda),0)(0)\quad\Longrightarrow\quad\xi,\mu=0$

is valid for each $\lambda\in K(\bar{z})$ which is inherent whenever $G$
posseses the Aubin property at $((\bar{z},\lambda),0)$ for each $\lambda\in
K(\bar{z})$. Then $\bar{z}$ is explicitly M-stationary.

######  Proof 4.26.

Let us start with the proof of statement (a). The relation between the
coderivatives of $\mathcal{H}$ and $\widehat{\mathcal{H}}$, which has been
discussed above Proposition 4.24, yields

$\ker
D^{*}\widehat{\mathcal{H}}((\bar{z},0,\lambda),(0,0))=\bigl{\\{}(\mu,0)\,\big{|}\,(\mu,0)\in\ker
D^{*}\mathcal{H}((\bar{z},\lambda),(0,0))\bigr{\\}}$

for each $\lambda\in K(\bar{z})$. Thus, the constraint qualification (4.7)
implies metric regularity of $\widehat{\mathcal{H}}$ at the point
$((\bar{z},0,\lambda),(0,0))$ for each $\lambda\in K(\bar{z})$ by means of the
Mordukhovich criterion. Thus, the assertion follows from Proposition 4.24. For
the proof of (b), we observe that due to validity of (Inc$(\lambda)$) for each
$\lambda\in K(\bar{z})$, (4.8) implies (4.7) for each $\lambda\in K(\bar{z})$,
i.e., the assertion follows from statement (a). Finally, (c) follows from (b)
observing that (4.9) implies validity of (4.8) as well as (Inc$(\lambda)$) by
means of Remark 4.22.

Let us mention that, in general, explicitly M-stationary points do not need to
be implicitly M-stationary, see e.g. Section 5.3 and [44, Section 4] where
this issue is visualized in the context of cardinality- and or-constrained
programming, respectively.

As a consequence of Propositions 4.15, 4.24 and 4.23, we obtain the following
constraint qualifications which guarantee that a given local minimizer of (P)
is explicitly M-stationary.

######  Theorem 4.27.

Let $\bar{z}\in\mathbb{R}^{n}$ be a local minimizer of (P) and consider the
following assumptions:

  1. (a)

$H_{M}$ is metrically subregular at $(\bar{z},(0,0))$, $\widehat{K}$ is inner
semicompact at $(\bar{z},0)$ w.r.t. $\operatorname{dom}\widehat{K}$, and for
each $\lambda\in K(\bar{z})$, $\widehat{\mathcal{H}}$ is metrically subregular
at $((\bar{z},0,\lambda),(0,0))$ while the inclusion (Inc$(\lambda)$) holds,

  2. (b)

$H_{M}$ is metrically subregular at $(\bar{z},(0,0))$, the mapping defined in
(4.4) is inner semicompact at $(\bar{z},0)$ w.r.t. its domain, and for each
$\lambda\in K(\bar{z})$, the mapping defined in (4.5) is metrically subregular
at $((\bar{z},0,\bar{z},\lambda),(0,0,0))$,

  3. (c)

$\mathcal{H}_{M}$ is metrically subregular at
$((\bar{z},\bar{\lambda}),(0,0,0))$ for some $\bar{\lambda}\in K(\bar{z})$ and
the inclusion (Inc$(\bar{\lambda})$) holds,

  4. (d)

$\mathfrak{H}_{M}$ is metrically subregular at
$((\bar{z},\bar{\lambda}),((0,0),(0,0,0),0))$ for some $\bar{\lambda}\in
K(\bar{z})$.

Then each of (a), (b), (c), and (d) implies that $\bar{z}$ is explicitly
M-stationary.

Once more, let us emphasize that validity of the inclusion (Inc$(\lambda)$)
can be guaranteed under not too restrictive conditions which can be found in
Lemmas 3.6 and 3.7, see Remark 4.22 as well.

In Section 4.3, we will see that the most essential ingredients from Theorem
4.27 are the metric subregularity assumptions on $H_{M}$, $\mathcal{H}_{M}$,
and $\mathfrak{H}_{M}$, respectively, while the other requirements can often
be guaranteed by simpler structure of the problem or by suitable qualification
conditions.

A general purpose of necessary optimality conditions is to shrink the feasible
set down to a (hopefully) small number of points which are potential
candidates for local minimizers. Since we are interested in finding local
minimizers $\bar{z}\in\mathbb{R}^{n}$ of (P) even if (Q) is under
consideration, Theorem 4.8 underlines that validity of explicit M-stationarity
w.r.t.  _each_ $\bar{\lambda}\in K(\bar{z})$ is desirable for that purpose
since this corresponds to standard M-stationarity for (Q) at its local
minimizers $(\bar{z},\bar{\lambda})$ under mild assumptions, see Remark 4.22
again. In order to infer this directly from (Q), one has to impose metric
subregularity of $\mathfrak{H}_{M}$ at all points
$((\bar{z},\bar{\lambda}),((0,0),(0,0,0),0))$ such that $\bar{\lambda}\in
K(\bar{z})$ holds. Postulating that the intermediate mapping $\widehat{K}$
from (4.3) is inner semicompact w.r.t. $\operatorname{dom}\widehat{K}$ at
$(\bar{z},0)$ (which is inherent in several underlying applications),
Propositions 4.18 and 4.20 guarantee that $H_{M}$ is metrically subregular at
$(\bar{z},(0,0))$. Due to Proposition 4.15, this is already enough to ensure
that the local minimizer $\bar{z}$ of (P) is implicitly M-stationary. In this
regard, the constraint qualifications one has to impose on (Q) in order to
find potential candidates for local minimizers of (P) via the associated
M-stationarity conditions are in several situations not weaker than the
constraint qualifications one has to impose directly on (P) in order to infer
implicit M-stationarity as a necessary optimality condition. In the context of
bilevel optimization, the counterexamples in [1, Section 3.1] depict that the
converse statement of Proposition 4.18 does not hold in general. This also
shows that, in some situations, the conditions in statement (a) of Theorem
4.27 might be weaker than the condition from statement (d) (but for all
$\bar{\lambda}\in K(\bar{z})$) in this regard. Let us sum up some important
points:

  1. (i)

it may happen that $\bar{z}$ is implicitly M-stationary while it is _not_
explicitly M-stationary w.r.t.  _all_ elements of $K(\bar{z})$ (in case where
the chain rule is applicable in order to compute the coderivative of $H$, one
can only ensure explicit M-stationarity w.r.t. those implicit variables which
are _active_ in the union appearing in the chain rule), however, under mild
assumptions, explicit M-stationarity for _some_ instance of the implicit
variable can be derived,

  2. (ii)

if $\bar{z}$ is a local minimizer of (P), then due to Theorem 4.8, explicit
M-stationarity w.r.t.  _all_ elements of $K(\bar{z})$ is a reasonable
necessary optimality condition for (P) (under suitable constraint
qualifications), and

  3. (iii)

the constraint qualifications needed to infer implicit M-stationarity of a
local minimizer $\bar{z}$ of (P) ($H_{M}$ metrically subregular at some
reference point) and to obtain explicit M-stationarity from that, see
Propositions 4.23 and 4.24 as well as Corollary 4.25, might still be weaker
than the constraint qualifications needed to infer explicit M-stationarity
w.r.t.  _all_ $\bar{\lambda}\in K(\bar{z})$ directly from (Q).

These observations underline that although the use of implicit variables as
explicit ones might be beneficial for computational purposes, this
transformation is disadvantageous since it comes for the price of additional
artificial local minimizers and potentially stronger constraint
qualifications. Instead of treating implicit variables as explicit ones, one
should keep them implicit while exploiting the inherent underlying problem
structure as long as possible in order to infer reasonably weak constraint
qualifications ensuring validity of useful necessary optimality conditions at
local minimizers.

Let us mention some positive features of implicit variables regarding
optimality conditions. Clearly, whenever we are given some
$\tilde{z}\in\mathbb{R}^{n}$ feasible to (P) and some $\tilde{\lambda}\in
K(\tilde{z})$ such that $\mathfrak{H}_{M}$ is metrically subregular at
$((\tilde{z},\tilde{\lambda}),((0,0),(0,0,0),0))$ while $\tilde{z}$ is _not_
explicitly M-stationary w.r.t. $\tilde{\lambda}$, then $\tilde{z}$ cannot be a
local minimizer of (P), see Proposition 4.15. This means that implicit
variables can be used to infer suboptimality conditions for (P). Secondly, let
us mention that it might happen that a practically _useful_ representation of
the coderivative of $H$ is not available for some underlying applications
while the computation of the coderivative of $F$ and $G$ might be possible in
terms of initial problem data, see e.g. Section 5.2. Then the explicit
M-stationarity conditions of (P) might be applicable while the implicit
counterpart is of limited practical use. Of course, under rather mild
assumptions one can estimate the coderivative of $H$ via the coderivatives of
$F$ and $G$, but this is not completely for free in general.

###  4.3 Necessary optimality conditions under additional structural
assumptions

In this section, we show how the situation from Section 4.2 simplifies in
specific settings that cover our example problems from Section 2. To this end,
we impose that the following assumption on the problem data holds throughout
the section.

######  Assumption 4.28.

The set $\operatorname{gph}H$ is closed, and the problem data satisfies one of
the following assumptions on the set-valued mapping $G$:

  1. (i)

$G(z,\lambda):=g(z,\lambda)-\Theta$ holds for all $z\in\mathbb{R}^{n}$ and
$\lambda\in\mathbb{R}^{m}$ where
$g\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}^{s}$ is a continuously
differentiable function and $\Theta\subset\mathbb{R}^{s}$ is a closed set,

  2. (ii)

$G(z,\lambda):=\widetilde{G}(\lambda)+\tilde{g}(z)$ holds for all
$z\in\mathbb{R}^{n}$ and $\lambda\in\mathbb{R}^{m}$ where
$\widetilde{G}\colon\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{s}$ is a set-
valued mapping with a closed graph and
$\tilde{g}\colon\mathbb{R}^{n}\to\mathbb{R}^{s}$ is a continuously
differentiable function.

Let us point out that (i) covers the setting of bilevel programming from (2.1)
as well as the setting of cardinality-constrained optimization from (2.5),
while (ii) covers the setting of evaluated multiobjective programming from
(2.2).

Statements (a) and (b) of Lemma 3.7 yield that the inclusion (Inc$(\lambda)$)
holds with equality under any of the assumptions (i) or (ii). Thus, due to
Remark 4.22, fuzzy M-stationarity in fact coincides with explicit
M-stationarity and so we can work only with the latter. Particularly, we will
only consider the implicit and explicit M-stationarity conditions with the
respective constraint qualification being metric subregularity of $H_{M}$ and
$\mathcal{H}_{M}$.

For the remaining part, let us add the inner semicompactness of $\widehat{K}$
w.r.t. $\operatorname{dom}\widehat{K}$ at $(\bar{z},0)$ for some feasible
point $\bar{z}\in\mathbb{R}^{n}$ of (P) to the standing assumption. Then the
comparison of the metric subregularity conditions reduces to simply saying
that $H_{M}$ is metrically subregular at $(\bar{z},(0,0))$ provided
$\mathcal{H}_{M}$ is metrically subregular at $((\bar{z},\lambda),(0,0,0))$
for all $\lambda\in K(\bar{z})$, see Proposition 4.18.

Finally, we discuss when implicit M-stationarity implies explicit
M-stationarity. Again, the statements (a) and (b) of Lemma 3.7 show that there
is now no problem with the computation of the coderivative of the mapping
$\mathcal{H}$ and the same applies to the mapping $\widehat{\mathcal{H}}$ from
(4.6) due to the arguments above Proposition 4.24. Particularly, we infer that
$\widehat{\mathcal{H}}$ is metrically regular at $((\bar{z},0,\lambda),(0,0))$
for $\lambda\in K(\bar{z})$ if and only if the constraint qualification (4.8)
is valid. One can check that the latter is inherently satisfied in the setting
(i) since $G$ possesses the Aubin property in this case. If (ii) holds, (4.8)
boils down to

$\ker D^{*}F(\bar{z},\lambda)\cap
D^{*}\widetilde{G}(\lambda,-\tilde{g}(\bar{z}))(0)=\\{0\\}.$

We sum up all these arguments in the following proposition.

######  Proposition 4.29.

Let $\bar{z}\in\mathbb{R}^{n}$ be implicitly M-stationary for problem (P) and
let $\widehat{K}$ be inner semicompact w.r.t. $\operatorname{dom}\widehat{K}$
at $(\bar{z},0)$. Then the following assertions hold.

  1. (a)

Let $G$ be given as stated in (i). Then $\bar{z}$ is explicitly M-stationary,
i.e., there exist $\bar{\lambda}\in K(\bar{z})$ and
$\nu\in\mathcal{N}_{\Theta}(g(\bar{z},\bar{\lambda}))$ such that

$0\in\partial
f(\bar{z})+D^{*}F(\bar{z},\bar{\lambda})(\nabla_{\lambda}g(\bar{z},\bar{\lambda})^{\top}\nu)+\nabla_{z}g(\bar{z},\bar{\lambda})^{\top}\nu+\mathcal{N}_{M}(\bar{z}).$

  2. (b)

Let $G$ be given as stated in (ii) and let $\widehat{\mathcal{H}}$ be
metrically subregular at $((\bar{z},0,\lambda),(0,0))$ for each $\lambda\in
K(\bar{z})$. Then $\bar{z}$ is explicitly M-stationary, i.e., there exist
$\bar{\lambda}\in K(\bar{z})$ and $\nu\in\mathbb{R}^{s}$ such that

$0\in\partial f(\bar{z})+\bigl{(}D^{*}F(\bar{z},\bar{\lambda})\circ
D^{*}\widetilde{G}(\bar{\lambda},-\tilde{g}(\bar{z}))\bigr{)}(\nu)+\nabla\tilde{g}(\bar{z})^{\top}\nu+\mathcal{N}_{M}(\bar{z}).$

The above proposition shows that in the setting (i) from 4.28, one only has to
impose metric subregularity of $H_{M}$ at some reference point
$(\bar{z},(0,0))$, where $\bar{z}$ is a local minimizer of (P), and some inner
semicompactness of $\widehat{K}$ in order to come up with fully explicit
optimality conditions in terms of initial problem data. In the setting (ii),
an additional metric subregularity requirement on $\widehat{\mathcal{H}}$ is
necessary for that purpose. As we will see, inner semicompactness of
$\widehat{K}$ is inherent under reasonable assumptions in the context of the
problem settings from Section 2. Thus, one might be tempted to say that in any
of the settings from 4.28, an implicitly M-stationary point of (P) is likely
to be explicitly M-stationary w.r.t. at least one choice of the implicit
variable.

###  4.4 Convexity and sufficient optimality conditions

We want to close our theoretical analysis of the abstract model (P) with a
brief look at sufficient optimality conditions in the presence of convexity.
More precisely, we investigate the problem of interest under the subsequently
stated standing assumption.

######  Assumption 4.30.

Let $f$ be a convex function, let $F$ and $G$ be convex set-valued mappings,
and let $M$ be a convex set.

As we already mentioned in Corollary 4.7, 4.30 ensures that $H$ is convex as
well. Observing that the graphs of $F$, $G$, and $H$ are convex, their
coderivatives are given via the normal cone in the sense of convex analysis.
That is why we obtain the following result.

######  Theorem 4.31.

Let $\bar{z}\in\mathbb{R}^{n}$ be an implicitly, fuzzily, or explicitly
M-stationary point of (P). Then $\bar{z}$ is a minimizer of (P).

######  Proof 4.32.

We only show the statement for explicitly M-stationary points. The remaining
assertions can be derived similarly.
Let $\bar{z}$ be explicitly M-stationary. Then we find $\bar{\lambda}\in
K(\bar{z})$, $\mu\in\mathbb{R}^{m}$, and $\nu\in\mathbb{R}^{s}$ as well as
$\xi_{1}\in\partial f(\bar{z})$, $\xi_{2}\in
D^{*}F(\bar{z},\bar{\lambda})(\mu)$, $(\xi_{3},\mu)\in
D^{*}G((\bar{z},\bar{\lambda}),0)(\nu)$, and
$\xi_{4}\in\mathcal{N}_{M}(\bar{z})$ with $0=\xi_{1}+\xi_{2}+\xi_{3}+\xi_{4}$.
For each $(z,\lambda)\in\tilde{Z}$, we obtain

$\displaystyle f(z)$ $\displaystyle\geq
f(\bar{z})+\xi_{1}^{\top}(z-\bar{z})=f(\bar{z})-\xi_{2}^{\top}(z-\bar{z})-\xi_{3}^{\top}(z-\bar{z})-\xi_{4}^{\top}(z-\bar{z})$
$\displaystyle\geq
f(\bar{z})-\xi_{2}^{\top}(z-\bar{z})-(-\mu)^{\top}(\lambda-\bar{\lambda})-\xi_{3}^{\top}(z-\bar{z})-\mu^{\top}(\lambda-\bar{\lambda})-(-\nu)^{\top}(0-0)$
$\displaystyle\geq f(\bar{z})$

by definition of the subdifferential and the normal cone in the sense of
convex analysis. This shows that $(\bar{z},\bar{\lambda})$ is a global
minimizer of (Q), i.e., $\bar{z}$ is a global minimizer of (P) due to Theorem
4.5.

##  5 Consequences for certain problem classes

In this section, we discuss some of the results obtained in Section 4 by means
of the example problems introduced in Section 2.

###  5.1 Bilevel programming

In this section, we take a look back at the bilevel programming problem (BPP)
from Section 2.1. Throughout the section, the following additional standing
assumption may hold.

######  Assumption 5.1.

The lower level feasibility mapping $y\rightrightarrows g(y)-C$ is metrically
subregular at all points $(y,0)$ belonging to its graph.

Clearly, the requirements from 5.1 are inherent whenever a Robinson-type
constraint qualification holds at all lower level feasible points. In case
$C:=\mathbb{R}^{m}_{-}$, this amounts to validity of MFCQ at all points from
$\Gamma$. However, in many situations, the metric subregularity assumption
from 5.1 might be weaker.

Consulting Section 3.2 and [53, Theorem 6.14], we find that the pre-image
formula

$\widehat{\mathcal{N}}_{\Gamma}(y)=\nabla
g(y)^{\top}\widehat{\mathcal{N}}_{C}(g(y))=\nabla
g(y)^{\top}\bigl{[}C^{\circ}\cap g(y)^{\perp}\bigr{]}$

holds for all $y\in\Gamma$. Thus, the associated intermediate mapping
$K\colon\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}\rightrightarrows\mathbb{R}^{m}$
is given by

$\displaystyle K(x,y)=\bigl{\\{}\lambda\in
C^{\circ}\,\big{|}\,\nabla_{y}j(x,y)+\nabla
g(y)^{\top}\lambda=0,\,\lambda^{\top}g(y)=0\bigr{\\}}$

which is nothing else but the so-called Lagrange multiplier mapping associated
with (LL). Keeping Proposition 3.3 and the continuity of
$\nabla_{y}j(\cdot,\cdot)$ in mind, $K$ is inner semicompact w.r.t. its domain
everywhere. Thus, our Theorems 4.5 and 4.8 recover the results obtained in
[20, 22] under validity of weaker constraint qualifications at the lower
level. Indeed, we do not exploit the local boundedness of the intermediate
mapping $K$, which was the key idea in the latter papers, but only its inner
semicompactness. For that purpose, metric subregularity of the feasibility
mapping is enough. Let us inspect the assertion of Corollary 4.10 in the light
of the present setting. Therefore, we fix a point
$((\bar{x},\bar{y}),\bar{\lambda})\in\operatorname{gph}K$. Relying on [14,
Lemma 4.44, Proposition 4.47] and observing that $C$ is a cone, we obtain that
$K$ is inner semicontinuous at $((\bar{x},\bar{y}),\bar{\lambda})$ if the
condition

(5.1) $\nabla
g(\bar{y})^{\top}\lambda=0,\,\lambda^{\top}g(\bar{y})=0,\,\lambda\in(C\cap\bar{\lambda}^{\perp})^{\circ}\quad\Longrightarrow\quad\lambda=0$

is valid. Actually, this already implies
$K(\bar{x},\bar{y})=\\{\bar{\lambda}\\}$ and that $K$ is so-called locally
upper Lipschitz continuous at $(\bar{x},\bar{y})$, see [14, Section 2.3] for a
definition. In general, (5.1) is more restrictive than validity of GMFCQ at
$\bar{y}$. Noting that (5.1) depends on the multiplier $\bar{\lambda}$ and,
thus, implicitly on the objective function $j$, this condition is not a
constraint qualification in the narrower sense. In the setting of standard
nonlinear programming, i.e., where $C:=\mathbb{R}_{-}^{m}$ holds, (5.1) is
referred to as the _strict Mangasarian–Fromovitz condition_ which is known to
be the weakest condition implying uniqueness of Lagrange multipliers, see
[55]. In the more general setting where $C$ is a polyhedral, convex cone,
(5.1) is implied by the so-called _non-degeneracy_ condition

$\displaystyle\nabla
g(\bar{y})^{\top}\lambda=0,\,\lambda\in\bigl{(}C^{\circ}\cap
g(\bar{y})^{\perp}-C^{\circ}\cap
g(\bar{y})^{\perp}\bigr{)}\quad\Longrightarrow\quad\lambda=0$

which corresponds to the prominent _linear independence constraint
qualification_ (LICQ) in standard nonlinear programming. It can be distilled
from [20, Theorem 3.2] that a bilevel optimization problem and its
reformulated single-level counterpart, where lower level multipliers are
treated as explicit variables, are equivalent w.r.t. local minimizers whenever
LICQ is valid at each point which is feasible for the lower level problem. In
this regard, the above observations provide another generalization of the
results from [20]. Let us also mention that if $C$ is polyhedral, we can
actually obtain stronger properties of $K$ which correspond to inner
semicontinuity and inner semicompactness but with linear rate of change
(called inner calmness and inner calmness*, respectively, in [6, 9], where
more details can be found).

Recalling the setting from (2.1), we have
$H(z):=\nabla_{y}j(z)+\widehat{\mathcal{N}}_{\Gamma}(y)$ for all $z:=(x,y)$.
In this regard, the implicit M-stationarity conditions of (BPP) at some
feasible point $\bar{z}:=(\bar{x},\bar{y})$ reduce to the existence of
$\nu\in\mathbb{R}^{n_{2}}$ such that

$(0,0)\in\partial f(\bar{z})+\nabla^{2}_{yz}j(\bar{z})^{\top}\nu+\\{0\\}\times
D^{*}\widehat{\mathcal{N}}_{\Gamma}(\bar{y},-\nabla_{y}j(\bar{z}))(\nu)+\mathcal{N}_{S}(\bar{x})\times\\{0\\}.$

Some recent progress in the field of variational analysis even allows to
calculate or estimate the appearing coderivative of the normal cone mapping
$\widehat{\mathcal{N}}_{\Gamma}\colon\mathbb{R}^{n_{2}}\rightrightarrows\mathbb{R}^{n_{2}}$
in terms of initial data under suitable assumptions, see e.g. [31, 32, 34]. On
the other hand, the explicit M-stationarity conditions of (BPP) reduce to the
existence of $\bar{\lambda}\in K(\bar{z})$ and $\nu\in\mathbb{R}^{n_{2}}$
which satisfy

$\displaystyle(0,0)$ $\displaystyle\in\partial
f(\bar{z})+\nabla^{2}_{yz}j(\bar{z})^{\top}\nu+\bigl{\\{}\bigl{(}0,\sum\nolimits_{i=1}^{m}\bar{\lambda}_{i}\nabla^{2}g_{i}(\bar{y})\nu\bigr{)}\bigr{\\}}$
$\displaystyle\qquad+\\{0\\}\times D^{*}(\widehat{\mathcal{N}}_{C}\circ
g)(\bar{y},\bar{\lambda})(\nabla
g(\bar{y})\nu)+\mathcal{N}_{S}(\bar{x})\times\\{0\\},$

see statement (a) of Proposition 4.29. Above,
$g_{1},\ldots,g_{m}\colon\mathbb{R}^{n_{2}}\to\mathbb{R}$ denote the component
functions of $g$. Naturally, this stationarity system might be deduced
directly from the above system of implicit M-stationarity with the aid of the
chain rule from Lemma 3.4. Consulting Proposition 3.3 once more, however, we
see that the intermediate mapping $\widehat{K}$ from (4.3), which takes the
form

$\widehat{K}((x,y),w)=\bigl{\\{}\lambda\in
C^{\circ}\,\big{|}\,-w+\nabla_{y}j(x,y)+\nabla
g(y)^{\top}\lambda=0,\,\lambda^{\top}g(y)=0\bigr{\\}},$

is also inner semicompact w.r.t. its domain at all points
$((\bar{x},\bar{y}),0)$ that satisfy the relation
$(\bar{x},\bar{y})\in\operatorname{dom}K$. In this regard, statement (a) of
Proposition 4.29 guarantees that each implicitly M-stationary point of (BPP)
is automatically explicitly M-stationary as well. This observation generalizes
the classical results from [49].

Note that the coderivative of $\widehat{\mathcal{N}}_{C}\circ g$ might be
computed or estimated using again a suitable chain rule while observing that
the associated intermediate mapping from (3.2) is naturally inner
semicontinuous w.r.t. its domain at each point of its graph by continuity of
$g$. This way, one might be tempted to call the stationarity system

$\displaystyle(0,0)$ $\displaystyle\in\partial
f(\bar{z})+\nabla^{2}_{yz}j(\bar{z})^{\top}\nu+\bigl{\\{}\bigl{(}0,\sum\nolimits_{i=1}^{m}\bar{\lambda}_{i}\nabla^{2}g_{i}(\bar{y})\nu\bigr{)}\bigr{\\}}$
$\displaystyle\qquad+\\{0\\}\times\nabla
g(\bar{y})^{\top}D^{*}\widehat{\mathcal{N}}_{C}(g(\bar{y}),\bar{\lambda})(\nabla
g(\bar{y})\nu)+\mathcal{N}_{S}(\bar{x})\times\\{0\\}$

the _fully_ explicit M-stationarity system of (BPP) (w.r.t. $\bar{\lambda}$).
We want to point out that this system can be written equivalently as

$\displaystyle(0,0)\in\partial
f(\bar{z})+\nabla^{2}_{yz}j(\bar{z})^{\top}\nu+\bigl{\\{}\bigl{(}0,\sum\nolimits_{i=1}^{m}\bar{\lambda}_{i}\nabla^{2}g_{i}(\bar{y})\nu+\nabla
g(\bar{y})^{\top}\mu\bigr{)}\bigr{\\}}+\mathcal{N}_{S}(\bar{x})\times\\{0\\}$
$\displaystyle(\mu,-\nabla
g(\bar{y})\nu)\in\mathcal{N}_{\operatorname{gph}{\widehat{\mathcal{N}}_{C}}}(g(\bar{y}),\bar{\lambda}),$

corresponding to the M-stationarity system of the optimization problem

(5.2) $\displaystyle f(x,y)$ $\displaystyle\,\to\,\min\limits_{x,y,\lambda}$
$\displaystyle x$ $\displaystyle\,\in\,S$
$\displaystyle\nabla_{y}j(x,y)+\nabla g(y)^{\top}\lambda$
$\displaystyle\,=\,0$ $\displaystyle(g(y),\lambda)$
$\displaystyle\,\in\,\operatorname{gph}\widehat{\mathcal{N}}_{C}.$

Observing that $C$ is a convex cone, we have

$\operatorname{gph}\widehat{\mathcal{N}}_{C}=\bigl{\\{}(a,b)\in C\times
C^{\circ}\,\big{|}\,a^{\top}b=0\bigr{\\}},$

and this motivates us to call (5.2) a generalized _mathematical problem with
complementarity constraints_ , see [29, Section 4] or [56]. Following the
above arguments and keeping Section 3.2 in mind, we obtain the following
result.

######  Corollary 5.2.

Let $\bar{z}:=(\bar{x},\bar{y})\in\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}$
be a local minimizer of (BPP) and assume that, for some $\bar{\lambda}\in
K(\bar{z})$, the mapping

$(x,y,\lambda)\rightrightarrows\left(x-S,\nabla_{y}j(x,y)+\nabla
g(y)^{\top}\lambda,(g(y),\lambda)-\operatorname{gph}\widehat{\mathcal{N}}_{C}\right)$

is metrically subregular at $((\bar{x},\bar{y},\bar{\lambda}),(0,0,(0,0)))$.
Then $\bar{z}$ is fully explicitly M-stationary for (BPP) w.r.t.
$\bar{\lambda}$.

Using the above terminology, we would like to mention that the authors in [1]
discussed the implicit and fully explicit M-stationarity conditions of (BPP)
in case $C:=\mathbb{R}^{m}_{-}$. They came up with refined conditions ensuring
that the feasibility mapping from Corollary 5.2 is indeed metrically
subregular at some reference point, see [1, Theorem 8]. From the viewpoint of
applicability, the system of fully explicit M-stationarity might be the most
useful one among the stated ones since the appearing coderivative of the
normal cone mapping $\widehat{\mathcal{N}}_{C}$ is computable in some
situations where the set $C$ is _simple_ , see e.g. the proof of [24, Theorem
2] and [33, Theorem 2.12]. Let us mention that yet another M-stationarity-type
system associated with (BPP) has been derived in the recent paper [36].

###  5.2 Evaluating weakly efficient points in multicriteria optimization

Let us consider (EMOP) under the assumptions from Section 2.2. Particularly,
we consider problem (P) with the setting from (2.2). The associated
intermediate mapping $K\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$
reads as

$\forall z\in\mathbb{R}^{n}\colon\quad
K(z)=\\{\lambda\in\Delta\,|\,z\in\Psi(\lambda)\\}.$

The subsequent lemma provides essential foundations of our analysis.

######  Lemma 5.3.

The mapping $G$ from (2.2) possesses a closed graph while $K$ from above is
inner semicompact w.r.t. its domain everywhere.

######  Proof 5.4.

First, we show that $G$ possesses a closed graph. Choose sequences
$\\{z_{k}\\}_{k\in\mathbb{N}}\subset\mathbb{R}^{n}$,
$\\{\lambda_{k}\\}_{k\in\mathbb{N}}\subset\mathbb{R}^{m}$, and
$\\{w_{k}\\}_{k\in\mathbb{N}}\subset\mathbb{R}^{n}$ such that $z_{k}\to z$,
$\lambda_{k}\to\lambda$, and $w_{k}\to w$ for some $z\in\mathbb{R}^{n}$,
$\lambda\in\mathbb{R}^{m}$, and $w\in\mathbb{R}^{n}$ are valid while $w_{k}\in
G(z_{k},\lambda_{k})$ holds for all $k\in\mathbb{N}$. Particularly, we find
$\\{\lambda_{k}\\}_{k\in\mathbb{N}}\subset\Delta$ and
$z_{k}+w_{k}\in\Psi(\lambda_{k})$, i.e.,

$\forall k\in\mathbb{N},\,\forall
z^{\prime}\in\Gamma\colon\quad\lambda_{k}^{\top}j(z_{k}+w_{k})\leq\lambda_{k}^{\top}j(z^{\prime})$

and $z_{k}+w_{k}\in\Gamma$ for all $k\in\mathbb{N}$. Taking the limit
$k\to\infty$ and observing that $j$ is continuous while $\Gamma$ and $\Delta$
are closed, we infer $z+w\in\Gamma$ and
$\lambda^{\top}j(z+w)\leq\lambda^{\top}j(z^{\prime})$ for all
$z^{\prime}\in\Gamma$. This yields $z+w\in\Psi(\lambda)$ which equals $w\in
G(z,\lambda)$, i.e., $((z,\lambda),w)\in\operatorname{gph}G$. Particularly,
$\operatorname{gph}G$ is closed.

By definition, $F$ is locally bounded everywhere which is why the lemma’s
assertion regarding $K$ follows directly from Lemma 4.3.

Now, Theorems 4.5 and 4.8 can be used to infer the precise relationship
between (EMOP) and its associated counterpart (Q) w.r.t. global and local
minimizers, respectively. Related results can be obtained in the slightly more
general context of _semivectorial_ bilevel programming where the lower level
decision maker has to solve a multiobjective optimization problem, see [23].

Let us now focus on optimality conditions for (EMOP). Clearly, the associated
implicit M-stationarity conditions take the form

$0\in\partial f(\bar{z})+\mathcal{N}_{\Gamma_{\textup{we}}}(\bar{z})$

for an arbitrary feasible point $\bar{z}\in\mathbb{R}^{n}$. However, these
conditions are of limited practical use due to an essential lack of knowledge
regarding the variational geometry of $\Gamma_{\textup{we}}$. On the other
hand, invoking Proposition 4.29, we find that the explicit M-stationarity
conditions of (EMOP) take the following form: there exist $\bar{\lambda}\in
K(\bar{z})$ and $\nu\in\mathbb{R}^{n}$ such that

$\nu\in\partial f(\bar{z}),\qquad 0\in
D^{*}\Psi(\bar{\lambda},\bar{z})(\nu)+\mathcal{N}_{\Delta}(\bar{\lambda}).$

Taking into account that

$\forall\lambda\in\Delta\colon\quad\Psi(\lambda)=\left\\{z\in\mathbb{R}^{n}\,\middle|\,0\in\nabla
j(z)^{\top}\lambda+\widehat{\mathcal{N}}_{\Gamma}(z)\right\\}$

holds, we refer to [25, 33] for a broader view on solution mappings of
parametrized variational systems and estimates of their generalized
derivatives. Particularly, in case where $j$ is twice continuously
differentiable, we obtain the additional estimate

$D^{*}\Psi(\bar{\lambda},\bar{z})(\nu)\subset\left\\{\nabla
j(\bar{z})\mu\,\middle|\,-\nu\in\sum\nolimits_{i=1}^{m}\bar{\lambda}_{i}\nabla^{2}j_{i}(\bar{z})\mu+D^{*}\widehat{\mathcal{N}}_{\Gamma}\bigl{(}\bar{z},-\nabla
j(\bar{z})^{\top}\bar{\lambda}\bigr{)}(\mu)\right\\}+\mathcal{N}_{\Delta}(\bar{\lambda})$

applying the pre-image rule to

$\operatorname{gph}\Psi=\left\\{(\lambda,z)\,\middle|\,(z,-\nabla
j(z)^{\top}\lambda,\lambda)\in\operatorname{gph}\widehat{\mathcal{N}}_{\Gamma}\times\Delta\right\\}$

which is possible whenever the feasibility mapping
$(\lambda,z)\rightrightarrows(z,-\nabla
j(z)^{\top}\lambda,\lambda)-\operatorname{gph}\widehat{\mathcal{N}}_{\Gamma}\times\Delta$
is metrically subregular at $((\bar{\lambda},\bar{z}),(0,0,0))$, see Section
3.2. The coderivative of the normal cone mapping associated with $\Gamma$ can
be estimated from above in several interesting situations covering the setting
where $\Gamma$ is the pre-image of a closed and convex (polyhedral) set under
a sufficiently smooth mapping, see the references mentioned in Section 5.1.
Using a related approach, fully explicit necessary optimality condition for
semivectorial bilevel optimization problems are derived in [59].

Observing that $F$ and $G$ are metrically subregular mappings in the present
setting (2.2), metric subregularity of the mapping
$\widetilde{\Sigma}\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{m}\times\mathbb{R}^{m+n}$
given by

$\forall
z\in\mathbb{R}^{n},\,\forall\lambda\in\mathbb{R}^{m}\colon\quad\widetilde{\Sigma}(z,\lambda):=\bigl{(}\lambda-\Delta\bigr{)}\times\bigl{(}(\lambda,z)-\operatorname{gph}\Psi\bigr{)}$

at $((\bar{z},\bar{\lambda}),(0,(0,0)))$ for some $\bar{\lambda}\in
K(\bar{z})$ is already enough to obtain that the associated mapping
$\mathcal{H}_{M}$ is metrically subregular at
$((\bar{z},\bar{\lambda}),(0,0))$, see Lemma 3.8. Note that
$\widetilde{\Sigma}$ results from the mapping $\Sigma$ given in Lemma 3.8 by
deleting the trivial factor $\mathbb{R}^{n}$ which does not influence the
metric subregularity property. In the presence of this metric subregularity,
$\bar{z}$ is an explicitly M-stationary point of (EMOP) provided $\bar{z}$ is
a local minimizer of this program, see Proposition 4.15 and the arguments in
Section 4.3.

###  5.3 Cardinality-constrained programming

Finally, we investigate the setting of cardinality-constrained optimization
from Section 2.3. In the context of (2.5), the mapping
$K\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is given by

$\forall z\in\mathbb{R}^{n}\colon\quad
K(z)=\left\\{\lambda\in[0,1]^{n}\,\middle|\,\sum\nolimits_{i\in
I^{0}(z)}\lambda_{i}\geq n-\kappa,\,\forall i\in
I^{\pm}(z)\colon\,\lambda_{i}=0\right\\}$

where we used

$I^{\pm}(z):=\\{i\in\\{1,\ldots,n\\}\,|\,z_{i}\neq 0\\},\qquad
I^{0}(z):=\\{i\in\\{1,\ldots,n\\}\,|\,z_{i}=0\\}$

for arbitrary $z\in\mathbb{R}^{n}$. Obviously, $K$ is locally bounded and,
thus, inner semicompact w.r.t. the set
$\operatorname{dom}K=\\{z\in\mathbb{R}^{n}\,|\,\left\|z\right\|_{0}\leq\kappa\\}$
at all points of its domain. The images of $K$ are polytopes (i.e., bounded
polyhedrons). Furthermore, $K(z)$ is a singleton if and only if $z$ satisfies
$\left\|z\right\|_{0}=\kappa$. In this regard, Theorem 4.5 recovers [17,
Theorem 3.2]. On the other hand, the results [17, Proposition 3.5, Theorem
3.6] are consequences of Theorem 4.8. However, our result even applies to
settings where $\left\|z\right\|_{0}<\kappa$ is valid, and, thus, clarifies
the situation in [17, Examples 1 and 2].

Let us mention first that due to the arguments from Section 2.3, the mapping
$H$ takes the form $z\rightrightarrows D_{\kappa}-z$ in the situation at hand,
see (2.3), and we note that it is polyhedral by nature of $D_{\kappa}$ (since
$D_{\kappa}$ is the union of finitely many convex, polyhedral sets). The
implicit M-stationarity conditions of (CCMP) w.r.t. a feasible point
$\bar{z}\in\mathbb{R}^{n}$ are given by

$0\in\partial
f(\bar{z})+\mathcal{N}_{D_{\kappa}}(\bar{z})+\mathcal{N}_{M}(\bar{z}).$

By means of the formula

$\mathcal{N}_{D_{\kappa}}(\bar{z})=\\{\nu\in\mathbb{R}^{n}\,|\,\left\|\nu\right\|_{0}\leq
n-\kappa,\,\forall i\in I^{\pm}(\bar{z})\colon\,\nu_{i}=0\\},$

which can be distilled from [50, Lemma 2.3], we obtain a reasonable optimality
condition as soon as the variational structure of $M$ is nice enough. Let us
point out that whenever $M$ is the union of finitely many convex polyhedral
sets, then each local minimizer of the associated problem (CCMP) is implicitly
M-stationary by Remark 4.17 since the feasibility mapping
$z\rightrightarrows(z-D_{\kappa})\times(z-M)$ is polyhedral in this situation
and, thus, metrically subregular at all points of its graph. In case where the
variational geometry of $M$ is more difficult, metric subregularity of this
feasibility mapping at $(\bar{z},(0,0))$ is still enough to infer implicit
M-stationarity whenever $\bar{z}$ is a local minimizer of (CCMP). In case
where $M:=\\{z\in\mathbb{R}^{n}\,|\,\Phi(z)\in\Omega\\}$ holds for a
continuously differentiable mapping
$\Phi\colon\mathbb{R}^{n}\to\mathbb{R}^{p}$ and a closed set
$\Omega\subset\mathbb{R}^{p}$, the associated Mordukhovich criterion, which
ensures metric regularity of the feasibility mapping and validity of the pre-
image rule for the estimation of the limiting normal cone to $D_{\kappa}\cap
M$ at $\bar{z}$, takes the form

$\bigl{\|}\nabla\Phi(\bar{z})^{\top}\eta\bigr{\|}_{0}\leq
n-\kappa,\,\eta\in\mathcal{N}_{\Omega}(\Phi(\bar{z})),\,\forall i\in
I^{\pm}(\bar{z})\colon\,\bigl{(}\nabla\Phi(\bar{z})^{\top}\eta\bigr{)}_{i}=0\quad\Longrightarrow\quad\eta=0.$

As we pointed out in Section 4.3, the fuzzy and explicit M-stationarity
conditions of (CCMP) which follow from the setting (2.5) coincide. Performing
some calculations and keeping statement (a) of Proposition 4.29 in mind, these
explicit M-stationarity conditions take the following form at a reference
point $\bar{z}$: there exists some $\bar{\lambda}\in K(\bar{z})$ such that

$0\in\partial f(\bar{z})+\\{\nu\in\mathbb{R}^{n}\,|\,\forall i\in
I^{\pm}(\bar{z})\colon\,\nu_{i}=0\\}+\mathcal{N}_{M}(\bar{z}).$

We note that this condition does not depend on $\bar{\lambda}$ at all. It
corresponds to the M-stationarity notion discussed in [16, 17, 18]. At the
first glance, we observe that the implicit M-stationarity condition is more
restrictive than its explicit counterpart. In light of statement (a) of
Proposition 4.29, this is not surprising since the intermediate mapping
$\widehat{K}$ associated with the present setting is inner semicompact w.r.t.
its domain at each point of the latter. Recall that the explicit
M-stationarity system does not depend on the precise choice of the implicit
variable from $K(\bar{z})$, i.e., implicit M-stationarity of $\bar{z}$ implies
explicit M-stationarity w.r.t. all implicit variables from $K(\bar{z})$. On
the other hand, let us mention that in case of $\bar{z}:=0$ being feasible to
(CCMP), it is always an explicitly M-stationary point of (CCMP) w.r.t. each
implicit variable from $K(\bar{z})$ while this point is not necessarily
implicitly M-stationary.

##  6 Conclusions

The essential message of this paper says that whenever optimization problems
with implicit variables are under consideration, it is better to leave them
implicit as long as possible. In many practically relevant situations like
cardinality-constrained programming, see Section 5.3, this procedure leads to
more restrictive necessary optimality conditions which hold under less
restrictive constraint qualifications (in a certain sense). Furthermore, the
implicit formulation avoids the appearance of artificial local minimizers, and
this might be beneficial not only from a theoretical but also from a numerical
point of view. It is, thus, always desirable to explore the inherent problem
structure of the original problem instead of making its implicit variables
explicit for a non-negligible price. Exemplary, let us mention that a
convincing variational description of the weakly efficient set of a
multiobjective optimization problem which avoids the use of scalarization
variables is likely to enhance the results from Section 5.2.

## References

  * [1] L.Adam, R.Henrion, and J.Outrata, On M-stationarity conditions in MPECs and the associated qualification conditions, _Mathematical Programming_ 168 (2018), 229–259, doi:10.1007/s10107-017-1146-3.
  * [2] D.Aussel and A.Svensson, Is pessimistic bilevel programming a special case of a mathematical program with complementarity constraints?, _Journal of Optimization Theory and Applications_ 181 (2019), 504–520, doi:10.1007/s10957-018-01467-7.
  * [3] K.Bai, J. J.Ye, and J.Zhang, Directional quasi-/pseudo-normality as sufficient conditions for metric subregularity, _SIAM Journal on Optimization_ 29 (2019), 2625–2649, doi:10.1137/18m1232498.
  * [4] J. F.Bard, _Practical Bilevel Optimization: Algorithms and Applications_ , Kluwer Academic, Dordrecht, 1998.
  * [5] A.Beck and N.Hallak, On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms, _Mathematics of Operations Research_ 41 (2016), 196–223, doi:10.1287/moor.2015.0722.
  * [6] M.Benko, On inner calmness*, generalized calculus, and derivatives of the normal-cone mapping, _Journal of Nonsmooth Analysis and Optimization_ 2 (2021), 5881, doi:10.46298/jnsao-2021-5881.
  * [7] 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 and Variational Analysis_ (2021), 1–35, doi:10.1007/s11228-020-00569-7.
  * [8] M.Benko, H.Gfrerer, and J. V.Outrata, Calculus for directional limiting normal cones and subdifferentials, _Set-Valued and Variational Analysis_ 27 (2019), 713–745, doi:10.1007/s11228-018-0492-5.
  * [9] M.Benko and P.Mehlitz, Calmness and calculus: two basic patterns, _Set-Valued and Variational Analysis_ (2021), 1–37, doi:10.1007/s11228-021-00589-x.
  * [10] H. P.Benson, An algorithm for optimizing over the weakly-efficient set, _European Journal of Operational Research_ 25 (1986), 192–199, doi:10.1016/0377-2217(86)90085-8.
  * [11] D.Bienstock, Computational study of a family of mixed-integer quadratic programming problems, _Mathematical Programming_ 74 (1996), 121–140, doi:10.1007/bf02592208.
  * [12] S.Bolintineanu, Necessary conditions for nonlinear suboptimization over the weakly-efficient set, _Journal of Optimization Theory and Applications_ 78 (1993), 579–598, doi:10.1007/bf00939883.
  * [13] S.Bolintineanu, Optimality conditions for minimization over the (weakly or properly) efficient set, _Journal of Mathematical Analysis and Applications_ 173 (1993), 523–541, doi:10.1006/jmaa.1993.1085.
  * [14] J. F.Bonnans and A.Shapiro, _Perturbation Analysis of Optimization Problems_ , Springer, New York, 2000.
  * [15] R. I.Boţ, E. R.Csetnek, and E.Nagy, Solving systems of monotone inclusions via primal-dual splitting techniques, _Taiwanese Journal of Mathematics_ 17 (2013), 1983–2009, doi:10.11650/tjm.17.2013.3087.
  * [16] M.Bucher and A.Schwartz, Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems, _Journal of Optimization Theory and Applications_ 178 (2018), 383–410, doi:10.1007/s10957-018-1320-7.
  * [17] O. P.Burdakov, C.Kanzow, and A.Schwartz, Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method, _SIAM Journal on Optimization_ 26 (2016), 397–425, doi:10.1137/140978077.
  * [18] M.Červinka, C.Kanzow, and A.Schwartz, Constraint qualifications and optimality conditions for optimization problems with cardinality constraints, _Mathematical Programming_ 160 (2016), 353–377, doi:10.1007/s10107-016-0986-6.
  * [19] S.Dempe, _Foundations of Bilevel Programming_ , Kluwer, Dordrecht, 2002.
  * [20] S.Dempe and J.Dutta, Is bilevel programming a special case of a mathematical program with complementarity constraints?, _Mathematical Programming_ 131 (2012), 37–48, doi:10.1007/s10107-010-0342-1.
  * [21] S.Dempe, V.Kalashnikov, G.Pérez-Valdéz, and N.Kalashnykova, _Bilevel Programming Problems - Theory, Algorithms and Applications to Energy Networks_ , Springer, Berlin, 2015.
  * [22] S.Dempe, F.Mefo Kue, and P.Mehlitz, Optimality conditions for special semidefinite bilevel optimization problems, _SIAM Journal on Optimization_ 28 (2018), 1564–1587, doi:10.1137/16m1099303.
  * [23] S.Dempe and P.Mehlitz, Semivectorial bilevel programming versus scalar bilevel programming, _Optimization_ 69 (2020), 657–679, doi:10.1080/02331934.2019.1625900.
  * [24] A. L.Dontchev and R. T.Rockafellar, Characterizations of strong regularity for variational inequalities over polyhedral convex sets, _SIAM Journal on Optimization_ 6 (1996), 1087–1105, doi:10.1137/s1052623495284029.
  * [25] A. L.Dontchev and R. T.Rockafellar, _Implicit Functions and Solution Mappings_ , Springer, Heidelberg, 2014.
  * [26] M.Ehrgott, _Multicriteria Optimization_ , Springer, Berlin, 2005.
  * [27] M. J.Fabian, R.Henrion, A. Y.Kruger, and J. V.Outrata, Error bounds: necessary and sufficient conditions, _Set-Valued and Variational Analysis_ 18 (2010), 121–149, doi:10.1007/s11228-010-0133-0.
  * [28] M. L.Flegel, C.Kanzow, and J. V.Outrata, Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints, _Set-Valued Analysis_ 15 (2007), 139–162, doi:10.1007/s11228-006-0033-5.