###### Acknowledgements.

C. Kirches discloses financial support by the German Federal Ministry of
Education and Research through grants no 05M17MBA-MoPhaPro, 05M18MBA-MOReNet,
01/S17089C-ODINE, and 05M20MBA-LEOPLAN, and by Deutsche Forschungsgemeinschaft
(DFG) through Priority Programme 1962, grant Ki1839/1-2. © the authors CC-BY-
SA 4.0 2020-07-30 2021-02-12 2 6672 2021 10.46298/jnsao-2021-6672

# Relations Between Abs-Normal NLPs and MPCCs. Part 1: Strong Constraint
Qualifications

L.C. Hegerhorst-Schultchen Leibniz Universität Hannover, Institut für
Angewandte Mathematik, Welfengarten 1, 30167 Hannover, Germany.
<EMAIL_ADDRESS>C. Kirches Technische Universität Carolo-
Wilhelmina zu Braunschweig, Institut für Mathematische Optimierung,
Universitätsplatz 2, 38106 Braunschweig, Germany<EMAIL_ADDRESS>M.C.
Steinbach Leibniz Universität Hannover, Institut für Angewandte Mathematik,
Welfengarten 1, 30167 Hannover, Germany<EMAIL_ADDRESS>
()

###### Abstract

This work is part of an ongoing effort of comparing non-smooth optimization
problems in abs-normal form to MPCCs. We study the general abs-normal NLP with
equality and inequality constraints in relation to an equivalent MPCC
reformulation. We show that kink qualifications and MPCC constraint
qualifications of linear independence type and Mangasarian-Fromovitz type are
equivalent. Then we consider strong stationarity concepts with first and
second order optimality conditions, which again turn out to be equivalent for
the two problem classes. Throughout we also consider specific slack
reformulations suggested in [9], which preserve constraint qualifications of
linear independence type but _not_ of Mangasarian-Fromovitz type.

##  1 Introduction

Nonsmoothness arises frequently in practical optimization problems from
various areas. In finite dimensions, certain nonsmooth functions like
$\ell_{1}$ and $\ell_{\infty}$ norms can be avoided by smooth remodeling, but
models that involve (possibly nested) absolute value, maximum, and minimum
functions, models with piecewise definitions and models with equilibrium
conditions or complementarity conditions lead to genuine nonsmoothness. An
important sub-class of such nonsmooth finite-dimensional optimization problems
is essentially characterized as “NLPs with finitely many kinks”, which gives
rise to more general standard problem classes like MPCCs [10] and optimization
problems in abs-normal form [2].

The latter are non-smooth nonlinear optimization problems of the form

(NLP) $\displaystyle\smash[b]{\min_{x}}\ f(x)\quad\textup{s.t.}\quad g(x)$
$\displaystyle=0,$ $\displaystyle h(x)$ $\displaystyle\geq 0,$

where $D^{x}\subseteq\mathbb{R}^{n}$ is open, the objective $f\in
C^{d}(D^{x},\mathbb{R})$ is a smooth function ($d\geq 1$) and the equality and
inequality constraints $g\in C^{d}_{\text{abs}}(D^{x},\mathbb{R}^{m_{1}})$ and
$h\in C^{d}_{\text{abs}}(D^{x},\mathbb{R}^{m_{2}})$ are non-smooth functions
with the non-smoothness exposed in abs-normal form [2]. Thus, there exist
functions $c_{\mathcal{E}}\in C^{d}(D^{x,\lvert z\rvert},\mathbb{R}^{m_{1}})$,
$c_{\mathcal{I}}\in C^{d}(D^{x,\lvert z\rvert},\mathbb{R}^{m_{2}})$ and
$c_{\mathcal{Z}}\in C^{d}(D^{x,\lvert z\rvert},\mathbb{R}^{s})$ with
$D^{x,\lvert z\rvert}=D^{x}\times D^{\lvert z\rvert}$, $D^{\lvert
z\rvert}\subseteq\mathbb{R}^{s}$ open and _symmetric_ (i.e., $z\in D^{\lvert
z\rvert}$ implies $\Sigma z\in D^{\lvert z\rvert}$ for every signature matrix
$\Sigma$, see Definition 1.1) such that

$\displaystyle g(x)$ $\displaystyle=c_{\mathcal{E}}(x,\lvert z\rvert),$ (ANF)
$\displaystyle h(x)$ $\displaystyle=c_{\mathcal{I}}(x,\lvert z\rvert),$
$\displaystyle z$ $\displaystyle=c_{\mathcal{Z}}(x,\lvert
z\rvert)\quad\textup{with $\partial_{2}c_{\mathcal{Z}}(x,\lvert z\rvert)$
strictly lower triangular}.$

Note that we introduce one joint _switching constraint_ $c_{\mathcal{Z}}$ for
$g$ and $h$ and reuse _switching variables_ $z_{i}$ if the same argument
occurs inside an absolute value in $g$ and $h$. Here, components of $z$ can be
computed one by one from $x$ and $z_{i}$, $i<j$, since
$\partial_{2}c_{\mathcal{Z}}(x,\lvert z\rvert)$ is strictly lower triangular.
In the following we write $z(x)$ to denote this dependence explicitly.
However, $z$ is implicitly defined by $z=c_{\mathcal{Z}}(x,\lvert z\rvert)$.
To consider solvability of this system, we use the reformulation $\lvert
z_{i}\rvert=\operatorname{sign}(z_{i})z_{i}$.

######  Definition 1.1 (Signature of $z$).

Let $x\in D^{x}$. We define the _signature_ $\sigma(x)$ and the associated
_signature matrix_ $\Sigma(x)$ as

$\displaystyle\sigma(x)$
$\displaystyle\mathrel{{\mathop{:}}{=}}\operatorname{sign}(z(x))\in\\{-1,0,1\\}^{s},$
$\displaystyle\Sigma(x)$
$\displaystyle\mathrel{{\mathop{:}}{=}}\operatorname{diag}(\sigma(x)).$

A signature vector $\sigma(x)\in\\{-1,1\\}^{s}$ is called _definite_ ,
otherwise _indefinite_.

With Definition 1.1, we can write $\lvert z(x)\rvert=\Sigma(x)z(x)$ and
consider the system $z=c_{\mathcal{Z}}(x,\Sigma z)$, which for any fixed
signature $\Sigma=\Sigma(\leavevmode\hat{x})$ becomes a differentiable system.
Then, application of the implicit function theorem yields the existence of a
locally unique solution $z(x)$ with Jacobian

$\partial_{x}z(\leavevmode\hat{x})=[I-\partial_{2}c_{\mathcal{Z}}(\leavevmode\hat{x},\lvert
z(\leavevmode\hat{x})\rvert)\Sigma]^{-1}\partial_{1}c_{\mathcal{Z}}(\leavevmode\hat{x},\lvert
z(\leavevmode\hat{x})\rvert)\in\mathbb{R}^{s\times n}.$

######  Definition 1.2 (Active Switching Set).

We call the switching variable $z_{i}$ _active_ if $z_{i}(x)=0$. The _active
switching set_ $\alpha$ consists of all indices of active switching variables,
i.e.

$\alpha(x)\mathrel{{\mathop{:}}{=}}\\{i\in\\{1,\dots,s\\}\colon
z_{i}(x)=0\\}.$

We denote the number of active switching variables by $\lvert\alpha(x)\rvert$
and the number of inactive ones by
$\lvert\sigma(x)\rvert\mathrel{{\mathop{:}}{=}}s-\lvert\alpha(x)\rvert$.

Unconstrained optimization problems in abs-normal form have recently been
introduced by [3], and have been shown to come with favorable theoretical
properties that lead to globally convergent solution methods based on
piecewise linearizations that can be generated by algorithmic differentiation
[5, 6]. When nonsmooth equality and inequality constraints are added, the
resulting abs-normal NLPs can be compared to MPCCs, for which a well-
established theoretical framework has been developed over the past decades
[10]. Comparing the two classes of nonsmooth optimization problems, the
authors reported in [8] that they basically form the same problem class,
although with a different representation of nonsmoothness and not necessarily
with the same regularity properties.

### Literature

The abs-normal NLPs considered here are a direct generalization of
unconstrained abs-normal problems developed by Griewank and Walther [2, 3].
These problems offer particularly attractive theoretical features when
generalizing KKT theory and stationarity concepts, and they are tractable by
sophisticated algorithms with guaranteed convergence based on piecewise
linearizations and using algorithmic differentiation techniques [5, 6].

Another important class of nonsmooth optimization problems are Mathematical
Programs with Complementarity (or Equilibrium) Constraints (MPCCs, MPECs); an
overview can be found in the book [10]. Since standard theory for smooth
optimization problems cannot be applied, new constraint qualifications and
corresponding optimality conditions were introduced. By now, there is a large
body of literature on MPCCs, and we refer to [12] for an overview of the basic
concepts and theory. In this paper, constraint qualifications for MPCCs in the
sense of linear independence and Mangasarian Fromowitz are considered.
Further, the corresponding stationarity concept (S-stationarity) as well as
first and second order optimality conditions are studied. Details can be found
in [11], [10] and [1].

In [8] we have shown that unconstrained optimization problems in abs-normal
form are a subclass of MPCCs and we have studied regularity concepts of linear
independence type, Mangasarian-Fromovitz type and Abadie type. We have also
shown that abs-normal NLPs with general constraints are equivalent to the
class of MPCCs. In [9] we have generalized optimality conditions of
unconstrained abs-normal problems to the case with equality and inequality
constraints under the linear independence kink qualification. More details and
additional information about these results as well as about the results in
this paper can be found in [7].

### Contributions

We develop a deeper understanding of the commonalities of these problem
classes of NLPs in abs-normal form on the one hand, and MPCCs on the other. We
provide a detailed comparative study of general abs-normal NLPs and MPCCs,
considering constraint qualifications of linear independence type and
Mangasarian Fromovitz type for the standard formulation and for a
reformulation with absolute value slacks that was suggested in [9]. In
particular, we show that corresponding constraint qualifications of abs-normal
NLPs and MPCCs are equivalent and that the linear independence type constraint
qualifications are preserved by the slack reformulation while this is not the
case for a Mangasarian-Fromovitz type constraint qualification. We then
compare optimality conditions of first and second order for abs-normal NLPs
and MPCCs under the respective linear independence type constraint
qualifications. We show equivalence of the respective first order necessary
conditions, kink stationarity and strong stationarity. We also show how second
order conditions for MPCCs can be carried over to abs-normal NLPs. Under
suitable additional assumptions, we prove equivalence of positive
(semi-)definiteness of the associated reduced Hessians, which gives
correspondences of second order necessary and sufficient conditions.

We expect that our theoretical results will contribute to the understanding
and further development of rigorous solution algorithms for abs-normal NLPs.
We also expect the results to facilitate a possible transferral of active-
signature methods for abs-normal forms, such as SALMIN [5], to MPCCs.

### Structure

The remainder of this article is structured as follows. In Section 2 we
present the general abs-normal NLP and its slack reformulation, and we
formulate the associated kink qualifications and compare them. In Section 3 we
introduce counterpart MPCCs for the two formulations of abs-normal NLPs and
compare the associated MPCC-constraint qualifications. Then, we show
equivalence of the regularity concepts for abs-normal NLPs and MPCCs in
Section 4. Finally, in Section 5 we state optimality conditions of first and
second-order for abs-normal NLPs and MPCCs and prove equivalence relations
between them. We conclude in Section 6 and give a brief outlook.

##  2 Abs-Normal NLPs

In this section we consider two formulations for non-smooth NLPs in abs-normal
form that differ in the treatment of inequality constraints.

###  2.1 General Abs-Normal NLPs

In this paragraph we consider abs-normal NLPs with equalities and
inequalities, obtained by substituting the constraints representation in abs-
normal form (ANF) into the general non-smooth problem (NLP). Note that we use
the variables $(t,z^{t})$ instead of $(x,z)$.

######  Definition 2.1 (Abs-Normal NLP).

Let $D^{t}$ be an open subset of $\mathbb{R}^{n_{t}}$. A non-smooth NLP is
called an _abs-normal NLP_ if functions $f\in C^{d}(D^{t},\mathbb{R})$,
$c_{\mathcal{E}}\in C^{d}(D^{t,\lvert z^{t}\rvert},\mathbb{R}^{m_{1}})$,
$c_{\mathcal{I}}\in C^{d}(D^{t,\lvert z^{t}\rvert},\mathbb{R}^{m_{2}})$, and
$c_{\mathcal{Z}}\in C^{d}(D^{t,\lvert z^{t}\rvert},\mathbb{R}^{s_{t}})$ with
$d\geq 1$ exist such that the NLP reads

$\displaystyle\smash[b]{\min_{t,z^{t}}}\ f(t)\quad\textup{s.t.}\quad$
$\displaystyle c_{\mathcal{E}}(t,\lvert z^{t}\rvert)=0,$ (I-NLP)
$\displaystyle c_{\mathcal{I}}(t,\lvert z^{t}\rvert)\geq 0,$ $\displaystyle
c_{\mathcal{Z}}(t,\lvert z^{t}\rvert)-z^{t}=0,$

where $D^{\lvert z^{t}\rvert}$ is open and symmetric and
$\partial_{2}c_{\mathcal{Z}}(x,\lvert z^{t}\rvert)$ is strictly lower
triangular.

The feasible set of (I-NLP) is denoted by

$\displaystyle\mathcal{F}_{\textup{abs}}$
$\displaystyle\mathrel{{\mathop{:}}{=}}\left\\{\,(t,z^{t})\,\left|\begin{array}[]{l}c_{\mathcal{E}}(t,\lvert
z^{t}\rvert)=0,\ c_{\mathcal{I}}(t,\lvert z^{t}\rvert)\geq 0,\\\
c_{\mathcal{Z}}(t,\lvert z^{t}\rvert)-z^{t}=0\end{array}\right.\\!\right\\}$
$\displaystyle\hphantom{:}=\\{(t,z^{t}(t))\colon t\in D^{t},\
c_{\mathcal{E}}(t,\lvert z^{t}(t)\rvert)=0,\ c_{\mathcal{I}}(t,\lvert
z^{t}(t)\rvert)\geq 0\\}.$

In contrast to standard NLP theory, we do not count equalities as active
constraints.

######  Definition 2.2 (Active Inequality Set).

Let $(t,z^{t}(t))\in\mathcal{F}_{\textup{abs}}$. We call the constraint
$i\in\mathcal{I}$ _active_ if $c_{i}(t,\lvert z^{t}(t)\rvert)=0$. The _active
set_ $\mathcal{A}(t)$ consists of all indices of active constraints,

$\mathcal{A}(t)=\\{i\in\mathcal{I}\colon c_{i}(t,\lvert z^{t}(t)\rvert)=0\\}.$

We denote the number of active inequality constraints by
$\lvert\mathcal{A}(t)\rvert$.

To define the linear independence kink qualification as well as the interior
direction kink qualification for (I-NLP) we need its Jacobians.

######  Definition 2.3 (Jacobians).

Consider the abs-normal NLP (I-NLP). For
$(t,z^{t}(t))\in\mathcal{F}_{\textup{abs}}$ set $\mathcal{A}=\mathcal{A}(t)$,
$\alpha=\alpha(t)$, $\sigma=\sigma(t)$, $\Sigma=\operatorname{diag}(\sigma)$,
and $c_{\mathcal{A}}=[c_{i}]_{i\in\mathcal{A}}$. The _equality-constraints
Jacobian_ is

$\displaystyle
J_{\mathcal{E}}(t)\mathrel{{\mathop{:}}{=}}\partial_{t}c_{\mathcal{E}}(t,\Sigma
z^{t}(t))$ $\displaystyle=\partial_{1}c_{\mathcal{E}}(t,\Sigma
z^{t}(t))+\partial_{2}c_{\mathcal{E}}(t,\Sigma
z^{t}(t))\Sigma\partial_{t}z^{t}(t)$
$\displaystyle=\partial_{1}c_{\mathcal{E}}(t,\lvert
z^{t}(t)\rvert)+\partial_{2}c_{\mathcal{E}}(t,\lvert
z^{t}(t)\rvert)\Sigma\partial_{t}z^{t}(t),$

the _active inequality Jacobian_ is

$\displaystyle
J_{\mathcal{A}}(t)\mathrel{{\mathop{:}}{=}}\partial_{t}c_{\mathcal{A}}(t,\Sigma
z^{t}(t))$ $\displaystyle=\partial_{1}c_{\mathcal{A}}(t,\Sigma
z^{t}(t))+\partial_{2}c_{\mathcal{A}}(t,\Sigma
z^{t}(t))\Sigma\partial_{t}z^{t}(t)$
$\displaystyle=\partial_{1}c_{\mathcal{A}}(t,\lvert
z^{t}(t)\rvert)+\partial_{2}c_{\mathcal{A}}(t,\lvert
z^{t}(t)\rvert)\Sigma\partial_{t}z^{t}(t),$

and the _active switching Jacobian_ is

$\displaystyle
J_{\alpha}(t)\mathrel{{\mathop{:}}{=}}\left[e_{i}^{T}\partial_{t}z^{t}(t)\right]_{i\in\alpha}=\left[e_{i}^{T}[I-\partial_{2}c_{\mathcal{Z}}(t,\lvert
z^{t}(t)\rvert)\Sigma]^{-1}\partial_{1}c_{\mathcal{Z}}(t,\lvert
z^{t}(t)\rvert)\right]_{i\in\alpha}.$

######  Definition 2.4 (Linear Independence Kink Qualification).

Let $(t,z^{t}(t))\in\mathcal{F}_{\textup{abs}}$. We say that the _linear
independence kink qualification (LIKQ)_ holds for (I-NLP) at $t$ if

$\displaystyle J_{\textup{abs}}(t)=\begin{bmatrix}J_{\mathcal{E}}(t)\\\
J_{\mathcal{A}}(t)\\\
J_{\alpha}(t)\end{bmatrix}=\begin{bmatrix}\partial_{t}c_{\mathcal{E}}(t,\lvert
z^{t}(t)\rvert)\\\ \partial_{t}c_{\mathcal{A}}(t,\lvert z^{t}(t)\rvert)\\\
[e_{i}^{T}\partial_{t}z^{t}(t)]_{i\in\alpha}\end{bmatrix}\in\mathbb{R}^{(m_{1}+\lvert\mathcal{A}\rvert+\lvert\alpha\rvert)\times
n_{t}}$

has full row rank $m_{1}+\lvert\mathcal{A}\rvert+\lvert\alpha\rvert$.

######  Definition 2.5 (Interior Direction Kink Qualification).

Let $(t,z^{t}(t))\in\mathcal{F}_{\textup{abs}}$. We say that the _interior
direction kink qualification (IDKQ)_ holds for (I-NLP) at $t$ if

$\displaystyle\begin{bmatrix}J_{\mathcal{E}}(t)\\\
J_{\alpha}(t)\end{bmatrix}=\begin{bmatrix}\partial_{t}c_{\mathcal{E}}(t,\lvert
z^{t}(t)\rvert)\\\
[e_{i}^{T}\partial_{t}z^{t}(t)]_{i\in\alpha}\end{bmatrix}\in\mathbb{R}^{(m_{1}+\lvert\alpha\rvert)\times
n_{t}}$

has full row rank $m_{1}+\lvert\alpha\rvert$ and if there exists a vector
$d\in\mathbb{R}^{n_{t}}$ such that

$J_{\mathcal{E}}(t)d=0,\quad J_{\alpha}(t)d=0,\quad\text{and}\quad
J_{\mathcal{A}}(t)d>0.$

For the general abs-normal NLP (I-NLP) considered here, IDKQ actually
generalizes MFCQ from the smooth case and corresponds to MPCC-MFCQ, as we will
show below. We cannot use the canonical name MFKQ, however, since Griewank and
Walther have already defined MFKQ as a different weakening of LIKQ in [4]. We
believe that other possible names like “Abs-normal MFKQ” or “Constrained MFKQ”
would produce confusion rather than clarification and hence suggest the
descriptive name “Interior Direction KQ”.

The following example from [11] (converted from MPCC form to abs-normal NLP
form) shows that IDKQ is weaker than LIKQ in the presence of inequality
constraints.

######  Example 2.6 (IDKQ is weaker than LIKQ).

Consider the problem

$\displaystyle\smash[b]{\min_{t\in\mathbb{R}^{3},z^{t}\in\mathbb{R}}}\
t_{1}+t_{2}-t_{3}\quad\textup{s.t.}\quad$ $\displaystyle t_{1}+t_{2}-\lvert
z^{t}\rvert=0,$ $\displaystyle 4t_{1}-t_{3}\geq 0,$ $\displaystyle
4t_{2}-t_{3}\geq 0,$ $\displaystyle t_{1}-t_{2}-z^{t}=0,$

with solution $t^{*}=(0,0,0)$ and $(z^{t})^{*}=0$. We compute

$\displaystyle J_{\mathcal{A}}(t^{*})=\begin{bmatrix}4&0&-1\\\
0&4&-1\end{bmatrix},\quad
J_{\mathcal{E}}(t^{*})=\begin{bmatrix}1&1&0\end{bmatrix},\quad\text{and}\quad
J_{\alpha}(t^{*})=\begin{bmatrix}1&-1&0\end{bmatrix}.$

Here, LIKQ is not satisfied but IDKQ is satisfied with $d=(0,0,-1)$.

###  2.2 Abs-Normal NLPs with Inequality Slacks

In this paragraph we consider abs-normal NLPs with slack variables introduced
for all inequalities. We make use of the absolute value of a slack variable,
an idea due to Griewank. This results in a class of purely equality-
constrained abs-normal NLPs, which simplifies the derivation of optimality
conditions under the LIKQ, see [9] and Section 5.

Using slack variables $w\in\mathbb{R}^{m_{2}}$, we obtain the following
reformulation of (NLP):

$\displaystyle\smash[b]{\min_{t,w}}\ f(t)\quad\textup{s.t.}\quad$
$\displaystyle g(t)=0,$ $\displaystyle h(t)-\lvert w\rvert=0.$

Then, we express $g$ and $h$ in abs-normal form as in (ANF) and introduce
additional switching variables $z^{w}$ to handle $\lvert w\rvert$. This
approach leads to the next definition.

######  Definition 2.7 (Abs-Normal NLP with Inequality Slacks).

An abs-normal NLP posed in the following form is called an _abs-normal NLP
with inequality slacks_ :

$\displaystyle\smash[b]{\min_{t,w,z^{t},z^{w}}}\ f(t)\quad\textup{s.t.}\quad$
$\displaystyle c_{\mathcal{E}}(t,\lvert z^{t}\rvert)=0,$ (E-NLP)
$\displaystyle c_{\mathcal{I}}(t,\lvert z^{t}\rvert)-\lvert z^{w}\rvert=0,$
$\displaystyle c_{\mathcal{Z}}(t,\lvert z^{t}\rvert)-z^{t}=0,$ $\displaystyle
w-z^{w}=0,$

where $D^{\lvert z^{t}\rvert}$ is open and symmetric and
$\partial_{2}c_{\mathcal{Z}}(x,\lvert z^{t}\rvert)$ is strictly lower
triangular.

The feasible set of (E-NLP) is a lifting of $\mathcal{F}_{\textup{abs}}$,

$\displaystyle\mathcal{F}_{\textup{e-abs}}$
$\displaystyle\mathrel{{\mathop{:}}{=}}\left\\{\,(t,w,z^{t},z^{w})\,\left|\begin{array}[]{l}c_{\mathcal{E}}(t,\lvert
z^{t}\rvert)=0,\ c_{\mathcal{I}}(t,\lvert z^{t}\rvert)-\lvert
z^{w}\rvert=0,\\\ c_{\mathcal{Z}}(t,\lvert z^{t}\rvert)-z^{t}=0,\
w-z^{w}=0\end{array}\right.\\!\right\\}$
$\displaystyle\hphantom{:}=\left\\{(t,w,z^{t},z^{w})\colon(t,z^{t})\in\mathcal{F}_{\textup{abs}},\
w=z^{w},\ \lvert z^{w}\rvert=c_{\mathcal{I}}(t,\lvert z^{t}\rvert)\right\\}.$

Using the dependence of $z^{t}$ and $z^{w}$ of $t$ and $w$, the feasible set
can be written as

$\displaystyle\mathcal{F}_{\textup{e-abs}}$
$\displaystyle=\left\\{\,(t,w,z^{t}(t),z^{w}(w))\,\left|\begin{array}[]{l}t\in
D^{t},\ c_{\mathcal{E}}(t,\lvert z^{t}(t)\rvert)=0,\\\
c_{\mathcal{I}}(t,\lvert z^{t}(t)\rvert)-\lvert z^{w}(w)\rvert=0,\
w-z^{w}(w)=0\end{array}\right.\\!\right\\}$
$\displaystyle=\left\\{(t,w,z^{t}(t),z^{w}(w))\colon(t,z^{t}(t))\in\mathcal{F}_{\textup{abs}},\
w=z^{w}(w),\ \lvert z^{w}(w)\rvert=c_{\mathcal{I}}(t,\lvert
z^{t}(t)\rvert)\right\\}.$

We split the active switching set into subsets for variables $t$ and $w$ as
$\alpha=(\alpha^{t},\alpha^{w})$.

######  Remark 2.8.

Note that introducing $\lvert w\rvert$ converts inequalities to pure
equalities without a nonnegativity condition for the slack variables $w$.
However, the slack reformulation has some subtle issues. Subsequently we will
show that, in contrast to LIKQ, IDKQ is _not_ preserved. Moreover, one cannot
eliminate the equation $w-z^{w}=0$ (and hence $z^{w}$ or $w$) in (E-NLP) since
this would destroy the abs-normal form. Finally, the slack $w$ is not uniquely
determined since the signs of nonzero components $w_{i}$ can be chosen
arbitrarily, yielding a set of $2^{m_{2}-\lvert\alpha^{w}\rvert}$ choices,
$W(t)\mathrel{{\mathop{:}}{=}}\\{w\colon\lvert
w\rvert=c_{\mathcal{I}}(t,\lvert z^{t}(t)\rvert)\\}$.

######  Lemma 2.9.

Consider $(t,w,z^{t}(t),z^{w}(w))\in\mathcal{F}_{\textup{e-abs}}$. Then, LIKQ
for (E-NLP) at $(t,w)$ is full row rank of

$\displaystyle
J_{\textup{e-abs}}(t,w)=\begin{bmatrix}\partial_{t}c_{\mathcal{E}}(t,\lvert
z^{t}(t)\rvert)&0\\\ \partial_{t}c_{\mathcal{I}}(t,\lvert
z^{t}(t)\rvert)&-\Sigma^{w}\\\
[e_{i}^{T}\partial_{t}z^{t}(t)]_{i\in\alpha^{t}}&0\\\
0&[e_{i}^{T}I]_{i\in\alpha^{w}}\end{bmatrix}\in\mathbb{R}^{(m_{1}+m_{2}+\lvert\alpha^{t}\rvert+\lvert\alpha^{w}\rvert)\times(n_{t}+m_{2})}.$

######  Proof 2.10.

Set $x=(t,w)$, $z=(z^{t},z^{w})$, $\leavevmode\bar{f}(x)=f(t)$,
$\leavevmode\bar{c}_{\mathcal{E}}(x,\lvert z\rvert)=(c_{\mathcal{E}}(t,\lvert
z^{t}\rvert),c_{\mathcal{I}}(t,\lvert z^{t}\rvert)-\lvert z^{w}\rvert)$, and
$\leavevmode\bar{c}_{\mathcal{Z}}(x,\lvert z\rvert)=(c_{\mathcal{Z}}(t,\lvert
z^{t}\rvert),w)$. Then, we can write (E-NLP) compactly as

($\overline{\text{E-NLP}}$) $\displaystyle\smash[b]{\min_{x,z}}\
\leavevmode\bar{f}(x)\quad\textup{s.t.}\quad$
$\displaystyle\leavevmode\bar{c}_{\mathcal{E}}(x,\lvert z\rvert)=0,$
$\displaystyle\leavevmode\bar{c}_{\mathcal{Z}}(x,\lvert z\rvert)-z=0,$

and compute $\leavevmode\bar{J}_{\mathcal{E}}$ and
$\leavevmode\bar{J}_{\alpha}$ from Definition 2.3 using the special structure
of (E-NLP). The resulting matrix
$J_{\textup{e-abs}}(x)=\begin{bmatrix}\leavevmode\bar{J}_{\mathcal{E}}(x)^{T}&\leavevmode\bar{J}_{\alpha}(x)^{T}\end{bmatrix}^{T}$
in Definition 2.4 has the form above.

######  Remark 2.11.

Clearly, the rank of $J_{\textup{e-abs}}$ does not depend on the signs of $\pm
1$ entries in $\Sigma^{w}$ but only on their positions. Hence, LIKQ does not
depend on the particular choice of $w$. Otherwise it would not make sense to
consider (E-NLP).

Note that, since the abs-normal NLP (E-NLP) does not contain any inequalities,
the concept of IDKQ is equivalent to LIKQ here. This is in contrast to the
standard reformulation of smooth NLP inequalities as equalities with
nonnegative slacks where the validity of LICQ and MFCQ are both unaffected.

###  2.3 Relations of Kink Qualifications for Abs-Normal NLPs

In this paragraph we discuss the relations of kink qualifications for the two
different formulations of abs-normal NLPs. We use the set $W(t)$ from above.

######  Theorem 2.12.

LIKQ for (I-NLP) holds at $(t,z^{t}(t))\in\mathcal{F}_{\textup{abs}}$ if and
only if LIKQ for (E-NLP) holds at
$(t,w,z^{t}(t),z^{w}(w))\in\mathcal{F}_{\textup{e-abs}}$ for any (and hence
all) $w\in W(t)$.

######  Proof 2.13.

This follows immediately by comparison of $J_{\textup{abs}}$ and
$J_{\textup{e-abs}}$ using that

$\alpha^{w}(w)=\\{i\in\mathcal{I}\colon w_{i}=0\\}=\\{i\in\mathcal{I}\colon
c_{i}(t,z^{t}(t))=0\\}=\mathcal{A}(t)$

and

$\Sigma^{w}=\operatorname{diag}(\sigma^{w})\quad\text{with}\quad\sigma^{w}_{i}=\operatorname{sign}(w_{i})=\begin{cases}0,&i\in\mathcal{A}(t),\\\
\pm 1,&i\notin\mathcal{A}(t).\end{cases}$

######  Theorem 2.14.

IDKQ for (I-NLP) holds at $(t,z^{t}(t))\in\mathcal{F}_{\textup{abs}}$ if IDKQ
for (E-NLP) holds at the lifted point
$(t,w,z^{t}(t),z^{w}(w))\in\mathcal{F}_{\textup{e-abs}}$ for any (and hence
all) $w\in W(t)$. The converse is not true.

######  Proof 2.15.

Since (E-NLP) has no inequalities, the concepts of IDKQ and LIKQ coincide.
LIKQ for (E-NLP) is equivalent to LIKQ for (I-NLP) by Theorem 2.12, and LIKQ
for (I-NLP) implies IDKQ for (I-NLP). The converse does not hold since LIKQ
for (I-NLP) is stronger then IDKQ as we have shown in Example 2.6.

##  3 Counterpart MPCCs

In this section we introduce MPCC counterpart problems for the two
formulations (I-NLP) and (E-NLP). Then, we have a quick look at relations
between them.

###  3.1 Counterpart MPCC for the General Abs-Normal NLP

To reformulate (I-NLP) as an MPCC, we partition $z^{t}$ into its nonnegative
part and the modulus of its nonpositive part,
$u^{t}\mathrel{{\mathop{:}}{=}}[z^{t}]^{+}\mathrel{{\mathop{:}}{=}}\max(z^{t},0)$
and
$v^{t}\mathrel{{\mathop{:}}{=}}[z^{t}]^{-}\mathrel{{\mathop{:}}{=}}\max(-z^{t},0)$.
Then, we require complementarity of these two variables to replace $\lvert
z^{t}\rvert$ by $u^{t}+v^{t}$ and $z^{t}$ itself by $u^{t}-v^{t}$.

######  Definition 3.1 (Counterpart MPCC of (I-NLP)).

The _counterpart MPCC_ of the abs-normal NLP (I-NLP) reads

$\displaystyle\smash[b]{\min_{t,u^{t},v^{t}}}\ f(t)\quad\textup{s.t.}\quad$
$\displaystyle c_{\mathcal{E}}(t,u^{t}+v^{t})=0,$ (I-MPCC) $\displaystyle
c_{\mathcal{I}}(t,u^{t}+v^{t})\geq 0,$ $\displaystyle
c_{\mathcal{Z}}(t,u^{t}+v^{t})-(u^{t}-v^{t})=0,$ $\displaystyle 0\leq
u^{t}\perp v^{t}\geq 0,$ where $u^{t},v^{t}\in\mathbb{R}^{s_{t}}$.

The feasible set of (I-MPCC) is denoted by

$\mathcal{F}_{\textup{mpcc}}\mathrel{{\mathop{:}}{=}}\left\\{\,(t,u^{t},v^{t})\,\left|\begin{array}[]{l}c_{\mathcal{E}}(t,u^{t}+v^{t})=0,\
c_{\mathcal{I}}(t,u^{t}+v^{t})\geq 0,\\\
c_{\mathcal{Z}}(t,u^{t}+v^{t})=u^{t}-v^{t},\ 0\leq u^{t}\perp v^{t}\geq
0\end{array}\right.\\!\right\\}.$

######  Lemma 3.2.

Given an abs-normal NLP (I-NLP) and its counterpart MPCC (I-MPCC), we have a
homeomorphism
$\phi\leavevmode\colon{}\mathcal{F}_{\textup{mpcc}}\to\mathcal{F}_{\textup{abs}}$
defined as

$\displaystyle\phi(t,u^{t},v^{t})$ $\displaystyle=(t,u^{t}-v^{t}),$
$\displaystyle\phi^{-1}(t,z^{t})$ $\displaystyle=(t,[z^{t}]^{+},[z^{t}]^{-}).$

######  Proof 3.3.

Obvious.

Just like the active switching set of the abs-normal NLP, we define index sets
of the counterpart MPCC.

######  Definition 3.4 (Index Sets).

We denote by
$\mathcal{U}^{t}_{0}\mathrel{{\mathop{:}}{=}}\\{i\in\\{1,\dots,s_{t}\\}\colon
u^{t}_{i}=0\\}$ the set of indices of active inequalities $u^{t}_{i}\geq 0$,
and by
$\mathcal{U}^{t}_{+}\mathrel{{\mathop{:}}{=}}\\{i\in\\{1,\dots,s_{t}\\}\colon
u^{t}_{i}>0\\}$ the set of indices of inactive inequalities $u^{t}_{i}\geq 0$.
Analogous definitions hold of $\mathcal{V}^{t}_{0}$ and $\mathcal{V}^{t}_{+}$.
By
$\mathcal{D}^{t}\mathrel{{\mathop{:}}{=}}\mathcal{U}^{t}_{0}\cap\mathcal{V}^{t}_{0}$
we denote the set of indices of non-strict (degenerate) complementarity pairs.
Thus we have the partitioning
$\\{1,\dots,s_{t}\\}=\mathcal{U}^{t}_{+}\cup\mathcal{V}^{t}_{+}\cup\mathcal{D}^{t}$.

In the following we define constraint qualifications for the counterpart MPCC.
The standard definitions say that MPCC-LICQ and MPCC-MFCQ are LICQ and MFCQ,
respectively, for the so-called _tightened NLP_ (see [11]) with associated
Jacobian

$\displaystyle
J(t,u^{t},v^{t})=\begin{bmatrix}\partial_{1}c_{\mathcal{E}}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{U}^{t}_{0}}^{T}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{V}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{V}^{t}_{0}}^{T}\\\
\partial_{1}c_{\mathcal{A}}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{U}^{t}_{0}}^{T}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{V}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{V}^{t}_{0}}^{T}\\\
\partial_{1}c_{\mathcal{Z}}&[\partial_{2}c_{\mathcal{Z}}-I]P_{\mathcal{U}^{t}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}-I]P_{\mathcal{U}^{t}_{0}}^{T}&[\partial_{2}c_{\mathcal{Z}}+I]P_{\mathcal{V}^{t}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}+I]P_{\mathcal{V}^{t}_{0}}^{T}\\\
0&0&I&0&0\\\ 0&0&0&0&I\end{bmatrix},$

where $P_{\mathcal{S}}\in\mathbb{R}^{\lvert\mathcal{S}\rvert\times s_{t}}$
denotes the projector onto the subspace defined by
$\mathcal{S}\subseteq\\{1,\dots,s_{t}\\}$ and all partial darivatives are
evaluated at $(t,u^{t}+v^{t})$. This Jacobian will be needed in Section 5.2 to
formulate second order conditions. Here we exploit the two unit blocks to
state constraint qualifications in a more compact form as in [8].

######  Definition 3.5 (MPCC-LICQ for (I-MPCC), see [11]).

We say that the _MPCC-LICQ_ holds for (I-MPCC) at a feasible point
$(t,u^{t},v^{t})$ if

$\displaystyle J_{\textup{mpcc}}(t,u^{t},v^{t})$
$\displaystyle=\begin{bmatrix}\partial_{1}c_{\mathcal{E}}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{V}^{t}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{A}}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{V}^{t}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{Z}}&[\partial_{2}c_{\mathcal{Z}}-I]P_{\mathcal{U}^{t}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}+I]P_{\mathcal{V}^{t}_{+}}^{T}\end{bmatrix}$
$\displaystyle\in\mathbb{R}^{(m_{1}+\lvert\mathcal{A}\rvert+s_{t})\times(n_{t}+\lvert\mathcal{U}^{t}_{+}\rvert+\lvert\mathcal{V}^{t}_{+}\rvert)}$

has full row rank $m_{1}+\lvert\mathcal{A}\rvert+s_{t}$. Here all partial
derivatives are evaluated at $(t,u^{t}+v^{t})$.

######  Definition 3.6 (MPCC-MFCQ for (I-MPCC), see [11]).

We say that the _MPCC-MFCQ_ holds for (I-MPCC) at a feasible point
$(t,u^{t},v^{t})$ if

$\displaystyle\begin{bmatrix}\partial_{1}c_{\mathcal{E}}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{V}^{t}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{Z}}&[\partial_{2}c_{\mathcal{Z}}-I]P_{\mathcal{U}^{t}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}+I]P_{\mathcal{V}^{t}_{+}}^{T}\end{bmatrix}\in\mathbb{R}^{(m_{1}+s_{t})\times(n_{t}+\lvert\mathcal{U}^{t}_{+}\rvert+\lvert\mathcal{V}^{t}_{+}\rvert)}$

has full row rank $m_{1}+s_{t}$ and if there exists a vector
$d\in\mathbb{R}^{n_{t}+\lvert\mathcal{U}^{t}_{+}\rvert+\lvert\mathcal{V}^{t}_{+}\rvert}$
such that

$\displaystyle\begin{bmatrix}\partial_{1}c_{\mathcal{E}}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{V}^{t}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{Z}}&[\partial_{2}c_{\mathcal{Z}}-I]P_{\mathcal{U}^{t}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}+I]P_{\mathcal{V}^{t}_{+}}^{T}\end{bmatrix}d$
$\displaystyle=0,$
$\displaystyle\begin{bmatrix}\partial_{1}c_{\mathcal{A}}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{V}^{t}_{+}}^{T}\end{bmatrix}d$
$\displaystyle>0.$

Again all partial derivatives are evaluated at $(t,u^{t}+v^{t})$.

As with LIKQ and IDKQ for (I-NLP), MPCC-MFCQ is weaker then MPCC-LICQ for the
counterpart MPCC of (I-NLP). The latter fact is well known, and can also be
seen easily by rewriting Example 2.6 as the counterpart MPCC and checking the
above conditions.

###  3.2 Counterpart MPCC for the Abs-Normal NLP with Inequality Slacks

Using the same approach as in the preceding paragraph, we formulate the
counterpart MPCC of (E-NLP).

######  Definition 3.7 (Counterpart MPCC of (E-NLP)).

The _counterpart MPCC_ of the abs-normal NLP (E-NLP) reads:

$\displaystyle\smash[b]{\min_{t,w,u^{t},v^{t},u^{w},v^{w}}}\
f(t)\quad\textup{s.t.}\quad$ $\displaystyle c_{\mathcal{E}}(t,u^{t}+v^{t})=0,$
$\displaystyle c_{\mathcal{I}}(t,u^{t}+v^{t})-(u^{w}+v^{w})=0,$ (E-MPCC)
$\displaystyle c_{\mathcal{Z}}(t,u^{t}+v^{t})-(u^{t}-v^{t})=0,$ $\displaystyle
w-(u^{w}-v^{w})=0,$ $\displaystyle 0\leq u^{t}\perp v^{t}\geq 0,$
$\displaystyle 0\leq u^{w}\perp v^{w}\geq 0,$

where $u^{t},v^{t}\in\mathbb{R}^{s_{t}}$ and
$u^{w},v^{w}\in\mathbb{R}^{m_{2}}$.

The feasible set of (E-MPCC) is a lifting of $\mathcal{F}_{\textup{mpcc}}$:

$\displaystyle\mathcal{F}_{\textup{e-mpcc}}$
$\displaystyle\mathrel{{\mathop{:}}{=}}\left\\{\,(t,w,u^{t},v^{t},u^{w},v^{w})\,\left|\begin{array}[]{l}c_{\mathcal{E}}(t,u^{t}+v^{t})=0,\
c_{\mathcal{I}}(t,u^{t}+v^{t})=u^{w}+v^{w},\\\
c_{\mathcal{Z}}(t,u^{t}+v^{t})=u^{t}-v^{t},\ w=u^{w}-v^{w},\\\ 0\leq
u^{t}\perp v^{t}\geq 0,\ 0\leq u^{w}\perp v^{w}\geq
0\end{array}\right.\\!\right\\}$
$\displaystyle\hphantom{:}=\left\\{\,(t,w,u^{t},v^{t},u^{w},v^{w})\,\left|\begin{array}[]{l}(t,u^{t},v^{t})\in\mathcal{F}_{\textup{mpcc}},\
c_{\mathcal{I}}(t,u^{t}+v^{t})=u^{w}+v^{w},\\\ w=u^{w}-v^{w},\ 0\leq
u^{w}\perp v^{w}\geq 0\end{array}\right.\\!\right\\}.$

Clearly, the homeomorphism between $\mathcal{F}_{\textup{mpcc}}$ and
$\mathcal{F}_{\textup{abs}}$ extends to $\mathcal{F}_{\textup{e-mpcc}}$ and
$\mathcal{F}_{\textup{e-abs}}$.

######  Lemma 3.8.

Given an abs-normal NLP (E-NLP) and its counterpart MPCC (E-MPCC), we have a
homeomorphism
$\leavevmode\bar{\phi}:\mathcal{F}_{\textup{e-mpcc}}\to\mathcal{F}_{\textup{e-abs}}$
defined as

$\displaystyle\leavevmode\bar{\phi}(t,w,u^{t},v^{t},u^{w},v^{w})$
$\displaystyle=(t,w,u^{t}-v^{t},u^{w}-v^{w}),$
$\displaystyle\leavevmode\bar{\phi}^{-1}(t,w,z^{t},z^{w})$
$\displaystyle=(t,w,[z^{t}]^{+},[z^{t}]^{-},[z^{w}]^{+},[z^{w}]^{-}).$

######  Proof 3.9.

Obvious.

######  Lemma 3.10.

MPCC-LICQ for (E-MPCC) at a feasible point $y=(t,w,u^{t},v^{t},u^{w},v^{w})$
is full row rank of

$\displaystyle J_{\textup{e-mpcc}}(y)$
$\displaystyle=\begin{bmatrix}\partial_{1}c_{\mathcal{E}}&0&\partial_{2}c_{\mathcal{E}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{V}^{t}_{+}}^{T}&0&0\\\
\partial_{1}c_{\mathcal{I}}&0&\partial_{2}c_{\mathcal{I}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{I}}P_{\mathcal{V}^{t}_{+}}^{T}&-P_{\mathcal{U}^{w}_{+}}^{T}&-P_{\mathcal{V}^{w}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{Z}}&0&[\partial_{2}c_{\mathcal{Z}}-I]P_{\mathcal{U}^{t}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}+I]P_{\mathcal{V}^{t}_{+}}^{T}&0&0\\\
0&I&0&0&-P_{\mathcal{U}^{w}_{+}}^{T}&+P_{\mathcal{V}^{w}_{+}}^{T}\end{bmatrix}$
$\displaystyle\in\mathbb{R}^{(m_{1}+m_{2}+s_{t}+m_{2})\times(n_{t}+m_{2}+\lvert\mathcal{U}^{t}_{+}\rvert+\lvert\mathcal{V}^{t}_{+}\rvert+\lvert\mathcal{U}^{w}_{+}\rvert+\lvert\mathcal{V}^{w}_{+}\rvert)},$

where all partial derivatives are evaluated at $(t,u^{t}+v^{t})$.

######  Proof 3.11.

We set $x=(t,w)$, $u=(u^{t},u^{w})$, $v=(v^{t},v^{w})$ as well as
$\leavevmode\bar{f}(x)=f(t)$,

$\leavevmode\bar{c}_{\mathcal{E}}(x,u+v)=\begin{pmatrix}c_{\mathcal{E}}(t,u^{t}+v^{t})\\\
c_{\mathcal{I}}(t,u^{t}+v^{t})-(u^{w}+v^{w}))\end{pmatrix},\quad\leavevmode\bar{c}_{\mathcal{Z}}(x,u+v)=\begin{pmatrix}c_{\mathcal{Z}}(t,u^{t}+v^{t})\\\
w\end{pmatrix}.$

Then, (E-MPCC) becomes

$\displaystyle\smash[b]{\min_{x,u,v}}\
\leavevmode\bar{f}(x)\quad\textup{s.t.}\quad$
$\displaystyle\leavevmode\bar{c}_{\mathcal{E}}(x,u+v)=0,$
($\overline{\text{E-MPCC}}$)
$\displaystyle\leavevmode\bar{c}_{\mathcal{Z}}(x,u+v)-(u-v)=0,$ $\displaystyle
0\leq u\perp v\geq 0,$

and we can compute the Jacobian from Definition 3.5 using the special
structure of (E-MPCC). The resulting matrix has the stated form, except that
the last four columns belong to variables $(u^{t},v^{t},u^{w},v^{w})$ rather
than $(u,v)=(u^{t},u^{w},v^{t},v^{w})$.

Like LIKQ for (E-NLP), MPCC-LICQ for (E-MPCC) does not depend on the
particular choice of $w$, and like IDKQ for (E-NLP), the concept of MPCC-MFCQ
for (E-MPCC) is equivalent to MPCC-LICQ since no inequalities are present
besides the complementarities.

###  3.3 Relations of MPCC Constraint Qualifications

In this paragraph we state the relations of constraint qualifications for the
two different formulations introduced in the previous paragraphs. They follow
from the results in the previous section and in the two _following_ sections.
For an illustration see Fig. 1 below. We set
$W(t,u^{t},v^{t})\mathrel{{\mathop{:}}{=}}\\{(w,u^{w},v^{w})\colon\lvert
w\rvert=c_{\mathcal{I}}(t,u^{t}+v^{t}),u^{w}=[w]^{+},v^{w}=[w]^{-}\\}$.

######  Theorem 3.12.

MPCC-LICQ for (I-MPCC) holds at
$(t,u^{t},v^{t})\in\mathcal{F}_{\textup{mpcc}}$ if and only if MPCC-LICQ for
(E-MPCC) holds at
$(t,w,u^{t},u^{w},v^{t},v^{w})\in\mathcal{F}_{\textup{e-mpcc}}$ for any (and
hence all) $(w,u^{w},v^{w})\in W(t,u^{t},v^{t})$.

######  Proof 3.13.

This follows directly from Theorem 2.12, Theorem 4.1 and Theorem 4.5.

######  Theorem 3.14.

MPCC-MFCQ for (I-MPCC) holds at
$(t,u^{t},v^{t})\in\mathcal{F}_{\textup{mpcc}}$ if MPCC-MFCQ for (E-MPCC)
holds at $(t,w,u^{t},u^{w},v^{t},v^{w})\in\mathcal{F}_{\textup{e-mpcc}}$ for
any (and hence all) $(w,u^{w},v^{w})\in W(t,u^{t},v^{t})$. The converse is not
true.

######  Proof 3.15.

This follows directly from Theorem 2.14, Theorem 4.3 and Corollary 4.7.

##  4 Kink Qualifications and MPCC Constraint Qualifications

In this section we have a closer look at relations between abs-normal NLPs and
counterpart MPCCs in both formulations.

###  4.1 Relations of General Abs-Normal NLP and MPCC

Here we use the variables $x$ and $z$ instead of $t$ and $z^{t}$ to shorten
notation because we do not consider inequality slacks. Then the general abs-
normal NLP (I-NLP) becomes:

$\displaystyle\smash[b]{\min_{x,z}}\ f(x)\quad\textup{s.t.}\quad$
$\displaystyle c_{\mathcal{E}}(x,\lvert z\rvert)=0,$ $\displaystyle
c_{\mathcal{I}}(x,\lvert z\rvert)\geq 0,$ $\displaystyle
c_{\mathcal{Z}}(x,\lvert z\rvert)-z=0.$

The counterpart MPCC (I-MPCC) reads:

$\displaystyle\smash[b]{\min_{x,u,v}}\ f(x)\quad\textup{s.t.}\quad$
$\displaystyle c_{\mathcal{E}}(x,u+v)=0,$ $\displaystyle
c_{\mathcal{I}}(x,u+v)\geq 0,$ $\displaystyle c_{\mathcal{Z}}(x,u+v)-(u-v)=0,$
$\displaystyle 0\leq u\perp v\geq 0.$

We obtain the following relations of kink qualifications and MPCC constraint
qualifications.

######  Theorem 4.1 (LIKQ $\iff$ MPCC-LICQ).

LIKQ for (I-NLP) at $x\in\mathcal{F}_{\textup{abs}}$ is equivalent to MPCC-
LICQ for (I-MPCC) at
$(x,u,v)=(x,[z(x)]^{+},[z(x)]^{-})\in\mathcal{F}_{\textup{mpcc}}$.

######  Proof 4.2.

Setting $y\mathrel{{\mathop{:}}{=}}(x,u+v)$ and
$r\mathrel{{\mathop{:}}{=}}m_{1}+\lvert\mathcal{A}\rvert+s$, MPCC-LICQ for the
counterpart MPCC is

$\displaystyle\operatorname{rank}\begin{bmatrix}\partial_{1}c_{\mathcal{E}}(y)&\partial_{2}c_{\mathcal{E}}(y)P_{\mathcal{U}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}(y)P_{\mathcal{V}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{A}}(y)&\partial_{2}c_{\mathcal{A}}(y)P_{\mathcal{U}_{+}}^{T}&\partial_{2}c_{\mathcal{A}}(y)P_{\mathcal{V}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{Z}}(y)&[\partial_{2}c_{\mathcal{Z}}(y)-I]P_{\mathcal{U}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}(y)+I]P_{\mathcal{V}_{+}}^{T}\end{bmatrix}=r.$

By negating the second column and combining it with the third column, this is
equivalent to

$\displaystyle\operatorname{rank}\begin{bmatrix}\partial_{1}c_{\mathcal{E}}(y)&-\partial_{2}c_{\mathcal{E}}(y)\Sigma
P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{A}}(y)&-\partial_{2}c_{\mathcal{A}}(y)\Sigma
P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{Z}}(y)&[I-\partial_{2}c_{\mathcal{Z}}(y)\Sigma]P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}\end{bmatrix}=r$

and, by non-singularity of $I-\partial_{2}c_{\mathcal{Z}}(y)\Sigma$, to

$\displaystyle\operatorname{rank}\begin{bmatrix}\partial_{1}c_{\mathcal{E}}(y)&-\partial_{2}c_{\mathcal{E}}(y)\Sigma
P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{A}}(y)&-\partial_{2}c_{\mathcal{A}}(y)\Sigma
P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}\\\
[I-\partial_{2}c_{\mathcal{Z}}(y)\Sigma]^{-1}\partial_{1}c_{\mathcal{Z}}(y)&P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}\end{bmatrix}=r.$

Next, we use the third row to eliminate the entries above
$P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}$ to obtain

$\displaystyle\operatorname{rank}\begin{bmatrix}\partial_{1}c_{\mathcal{E}}(y)+\partial_{2}c_{\mathcal{E}}(y)\Sigma[I-\partial_{2}c_{\mathcal{Z}}(y)\Sigma]^{-1}\partial_{1}c_{\mathcal{Z}}(y)&0\\\
\partial_{1}c_{\mathcal{A}}(y)+\partial_{2}c_{\mathcal{A}}(y)\Sigma[I-\partial_{2}c_{\mathcal{Z}}(y)\Sigma]^{-1}\partial_{1}c_{\mathcal{Z}}(y)&0\\\
[I-\partial_{2}c_{\mathcal{Z}}(y)\Sigma]^{-1}\partial_{1}c_{\mathcal{Z}}(y)&P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}\end{bmatrix}=r,$

which we can write with $u+v=\lvert z\rvert=\lvert z(x)\rvert$ as

$\displaystyle\operatorname{rank}\begin{bmatrix}\partial_{x}c_{\mathcal{E}}(x,\lvert
z(x)\rvert)&0\\\ \partial_{x}c_{\mathcal{A}}(x,\lvert z(x)\rvert)&0\\\
\partial_{x}z(x)&P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}\end{bmatrix}=r.$

Finally, since $\alpha=\mathcal{D}$ is the complement of
$\mathcal{U}_{+}\cup\mathcal{V}_{+}$, this is equivalent to

$\displaystyle\operatorname{rank}\begin{bmatrix}\partial_{x}c_{\mathcal{E}}(x,\lvert
z(x)\rvert)\\\ \partial_{x}c_{\mathcal{A}}(x,\lvert z(x)\rvert)\\\
[e_{i}^{T}\partial_{x}z(x)]_{i\in\alpha}\end{bmatrix}=m_{1}+\lvert\mathcal{A}\rvert+\lvert\alpha\rvert,$

which is LIKQ for the abs-normal NLP.

######  Theorem 4.3 (IDKQ $\iff$ MPCC-MFCQ).

IDKQ for (I-NLP) at $x\in\mathcal{F}_{\textup{abs}}$ is equivalent to MPCC-
MFCQ for (I-MPCC) at
$(x,u,v)=(x,[z(x)]^{+},[z(x)]^{-})\in\mathcal{F}_{\textup{mpcc}}$.

######  Proof 4.4.

Again with $y\mathrel{{\mathop{:}}{=}}(x,u+v)$, MPCC-MFCQ for the counterpart
MPCC is

  1. 1.

full row rank of

$\displaystyle\begin{bmatrix}\partial_{1}c_{\mathcal{E}}(y)&\partial_{2}c_{\mathcal{E}}(y)P_{\mathcal{U}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}(y)P_{\mathcal{V}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{Z}}(y)&[\partial_{2}c_{\mathcal{Z}}(y)-I]P_{\mathcal{U}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}(y)+I]P_{\mathcal{V}_{+}}^{T}\end{bmatrix}\in\mathbb{R}^{(m_{1}+s)\times(n+\lvert\mathcal{U}_{+}\cup\mathcal{V}_{+}\rvert)}.$

As in the proof of Theorem 4.1, this is seen to be full row rank of

$\displaystyle\begin{bmatrix}\partial_{x}c_{\mathcal{E}}(x,\lvert
z(x)\rvert)\\\
[e_{i}^{T}\partial_{x}z(x)]_{i\in\alpha}\end{bmatrix}\in\mathbb{R}^{(m_{1}+\lvert\alpha\rvert)\times
n}.$

  2. 2.

the existence of a vector
$d=(d_{x},d_{u},d_{v})\in\mathbb{R}^{n+\lvert\mathcal{U}_{+}\cup\mathcal{V}_{+}\rvert}$
such that

$\displaystyle\begin{bmatrix}\partial_{1}c_{\mathcal{E}}(y)&\partial_{2}c_{\mathcal{E}}(y)P_{\mathcal{U}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}(y)P_{\mathcal{V}_{+}}^{T}\\\
\partial_{1}c_{\mathcal{Z}}(y)&[\partial_{2}c_{\mathcal{Z}}(y)-I]P_{\mathcal{U}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}(y)+I]P_{\mathcal{V}_{+}}^{T}\end{bmatrix}d=0,$
$\displaystyle\begin{bmatrix}\partial_{1}c_{\mathcal{A}}(y)&\partial_{2}c_{\mathcal{A}}(y)P_{\mathcal{U}_{+}}^{T}&\partial_{2}c_{\mathcal{A}}(y)P_{\mathcal{V}_{+}}^{T}\\\
\end{bmatrix}d>0.$

We combine $d_{u}$ and $-d_{v}$ to
$d_{uv}\in\mathbb{R}^{\lvert\mathcal{U}_{+}\cup\mathcal{V}_{+}\rvert}$. Then
this is equivalent to

$\displaystyle\partial_{1}c_{\mathcal{E}}(y)d_{x}+\partial_{2}c_{\mathcal{E}}(y)\Sigma
P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}d_{uv}$ $\displaystyle=0,$
$\displaystyle\partial_{1}c_{\mathcal{Z}}(y)d_{x}-[I-\partial_{2}c_{\mathcal{Z}}(y)\Sigma]P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}d_{uv}$
$\displaystyle=0,$
$\displaystyle\partial_{1}c_{\mathcal{A}}(y)d_{x}+\partial_{2}c_{\mathcal{A}}(y)\Sigma
P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}d_{uv}$ $\displaystyle>0.$

The second condition can be written as

(3)
$[I-\partial_{2}c_{\mathcal{Z}}(y)\Sigma]^{-1}\partial_{1}c_{\mathcal{Z}}(y)d_{x}=P_{\mathcal{U}_{+}\cup\mathcal{V}_{+}}^{T}d_{uv}.$

Multiplying this by $P_{\mathcal{D}}^{T}=P_{\alpha}^{T}$ yields

$\left[e_{i}^{T}[I-\partial_{2}c_{\mathcal{Z}}(y)\Sigma]^{-1}\partial_{1}c_{\mathcal{Z}}(y)\right]_{i\in\alpha}d_{x}=[e_{i}^{T}\partial_{x}z(x)]_{i\in\alpha}d_{x}=0.$

With $u+v=\lvert z\rvert=\lvert z(x)\rvert$, substituting the right-hand side
of (3) into the first and third condition finally gives

$\displaystyle\partial_{x}c_{\mathcal{E}}(x,\lvert z(x)\rvert)d_{x}$
$\displaystyle=0,$
$\displaystyle[e_{i}^{T}\partial_{x}z(x)]_{i\in\alpha}d_{x}$
$\displaystyle=0,$ $\displaystyle\partial_{x}c_{\mathcal{A}}(x,\lvert
z(x)\rvert)d_{x}$ $\displaystyle>0,$

which is IDKQ for the abs-normal NLP.

###  4.2 Relations of Abs-Normal NLP and MPCC with Inequality Slacks

As the reformulation with inequality slacks is just a specialization of the
general case, we do without proofs and give remarks where differences occur.

Using the short notation ($\overline{\text{E-NLP}}$) for (E-NLP) (see proof of
Lemma 2.9) and similarly ($\overline{\text{E-MPCC}}$) for the counterpart MPCC
(E-MPCC) (see proof of Lemma 3.10), we obtain the same relation between LIKQ
and MPCC-LICQ as in the previous paragraph.

######  Theorem 4.5 (LIKQ $\iff$ MPCC-LICQ).

LIKQ for (E-NLP) at $x\in\mathcal{F}_{\textup{e-abs}}$ is equivalent to MPCC-
LICQ for (E-MPCC) at
$(x,u,v)=(x,[z(x)]^{+},[z(x)]^{-})\in\mathcal{F}_{\textup{e-mpcc}}$.

######  Proof 4.6.

This follows as in the proof of Theorem 4.1.

Note that this directly implies the next result since LIKQ and IDKQ as well as
MPCC-LICQ and MPCC-MFCQ coincide in the purely equality constrained setting.

######  Corollary 4.7 (IDKQ $\iff$ MPCC-MFCQ).

IDKQ for (E-NLP) at $x\in\mathcal{F}_{\textup{e-abs}}$ is equivalent to MPCC-
MFCQ for (E-MPCC) at
$(x,u,v)=(x,[z(x)]^{+},[z(x)]^{-})\in\mathcal{F}_{\textup{e-mpcc}}$.

${{\begin{array}[]{c}\textup{Reformulation}\\\
\textup{\eqref{eq:e-anf}}\end{array}}}$
${{\begin{array}[]{c}\textup{Reformulation}\\\
\textup{\eqref{eq:e-mpcc}}\end{array}}}$
${{\begin{array}[]{c}\textup{\kern-3.0ptAbs-normal NLP}\\\
\textup{\eqref{eq:i-anf}}\end{array}}}$ ${{\begin{array}[]{c}\textup{General
MPCC}\\\ \textup{\eqref{eq:i-mpcc}}\end{array}}}$ Corollary 4.7Theorem
4.5Theorem 2.14Theorem 2.12(implied)(implied)Theorem 4.1Theorem 4.3 Figure 1:
Solid arrows: relations between LIKQ and MPCC-LICQ; dashed arrows: relations
between IDKQ and MPCC-MFCQ.

##  5 Optimality Conditions

In this section we consider first and second order optimality conditions for
(I-MPCC) under MPCC-LICQ and for (I-NLP) under LIKQ, respectively, and discuss
their relations. Since both regularity conditions are invariant under the
slack reformulation by Theorem 2.12 and Theorem 3.12, the results hold also
for (E-MPCC) and (E-NLP). Conditions for general MPCCs can be found in the
literature; in case of first order conditions for example in [10, 11]. Second
order conditions stated in [10, 11] however have to be adapted to our
different setting. For the abs-normal NLP (E-NLP) we have derived first and
second order conditions in [9]. Since LIKQ is preserved under the slack
reformulation by Theorem 2.12, we can transfer these results directly to
(I-NLP).

###  5.1 First Order Optimality Conditions

In this paragraph, we compare stationarity concepts and first order optimality
conditions for (I-MPCC) and (I-NLP). First, we define strong stationarity for
(I-MPCC) and state the corresponding first order conditions.

######  Definition 5.1 (Strong Stationarity, see [10, §3.3], [11, Thm. 2]).

A feasible point $y^{*}=(t^{*},(u^{t})^{*},(v^{t})^{*})$ of (I-MPCC) is
_strongly stationary_ (_S-stationary_) if there exist multipliers
$\lambda=(\lambda_{\mathcal{E}},\lambda_{\mathcal{I}},\lambda_{\mathcal{Z}})$
and $\mu=(\mu_{u},\mu_{v})$ such that the following conditions are satisfied:

(4a) $\displaystyle\partial_{y}\mathcal{L}_{\perp}(y^{*},\lambda,\mu)$
$\displaystyle=0,$ (4b) $\displaystyle(\mu_{u})_{i}\geq 0,\ (\mu_{v})_{i}$
$\displaystyle\geq 0,\quad i\in\mathcal{D}^{t}(t^{*}),$ (4c)
$\displaystyle(\mu_{u})_{i}$ $\displaystyle=0,\quad
i\in\mathcal{U}^{t}_{+}(t^{*}),$ (4d) $\displaystyle(\mu_{v})_{i}$
$\displaystyle=0,\quad i\in\mathcal{V}^{t}_{+}(t^{*}),$ (4e)
$\displaystyle\lambda_{\mathcal{I}}$ $\displaystyle\geq 0,$ (4f)
$\displaystyle\lambda_{\mathcal{I}}^{T}c_{\mathcal{I}}(t^{*},(u^{t})^{*}+(v^{t})^{*})$
$\displaystyle=0.$

Herein, $\mathcal{L}_{\perp}$ is the MPCC-Lagrangian function associated with
(I-MPCC):

$\displaystyle\mathcal{L}_{\perp}(y,\lambda,\mu)\mathrel{{\mathop{:}}{=}}f(t)$
$\displaystyle+\lambda_{\mathcal{E}}^{T}c_{\mathcal{E}}(t,u^{t}+v^{t})-\lambda_{\mathcal{I}}^{T}c_{\mathcal{I}}(t,u^{t}+v^{t})$
$\displaystyle+\lambda_{\mathcal{Z}}^{T}[c_{\mathcal{Z}}(t,u^{t}+v^{t})-(u^{t}-v^{t})]-\mu_{u}^{T}u^{t}-\mu_{v}^{T}v^{t}.$

######  Theorem 5.2 (First Order Optimality Conditions for (I-MPCC)).

Assume that $(t^{*},(u^{t})^{*},(v^{t})^{*})$ is a local minimizer of (I-MPCC)
and that MPCC-LICQ holds at $(t^{*},(u^{t})^{*},(v^{t})^{*})$. Then,
$(t^{*},(u^{t})^{*},(v^{t})^{*})$ is an S-stationary point.

######  Proof 5.3.

The proof is due to [10, §3.3] and is presented in [11, Thm. 2] in the form
used here.

Now, kink stationarity is defined and the corresponding first order optimality
conditions are formulated.

######  Definition 5.4 (Kink Stationarity, see [9]).

A feasible point $(t^{*},(z^{t})^{*})$ of (I-NLP) is _kink stationary_ if
there exist multipliers
$\lambda=(\lambda_{\mathcal{E}},\lambda_{\mathcal{I}},\lambda_{\mathcal{Z}})$
such that the following conditions are satisfied:

(5a) $\displaystyle\qquad
f^{\prime}(t^{*})+\lambda_{\mathcal{E}}^{T}\partial_{1}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{1}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}\partial_{1}c_{\mathcal{Z}}$
$\displaystyle=0,$ (5b)
$\displaystyle[\lambda_{\mathcal{E}}^{T}\partial_{2}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{2}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}\partial_{2}c_{\mathcal{Z}}]_{i}$
$\displaystyle\geq\lvert(\lambda_{\mathcal{Z}})_{i}\rvert,$ $\displaystyle i$
$\displaystyle\in\alpha^{t}(t^{*}),\qquad$ (5c)
$\displaystyle[\lambda_{\mathcal{E}}^{T}\partial_{2}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{2}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}\partial_{2}c_{\mathcal{Z}}]_{i}$
$\displaystyle=(\lambda_{\mathcal{Z}})_{i}(\sigma^{t})^{*}_{i},$
$\displaystyle i$ $\displaystyle\notin\alpha^{t}(t^{*}),$ (5d)
$\displaystyle\lambda_{\mathcal{I}}$ $\displaystyle\geq 0,$ (5e)
$\displaystyle\lambda_{\mathcal{I}}^{T}c_{\mathcal{I}}$ $\displaystyle=0.$

Here, the constraints and the partial derivatives are evaluated at
$(t^{*},\lvert(z^{t})^{*}\rvert)$.

######  Theorem 5.5 (First Order Conditions for (I-NLP)).

Assume that $(t^{*},(z^{t})^{*})$ is a local minimizer of (I-NLP) and that
LIKQ holds at $t^{*}$. Then, $(t^{*},(z^{t})^{*})$ is a kink stationary point.

######  Proof 5.6.

By Theorem 2.12 we may consider the slack reformulation (E-NLP) instead of
(I-NLP). In [9, Theorem 5.10], conditions (5) were proven for
($\overline{\text{E-NLP}}$) using a splitting of the switching variables $z$
and the switching constraints $c_{\mathcal{Z}}$. Without the splitting they
read:

$\displaystyle\qquad\leavevmode\bar{f}^{\prime}(x^{*})+\leavevmode\bar{\lambda}_{\mathcal{E}}^{T}\partial_{1}\leavevmode\bar{c}_{\mathcal{E}}(x^{*},\lvert
z^{*}\rvert)+\leavevmode\bar{\lambda}_{\mathcal{Z}}^{T}\partial_{1}\leavevmode\bar{c}_{\mathcal{Z}}(x^{*},\lvert
z^{*}\rvert)$ $\displaystyle=0,$
$\displaystyle[\leavevmode\bar{\lambda}_{\mathcal{E}}^{T}\partial_{2}\leavevmode\bar{c}_{\mathcal{E}}(x^{*},\lvert
z^{*}\rvert)+\leavevmode\bar{\lambda}_{\mathcal{Z}}^{T}\partial_{2}\leavevmode\bar{c}_{\mathcal{Z}}(x^{*},\lvert
z^{*}\rvert)]_{i}$
$\displaystyle\geq\lvert(\leavevmode\bar{\lambda}_{\mathcal{Z}})_{i}\rvert,$
$\displaystyle i$ $\displaystyle\in\alpha(x^{*}),\qquad$
$\displaystyle[\leavevmode\bar{\lambda}_{\mathcal{E}}^{T}\partial_{2}\leavevmode\bar{c}_{\mathcal{E}}(x^{*},\lvert
z^{*}\rvert)+\leavevmode\bar{\lambda}_{\mathcal{Z}}^{T}\partial_{2}\leavevmode\bar{c}_{\mathcal{Z}}(x^{*},\lvert
z^{*}\rvert)]_{i}$
$\displaystyle=(\leavevmode\bar{\lambda}_{\mathcal{Z}})_{i}\sigma^{*}_{i},$
$\displaystyle i$ $\displaystyle\notin\alpha(x^{*}).$

We rewrite these conditions in the original notation of (E-NLP) with
$\leavevmode\bar{\lambda}_{\mathcal{E}}=(\lambda_{\mathcal{E}},-\lambda_{\mathcal{I}})$
and
$\leavevmode\bar{\lambda}_{\mathcal{Z}}=(\lambda_{\mathcal{Z}},\lambda_{\mathcal{Z}}^{w})$,
where all derivatives are evaluated at $(t^{*},\lvert(z^{t})^{*}\rvert)$:

$\displaystyle\qquad
f^{\prime}(t^{*})+\lambda_{\mathcal{E}}^{T}\partial_{1}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{1}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}\partial_{1}c_{\mathcal{Z}}$
$\displaystyle=0,$ $\displaystyle(\lambda_{\mathcal{Z}}^{w})^{T}$
$\displaystyle=0,$
$\displaystyle[\lambda_{\mathcal{E}}^{T}\partial_{2}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{2}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}\partial_{2}c_{\mathcal{Z}}]_{i}$
$\displaystyle\geq\lvert(\lambda_{\mathcal{Z}})_{i}\rvert,$ $\displaystyle i$
$\displaystyle\in\alpha^{t}(t^{*}),$
$\displaystyle[\lambda_{\mathcal{E}}^{T}\partial_{2}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{2}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}\partial_{2}c_{\mathcal{Z}}]_{i}$
$\displaystyle=(\lambda_{\mathcal{Z}})_{i}(\sigma^{t})_{i}^{*},$
$\displaystyle i$ $\displaystyle\notin\alpha^{t}(t^{*}),$
$\displaystyle\lambda_{\mathcal{I}}$
$\displaystyle\geq\lvert(\lambda_{\mathcal{Z}}^{w})_{i}\rvert,$ $\displaystyle
i$ $\displaystyle\in\alpha^{w}(w^{*}),$ $\displaystyle\lambda_{\mathcal{I}}$
$\displaystyle=(\lambda_{\mathcal{Z}}^{w})_{i}\sigma_{i}^{*},$ $\displaystyle
i$ $\displaystyle\notin\alpha^{w}(w^{*}).\qquad$

The claim follows by eliminating $\lambda_{\mathcal{Z}}^{w}=0$ and noting that
$\alpha^{w}(w^{*})=\mathcal{A}(t^{*})$.

The next theorem shows that the two stationarity concepts coincide.

######  Theorem 5.7 (S-Stationarity is Kink Stationarity).

A feasible point $(t^{*},(z^{t})^{*})$ of (I-NLP) is kink stationary if and
only if
$(t^{*},(u^{t})^{*},(v^{t})^{*})=(t^{*},[z^{t}(t^{*})]^{+},[z^{t}(t^{*})]^{-})$
of (I-MPCC) is S-stationary.

######  Proof 5.8.

Comparison of the stationarity conditions of (I-NLP) and (I-MPCC) shows
directly that (4e) and (5d) as well as (4f) and (5e) coincide. Thus, we have
to compare the remaining conditions (4a) to (4d) for (I-MPCC) with (5a) to
(5c) for (I-NLP). Condition (4a) of (I-MPCC), where all derivatives are
evaluated at $(t^{*},(u^{t})^{*}+(v^{t})^{*})$, is

$\displaystyle
f^{\prime}(t^{*})+\lambda_{\mathcal{E}}^{T}\partial_{1}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{1}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}\partial_{1}c_{\mathcal{Z}}$
$\displaystyle=0,$
$\displaystyle\lambda_{\mathcal{E}}^{T}\partial_{2}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{2}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}[\partial_{2}c_{\mathcal{Z}}-I]-\mu_{u}^{T}$
$\displaystyle=0,$
$\displaystyle\lambda_{\mathcal{E}}^{T}\partial_{2}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{2}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}[\partial_{2}c_{\mathcal{Z}}+I]-\mu_{v}^{T}$
$\displaystyle=0.$

The first condition coincides with (5a). We combine the second and the third
condition with conditions (4b) to (4d), yielding

$\displaystyle\qquad\left[\lambda_{\mathcal{E}}^{T}\partial_{2}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{2}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}\partial_{2}c_{\mathcal{Z}}\hphantom{[{}+I]}\right]_{i}$
$\displaystyle=+(\lambda_{\mathcal{Z}})_{i},$ $\displaystyle i$
$\displaystyle\in\mathcal{U}^{t}_{+}(t^{*}),\qquad$
$\displaystyle\left[\lambda_{\mathcal{E}}^{T}\partial_{2}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{2}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}\partial_{2}c_{\mathcal{Z}}\hphantom{[{}+I]}\right]_{i}$
$\displaystyle=-(\lambda_{\mathcal{Z}})_{i},$ $\displaystyle i$
$\displaystyle\in\mathcal{V}^{t}_{+}(t^{*}),$
$\displaystyle\left[\lambda_{\mathcal{E}}^{T}\partial_{2}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{2}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}[\partial_{2}c_{\mathcal{Z}}\pm
I]\right]_{i}$ $\displaystyle\geq 0,$ $\displaystyle i$
$\displaystyle\in\mathcal{D}^{t}(t^{*}).$

These are precisely conditions (5b) and (5c) for (I-NLP) by definition of the
index sets and of $\sigma^{*}$.

As LIKQ for (I-NLP) is equivalent to MPCC-LICQ for (I-MPCC), the previous
theorem provides a different perspective on Theorem 5.5 and Theorem 5.2: one
can be obtained from the other directly via Theorem 5.7 and vice versa.

###  5.2 Second Order Conditions

In this paragraph, we compare second-order conditions for MPCCs and abs-normal
NLPs.

First, we formulate them for (I-MPCC). This is based on material from [11] for
MPCCs, but some additional assumptions on the Lagrange multipliers need to be
made. These are given in the next definition.

######  Definition 5.9 (MPCC-Strict Complementarity).

Consider a strongly stationary point $(t^{*},(u^{t})^{*},(v^{t})^{*})$ with
Lagrange multipliers $(\lambda^{*},\mu^{*})$. We say that _MPCC-strict
complementarity_ holds if $\lambda_{i}^{*}>0$ for all $i\in\mathcal{A}$ as
well as $(\mu_{u}^{*})_{i}>0$ and $(\mu_{v}^{*})_{i}>0$ for all
$i\in\mathcal{D}^{t}$.

We will show in the next lemma that under MPCC-LICQ and MPCC-strict
complementarity the critical cone reduces to the nullspace of the Jacobian of
the tightened NLP (with columns reordered according to the index sets
$\mathcal{U}^{t}_{+},\mathcal{U}^{t}_{0},\mathcal{V}^{t}_{+},\mathcal{V}^{t}_{0}$),

$\displaystyle
J(y^{*})=\begin{bmatrix}\partial_{1}c_{\mathcal{E}}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{U}^{t}_{0}}^{T}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{V}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{E}}P_{\mathcal{V}^{t}_{0}}^{T}\\\
\partial_{1}c_{\mathcal{A}}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{U}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{U}^{t}_{0}}^{T}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{V}^{t}_{+}}^{T}&\partial_{2}c_{\mathcal{A}}P_{\mathcal{V}^{t}_{0}}^{T}\\\
\partial_{1}c_{\mathcal{Z}}&[\partial_{2}c_{\mathcal{Z}}-I]P_{\mathcal{U}^{t}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}-I]P_{\mathcal{U}^{t}_{0}}^{T}&[\partial_{2}c_{\mathcal{Z}}+I]P_{\mathcal{V}^{t}_{+}}^{T}&[\partial_{2}c_{\mathcal{Z}}+I]P_{\mathcal{V}^{t}_{0}}^{T}\\\
0&0&I&0&0\\\ 0&0&0&0&I\end{bmatrix},$

as introduced in Section 3.1. Here, all partial derivatives are evaluated at
the point $(t^{*},(u^{t})^{*}+(v^{t})^{*})$. It is readily verified that the
nullspace of $J(y^{*})$ is spanned by the matrix

(6) $U_{\textup{mpcc}}(y^{*})=\begin{bmatrix}I\\\
+P_{\mathcal{U}^{t}_{+}}(I-\partial_{2}c_{\mathcal{Z}}\Sigma^{t})^{-1}\partial_{1}c_{\mathcal{Z}}\\\
0\\\
-P_{\mathcal{V}^{t}_{+}}(I-\partial_{2}c_{\mathcal{Z}}\Sigma^{t})^{-1}\partial_{1}c_{\mathcal{Z}}\\\
0\end{bmatrix}\tilde{U}(y^{*})$

where $\tilde{U}(y^{*})$ spans the nullspace of

(7)
$\begin{bmatrix}\partial_{1}c_{\mathcal{E}}+\partial_{2}c_{\mathcal{E}}\Sigma^{t}(I-\partial_{2}c_{\mathcal{Z}}\
\Sigma^{t})^{-1}\partial_{1}c_{\mathcal{Z}}\\\
\partial_{1}c_{\mathcal{A}}+\partial_{2}c_{\mathcal{A}}\Sigma^{t}(I-\partial_{2}c_{\mathcal{Z}}\
\Sigma^{t})^{-1}\partial_{1}c_{\mathcal{Z}}\\\
[e_{i}^{T}(I-\partial_{2}c_{\mathcal{Z}}\Sigma^{t})^{-1}\partial_{1}c_{\mathcal{Z}}]_{i\in\mathcal{D}^{t}}\end{bmatrix}.$

Second order necessary and sufficient conditions for a slightly more general
class of MPCCs are given in [11, Theorem 7] using the concept of critical
directions. We first specialize the definition from [11] to our setting.

######  Definition 5.10 (Critical Direction).

A vector
$d=(dt,du^{t},dv^{t})\in\mathbb{R}^{n_{t}}\times\mathbb{R}^{s_{t}}\times\mathbb{R}^{s_{t}}$
is called a _critical direction_ at a weakly stationary point $y^{*}$ of
(I-MPCC) if

(8a) $\displaystyle\min(du^{t}_{i},dv^{t}_{i})$ $\displaystyle=0,\quad
i\in\mathcal{D}^{t},$ (8b) $\displaystyle du^{t}_{i}$ $\displaystyle=0,\quad
i\in\mathcal{V}^{t}_{+},$ (8c) $\displaystyle dv^{t}_{i}$
$\displaystyle=0,\quad i\in\mathcal{U}^{t}_{+},$ (8d)
$\displaystyle\partial_{1}c_{\mathcal{A}}du^{t}+\partial_{2}c_{\mathcal{A}}(du^{t}+dv^{t})$
$\displaystyle\geq 0,$ (8e)
$\displaystyle\partial_{1}c_{\mathcal{E}}du^{t}+\partial_{2}c_{\mathcal{E}}(du^{t}+dv^{t})$
$\displaystyle=0,$ (8f)
$\displaystyle\partial_{1}c_{\mathcal{Z}}du^{t}+[\partial_{2}c_{\mathcal{Z}}-I]du^{t}+[\partial_{2}c_{\mathcal{Z}}+I]dv^{t}$
$\displaystyle=0,$ (8g) $\displaystyle f^{\prime}(t^{*})dt$ $\displaystyle=0,$

where all constraint derivatives are evaluated at
$(t^{*},(u^{t})^{*}+(v^{t})^{*})$.

The set of critical directions is just the nullspace of $J(y^{*})$ under
stronger assumptions.

######  Lemma 5.11.

Assume that MPCC-LICQ and MPCC-strict complementarity hold at an S-stationary
point $y^{*}=(t^{*},(u^{t})^{*},(v^{t})^{*})$ of (I-MPCC) with Lagrange
multipliers $(\lambda^{*},\mu^{*})$. Then, the set of critical directions is
$\ker J(y^{*})$.

######  Proof 5.12.

First consider a critical direction $d=(dt,du^{t},dv^{t})$ at the strongly
(hence weakly) stationary point $y^{*}$. Then, (8e) and (8f) imply that rows
one and three of $J(y^{*})d$ vanish, and by (4a) and (8g) we further have

$\displaystyle 0$
$\displaystyle=\partial_{t,u^{t},v^{t}}\mathcal{L}_{\perp}(y^{*},\lambda^{*},\mu^{*})d$
$\displaystyle=f^{\prime}(t^{*})dt+(\lambda_{\mathcal{E}}^{*})^{T}[\partial_{1}c_{\mathcal{E}}dt+\partial_{2}c_{\mathcal{E}}(du^{t}+dv^{t})]$
$\displaystyle\quad{}-(\lambda_{\mathcal{I}}^{*})^{T}[\partial_{1}c_{\mathcal{I}}dt+\partial_{2}c_{\mathcal{I}}(du^{t}+dv^{t})]$
$\displaystyle\quad{}+(\lambda_{\mathcal{Z}}^{*})^{T}[\partial_{1}c_{\mathcal{Z}}dt+(\partial_{2}c_{\mathcal{Z}}-I)du^{t}+(\partial_{2}c_{\mathcal{Z}}+I)dv^{t}]$
$\displaystyle\quad{}-(\mu_{u}^{*})^{T}du^{t}-(\mu_{v}^{*})^{T}dv^{t}$
$\displaystyle=-(\lambda_{\mathcal{I}}^{*})^{T}[\partial_{1}c_{\mathcal{I}}dt+\partial_{2}c_{\mathcal{I}}(du^{t}+dv^{t})]-(\mu_{u}^{*})^{T}du^{t}-(\mu_{v}^{*})^{T}dv^{t}.$

With $(\lambda_{\mathcal{I}}^{*})^{T}c_{\mathcal{I}}=0$ (4f),
$(\mu_{u}^{*})_{i}=0$ for $i\in\mathcal{U}^{t}_{+}$ (4c),
$(\mu_{v}^{*})_{i}=0$ for $i\in\mathcal{V}^{t}_{+}$ (4d), and (8b), (8c) we
obtain $(\lambda_{\mathcal{I}}^{*})_{i}=0$ for $i\notin\mathcal{A}$ and
further

$0=(\lambda_{\mathcal{A}}^{*})^{T}[\partial_{1}c_{\mathcal{A}}du^{t}+\partial_{2}c_{\mathcal{A}}(du^{t}+dv^{t})]+\sum_{i\in\mathcal{D}^{t}}[(\mu_{u}^{*})_{i}du^{t}_{i}+(\mu_{v}^{*})_{i}dv^{t}_{i}].$

All factors in this sum of products are nonnegative by (4b), (4e), (8d), and
(8a), which implies

$\displaystyle 0$
$\displaystyle=(\lambda_{\mathcal{A}}^{*})^{T}[\partial_{1}c_{\mathcal{A}}du^{t}+\partial_{2}c_{\mathcal{A}}(du^{t}+dv^{t})],$
$\displaystyle 0$
$\displaystyle=(\mu_{u}^{*})_{i}du_{i}^{t}=(\mu_{v}^{*})_{i}dv_{i}^{t},\quad
i\in\mathcal{D}^{t}.$

Finally, by MPCC-strict complementarity we have

$\displaystyle 0$
$\displaystyle=\partial_{1}c_{\mathcal{A}}du^{t}+\partial_{2}c_{\mathcal{A}}(du^{t}+dv^{t}),$
$\displaystyle 0$ $\displaystyle=du^{t}_{i}=dv^{t}_{i},\quad
i\in\mathcal{D}^{t},$

and $du^{t}_{i}=0$ for $i\in\mathcal{U}^{t}_{0}$ as well as $dv^{t}_{i}=0$ for
$i\in\mathcal{V}^{t}_{0}$ follow since
$\mathcal{U}^{t}_{0}=\mathcal{V}^{t}_{+}\cup\mathcal{D}^{t}$ and
$\mathcal{V}^{t}_{0}=\mathcal{U}^{t}_{+}\cup\mathcal{D}^{t}$. Thus $d$ is a
nullspace vector of $J(y^{*})$.

Conversely, given any nullspace vector $d=(dt,du^{t},dv^{t})$, the first three
rows of $J(y^{*})d=0$ yield conditions (8e), (8d), and (8f), with equality
“$=0$” in case of (8d). The last two rows yield $du^{t}_{i}=0$ for
$i\in\mathcal{U}^{t}_{0}$ and $dv^{t}_{i}=0$ for $i\in\mathcal{V}^{t}_{0}$,
hence (8b), (8c), and $du^{t}_{i}=dv^{t}_{i}=0$ for $i\in\mathcal{D}^{t}$
(8a). Moreover, we have $(\mu_{u}^{*})_{i}=0$ for $i\in\mathcal{U}^{t}_{+}$
(4c), $(\mu_{v}^{*})_{i}=0$ for $i\in\mathcal{V}^{t}_{+}$ (4d), and
$(\lambda_{\mathcal{I}}^{*})_{i}=0$ for $i\notin\mathcal{A}$ (4f), so that
(4a) becomes (8g):

$0=\partial_{t,u^{t},v^{t}}\mathcal{L}_{\perp}(y^{*},\lambda^{*},\mu^{*})d=f^{\prime}(t^{*})dt.$

Thus $d$ is a critical direction.

Now we use [11, Theorem 7] to prove second order necessary and sufficient
conditions for our setting.

######  Theorem 5.13 (Second Order Necessary Conditions for (I-MPCC)).

Assume that $y^{*}=(t^{*},(u^{t})^{*},(v^{t})^{*})$ is a local minimizer of
(I-MPCC) and that MPCC-LICQ holds at $y^{*}$. Denote by
$(\lambda^{*},\mu^{*})$ the unique Lagrange multiplier vector and assume
further that MPCC-strict complementarity holds. Then,

$\displaystyle
U_{\textup{mpcc}}(y^{*})^{T}H_{\textup{mpcc}}(y^{*},\lambda^{*})U_{\textup{mpcc}}(y^{*})\geq
0$

where
$H_{\textup{mpcc}}(y^{*},\lambda^{*})=\partial^{2}_{yy}\mathcal{L}_{\perp}(y^{*},\lambda^{*},\mu^{*})$.
(Note that $\partial^{2}_{yy}\mathcal{L}_{\perp}$ does not depend on
$\mu^{*}$.)

######  Proof 5.14.

The first part of Theorem 7 in [11] asserts that every critical direction $d$
satisfies the inequality $d^{T}H_{\textup{mpcc}}(y^{*},\lambda^{*})d\geq 0$ at
a local minimizer $y^{*}$ if MPCC-SMFCQ (cf. [10]) holds at $y^{*}$. Since
MPCC-LICQ implies MPCC-SMFCQ and the set of critical directions is $\ker
J(y^{*})$ under our stronger assumptions, the claim follows directly from [11,
Theorem 7].

######  Remark 5.15.

Here we have simplified the exposition by making the assumption of MPCC-strict
complementarity, so that we can directly rely on [11, Theorem 7]. However, the
second order necessary conditions can also be proved without MPCC-strict
complementarity by considering branch problems of (I-MPCC). The corresponding
approach for (I-NLP) has been taken in [9], so that Theorem 5.18 below does
not require strict complementarity.

######  Theorem 5.16 (Second Order Sufficient Conditions for (I-MPCC)).

Assume that $y^{*}=(t^{*},(u^{t})^{*},(v^{t})^{*})$ is strongly stationary for
(I-MPCC) with Lagrange multiplier vector $(\lambda^{*},\mu^{*})$ satisfying
MPCC-strict complementarity. Assume further that MPCC-LICQ holds at $y^{*}$,
and that

$\displaystyle
U_{\textup{mpcc}}(y^{*})^{T}H_{\textup{mpcc}}(y^{*},\lambda^{*})U_{\textup{mpcc}}(y^{*})>0.$

Then, $y^{*}$ is a strict local minimizer of (I-MPCC).

######  Proof 5.17.

In the second part of [11, Theorem 7], our assertion is proved under the
weaker assumption that $y^{*}$ is strongly stationary and for every critical
direction $d\neq 0$ there exists a Lagrange multiplier vector
$(\lambda^{*},\mu^{*})$ such that
$d^{T}H_{\textup{mpcc}}(y^{*},\lambda^{*})d>0$. Under our additional
assumptions of MPCC-LICQ and MPCC-strict complementarity, the set of critical
directions is spanned by the matrix $U_{\textup{mpcc}}(y^{*})$, see proof of
the previous lemma. Thus, the claim follows directly from [11, Theorem 7].

We proceed by formulating second-order conditions for (I-NLP). To this end, we
denote by $(\alpha^{t})^{c}$ the complement of $\alpha^{t}$, and we need the
Lagrangian

$\displaystyle\mathcal{L}(t,\lvert
z^{t}\rvert,\lambda)=f(t)+\lambda_{\mathcal{E}}^{T}c_{\mathcal{E}}(t,\lvert
z^{t}\rvert)-\lambda_{\mathcal{I}}^{T}c_{\mathcal{I}}(t,\lvert
z^{t}\rvert)+\lambda_{\mathcal{Z}}^{T}\bigl{(}c_{\mathcal{Z}}(t,\lvert
z^{t}\rvert)-\mathcal{P}_{(\alpha^{t})^{c}}^{T}\mathcal{P}_{(\alpha^{t})^{c}}\Sigma^{t}\lvert
z^{t}\rvert\bigr{)}$

and the matrix

(9) $U_{\textup{abs}}(t)\mathrel{{\mathop{:}}{=}}\begin{bmatrix}U(t)\\\
[e_{i}^{T}\Sigma\partial_{t}z^{t}(t)U(t)]_{i\notin\alpha^{t}}\end{bmatrix},$

where $U(t)$ spans the nullspace of $J_{\textup{abs}}(t)$. We also use the
Lagrangian

$\displaystyle\leavevmode\bar{\mathcal{L}}(x,\lvert
z\rvert,\leavevmode\bar{\lambda})=\leavevmode\bar{f}(x)$
$\displaystyle+\leavevmode\bar{\lambda}_{\mathcal{E}}^{T}\leavevmode\bar{c}_{\mathcal{E}}(x,\lvert
z\rvert)+\leavevmode\bar{\lambda}_{\mathcal{Z}}^{T}\bigl{(}\leavevmode\bar{c}_{\mathcal{Z}}(x,\lvert
z\rvert)-\mathcal{P}_{\alpha^{c}}^{T}\mathcal{P}_{\alpha^{c}}\Sigma\lvert
z\rvert\bigr{)},$ $\displaystyle{}=f(t)$
$\displaystyle+\lambda_{\mathcal{E}}^{T}c_{\mathcal{E}}(t,\lvert
z^{t}\rvert)-\lambda_{\mathcal{I}}^{T}\bigl{(}c_{\mathcal{I}}(t,\lvert
z^{t}\rvert)-\lvert z^{w}\rvert\bigr{)}$
$\displaystyle+\lambda_{\mathcal{Z}}^{T}\bigl{(}c_{\mathcal{Z}}(t,\lvert
z^{t}\rvert)-\mathcal{P}_{(\alpha^{t})^{c}}^{T}\mathcal{P}_{(\alpha^{t})^{c}}\Sigma^{t}\lvert
z^{t}\rvert\bigr{)}$
$\displaystyle+(\lambda_{\mathcal{Z}}^{w})^{T}\bigl{(}w-\mathcal{P}_{(\alpha^{w})^{c}}^{T}\mathcal{P}_{(\alpha^{w})^{c}}\Sigma^{w}\lvert
z^{w}\rvert\bigr{)}.$

######  Theorem 5.18 (Second Order Necessary Conditions for (I-NLP)).

Assume that $y^{*}=(t^{*},(z^{t})^{*})$ is a local minimizer of (I-NLP) and
that LIKQ holds at $t^{*}$. Denote by $\lambda^{*}$ the unique Lagrange
multiplier and set $\alpha^{t}=\alpha^{t}(t^{*})$. Then,

$U_{\textup{abs}}(t^{*})^{T}H_{\textup{abs}}(y^{*},\lambda^{*})U_{\textup{abs}}(t^{*})\geq
0$

where $H_{\textup{abs}}(y^{*},\lambda^{*})=\begin{bmatrix}I&0\\\
0&P_{(\alpha^{t})^{c}}\end{bmatrix}\begin{bmatrix}\partial_{11}\mathcal{L}(y^{*},\lambda^{*})&\partial_{12}\mathcal{L}(y^{*},\lambda^{*})\\\
\partial_{21}\mathcal{L}(y^{*},\lambda^{*})&\partial_{22}\mathcal{L}(y^{*},\lambda^{*})\end{bmatrix}\begin{bmatrix}I&0\\\
0&P_{(\alpha^{t})^{c}}^{T}\end{bmatrix}$.

######  Proof 5.19.

As in Theorem 5.5, we can consider (E-NLP) instead of (I-NLP) by Theorem 2.12.
In [9, Theorem 5.15] the second order necessary conditions for
($\overline{\text{E-NLP}}$) have been derived using a variable splitting.
Without the splitting they read

$\displaystyle\leavevmode\bar{U}_{\textup{e-abs}}(x^{*})^{T}\leavevmode\bar{H}_{\textup{e-abs}}(\leavevmode\bar{y}^{*},\leavevmode\bar{\lambda}^{*})\leavevmode\bar{U}_{\textup{e-abs}}(x^{*})\geq
0$

with $\leavevmode\bar{y}^{*}=(x^{*},z^{*})$,
$\leavevmode\bar{\lambda}_{\mathcal{E}}=(\lambda_{\mathcal{E}},-\lambda_{\mathcal{I}})$,
$\leavevmode\bar{\lambda}_{\mathcal{Z}}=(\lambda_{\mathcal{Z}},\lambda_{\mathcal{Z}}^{w})$,
and the Hessian

$\displaystyle\leavevmode\bar{H}_{\textup{e-abs}}(\leavevmode\bar{y}^{*},\leavevmode\bar{\lambda}^{*})=\begin{bmatrix}I&0\\\
0&P_{\alpha^{c}}\end{bmatrix}\begin{bmatrix}\partial_{11}\leavevmode\bar{\mathcal{L}}(\leavevmode\bar{y}^{*},\leavevmode\bar{\lambda}^{*})&\partial_{12}\leavevmode\bar{\mathcal{L}}(\leavevmode\bar{y}^{*},\leavevmode\bar{\lambda}^{*})\\\
\partial_{21}\leavevmode\bar{\mathcal{L}}(\leavevmode\bar{y}^{*},\leavevmode\bar{\lambda}^{*})&\partial_{22}\leavevmode\bar{\mathcal{L}}(\leavevmode\bar{y}^{*},\leavevmode\bar{\lambda}^{*})\end{bmatrix}\begin{bmatrix}I&0\\\
0&P_{\alpha^{c}}^{T}\end{bmatrix},$

where $\alpha^{c}$ is the complement of $\alpha$ and the matrix
$\leavevmode\bar{U}_{\textup{e-abs}}$ is defined as

$\displaystyle\leavevmode\bar{U}_{\textup{e-abs}}(x^{*})=\begin{bmatrix}\leavevmode\bar{U}(x^{*})\\\
[e_{i}^{T}\Sigma^{*}\partial_{x}z(x^{*})\leavevmode\bar{U}(x^{*})]_{i\notin\alpha}\end{bmatrix}$

with $\leavevmode\bar{U}(x)$ spanning $\ker(J_{\textup{e-abs}}(x))$. Using the
special structure of ($\overline{\text{E-NLP}}$) and comparing the derivatives
of
$\leavevmode\bar{\mathcal{L}}(\leavevmode\bar{y}^{*},\leavevmode\bar{\lambda}^{*})$
and $\mathcal{L}(y^{*},\lambda^{*})$, the Hessian becomes:

$\displaystyle\leavevmode\bar{H}_{\textup{e-abs}}(\leavevmode\bar{y}^{*},\leavevmode\bar{\lambda}^{*})=\begin{bmatrix}I&0&0&0\\\
0&I&0&0\\\ 0&0&P_{(\alpha^{t})^{c}}&0\\\
0&0&0&P_{(\alpha^{w})^{c}}\end{bmatrix}\begin{bmatrix}\partial_{11}\mathcal{L}&0&\partial_{12}\mathcal{L}&0\\\
0&0&0&0\\\ \partial_{21}\mathcal{L}&0&\partial_{22}\mathcal{L}&0\\\ 0&0&0&0\\\
\end{bmatrix}\begin{bmatrix}I&0&0&0\\\ 0&I&0&0\\\
0&0&P_{(\alpha^{t})^{c}}^{T}&0\\\ 0&0&0&P_{(\alpha^{w})^{c}}^{T}\end{bmatrix}$

All partial derivatives of $\mathcal{L}$ are evaluated at
$(y^{*},\lambda^{*})$. Moreover,
$J_{\textup{e-abs}}(x)=J_{\textup{e-abs}}(t,w)$ has the form derived in Lemma
2.9, and thus its nullspace is spanned by

$\displaystyle\leavevmode\bar{U}(x)=\begin{bmatrix}U(t)\\\
\Sigma^{w}\partial_{t}c_{\mathcal{I}}\end{bmatrix},$

where $U(t)$ spans the nullspace of $J_{\textup{abs}}(t)$ from Definition 2.4.
Using this and $\partial_{t}z^{w}(w)=I$, the matrix
$\leavevmode\bar{U}_{\textup{e-abs}}$ reads

$\displaystyle\leavevmode\bar{U}_{\textup{e-abs}}(x)=\begin{bmatrix}U(t)\\\
\Sigma^{w}\partial_{t}c_{\mathcal{I}}\\\
[e_{i}^{T}\Sigma^{t}\partial_{t}z^{t}(t)U(t)]_{i\notin\alpha^{t}}\\\
[e_{i}^{T}\partial_{t}c_{\mathcal{I}}]_{i\notin\alpha^{w}}\end{bmatrix}.$

Finally, we have

$\displaystyle
0\leq\leavevmode\bar{U}_{\textup{e-abs}}(x^{*})^{T}\leavevmode\bar{H}_{\textup{e-abs}}(\leavevmode\bar{y}^{*},\leavevmode\bar{\lambda}^{*})\leavevmode\bar{U}_{\textup{e-abs}}(x^{*})=U_{\textup{abs}}(t^{*})^{T}H_{\textup{abs}}(y^{*},\lambda^{*})U_{\textup{abs}}(t^{*})$

with $U_{\textup{abs}}(t)$ from (9) and

$H_{\textup{abs}}(y,\lambda)=\begin{bmatrix}I&0\\\
0&P_{(\alpha^{t})^{c}}\end{bmatrix}\begin{bmatrix}\partial_{11}\mathcal{L}(y,\lambda)&\partial_{12}\mathcal{L}(y,\lambda)\\\
\partial_{21}\mathcal{L}(y,\lambda)&\partial_{22}\mathcal{L}(y,\lambda)\end{bmatrix}\begin{bmatrix}I&0\\\
0&P_{(\alpha^{t})^{c}}^{T}\end{bmatrix}.$

This proves the claim.

######  Theorem 5.20 (Second Order Sufficient Conditions for (I-NLP)).

Assume that $y^{*}=(t^{*},(z^{t})^{*})$ is kink stationary for (I-NLP) with a
Lagrange multiplier vector $\lambda^{*}$ that satisfies strict complementarity
for $\lambda_{\mathcal{I}}^{*}$ and strict normal growth,

$[\lambda_{\mathcal{E}}^{T}\partial_{2}c_{\mathcal{E}}-\lambda_{\mathcal{I}}^{T}\partial_{2}c_{\mathcal{I}}+\lambda_{\mathcal{Z}}^{T}\partial_{2}c_{\mathcal{Z}}]_{i}>\lvert(\lambda_{\mathcal{Z}})_{i}\rvert,\quad
i\in\alpha^{t}(t^{*}).$

Assume further that LIKQ holds at $t^{*}$, and that

$U_{\textup{abs}}(t^{*})^{T}H_{\textup{abs}}(y^{*},\lambda^{*})U_{\textup{abs}}(t^{*})>0.$

Then, $(t^{*},(z^{t})^{*})$ is a strict local minimizer of (I-NLP).

######  Proof 5.21.

As before we consider the slack reformulation (E-NLP) of (I-NLP). The
assumption of strict complementarity for $\lambda_{\mathcal{I}}^{*}$ and
strict normal growth for (I-NLP) implies strict normal growth for (E-NLP).
Moreover, the previous proof shows that the condition

$U_{\textup{abs}}(t^{*})^{T}H_{\textup{abs}}(y^{*},\lambda^{*})U_{\textup{abs}}(t^{*})>0$

is equivalent to

$\displaystyle\leavevmode\bar{U}_{\textup{e-abs}}(x^{*})^{T}\leavevmode\bar{H}_{\textup{e-abs}}(\leavevmode\bar{y}^{*},\leavevmode\bar{\lambda}^{*})\leavevmode\bar{U}_{\textup{e-abs}}(x^{*})>0,$

which can be reformulated using the variable splitting of [9]. Then, [9,
Theorem 5.19] can be applied, which gives the assertion.

######  Theorem 5.22.

Assume that $(t^{*},(z^{t})^{*})$ is kink stationary for (I-NLP) with Lagrange
multiplier vector $\lambda^{*}$ such that strict complementarity and strict
normal growth are satisfied. Assume further that LIKQ holds at $t^{*}$. Then,

$\displaystyle
U_{\textup{mpcc}}(y^{*})^{T}\\!H_{\textup{mpcc}}(y^{*},\lambda^{*})U_{\textup{mpcc}}(y^{*})\geq
0\iff
U_{\textup{abs}}(t^{*})^{T}\\!H_{\textup{abs}}(t^{*},(z^{t})^{*},\lambda^{*})U_{\textup{abs}}(x^{*})\geq
0,$

where
$y^{*}=(t^{*},(u^{t})^{*},(v^{t})^{*})=(t^{*},[(z^{t})^{*}]^{+},[(z^{t})^{*}]^{-})$.
The equivalence holds also with strict inequalities.

######  Proof 5.23.

Using that $u^{*}+v^{*}=\lvert(z^{t})^{*}\rvert$ and
$(z^{t})^{*}=z^{t}(t^{*})$ the matrix $U_{\textup{mpcc}}(y^{*})$ in (6) reads

$\displaystyle U_{\textup{mpcc}}(y^{*})=\begin{bmatrix}I\\\
+P_{\mathcal{U}^{t}_{+}}\partial_{t}z^{t}(t^{*})\\\ 0\\\
-P_{\mathcal{V}^{t}_{+}}\partial_{t}z^{t}(t^{*})\\\
0\end{bmatrix}\tilde{U}(y^{*})$

with $\tilde{U}(y^{*})$ defined in (7). The Lagrangians of (I-MPCC) and
(I-NLP), respectively, are

$\displaystyle\mathcal{L}_{\perp}(y,\lambda)$
$\displaystyle=f(t)+\lambda_{\mathcal{E}}^{T}c_{\mathcal{E}}(t,u^{t}+v^{t})-\lambda_{\mathcal{I}}^{T}c_{\mathcal{I}}(t,u^{t}+v^{t})+\lambda_{\mathcal{Z}}^{T}[c_{\mathcal{Z}}(t,u^{t}+v^{t})-(u^{t}-v^{t})],$
$\displaystyle\mathcal{L}(t,\lvert z^{t}\rvert,\lambda)$
$\displaystyle=f(t)+\lambda_{\mathcal{E}}^{T}c_{\mathcal{E}}(t,\lvert
z^{t}\rvert)-\lambda_{\mathcal{I}}^{T}c_{\mathcal{I}}(t,\lvert
z^{t}\rvert)+\lambda_{\mathcal{Z}}^{T}[c_{\mathcal{Z}}(t,\lvert
z^{t}\rvert)-\mathcal{P}_{\alpha^{c}}^{T}\mathcal{P}_{\alpha^{c}}\Sigma^{t}\lvert
z^{t}\rvert].$

Thus
$U_{\textup{mpcc}}(y^{*})^{T}H_{\textup{mpcc}}(y^{*},\lambda^{*})U_{\textup{mpcc}}(y^{*})=U_{\textup{mpcc}}(y^{*})^{T}\nabla_{yy}\mathcal{L}_{\perp}(y^{*},\lambda^{*})U_{\textup{mpcc}}(y^{*})$
can be written with $(z^{t})^{*}=(u^{t})^{*}-(v^{t})^{*}$ and using that
$\tilde{U}(y^{*})=U(t^{*})$, as

$\begin{bmatrix}U(y^{*})\\\
+P_{\mathcal{U}^{t}_{+}}\partial_{t}z^{t}(t^{*})U(y^{*})\\\
-P_{\mathcal{V}^{t}_{+}}\partial_{t}z^{t}(t^{*})U(y^{*})\end{bmatrix}^{T}\begin{bmatrix}\hfill
H_{11}&\hfill H_{21}P_{\mathcal{U}^{t}_{+}}^{T}&\hfill
H_{21}P_{\mathcal{V}^{t}_{+}}^{T}\\\
P_{\mathcal{U}^{t}_{+}}H_{12}&P_{\mathcal{U}^{t}_{+}}H_{22}P_{\mathcal{U}^{t}_{+}}^{T}&P_{\mathcal{U}^{t}_{+}}H_{22}P_{\mathcal{V}^{t}_{+}}^{T}\\\
P_{\mathcal{V}^{t}_{+}}H_{12}&P_{\mathcal{V}^{t}_{+}}H_{22}P_{\mathcal{U}^{t}_{+}}^{T}&P_{\mathcal{V}^{t}_{+}}H_{22}P_{\mathcal{V}^{t}_{+}}^{T}\end{bmatrix}\begin{bmatrix}U(y^{*})\\\
+P_{\mathcal{U}^{t}_{+}}\partial_{t}z^{t}(t^{*})U(y^{*})\\\
-P_{\mathcal{V}^{t}_{+}}\partial_{t}z^{t}(t^{*})U(y^{*})\end{bmatrix}$

where
$H_{ij}\mathrel{{\mathop{:}}{=}}\partial_{i}\partial_{j}\mathcal{L}(t^{*},(z^{t})^{*},\lambda^{*})$.
Now, since $\mathcal{U}^{t}_{+}\cup\mathcal{V}^{t}_{+}=(\alpha^{t})^{c}$, the
left-hand inequality of the claim reads

$\displaystyle\begin{bmatrix}U(y^{*})\\\
P_{(\alpha^{t})^{c}}\Sigma\partial_{t}z^{t}(t^{*})U(y^{*})\end{bmatrix}^{T}\begin{bmatrix}\hfill
H_{11}&\hfill H_{21}P_{(\alpha^{t})^{c}}^{T}\\\
P_{(\alpha^{t})^{c}}H_{12}&P_{(\alpha^{t})^{c}}H_{22}P_{(\alpha^{t})^{c}}^{T}\end{bmatrix}\begin{bmatrix}U(y^{*})\\\
P_{(\alpha^{t})^{c}}\Sigma\partial_{t}z^{t}(t^{*})U(y^{*})\end{bmatrix}\geq
0.$

This is
$U_{\textup{abs}}(t^{*})^{T}H_{\textup{abs}}(t^{*},(z^{t})^{*},\lambda^{*})U_{\textup{abs}}(t^{*})\geq
0$.

Note that the previous theorem can be used to transfer the second order
conditions for (I-NLP) and (I-MPCC) into each other. This follows from the
equivalence of LIKQ and MPCC-LICQ by Theorem 4.1 and from the equivalence of
stationarity concepts by Theorem 5.7.

##  6 Conclusions and Outlook

We have shown that general abs-normal NLPs are essentially the same problem
class as MPCCs. The two problem classes have corresponding constraint
qualifications, stationarity concepts, and optimality conditions of first and
second order. We have also shown that the slack reformulation from [9], which
is useful to simplify derivations under LIKQ, does not preserve IDKQ and has
other subtle drawbacks like non-uniqueness of slack variables. We have not
considered counterpart abs-normal NLPs of general MPCCs as in [8]. This would
provide a different perspective on the equivalence of the two problem classes
but no additional insight. It is hoped that the identities revealed may serve
to transfer algorithms for the solution of MPCCs to the young field of abs-
normal forms and abs-normal NLP. Vice versa, active signature algorithms for
abs-normal forms, such as SALMIN [5], may be applicable to MPCCs. Relations
between the two problem classes under weaker constraint qualifications of
Abadie type and Guignard type are the subject of part two of this research and
are put forward in a companion article.

## References

  * [1] M.Flegel, _Constraint Qualifications and Stationarity Concepts for Mathematical Programs with Equilibrium Constraints_ , Dissertation, Universität Würzburg, 2005, https://opus.bibliothek.uni-wuerzburg.de/frontdoor/index/index/year/2005/docId/1068.
  * [2] A.Griewank, On stable piecewise linearization and generalized algorithmic differentiation, _Optimization Methods and Software_ 28 (2013), 1139–1178, doi:10.1080/10556788.2013.796683.
  * [3] A.Griewank and A.Walther, First- and second-order optimality conditions for piecewise smooth objective functions, _Optimization Methods and Software_ 31 (2016), 904–930, doi:10.1080/10556788.2016.1189549.
  * [4] A.Griewank and A.Walther, Characterizing and testing subdifferential regularity for piecewise smooth objective functions, _SIAM Journal on Optimization_ 29 (2019), 1473–1501, doi:10.1137/17m115520x.
  * [5] A.Griewank and A.Walther, Finite convergence of an active signature method to local minima of piecewise linear functions, _Optimization Methods and Software_ 34 (2019), 1035–1055, doi:10.1080/10556788.2018.1546856.
  * [6] A.Griewank and A.Walther, Relaxing kink qualifications and proving convergence rates in piecewise smooth optimization, _SIAM Journal on Optimization_ 29 (2019), 262–289, doi:10.1137/17m1157623.
  * [7] L. C.Hegerhorst-Schultchen, _Optimality Conditions for Abs-Normal NLPs_ , Dissertation, Leibniz Universität Hannover, 2020, doi:10.15488/9867.
  * [8] L. C.Hegerhorst-Schultchen, C.Kirches, and M. C.Steinbach, On the relation between MPECs and optimization problems in abs-normal form, _Optimization Methods and Software_ 35 (2020), 565–575, doi:10.1080/10556788.2019.1588268.
  * [9] L. C.Hegerhorst-Schultchen and M. C.Steinbach, On first and second order optimality conditions for abs-normal NLP, _Optimization_ 69 (2020), 2629–2656, doi:10.1080/02331934.2019.1626386.
  * [10] Z.Luo, J.Pang, and D.Ralph, _Mathematical Programs with Equilibrium Constraints_ , Cambridge University Press, 1996.
  * [11] H.Scheel and S.Scholtes, Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity, _Mathematics of Operations Research_ 25 (2000), 1–22, doi:10.1287/moor.25.1.1.15213.
  * [12] J.Ye, Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints, _Journal of Mathematical Analysis and Applications_ 307 (2005), 350–369, doi:10.1016/j.jmaa.2004.10.032.