# Topological approach to mathematical programs with switching constraints

V. Shikhman  Department of Mathematics, Chemnitz University of Technology,
Reichenhainer Str. 41, 09126 Chemnitz, Germany; e-mail:
<EMAIL_ADDRESS>(corresponding author).

###### Abstract

We study mathematical programs with switching constraints (MPSC) from the
topological perspective. Two basic theorems from Morse theory are proved.
Outside the W-stationary point set, continuous deformation of lower level sets
can be performed. However, when passing a W-stationary level, the topology of
the lower level set changes via the attachment of a $w$-dimensional cell. The
dimension $w$ equals the W-index of the nondegenerate W-stationary point. The
W-index depends on both the number of negative eigenvalues of the restricted
Lagrangian’s Hessian and the number of bi-active switching constraints. As a
consequence, we show the mountain pass theorem for MPSC. Additionally, we
address the question if the assumption on the nondegeneracy of W-stationary
points is too restrictive in the context of MPSC. It turns out that all
W-stationary points are generically nondegenerate. Besides, we examine the gap
between nondegeneracy and strong stability of W-stationary points. A complete
characterization of strong stability for W-stationary points by means of first
and second order information of the MPSC defining functions under linear
independence constraint qualification is provided. In particular, all bi-
active Lagrange multipliers of a strongly stable W-stationary point cannot
vanish.

Keywords: switching constraints, W-stationarity, W-index, Morse theory, strong
stability, linear independence constraint qualification

##  1 Introduction

We consider the following mathematical program with switching constraints:

$\mbox{MPSC}[f,h,g,F_{1},F_{2}]:\quad\min\,\,f(x)\quad\mbox{ s.t.}\quad x\in
M[h,g,F_{1},F_{2}]$ (1)

with

$M[h,g,F_{1},F_{2}]=\left\\{x\in\mathbb{R}^{n}\left|\begin{array}[]{l}h_{i}(x)=0,i\in
I,g_{j}(x)\geq 0,j\in J,\\\ F_{1,m}(x)\cdot
F_{2,m}(x)=0,m=1,\ldots,k\end{array}\right.\right\\},$

where $f\in C^{2}(\mathbb{R}^{n},\mathbb{R})$, $h\in
C^{2}(\mathbb{R}^{n},\mathbb{R}^{|I|})$, $g\in
C^{2}(\mathbb{R}^{n},\mathbb{R}^{|J|})$, $F_{1},F_{2}\in
C^{2}(\mathbb{R}^{n},\mathbb{R}^{k})$. For simplicity, we write $M$ for
$M[h,g,F_{1},F_{2}]$ if no confusion is possible. MPSC has been introduced in
[14] by arguing that switching structures, which demand at most one control to
be active at any time instance, appear rather frequently in optimal control.
Discretization of such optimal control problems naturally leads to MPSC. In
[14], various stationarity concepts for MPSC were suggested, such as W-, M-,
and S-stationarity. Under suitable MPSC-tailored constraint qualifications,
necessary optimality conditions were derived. Numerical aspects of MPSC were
handled in [10], where different relaxation schemes for switching constraints
are discussed and compared.

The goal of this paper is the study of MPSC from the topological point of view
as it has been pioneered by H. Th. Jongen for nonlinear programming in [5] and
popularized in [6]. Subsequent studies in this direction are summarized in
[17], where, in particular, mathematical programs with complementarity
constraints (MPCC) and mathematical programs with vanishing constraints (MPVC)
are considered. The main question here is how the topological properties of
lower level sets

$M^{a}=\\{x\in M\,|\,f(x)\leq a\\}$

change as the level $a\in\mathbb{R}$ varies. For MPSC, it turns out that the
concept of W-stationarity is adequate in order to describe these changes. In
particular, within this context, we present two basic theorems from Morse
theory, cf. [6, 15]. First, we show that, for $a<b$, the set $M^{a}$ is a
strong deformation retract of $M^{b}$ if the set

$M^{b}_{a}=\\{x\in M\,|\,a\leq f(x)\leq b\\}$

does not contain W-stationary points, see Theorem 3.4(a). As a consequence,
the homotopy type of the lower level sets $M^{a}$ and $M^{b}$ are equal.
Second, if $M^{b}_{a}$ contains exactly one nondegenerate W-stationary point,
then $M^{b}$ is shown to be homotopy-equivalent to $M^{a}$ with a $w$-cell
attached, see Theorem 3.4(b). Here, the dimension $w$ is the so-called
W-index. It depends on both the number of negative eigenvalues of the
restricted Lagrangian’s Hessian and the number of bi-active switching
constraints. The latter fact constitutes the main difference to the cases
where feasible set is described by complementarity or vanishing constraints.
We remind that for MPCC the C-index of topologically relevant C-stationary
points depends on the number of negative pairs of bi-active Lagrange
multipliers, see [8], [16]. The same is true for MPVC, where just negative
pairs of bi-active Lagrange multipliers of T-stationary points matter, see
[1]. For switching constraints however all pairs of bi-active Lagrange
multipliers contribute to W-index. A global interpretation of the deformation
and cell-attachment theorems is as follows. Suppose that the feasible set is
compact and connected, that the linear independence constraint qualification
(LICQ) holds, and that all W-stationary points are nondegenerate with pairwise
different functional values. Then, passing a level corresponding to a local
minimizer, a connected component of the lower level set is created. Different
components can only be connected by attaching one-dimensional cells. This
shows the existence of at least $(r-1)$ W-stationary saddle points with
W-index equal to one, where $r$ is the number of local minimizers, see also
[2, 6]. This mountain pass result for MPSC is shown in Theorem 3.5.

We point out that the crucial assumption in Morse theory is the nondegeneracy
of W-stationary points. A W-stationary point is called nondegenerate, see
Definition 3.5, if (ND1) LICQ is satisfied, (ND2) the Lagrange multipliers
corresponding to active inequality constraints are positive, (ND3) the
Lagrange multipliers corresponding to bi-active switching constraints do not
vanish, and (ND4) the restricted Hessian of the Lagrangian is nonsingular. Are
the requirements ND1-ND4 too restrictive to be assumed for W-stationary points
of MPSC? First, we show that all W-stationary points of a generic MPSC are
nondegenerate, see Theorem 3.3. Genericity means that the set of MPSC defining
functions $(f,g,h,F_{1},F_{2})$, for which all W-stationary points are
nondegenerate, is open and -dense with respect to the so-called strong (or
Whitney) $C^{2}$-topology, see e. g. [4]. Second, we examine the gap between
nondegeneracy and strong stability of W-stationary points. Strongly stable
W-stationary points in the sense of M. Kojima [13] do not only remain locally
unique under sufficiently small $C^{2}$-perturbations of the MPSC defining
functions $(f,h,g,F_{1},F_{2})$, but can also be continuously tracked back.
All nondegenerate W-stationary points are strongly stable, but not vice versa.
In this paper, we present a full characterization of strong stability for
W-stationary points by means of first and second order information of the MPSC
defining functions under LICQ, see Theorem 4.6. In particular, ND3 is
necessary for strong stability of W-stationary points, i. e. all bi-active
Lagrange multipliers cannot vanish. This new issue is in strong contrast e. g.
with the characterization of strong stability for C-stationary points in MPCC,
see [9]. In MPCC, strong stability includes cases where one of the bi-active
Lagrange multipliers may vanish. We conclude that in absence of active
inequality constraints, nondegeneracy of W-stationary points is equivalent to
their strong stability.

The article is organized as follows. In Section 2 we provide notation and
auxiliary results which will be used later. Section 3 contains the exposition
of Morse theory for MPSC including the proofs of the deformation and cell-
attaching theorem. In Section 4 we fully characterize strongly stable
W-stationary points of MPSC and draw comparisons to their nondegeneracy.

Our notation is standard. The $n$-dimensional Euclidean space is denoted by
$\mathbb{R}^{n}$ with norm $\|\cdot\|$. We denote the set of nonnegative
numbers by $\mathbb{H}$. The solution set of the basic switching relation is
denoted by

$\mathbb{S}=\\{\left(a,b\right)\in\mathbb{R}^{2}\,|\,a\cdot b=0\\}.$

$B(\bar{x},r)$ stands for the ball
$\left\\{\left.x\in\mathbb{R}^{n}\,\right|\,\|x-\bar{x}\|\leq r\right\\}$ for
$\bar{x}\in\mathbb{R}^{n}$, $r>0$. Given a differentiable function
$F:\mathbb{R}^{n}\longrightarrow\mathbb{R}^{m}$, $DF$ denotes its Jacobian
matrix. Given a differentiable function
$f:\mathbb{R}^{n}\longrightarrow\mathbb{R}$, $Df$ denotes the row vector of
partial derivatives and $D^{T}f$ stands for the transposed vector.

##  2 Notations and auxiliary results

Given $\bar{x}\in M$, we define the following index sets:

$J_{0}(\bar{x})=\\{j\in J\,|\,g_{j}(\bar{x})=0\\},$
$\alpha(\bar{x})=\\{m\in\\{1,\ldots
k\\}\,|\,F_{1,m}(\bar{x})=0,F_{2,m}(\bar{x})\not=0\\},$
$\beta(\bar{x})=\\{m\in\\{1,\ldots
k\\}\,|\,F_{1,m}(\bar{x})=0,F_{2,m}(\bar{x})=0\\},$
$\gamma(\bar{x})=\\{m\in\\{1,\ldots
k\\}\,|\,F_{1,m}(\bar{x})\not=0,F_{2,m}(\bar{x})=0\\}.$

The index set $J_{0}(\bar{x})$ corresponds to the active inequality
constraints and $\beta({\bar{x}})$ to the bi-active switching constraints at
$\bar{x}$.

Without loss of generality, we assume throughout the whole article that at the
particular point of interest $\bar{x}\in M$ it holds:

$J_{0}(\bar{x})=\\{1,\ldots,|J_{0}(\bar{x})|\\},\alpha(\bar{x})=\\{1,\ldots,|\alpha(\bar{x})|\\},$
$\gamma(\bar{x})=\\{|\alpha(\bar{x})|+1,\ldots,|\alpha(\bar{x})|+|\gamma(\bar{x})|\\}.$

We put $s=|I|+|\alpha(\bar{x})|+|\gamma(\bar{x})|$, $q=s+|J_{0}(\bar{x})|$,
$p=n-q-2|\beta(\bar{x})|$.

Let us start by stating the MPSC-tailored linear independence constraint
qualification, which turns out to be the crucial assumption for all results to
follow.

######  Definition 2.1 (LICQ, cf. [14])

The linear independence constraint qualification (LICQ) for MPSC is said to
hold at $\bar{x}\in M$ if the vectors

$\begin{array}[]{l}Dh_{i}(\bar{x}),i\in
I,DF_{1,m_{\alpha}}(\bar{x}),m_{\alpha}\in\alpha(\bar{x}),DF_{2,m_{\gamma}}(\bar{x}),m_{\gamma}\in\gamma(\bar{x}),\\\
Dg_{j}(\bar{x}),j\in
J_{0}(\bar{x}),DF_{1,m_{\beta}}(\bar{x}),DF_{2,m_{\beta}}(\bar{x}),m_{\beta}\in\beta(\bar{x})\par\end{array}$

are linearly independent.

The assumption of LICQ is justified in the sense, that it generically holds on
the MPSC feasible set. In order to formulate this assertion in mathematically
precise terms, the space $C^{2}(\mathbb{R}^{n},\mathbb{R})$ will be
topologized by means of the strong (or Whitney-) $C^{2}$-topology, denoted by
$C^{2}_{s}$, cf. [4, 6]. The $C^{2}_{s}$-topology is generated by allowing
perturbations of the functions and their derivatives up to second order which
are controlled by means of continuous positive functions. The product space
$C^{2}(\mathbb{R}^{n},\mathbb{R}^{l})\cong
C^{2}(\mathbb{R}^{n},\mathbb{R})\times\cdots\times
C^{2}(\mathbb{R}^{n},\mathbb{R})$ will be topologized with the corresponding
product topology.

######  Theorem 2.1 (LICQ is generic)

Let $\mathcal{F}$ denote the subset of
$C^{2}(\mathbb{R}^{n},\mathbb{R}^{|I|})\times
C^{2}(\mathbb{R}^{n},\mathbb{R}^{|J|})\times
C^{2}(\mathbb{R}^{n},\mathbb{R}^{k})\times
C^{2}(\mathbb{R}^{n},\mathbb{R}^{k})$ consisting of those MPSC defining
functions for which LICQ holds at all feasible points. Then, $\mathcal{F}$ is
$C^{2}_{s}$-open and -dense.

Proof. Let us consider the following mathematical program with vanishing
constraints:

$\mbox{MPVC}[f,h,g,F_{1},F_{2}]\quad\min\,\,f(x)\quad\mbox{s.t.}\quad x\in
N[h,g,F_{1},F_{2}]$

with

$N[h,g,F_{1},F_{2}]=\left\\{x\in\mathbb{R}^{n}\left|\begin{array}[]{l}h_{i}(x)=0,i\in
I,g_{j}(x)\geq 0,j\in J,\\\ F_{1,m}(x)\geq 0,F_{1,m}(x)\cdot F_{2,m}(x)\leq
0,m=1,\ldots,k\end{array}\right.\right\\}.$

Obviously, it holds $M[h,g,F_{1},F_{2}]\subset N[h,g,F_{1},F_{2}]$. The MPVC-
tailored LICQ is shown to hold generically on the feasible set
$N[h,g,F_{1},F_{2}]$, see [1, Theorem 2.1(i)]. Moreover, the definitions of
MPVC- and MPCC-tailored LICQ coincide on $M[h,g,F_{1},F_{2}]$. The assertion
thus follows. $\square$

Among different stationarity concepts for MPSC discussed in [14] that of
W-stationarity appears to be relevant for our topologically motivated studies.

######  Definition 2.2 (W-stationary point, cf. [14])

A point $\bar{x}\in M$ is called W-stationary for MPSC if there exist real
numbers (Lagrange multipliers)

$\bar{\lambda}_{i},i\in I,\bar{\mu}_{j},j\in
J,\bar{\sigma}_{1,m},\bar{\sigma}_{2,m},m=1,\ldots,k,$

such that:

$\begin{array}[]{rcl}Df(\bar{x})&=&\displaystyle{\displaystyle\sum_{i\in
I}}\bar{\lambda}_{i}Dh_{i}(\bar{x})+{\displaystyle\sum_{j\in
J}}\bar{\mu}_{j}Dg_{j}(\bar{x})\\\
&&\displaystyle+{\displaystyle\sum_{m=1}^{k}}\left(\bar{\sigma}_{1,m}DF_{1,m}(\bar{x})+\bar{\sigma}_{2,m}DF_{2,m}(\bar{x})\right),\end{array}$
(2) $\bar{\mu}_{j}\cdot g_{j}(\bar{x})=0,j\in J,$ (3) $\bar{\mu}_{j}\geq
0,j\in J,$ (4) $\bar{\sigma}_{j,m}\cdot
F_{j,m}(\bar{x})=0,j=1,2,m=1,\ldots,k.$ (5)

A vector $(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})\in
M\times\mathbb{R}^{|I|}\times\mathbb{R}^{|J|}\times\mathbb{R}^{2k}$ satisfying
(2)-(5) is called a W-stationary pair for MPSC.

In the case where LICQ holds at a W-stationary point $\bar{x}\in M$, the
Lagrange multipliers in (2) are uniquely determined. It is well-known that
under LICQ a local minimum of MPSC is W-stationary [14].

Let us now locally describe the MPSC feasible set under LICQ. This is done by
an appropriate change of coordinates.

######  Definition 2.3 (Coordinate system)

The feasible set $M$ admits a local $C^{r}$-coordinate system of
$\mathbb{R}^{n}$ ($r\geq 1$) at $\bar{x}$ by means of a $C^{r}$-diffeomorphism
$\Phi:U\longrightarrow V$ with open $\mathbb{R}^{n}$-neighborhoods $U$ and $V$
of $\bar{x}$ and $0$, respectively, if it holds:

  * (i)

$\Phi(\bar{x})=0$,

  * (ii)

$\Phi(M\cap
U)=\left(\\{0_{s}\\}\times\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}\times\mathbb{R}^{p}\right)\cap
V$.

######  Lemma 2.1 (Local structure)

Suppose that LICQ holds at $\bar{x}\in M$. Then $M$ admits a local
$C^{2}$-coordinate system of $\mathbb{R}^{n}$ at $\bar{x}$.

Proof. Choose vectors $\xi_{l}\in\mathbb{R}^{n}$, $l=1,\ldots,p$, which form -
together with the vectors

$\begin{array}[]{l}D^{T}h_{i}(\bar{x}),i\in
I,D^{T}F_{1,m_{\alpha}}(\bar{x}),m_{\alpha}\in\alpha(\bar{x}),D^{T}F_{2,m_{\gamma}}(\bar{x}),m_{\gamma}\in\gamma(\bar{x}),\\\
D^{T}g_{j}(\bar{x}),j\in
J_{0}(\bar{x}),D^{T}F_{1,m_{\beta}}(\bar{x}),D^{T}F_{2,m_{\beta}}(\bar{x}),m_{\beta}\in\beta(\bar{x})\end{array}$

\- a basis for $\mathbb{R}^{n}$. Next we put

$\left.\begin{array}[]{lll}y_{i}&=&h_{i}(x),i\in I,\\\
y_{|I|+m_{\alpha}}&=&F_{1,m_{\alpha}}(x),m_{\alpha}\in\alpha(\bar{x}),\\\
y_{|I|+m_{\gamma}}&=&F_{2,m_{\gamma}}(x),m_{\gamma}\in\gamma(\bar{x}),\\\
y_{s+j}&=&g_{j}(x),j\in J_{0}(\bar{x}),\\\
y_{s+|J_{0}(\bar{x})|+2m_{\beta}-1}&=&F_{1,m_{\beta}}(x),\\\
y_{s+|J_{0}(\bar{x})|+2m_{\beta}}&=&F_{2,m_{\beta}}(x),m_{\beta}=1,\ldots,|\beta(\bar{x})|,\\\
y_{n-p+l}&=&\xi^{T}_{l}(x-\bar{x}),l=1,\ldots,p.\\\ \end{array}\right\\}$ (6)

or, shortly,

$y=\Phi(x).$ (7)

Note that $\Phi\in C^{2}(\mathbb{R}^{n},\mathbb{R}^{n})$, $\Phi(\bar{x})=0$
and the Jacobian matrix $D\Phi(\bar{x})$ is nonsingular in virtue of LICQ and
the choice of $\xi_{l}$, $l=1,\ldots,p$. By means of the implicit function
theorem there exist open neighborhoods $U$ of $\bar{x}$ and $V$ of $0$ such
that $\Phi:U\longrightarrow V$ is a $C^{2}$-diffeomorphism. By shrinking $U$,
if necessary, we can guarantee that $J_{0}(x)\subset J_{0}(\bar{x})$ and
$\beta(x)\subset\beta(\bar{x})$ for all $x\in M\cap U$. Thus, the property
(ii) in Definition 2.3 follows directly from the definition of $\Phi$.
$\square$

###### Definition 2.4

We will refer to the $C^{2}$-diffeomorphism $\Phi$ defined by (6), (7) as
standard diffeomorphism.

Let us interpret the first- and second-order derivatives of the objective
function $f\circ\Phi^{-1}$ in new coordinates given by the standard
diffeomorphism $\Phi$. For that, we define the Lagrange function

$\begin{array}[]{rcl}L(x,\lambda,\mu,\sigma)&=&\displaystyle
f(x)-{\displaystyle\sum_{i\in I}}\lambda_{i}h_{i}(x)-{\displaystyle\sum_{j\in
J}}\mu_{j}g_{j}(x)\\\
&&\displaystyle-{\displaystyle\sum_{m=1}^{k}}\left(\sigma_{1,m}F_{1,m}(x)+\sigma_{2,m}F_{2,m}(x)\right).\end{array}$

At $\bar{x}\in M$ we further consider the local part of the feasible set:

$\begin{array}[]{ll}M_{0}(\bar{x})=\\{x\in\mathbb{R}^{n}\,\,|&h_{i}(x)=0,i\in
I,g_{j}(x)=0,j\in J_{0}(\bar{x}),\\\
&F_{1,m_{\alpha}}(x)=0,m_{\alpha}\in\alpha(\bar{x}),F_{2,m_{\gamma}}(x)=0,m_{\gamma}\in\gamma(\bar{x}),\\\
&F_{1,m_{\beta}}(x)=0,F_{2,m_{\beta}}(x)=0,m_{\beta}\in\beta(\bar{x})\\}.\end{array}$

Obviously, $M_{0}(\bar{x})\subset M$ and, in the case where LICQ holds at
$\bar{x}$, $M_{0}(\bar{x})$ is locally a $p$-dimensional $C^{2}$-manifold. The
tangent space of $M_{0}(\bar{x})$ at $\bar{x}$ is

$\begin{array}[]{ll}T_{\bar{x}}M_{0}(\bar{x})=\\{\xi\in\mathbb{R}^{n}\,\,|&Dh_{i}(\bar{x})\,\xi=0,i\in
I,Dg_{j}(\bar{x})\,\xi=0,j\in J_{0}(\bar{x})\\\
&DF_{1,m_{\alpha}}(\bar{x})\,\xi=0,m_{\alpha}\in\alpha(\bar{x}),\\\
&DF_{2,m_{\gamma}}(\bar{x})\,\xi=0,m_{\gamma}\in\gamma(\bar{x}),\\\
&DF_{1,m_{\beta}}(\bar{x})\,\xi=0,DF_{2,m_{\beta}}(\bar{x})\,\xi=0,m_{\beta}\in\beta(\bar{x})\\}.\end{array}$

######  Remark 2.1 (New coordinates)

From the proof of Lemma 2.1 it follows that the Lagrange multipliers
$(\bar{\lambda},\bar{\mu},\bar{\sigma})$ of a W-stationary point $\bar{x}$ are
the corresponding partial derivatives of the objective function
$f\circ\Phi^{-1}$ in new coordinates given by the standard diffeomorphism
$\Phi$, cf. [7, Lemma 2.2.1]. Moreover, its Hessian with respect to the last
$p$ coordinates corresponds to the restriction of the Lagrange function’s
Hessian $D^{2}_{xx}L(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$ on the
respective tangent space $T_{\bar{x}}M_{0}(\bar{x})$, cf. [7, Lemma 2.2.10].

##  3 Morse theory

Our goal is to study topological changes of MPSC lower level sets as the level
of the objective function varies. For the topological concepts we refer to [6,
18]. In order to provide intuition on deformation and cell-attachment in
presence of switching constraints, we first consider the following simple
Example 3.1.

###### Example 3.1

Consider the MPSC:

$\min\,\,f\left(x_{1},x_{2}\right)=x_{1}+x_{2}\quad\mbox{s.t.}\quad x_{1}\cdot
x_{2}=0.$ (8)

We see that for all $a<b<0$ the lower level sets $M^{b}$ and $M^{a}$ are
homotopy-equivalent. More precisely, $M^{b}$ is a strong deformation retract
of $M^{a}$, see Figure 1. This is due to the fact that $M^{b}_{a}$ does not
contain any $W$-stationary points. The situation changes dramatically if we
pass the zero level corresponding to the W-stationary point $(0,0)$. For
$a<0<b$ the lower level sets $M^{b}$ and $M^{a}$ are not homotopy-equivalent
anymore. It is possible to describe the topological difference between $M^{b}$
and $M^{a}$ by means of the cell-attachment procedure. Namely, $M^{b}$ is
homotopy-equivalent to $M^{a}$ with a one-dimensional cell attached along its
boundary, see Figure 2. $\square$

In order to adequately describe the topological changes of MPSC lower level
sets, we introduce nondegenerate W-stationary points along with their
$W$-index. The latter will provide us with the dimension of the cell to be
attached while passing the corresponding W-stationary level.

######  Definition 3.5 (Nondegenerate W-stationarity)

A W-stationary point $\bar{x}\in M$ with Lagrange multipliers
$(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$ is called nondegenerate if
the following conditions are satisfied:

  * ND1: LICQ holds at $\bar{x}$,

  * ND2: $\bar{\mu}_{j}>0$ for all $j\in J_{0}(\bar{x})$,

  * ND3: $\bar{\sigma}_{1,m_{\beta}}\cdot\bar{\sigma}_{2,m_{\beta}}\neq 0$ for all $m_{\beta}\in\beta(\bar{x})$,

  * ND4: $D^{2}_{xx}L(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})\restriction_{T_{\bar{x}}M_{0}(\bar{x})}$ is nonsingular.

$x_{2}$$x_{1}$$M^{a}$$x_{2}$$x_{1}$$M^{b}$ Figure 1: Deformation in Example
3.1 for $a<b<0$ $x_{2}$$x_{1}$$M^{a}$$x_{2}$$x_{1}$$M^{b}$ Figure 2: Cell-
attachment in Example 3.1 for $a<0<b$

Condition ND4 means that the matrix $V^{T}D^{2}L(\bar{x})V$ is nonsingular,
where $V$ is some matrix whose columns form a basis for the tangent space
$T_{\bar{x}}M_{0}(\bar{x})$ and
$D^{2}_{xx}L(\bar{x},\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$ is the
Hessian of the Lagrange function with respect to $x$-variables.

######  Definition 3.6 (W-index)

Let $\bar{x}\in M$ be a nondegenerate W-stationary point with unique Lagrange
multipliers $(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$. The number of
negative eigenvalues of
$D^{2}_{xx}L(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})\restriction_{T_{\bar{x}}M_{0}(\bar{x})}$
is called the quadratic index ($QI$) of $\bar{x}$. The number
$\left|\beta(\bar{x})\right|$ of non-zero bi-active pairs
$(\bar{\sigma}_{1,m_{\beta}},\bar{\sigma}_{2,m_{\beta}})$,
$m_{\beta}\in\beta(\bar{x})$ is called the bi-active index ($BI$) of
$\bar{x}$. The number $QI+BI$ is called the W-index of $\bar{x}$.

Note that in absence of switching constraints, the W-index has only the
$QI$-part and coincides with the well-known quadratic index of a nondegenerate
Karush-Kuhn-Tucker-point in nonlinear programming or, equivalently, with the
Morse index, cf. [6, 13, 15]. Confer that for MPCC and MPVC the $BI$-part of
the topologically relevant C-stationary and T-stationary points, respectively,
counts the pairs of negative bi-active Lagrange multipliers, see [8] and [1].
In MPSC, all pairs of bi-active Lagrange multipliers – independently of their
sign – contribute to $BI$, which is an essentially new phenomenon here.

The following Theorem 3.2 describes the local structure of MPSC around a
nondegenerate W-stationary point.

######  Theorem 3.2 (Morse Lemma for MPSC)

Suppose that $\bar{x}$ is a nondegenerate W-stationary point for MPSC with
quadratic index $QI$, bi-active index $BI$ and W-index = $QI+BI$. Then, there
exists a local $C^{1}$-coordinate system $\Psi:U\longrightarrow V$ of
$\mathbb{R}^{n}$ around $\bar{x}$ such that:

$\begin{array}[]{rcl}f\circ\Psi^{-1}\left(0_{s},y_{s+1},\ldots,y_{n}\right)&=&\displaystyle
f(\bar{x})+{\displaystyle\sum_{j=1}^{|J_{0}(\bar{x})|}}y_{j+s}\\\
&&\displaystyle+{\displaystyle\sum_{m=1}^{|\beta(\bar{x})|}}\left(y_{2m+q-1}+y_{2m+q}\right)+{\displaystyle\sum_{k=1}^{p}}\pm
y^{2}_{k+n-p},\end{array}$ (9)

where
$y\in\\{0_{s}\\}\times\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}\times\mathbb{R}^{p}$.
Moreover, in (9) there are exactly $QI$ negative squares.

Proof. Without loss of generality, we may assume $f(\bar{x})=0$. Let
$\Phi:U\longrightarrow V$ be a standard diffeomorphism according to Definition
(2.4). We put $\bar{f}=f\circ\Phi^{-1}$ on the set
$\left(\\{0_{s}\\}\times\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}\times\mathbb{R}^{p}\right)\cap
V$. From now on we may assume $s=0$. In view of Remark 2.1 we have at the
origin:

  * (i)

$\displaystyle\frac{\partial\bar{f}}{\partial y_{j}}>0$, $j\in
J_{0}(\bar{x})$,

  * (ii)

$\displaystyle\frac{\partial\bar{f}}{\partial
y_{2m+q-1}}\cdot\frac{\partial\bar{f}}{\partial y_{2m+q}}\neq 0$,
$m=1,\ldots|\beta(\bar{x})|$,

  * (iii)

$\displaystyle\frac{\partial\bar{f}}{\partial y_{k+n-p}}=0$, $k=1,\ldots,p$
and $\left(\displaystyle\frac{\partial^{2}\bar{f}}{\partial
y_{k_{1}+n-p}\partial y_{k_{2}+n-p}}\right)_{1\leq k_{1},k_{2}\leq p}$ is a
nonsingular matrix with $QI$ negative eigenvalues.

From now on we denote $\bar{f}$ by $f$. Under the following coordinate
transformations the set
$\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}\times\mathbb{R}^{p}$
will be transformed in itself (equivariance). As an abbreviation we put
$y=\left(Y_{n-p},Y^{p}\right)$, where $Y_{n-p}=(y_{1},\ldots,y_{n-p})$ and
$Y^{p}=(y_{n-p+1},\ldots,y_{n})$. We write

$f(Y_{n-p},Y^{p})=f(0,Y^{p})+\int^{1}_{0}\frac{d}{dt}f(tY_{n-p},Y^{p})dt=f(0,Y^{p})+{\displaystyle\sum_{\ell=1}^{n-p}}y_{\ell}d_{\ell}(y),$

where $d_{\ell}\in C^{1}$, $\ell=1,\ldots,n-p$.

In view of (iii) we may apply the Morse Lemma on the $C^{2}$-function
$f(0,Y^{p})$, cf. [6, Theorem 2.8.2], without affecting the coordinates
$Y_{n-p}$. The corresponding coordinate transformation is of class $C^{1}$.
Denoting the transformed functions again by $f$ and $d_{\ell}$, we obtain:

$f(y)={\displaystyle\sum_{\ell=1}^{n-p}}y_{\ell}d_{\ell}(y)+{\displaystyle\sum_{k=1}^{p}}\pm
y^{2}_{k+n-p}.$

Note that $d_{\ell}(0)=\displaystyle\frac{\partial f}{\partial y_{\ell}}(0)$,
$\ell=1,\ldots,n-p$. Recalling (i)-(ii), we put

$\begin{array}[]{l}y_{j}|d_{i}(y)|,j=1,\ldots,|J_{0}(\bar{x})|,\\\
y_{m}d_{m}(y),m=|J_{0}(\bar{x})|+1,\ldots,n-p,\\\
y_{k},k=n-p+1,\ldots,n\end{array}$ (10)

as new local $C^{1}$-coordinates. Denoting the transformed function $f$ again
by $f$ and, recalling the signs in (i)-(ii), we obtain (9) by a
straightforward application of the inverse function theorem. Here, the
coordinate transformation $\Psi$ is understood as the composition of all
previous ones. $\square$

As a by-product we elaborate on how the W-index can be used to characterize
nondegenerate local minimizer of MPSC.

######  Corollary 3.1 (Minimizers and W-index)

Let $\bar{x}\in M$ be a nondegenerate W-stationary point. Then, $\bar{x}$ is a
local minimizer of MPSC if and only if its W-index vanishes.

Proof. Let $\bar{x}$ be a nondegenerate W-stationary point for MPSC. The
application of Morse Lemma from Theorem 3.2 says that there exist
neighborhoods $U$ and $V$ of $\bar{x}$ and $0$, respectively, and a local
$C^{1}$-coordinate system $\Psi:U\rightarrow V$ of $\mathbb{R}^{n}$ around
$\bar{x}$ such that (9) holds. Therefore, $\bar{x}$ is a local minimizer for
MPSC if and only if $0$ is a local minimizer of $f\circ\Psi^{-1}$ on the set
$\\{0_{s}\\}\times\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}\times\mathbb{R}^{p}$.
If the W-index vanishes, we have $\beta(\bar{x})=\emptyset$ and $QI=0$, and
(9) reads as

$f\circ\Psi^{-1}\left(0_{s},y_{s+1},\ldots,y_{n}\right)=f(\bar{x})+{\displaystyle\sum_{j=1}^{|J_{0}(\bar{x})|}}y_{j+s}+{\displaystyle\sum_{k=1}^{p}}y^{2}_{k+n-p},$
(11)

where
$y\in\\{0_{s}\\}\times\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{R}^{p}$.
Thus, $0$ is a local minimizer for (11). Vice versa, if $0$ is a local
minimizer for (9), then obviously $\beta(\bar{x})=\emptyset$ and $QI=0$,
hence, the W-index of $\bar{x}$ vanishes. $\square$

######  Remark 3.2 (Nondegenerate minimizers)

Corollary 3.1 says that at a nondegenerate minimizer $\bar{x}\in M$ of MPSC
with Lagrange multipliers $(\bar{\lambda},\bar{\mu},\bar{\sigma})$ we have:

  * 1:

LICQ holds at $\bar{x}$,

  * 2:

the Lagrange multipliers corresponding to active inequality constraints are
positive, i. e. $\bar{\mu}_{j}>$ for all $j\in J_{0}(\bar{x})$,

  * 3:

the bi-active switching constraints are absent, i. e.
$\beta(\bar{x})=\emptyset$,

  * 4:

the second-order sufficient condition (SOSC) is fulfilled, i. e. the matrix
$D^{2}_{xx}L(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})\restriction_{T_{\bar{x}}M_{0}(\bar{x})}$
is positive definite.

Whereas conditions 1, 2, and 4 are standard as compared e.g. to nondegenerate
minimizers of MPCC or MPVC, condition 3 is new and specific for MPSC.
$\square$

The assumption of nondegeneracy is justified in the sense, that it generically
holds at all W-stationary points of MPSC.

######  Theorem 3.3 (Nondegeneracy is generic)

Let $\mathcal{F}$ denote the subset of
$C^{2}(\mathbb{R}^{n},\mathbb{R}^{|I|})\times
C^{2}(\mathbb{R}^{n},\mathbb{R}^{|J|})\times
C^{2}(\mathbb{R}^{n},\mathbb{R}^{k})\times
C^{2}(\mathbb{R}^{n},\mathbb{R}^{k})$ consisting of those MPSC defining
functions for which each W-stationary point is nondegenerate. Then,
$\mathcal{F}$ is $C^{2}_{s}$-open and -dense.

Proof.

Let us fix an index set $J_{0}\subset\left\\{1,\ldots,|J|\right\\}$ of active
inequality constraints, an index subset $K_{0}\subset J_{0}$ of these active
inequality constraints, pairwise disjoint index sets
$\alpha,\gamma,\beta\subset\\{1,\ldots,k\\}$ of switching constraints
satisfying $\alpha\cup\gamma\cup\beta=\\{1,\ldots,k\\}$, an index subset
$\delta\subset\beta$ of be-active switching constraints, and a number
$r\in\mathbb{N}$ standing for the rank. For this choice we consider the set
$M_{J_{0},K_{0},\alpha,\gamma,\beta,\delta,r}$ of $x\in\mathbb{R}^{n}$ such
that the following conditions are satisfied:

  * (m1) $h_{i}(x)=0$ for all $i\in I$ and $g_{j}(x)=0$ for all $j\in J$,

  * (m2) $F_{1,m_{\alpha}}(x)=0$ for all $m_{\alpha}\in\alpha$, $F_{2,m_{\gamma}}(x)=0$ for all $m_{\gamma}\in\gamma$, $F_{1,m_{\beta}}(x)=F_{2,m_{\beta}}(x)=0$ for all $m_{\beta}\in\beta$,

  * (m3)

$\begin{array}[]{rcl}Df(x)&=&\displaystyle{\displaystyle\sum_{i\in
I}}\lambda_{i}Dh_{i}(x)+{\displaystyle\sum_{j\in J_{0}\backslash
K_{0}}}\mu_{j}Dg_{j}(x)\\\
&&\displaystyle+{\displaystyle\sum_{m_{\alpha}\in\alpha}}\sigma_{1,m_{\alpha}}DF_{1,m_{\alpha}}(x)+{\displaystyle\sum_{m_{\gamma}\in\gamma}}\sigma_{2,m_{\gamma}}DF_{2,m_{\gamma}}(x)\\\
&&\displaystyle+{\displaystyle\sum_{m_{\beta}\in\beta\backslash\delta}}\left(\sigma_{1,m_{\beta}}DF_{1,m_{\beta}}(x)+\sigma_{2,m_{\beta}}DF_{2,m_{\beta}}(x)\right),\end{array}$

  * (m4) the matrix $D^{2}_{xx}L(x,\lambda,\mu,\sigma)\restriction_{\mathcal{T}_{x}M(x)}$ has rank $r$.

Note that (m1) refers to equality and active inequality constraints, (m2) to
switching constraints, while (m3) describes violation of ND2 and ND3.
Furthermore, (m4) describes violation of ND4. Now, it suffices to show that
$M_{J_{0},K_{0},\alpha,\gamma,\beta,\delta,r}$ is generically empty whenever
one of the sets $K_{0}$ or $\delta$ is nonempty or the rank $r$ in (m4) is not
full, i. e. $r<\mbox{dim}\left(\mathcal{T}_{x}M(x)\right)$. In fact, the
available degrees of freedom of the variables involved in each
$M_{J_{0},K_{0},\alpha,\gamma,\beta,\delta,r}$ are equal to $n$. The loss of
freedom caused by (m1) is $\left|I\right|+\left|J_{0}\right|$, and the loss of
freedom caused by (m2) is
$\left|m_{\alpha}\right|+\left|m_{\gamma}\right|+2\left|m_{\beta}\right|$. Due
to Theorem 2.1, LICQ holds generically at any feasible $x$, i. e. (ND1) is
fulfilled. Suppose that the sets $K_{0}$ and $\delta$ are empty, then (m3)
causes a loss of freedom of
$n-\left|P\right|-\left|Q_{0}\right|-\left|m_{\alpha}\right|-\left|m_{\gamma}\right|-2\left|m_{\beta}\right|$.
Hence, the total loss of freedom is $n$. We conclude that a further
degeneracy, i. e. $K_{0}\not=\emptyset$, $\delta\not=\emptyset$ or
$r<\mbox{dim}\left(\mathcal{T}_{x}M(x)\right)$, would imply that the total
available degrees of freedom $n$ are exceeded. By virtue of the jet
transversality theorem from [6], generically the sets
$M_{J_{0},K_{0},\alpha,\gamma,\beta,\delta,r}$ must be empty. For the openness
result, we argue in a standard way. Locally, W-stationarity can be written via
stable equations. Then, the implicit function theorem for Banach spaces can be
applied to follow W-stationary points with respect to (local)
$C^{2}$-perturbations of defining functions. Finally, a standard globalization
procedure exploiting the specific properties of the strong
$C^{2}_{s}$-topology can be used to construct a (global)
$C^{2}_{s}$-neighborhood of problem data for which the nondegeneracy property
is stable, cf. [6]. $\square$

Now, we are ready to state and prove deformation and cell-attachment theorems
for MPSC, which constitute the core results of the paper.

###### Theorem 3.4

Let $M^{b}_{a}$ be compact and suppose that LICQ is satisfied at all points
$x\in M^{b}_{a}$.

  * (a)

(Deformation) If $M^{b}_{a}$ does not contain any W-stationary point for MPSC,
then $M^{a}$ is a strong deformation retract of $M^{b}$.

  * (b)

(Cell-attachment) If $M^{b}_{a}$ contains exactly one W-stationary point for
MPSC, say $\bar{x}$, and if $a<f(\bar{x})<b$ and the W-index of $\bar{x}$ is
equal to $w$, then $M^{b}$ is homotopy-equivalent to $M^{a}$ with a $w$-cell
attached.

Proof. (a) Due to LICQ at all $x\in M^{b}_{a}$ there exist real numbers
$\lambda_{i}(x)$, $i\in I$, $\sigma_{1,m_{\alpha}}(x)$,
$m_{\alpha}\in\alpha(x)$, $\sigma_{2,m_{\gamma}}(x)$,
$m_{\gamma}\in\gamma(x)$, $\mu_{j}(x)$, $j\in J_{0}(x)$,
$\sigma_{1,m_{\beta}}(x)$, $\sigma_{2,m_{\beta}}(x)$, $m_{\beta}\in\beta(x)$,
$\nu_{l}(x)$, $l=1,\ldots,p$ such that:

$\begin{array}[]{rcl}Df(x)&=&\displaystyle{\displaystyle\sum_{i\in
I}}\lambda_{i}(x)Dh_{i}(x)+{\displaystyle\sum_{j\in
J_{0}(x)}}\mu_{j}(x)Dg_{j}(x)\\\
&&\displaystyle+{\displaystyle\sum_{m_{\alpha}\in\alpha(x)}}\sigma_{1,m_{\alpha}}(x)DF_{1,m_{\alpha}}(x)+{\displaystyle\sum_{m_{\gamma}\in\gamma(x)}}\sigma_{2,m_{\gamma}}(x)DF_{2,m_{\gamma}}(x)\\\
&&\displaystyle+{\displaystyle\sum_{m_{\beta}\in\beta(x)}}\left(\sigma_{1,m_{\beta}}(x)DF_{1,m_{\beta}}(x)+\sigma_{2,m_{\beta}}(x)DF_{2,m_{\beta}}(x)\right)+{\displaystyle\sum_{l=1}^{p}}\nu_{l}(x)\,\xi_{l},\end{array}$

where vectors $\xi_{l}$, $l=1,\ldots,p$ are chosen as in Lemma 2.1. We set:

$\begin{array}[]{rcl}A&=&\displaystyle\left\\{\left.x\in
M^{b}_{a}\,\right|\,\mbox{there exists }l\in\\{1,\ldots,p\\}\mbox{ with
}\nu_{l}(x)\not=0\right\\},\\\ \\\ B&=&\displaystyle\left\\{\left.x\in
M^{b}_{a}\,\right|\,\mbox{there exists }j\in J_{0}(x)\mbox{ with
}\mu_{j}(x)<0\right\\},\end{array}$

Since each $\bar{x}\in M^{b}_{a}$ is not W-stationary for MPSC, we get
$\bar{x}\in A\cup B$.

The proof consists of a local argument and its globalization which are more or
less standard here, cf. [8, Theorem 3.2]. Let us briefly recall the details
for the sake of completeness.

First, we show the local argument: for each $\bar{x}\in M^{b}_{a}$ there exist
an $(\mathbb{R}^{n})$-neighborhood $U_{\bar{x}}$ of $\bar{x}$,
${t_{\bar{x}}}>0$ and a mapping

$\Psi^{\bar{x}}:\left\\{\begin{array}[]{ccc}[0,t_{\bar{x}})\times\left(M^{b}\cap
U_{\bar{x}}\right)&\longrightarrow&M\\\
(t,x)&\mapsto&\Psi^{\bar{x}}(t,x)\end{array}\right.$

such that

  * (i)

$\Psi^{\bar{x}}(t,M^{b}\cap U_{\bar{x}})\subset M^{b-t}$ for all
$t\in[0,t_{\bar{x}})$,

  * (ii)

$\Psi^{\bar{x}}(t_{1}+t_{2},\cdot)=\Psi^{\bar{x}}(t_{1},\Psi^{\bar{x}}(t_{2},\cdot))$
for all $t_{1},t_{2}\in[0,t_{\bar{x}})$ with $t_{1}+t_{2}\in[0,t_{\bar{x}})$,

  * (iii)

$\Psi^{\bar{x}}(\cdot,\cdot)$ is a $C^{1}$-flow corresponding to a
$C^{1}$-vector field $F^{\bar{x}}$.

Obviously, the level sets of $f$ are locally mapped onto the level sets of
$f\circ\Phi^{-1}$, where $\Phi$ is a $C^{1}$-diffeomorphism according to
Definition 2.3. Applying the standard diffeomorphism $\Phi$ from Definition
2.4, we consider $f\circ\Phi^{-1}$ (denoted by $f$ again). Thus, we have
$\bar{x}=0$ and $f$ is given on the feasible set
$\\{0_{s}\\}\times\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}\times\mathbb{R}^{p}$.

Case a) $\bar{x}\in A$

Then, due to Remark 2.1 there exists $l\in\\{1,\ldots,p\\}$ with
$\displaystyle\frac{\partial f}{\partial x_{l}}(\bar{x})\not=0$. Define a
local $C^{1}$-vector field $F^{\bar{x}}$ as follows:

$F^{\bar{x}}(x_{1},\ldots,x_{l},\ldots,x_{n})=\left(0,\ldots,-\frac{\partial
f}{\partial x_{l}}(x)\cdot\left(\frac{\partial f}{\partial
x_{l}}(x)\right)^{-2},\ldots,0\right)^{T}.$

After respective inverse changes of local coordinates $F^{\bar{x}}$ induces
the flow $\Psi^{\bar{x}}$, which fits the local argument, see [6, Theorem
2.7.6] for details.

Case b) $\bar{x}\in B$

Then, due to Remark 2.1 there exists $j\in J_{0}(x)$ with
$\displaystyle\frac{\partial f}{\partial x_{j}}(\bar{x})<0$. By means of a
$C^{1}$-coordinate transformation in the $j$-th coordinate on $\mathbb{H}$,
leaving the other coordinates unchanged, we obtain locally for $f$, see [6,
Theorem 3.2.26]:

$f(x_{1},\ldots,x_{j},\ldots,x_{n})=-x_{j}+f(x_{1},\ldots,\bar{x}_{j},\ldots,x_{n}).$

Define a local $C^{1}$-vector field $F^{\bar{x}}$ as follows:

$F^{\bar{x}}(x_{1},\ldots,x_{j},\ldots,x_{n})=\left(0,\ldots,1,\ldots,0\right)^{T}.$

After respective inverse changes of local coordinates $F^{\bar{x}}$ induces
the flow $\Psi^{\bar{x}}$, which fits the local argument, see [6, Theorem
3.3.25] for details.

Second, the globalization of the local argument will be performed. For that,
consider the open covering $\\{U_{\bar{x}}\,|\,\bar{x}\in M^{b}_{a}\\}$ of
$M^{b}_{a}$. Since $M^{b}_{a}$ is compact, we get a finite open subcovering
$\\{U_{\bar{x}_{j}}\,|\,\bar{x}_{j}\in M^{b}_{a}\\}$ of $M^{b}_{a}$. Using a
$C^{\infty}$-partition of unity $\\{\phi_{j}\\}$ subordinate to
$\\{U_{\bar{x}_{j}}\,|\,\bar{x}_{j}\in M^{b}_{a}\\}$ we define with
$F^{\bar{x}_{j}}$, cf. Cases a),b), a $C^{1}$-vector field
$F={\displaystyle\sum_{j}}\phi_{j}F^{\bar{x}_{j}}$. The last induces a flow
$\Psi$ on $\\{U_{\bar{x}_{j}}\,|\,\bar{x}_{j}\in M^{b}_{a}\\}$, see [6,
Theorem 3.3.14] for details. Moving along the local pieces of the trajectories
$\Psi(\cdot,x)$, $x\in M^{b}_{a}$ reduces the level of $f$ at least by a
positive real number

$\frac{\min\\{t_{x_{j}}\,|\,x_{j}\in M^{b}_{a}\\}}{2}.$

Thus, we obtain for $x\in M^{b}_{a}$ a unique $t_{a}(x)>0$ with
$\Psi(t_{a}(x),x)\in M^{a}$. It is not hard (but technical) to realize that
$t_{a}:x\longrightarrow t_{a}(x)$ is Lipschitz continuous. Finally, we define
$r:[0,1]\times M^{b}\longrightarrow M^{b}$ as follows:

$r(\tau,x)=\left\\{\begin{array}[]{lll}x&\mbox{for }x\in
M^{a},&\tau\in[0,1]\\\ \Psi(\tau t_{a}(x),x)&\mbox{for }x\in
M^{b}_{a},&\tau\in[0,1].\end{array}\right.$

The mapping $r$ provides that $M^{a}$ is a strong deformation retract of
$M^{b}$.

(b) Part (a) allows deformations up to an arbitrarily small neighborhood of
the W-stationary point $\bar{x}$. In such a neighborhood, we may assume
without loss of generality that $\bar{x}=0$ and $f$ has the following form as
from Theorem 3.2 (for simplicity we omit the trivial part by assuming $s=0$):

$f(x)=f(\bar{x})+{\displaystyle\sum_{j=1}^{|J_{0}(\bar{x})|}}x_{j}+{\displaystyle\sum_{m=1}^{|\beta(\bar{x})|}}\left(x_{2m+q-1}+x_{2m+q}\right)+{\displaystyle\sum_{k=1}^{p}}\pm
x^{2}_{k+n-p},$ (12)

where
$x\in\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}\times\mathbb{R}^{p}$,
and the number of negative squares in (12) equals $QI$. In terms of [3] the
set
$\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}\times\mathbb{R}^{p}$
can be interpreted as the product of the tangential part $\mathbb{R}^{p}$ and
the normal part
$\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}$. The cell-
attachment along the tangential part is standard. Analogously to the
unconstrained case, a $QI$-dimensional cell has to be attached on
$\mathbb{R}^{p}$. The cell-attachment along the normal part is more involved.
First, we emphasize that the linear terms $x_{j}$, $j\in J_{0}(\bar{x})$, in
(12) do not contribute to the dimension of the cell to be attached. In fact,
with respect to lower level sets, the $1$-dimensional constrained singularity
$x$ on $\mathbb{H}$ plays the same role as the unconstrained singularity
$x^{2}$. In this sense the linear terms on $\mathbb{H}^{|J_{0}(\bar{x})|}$ can
be neglected for cell-attachment. Second, the linear terms
$x_{2m+q-1}+x_{2m+q}$, $m\in\beta(\bar{x})$, in (12) contribute each with the
one-dimensional cell due to Example 3.1. Hence, the linear terms on
$\mathbb{S}^{|\beta(\bar{x})|}$ are responsible for the attachment of a
$BI$-dimensional cell – recall that $BI=|\beta(\bar{x})|$. Finally, we apply
Theorem 3.7 from Part I in [3], which says that the local Morse data is the
product of tangential and normal Morse data. Hence, the dimensions of the
attached cells add together. Here, a $(QI+BI)$-dimensional cell has to be
attached. The latter corresponds to the W-index of the W-stationary point
$\bar{x}$. $\square$

Let us present a global interpretation of Theorem 3.4 by showing a mountain
pass theorem for MPSC.

######  Theorem 3.5 (Mountain pass)

Let the MPSC feasible set $M$ be compact and connected, and all W-stationary
points of MPSC be nondegenerate. Then, it holds:

$r_{s}\geq r-1,$ (13)

where $r$ is the number of local minimizers of MPSC and $r_{s}$ is the number
of W-stationary saddle points with W-index equal to one.

Proof. We assume without loss of generality that the objective function $f$
has pairwise different values at all W-stationarity points of MPSC. If it is
not the case, we may enforce this property by sufficiently small perturbations
of the objective function. Due to the openness part in Theorem 3.3, all
W-stationarity points of such a perturbed MPSC remain nondegenerate. Moreover,
the formula (13) is still valid since it does not depend on the functional
values of $f$.

Further, let $q_{a}$ denote the number of connected components of the lower
level set $M^{a}$. We focus on how $q_{a}$ changes as $a\in\mathbb{R}$
increases. Due to Theorem 3.4(a), $q_{a}$ can change only if passing through a
value corresponding to a W-stationary point $\bar{x}$, i. e.
$a=f\left(\bar{x}\right)$. In fact, Theorem 3.4(a) allows homotopic
deformations of lower level sets up to an arbitrarily small neighborhood of
the W-stationary point $\bar{x}$. Then, we have to estimate the difference
between $q_{a}$ and $q_{a-\varepsilon}$, where $\varepsilon>0$ is arbitrarily,
but sufficiently small, and $a=f\left(\bar{x}\right)$. This is done by a local
argument. For that, let the W-index of $\bar{x}$ be $QI+BI$. We use Theorem
3.4(b) which says that $M^{a}$ is homotopy-equivalent to $M^{a-\varepsilon}$
with a $(QI+BI)$-dimensional cell attached. Let us distinguish the following
cases:

  * 1)

$\bar{x}$ is a local minimizer with vanishing W-index, cf. Corollary 3.1, i.
e. $QI=BI=0$. Then, we attach to $M^{a-\varepsilon}$ the cell of dimension
zero. Consequently, a new connected component is created, and it holds:

$q_{a}=q_{a-\varepsilon}+1.$

  * 2)

$\bar{x}$ is a saddle point with W-index equal to one, i. e. either $QI=1$,
$BI=0$ or $QI=0$, $BI=1$ holds. Then, we attach to $M^{a-\varepsilon}$ the
cell of dimension one. Consequently, at most one connected component
disappears, and it holds:

$q_{a-\varepsilon}-1\leq q_{a}\leq q_{a-\varepsilon}.$

The case $QI=1$, $BI=0$ is well known from nonlinear programming, see e. g.
[6]. The case $QI=0$, $BI=1$ is new and characteristic for MPSC, cf. Example
3.2.

  * 4)

$\bar{x}$ is W-stationary with W-index greater than one, i. e. $QI+BI>1$. The
boundary of the to be attached $(QI+BI)$-dimensional cell is thus connected.
Consequently, the number of connected components of $M^{a}$ remains unchanged,
and it holds:

$q_{a}=q_{a-\varepsilon}.$

Now, we proceed with the global argument. Compactness of $M$ implies that
there exists $c\in\mathbb{R}$ such that $M^{c}$ is empty, thus, $q_{c}=0$.
Additionally, there exists $d\in\mathbb{R}$ such that $M^{d}$ is connected and
contains all W-stationary points, thus, $q_{d}=1$. Since nondegenerate
W-stationary points are in particular isolated, we conclude that there must be
finitely many of them again due to the compactness of $M$. Let us now increase
the level $a$ from $c$ to $d$ and describe how the number $q_{a}$ of connected
components of the lower level sets $M^{a}$ changes. It follows from the local
argument that $r$ new connected components are created, where $r$ is the
number of local minimizers for MPSC. Let $q_{s}$ denote the actual number of
disappearing connected components if passing the levels corresponding to
W-stationary saddle points. The local argument provides that at most $r_{s}$
connected components might disappear while doing so, i. e.

$q_{s}\leq r.$

Altogether, we have:

$r-r_{s}\leq r-q_{s}=q_{d}-q_{c}.$

By recalling that $q_{d}=1$ and $q_{c}=0$, we get (13). $\square$

Finally, we link our results to the numerical investigations of MPSC
undertaken in [10]. There, the important role of W-stationary points is
highlighted if applying the Scholtes’ relaxation to switching constraints. In
[10, Theorem 3.2] it is proven that KKT-points of such relaxation converge to
a W-stationary point of MPSC under LICQ. Moreover, as shown in [10, Example
3.3] stronger results cannot be expect in general. Let us illustrate how the
global structure of MPSC is inherited by the Scholtes’ relaxation.

######  Example 3.2 (Scholtes’ relaxation, cf. [10])

Consider the MPSC:

$\min\,\,f\left(x_{1},x_{2}\right)=\left(x_{1}-1\right)^{2}+\left(x_{2}-1\right)^{2}\quad\mbox{s.t.}\quad
x_{1}\cdot x_{2}=0.$ (14)

It is easy to see that the feasible point $x^{1}=(0,0)$ is W-stationary.
Moreover, it is nondegenerate with quadratic index $QI=0$. For its bi-active
index we have $BI=1$. This means that $x^{1}$ is a saddle point with W-index
equal to one which connects two minimizers $x^{2}=(1,0)$ and $x^{3}=(0,1)$.
Let us consider the Scholtes’ relaxation for (3.2) with sufficiently small
$t>0$:

$\min\,\,f\left(x_{1},x_{2}\right)=\left(x_{1}-1\right)^{2}+\left(x_{2}-1\right)^{2}\quad\mbox{s.t.}\quad-t\leq
x_{1}\cdot x_{2}\leq t.$ (15)

It is easily seen that the KKT-points of (15) are

$x^{1}_{t}=\left(\sqrt{t},\sqrt{t}\right),$
$x^{2}_{t}=\left(\displaystyle\frac{1+\sqrt{1-4t}}{2},\displaystyle\frac{1-\sqrt{1-4t}}{2}\right),$
$x^{3}_{t}=\left(\displaystyle\frac{1-\sqrt{1-4t}}{2},\displaystyle\frac{1+\sqrt{1-4t}}{2}\right).$

Obviously, $x^{1}_{t}\longrightarrow x_{1}$, $x^{2}_{t}\longrightarrow x_{2}$,
and $x^{3}_{t}\longrightarrow x_{3}$ as $t\longrightarrow 0$. Moreover,
$x^{2}_{t}$ and $x^{3}_{t}$ are minimizers for (15) with zero quadratic index,
the quadratic index of $x^{1}_{t}$ is equal to one. By the smoothing
procedure, the W-stationary point $x^{1}$ with W-index equal to one
corresponds to the KKT-point $x^{1}_{t}$ with quadratic index equal to one
likewise. We conclude that the smoothed version fully preserves the global
topological structure of MPSC.

##  4 Characterization of strong stability

We would like to address the question whether the requirements ND1-ND4 for
W-stationary points are too restrictive. For that, let us examine the gap
between nondegeneracy and strong stability of W-stationary points. The concept
of strong stability is defined by means of an appropriate semi-norm. To this
aim let be $\bar{x}\in\mathbb{R}^{n}$, $r>0$. For defining functions
$\left(f,h,g,F_{1},F_{2}\right)$ from (1) the seminorm
$\left\|\left(f,h,g,F_{1},F_{2}\right)\right\|^{C^{2}}_{B(\bar{x},r)}$ is
defined to be the maximum modulus of the function values and partial
derivatives up to order two of $f,h,g,F_{1},F_{2}$.

######  Definition 4.7 (Strong Stability, cf. [13])

A W-stationary point $\bar{x}\in M$, resp. a W-stationary pair
$(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$, for
$MPSC[f,g,h,F_{1},F_{2}]$ is called ($C^{2}$)-strongly stable if for some
$r>0$ and each $\varepsilon\in(0,r]$ there exists
$\delta=\delta(\varepsilon)>0$ such that whenever
$\left(\widetilde{f},\widetilde{h},\widetilde{g},\widetilde{F}_{1},\widetilde{F}_{2}\right)\in
C^{2}$ and

$\left\|\left(f-\widetilde{f},h-\widetilde{h},g-\widetilde{g},F_{1}-\widetilde{F}_{1},F_{2}-\widetilde{F}_{2}\right)\right\|^{C^{2}}_{B(\bar{x},r)}\leq\delta,$

$B(\bar{x},\varepsilon)$, resp.
$B\left(\left(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma}\right),\varepsilon\right)$,
contains a W-stationary point $\widetilde{x}$, resp. a W-stationary pair
$\left(\widetilde{x},\widetilde{\lambda},\widetilde{\mu},\widetilde{\sigma}\right)$,
for
MPSC$\left[\widetilde{f},\widetilde{h},\widetilde{g},\widetilde{F}_{1},\widetilde{F}_{2}\right]$
which is unique in $B(\bar{x},r)$, resp. unique in
$B\left(\left(\widetilde{x},\widetilde{\lambda},\widetilde{\mu},\widetilde{\sigma}\right),r\right)$.

The following Lemma 4.2 establishes the connection between both definitions
just introduced, cf. [12] for the case of nonlinear programming.

######  Lemma 4.2 (W-stationary points and pairs)

The following assertions are equivalent:

  * (a)

$\bar{x}$ is a strongly stable W-stationary point for MPSC which satisfies
LICQ, and $(\bar{\lambda},\bar{\mu},\bar{\sigma})$ is the associated Lagrange
multiplier vector.

  * (b)

$(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$ is a strongly stable
W-stationary pair for MPSC.

Proof. (a) $\Longrightarrow$ (b) LICQ remains valid under small perturbations
of the defining functions. Hence, the corresponding Lagrange multipliers are
unique. Remark 2.1 provides the continuity of Lagrange multipliers with
respect to perturbations under consideration.

(b) $\Longrightarrow$ (a) The nontrivial part is to prove that LICQ holds at
$\bar{x}$. The proof goes along the lines of [12, Theorem 2.3]. To stress the
new aspects here we assume that there are only bi-active switching
constraints, i. e. $I=\emptyset$, $J=\emptyset$, $\alpha(\bar{x})=\emptyset$
and $\gamma(\bar{x})=\emptyset$. Let $(\bar{x},\bar{\sigma})$ be a strongly
stable W-stationary pair for MPSC and let LICQ be not fulfilled at $\bar{x}$.
Then, there exist real numbers $\delta_{1,m},\delta_{1,m}$,
$m\in\beta(\bar{x})$ (not all vanishing) such that:

${\displaystyle\sum_{m\in\beta(\bar{x})}}\left(\delta_{1,m}DF_{1,m}(\bar{x})+\delta_{2,m}DF_{2,m}(\bar{x})\right)=0.$
(16)

We define

$c={\displaystyle\sum_{m\in\beta(\bar{x})}}\left(DF_{1,m}(\bar{x})+DF_{2,m}(\bar{x})\right).$

For $\varepsilon>0$ let

$\sigma_{1,m}(\varepsilon)=\bar{\sigma}_{1,m}+\varepsilon,\sigma_{2,m}(\varepsilon)=\bar{\sigma}_{2,m}+\varepsilon\mbox{
for all }m\in m_{\beta}(\bar{x}).$

Putting $\varphi(x)=c\cdot x$ we obtain that $(\bar{x},\sigma(\varepsilon))$
is a W-stationary pair for
MPSC$\left[f+\varepsilon\cdot\varphi,F_{1},F_{2}\right]$. Moreover, due to the
strong stability of $(\bar{x},\bar{\sigma})$ for
MPSC$\left[f,F_{1},F_{2}\right]$ we claim that for each sufficiently small
$\varepsilon>0$ the W-stationary pair $(\bar{x},\sigma(\varepsilon))$ is
unique for MPSC$\left[f+\varepsilon\cdot\varphi,F_{1},F_{2}\right]$ in some
neighborhood $U$ of $(\bar{x},\bar{\sigma})$. However, (16) and
$\sigma_{i,m}(\varepsilon)\not=0$ for $m\in m_{\beta}(\bar{x})$, $i=1,2$,
ensure that for any sufficiently small real number $t$, the pair
$(\bar{x},v(\varepsilon,\delta,t))$ with

$v_{1,m}(\varepsilon,\delta,t)=\sigma_{1,m}(\varepsilon)+\delta_{1,m}t,v_{2,m}(\varepsilon,\delta,t)=\sigma_{2,m}(\varepsilon)+\delta_{2,m}t\mbox{
for all }m\in m_{\beta}(\bar{x})$

belongs to $U$ and is a W-stationary pair for
MPSC$\left[f+\varepsilon\cdot\varphi,F_{1},F_{2}\right]$. Hence, necessarily
$\delta=0$, and LICQ is shown. $\square$

Now we give two guiding examples for instability which may occur at
W-stationary points.

######  Example 4.3 (Instability I)

Consider the MPSC:

$\min\,\,\pm x_{1}^{2}\pm x_{2}^{2}\quad\mbox{s.t.}\quad x_{1}\cdot x_{2}=0.$
(17)

Obviously, $(0,0)$ is the unique W-stationary point for (17) with both
vanishing bi-active Lagrange multipliers. Consider the following perturbation
of (17) with respect to parameter $t>0$:

$\min\,\,\pm\left(x_{1}-t\right)^{2}\pm\left(x_{2}-t\right)^{2}\quad\mbox{s.t.}\quad
x_{1}\cdot x_{2}=0.$ (18)

It is easy to see that $(0,0)$, $(0,t)$ and $(t,0)$ are W-stationary points
for (18). It means that $(0,0)$ is not a strongly stable W-stationary point
for (17). $\square$

######  Example 4.4 (Instability II)

Consider the MPSC:

$\min\,\,x_{1}\pm x_{2}^{2}\quad\mbox{s.t.}\quad x_{1}\cdot x_{2}=0.$ (19)

Obviously, $(0,0)$ is the unique W-stationary point for (17) with exactly one
vanishing bi-active Lagrange multiplier. Consider the following perturbation
of (19) with respect to parameter $t>0$:

$\min\,\,x_{1}\pm\left(x_{2}-t\right)^{2}\quad\mbox{s.t.}\quad x_{1}\cdot
x_{2}=0.$ (20)

It is easy to see that $(0,0)$ and $(0,t)$ are W-stationary points for (20).
It means that $(0,0)$ is not a strongly stable W-stationary point for (19).
$\square$

For characterizing strong stability, we shall use some auxiliary objects
associated with a W-stationary point $\bar{x}\in M$ and its multipliers
$(\bar{\lambda},\bar{\mu},\bar{\gamma})$. Let the index set of positive
multipliers corresponding to the inequality constraints is given by

$J_{+}(\bar{x})=\left\\{q\in
J_{0}(\bar{x})\,\left|\,\bar{\mu}_{j}>0\right.\right\\}.$

For $J_{+}(\bar{x})\subset J_{*}\subset J_{0}(\bar{x})$ we set

$\begin{array}[]{ll}M_{*}(\bar{x})=\\{x\in\mathbb{R}^{n}\,\,|&h_{i}(x)=0,i\in
I,g_{j}(x)=0,j\in J_{*},\\\
&F_{1,m_{\alpha}}(x)=0,m_{\alpha}\in\alpha(\bar{x}),F_{2,m_{\gamma}}(x)=0,m_{\gamma}\in\gamma(\bar{x}),\\\
&F_{1,m_{\beta}}(x)=0,F_{2,m_{\beta}}(x)=0,m_{\beta}\in\beta(\bar{x})\\}.\end{array}$

Obviously, $M_{*}(\bar{x})\subset M$ and, in the case where LICQ holds at
$\bar{x}$, $M_{*}(\bar{x})$ is locally a $C^{2}$-manifold of dimension
$p+\left|J_{0}(\bar{x})\right|-\left|J_{*}(\bar{x})\right|$. The tangent space
of $M_{*}(\bar{x})$ at $\bar{x}$ is

$\begin{array}[]{ll}T_{\bar{x}}M_{*}(\bar{x})=\\{\xi\in\mathbb{R}^{n}\,\,|&Dh_{i}(\bar{x})\,\xi=0,i\in
I,Dg_{j}(\bar{x})\,\xi=0,j\in J_{*}\\\
&DF_{1,m_{\alpha}}(\bar{x})\,\xi=0,m_{\alpha}\in\alpha(\bar{x}),\\\
&DF_{2,m_{\gamma}}(\bar{x})\,\xi=0,m_{\gamma}\in\gamma(\bar{x}),\\\
&DF_{1,m_{\beta}}(\bar{x})\,\xi=0,DF_{2,m_{\beta}}(\bar{x})\,\xi=0,m_{\beta}\in\beta(\bar{x})\\}.\end{array}$

######  Theorem 4.6 (Characterization of strong stability)

Let $\bar{x}\in M$ be a W-stationary point of MPSC satisfying LICQ with the
unique Lagrange multipliers $(\bar{\lambda},\bar{\mu},\bar{\sigma})$. Then,
$\bar{x}$ is strongly stable if and only if

  * (i)

it fulfils ND3, i. e.
$\bar{\sigma}_{1,m_{\beta}}\cdot\bar{\sigma}_{2,m_{\beta}}\neq 0$ for all
$m_{\beta}\in\beta(\bar{x})$, and

  * (ii)

the matrices
$D^{2}_{xx}L(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})\restriction_{\mathcal{T}_{\bar{x}}M_{*}(\bar{x})}$
are nonsingular with the same determinant sign for all index subsets
$J_{+}(\bar{x})\subset J_{*}\subset J_{0}(\bar{x})$.

Proof. In virtue of LICQ at $\bar{x}$, Lemma 4.2 allows us to deal
equivalently with the strong stability of the W-stationary pair
$(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$.

Case 1: ND3 holds

We consider the following mapping
$\mathcal{T}:\mathbb{R}^{n+|I|+|J|+2k}\longrightarrow\mathbb{R}^{n+|I|+|J|+2k}$
locally at its zero $(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$:

$\mathcal{T}(x,\lambda,\mu,\sigma)=\left(\begin{array}[]{c}D_{x}L(x,\lambda,\mu,\sigma)\\\
h(x)\\\ \min\left\\{\mu,g(x)\right\\}\\\ F_{1,\alpha(\bar{x})}(x)\\\
F_{2,\gamma(\bar{x})}(x)\\\ F_{1,\beta(\bar{x})}(x)\\\
F_{2,\beta(\bar{x})}(x)\\\ \end{array}\right).$

Note that W-stationary pairs for MPSC - in a sufficiently small neighborhood
of $(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$ \- are precisely the zeros
of $\mathcal{T}$. Moreover, characterization of strong stability for KKT-
points in the case of nonlinear programming can be applied here. Indeed, as in
[12, Theorem 4.3], the strong stability for
$(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$ can be characterized by the
fact that all matrices in the Clarke’s subdifferential
$\partial\mathcal{T}(\bar{x},\bar{\lambda},\bar{\mu},\bar{\sigma})$ are
nonsingular. The latter can be equivalently rewritten as condition (ii), cf.
also [11] for the case of nonlinear programming.

Case 2: ND3 fails

Let $\Phi:U\longrightarrow V$ be the standard diffeomorphism from Defnition
2.4. We put $\bar{f}=f\circ\Phi^{-1}$ on the set
$\left(\\{0_{s}\\}\times\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}\times\mathbb{R}^{p}\right)\cap
V$. From now on we may assume $s=0$. In view of Remark 2.1 and failure of ND3
we have at the origin:

  * (i)

$\displaystyle\frac{\partial\bar{f}}{\partial y_{j}}\geq 0,j\in
J_{0}(\bar{x}),$

  * (ii)

$\displaystyle\frac{\partial\bar{f}}{\partial
y_{2m+q-1}}\cdot\frac{\partial\bar{f}}{\partial y_{2m+q}}=0$ for at least one
$m=1,\ldots|\beta(\bar{x})|,$

  * (iii)

$\displaystyle\frac{\partial\bar{f}}{\partial y_{k+n-p}}=0$, $k=1,\ldots,p$.

Without loss of generality, we assume $m=1$ in (ii). From now on we denote
$\bar{f}$ again by $f$. In what follows, we successively perform arbitrarily
small perturbations of $f$ such that the origin remains a W-stationary point
on
$\mathbb{H}^{|J_{0}(\bar{x})|}\times\mathbb{S}^{|\beta(\bar{x})|}\times\mathbb{R}^{p}$.

1) As a stabilization step we add to $f$ an arbitrarily small linear-quadratic
term

${\displaystyle\sum_{j=1}^{|J_{0}(\bar{x})|}}c_{j}\cdot
y_{j}+{\displaystyle\sum_{m=2}^{|\beta(\bar{x})|}}\left(c_{2m+q-1}\cdot
y_{2m+q-1}+c_{2m+q}\cdot
y_{2m+q}\right)+{\displaystyle\sum_{k=1}^{p}}c_{k+n-p}\cdot y^{2}_{k+n-p},$

such that it holds for the perturbed function (denoted again by $f$):

  * (i)

$\displaystyle\frac{\partial f}{\partial y_{j}}>0$, $j\in J_{0}(\bar{x})$,

  * (ii)

$\displaystyle\frac{\partial f}{\partial y_{2m+q-1}}\cdot\frac{\partial
f}{\partial y_{2m+q}}\neq 0$, $m=2,\ldots,|\beta(\bar{x})|$,

  * (iii)

$\displaystyle\frac{\partial f}{\partial y_{k+n-p}}=0$, $k=1,\ldots,p$ and
$\left(\displaystyle\frac{\partial^{2}f}{\partial y_{k_{1}+n-p}\partial
y_{k_{2}+n-p}}\right)_{1\leq k_{1},k_{2}\leq p}$ is a nonsingular matrix.

  * (iv)

$\displaystyle\frac{\partial f}{\partial y_{q+1}}\cdot\frac{\partial
f}{\partial y_{q+2}}=0$.

2) We approximate $f$ by means of a $C^{\infty}$-function in a small
$C^{2}$-neighborhood of $f$ such leaving its value, first and second order
derivatives at the origin invariant. This can be done since
$C^{\infty}$-functions lie $C^{2}$-dense in $C^{2}$-functions. We denote the
latter $C^{\infty}$-approximation again by $f$.

Due to the stabilization step 1) and step 2), we can restrict our
considerations to the following situation:

$f\in C^{\infty}\left(\mathbb{R}^{2},\mathbb{R}\right),0\mbox{ is a
W-stationary point for }f{\restriction_{\mathbb{S}}}\mbox{ and
}\displaystyle\frac{\partial f}{\partial x_{1}}(0)\cdot\frac{\partial
f}{\partial x_{2}}(0)=0.$

Case I: $\displaystyle\frac{\partial f}{\partial x_{1}}(0)=\frac{\partial
f}{\partial x_{2}}(0)=0$.

We can write

$f\left(x_{1},x_{2}\right)=g_{1,1}\left(x_{1},x_{2}\right)x^{2}_{1}+2g_{1,2}\left(x_{1},x_{2}\right)x_{1}x_{2}+g_{2,2}\left(x_{1},x_{2}\right)x_{2}^{2}$

with $g_{1,1},g_{1,2},g_{2,2}\in
C^{\infty}\left(\mathbb{R}^{2},\mathbb{R}\right)$. Adding to $f$ an
arbitrarily small quadratic term $ax_{1}^{2}+bx_{2}^{2}$, $a,b\in\mathbb{R}$
we can ensure that $g_{1,1}(0,0)\not=0$ and $g_{2,2}(0,0)\not=0$. Hence,

$\Psi\left(x_{1},x_{2}\right)=\left(\begin{array}[]{c}\displaystyle
x_{1}\cdot\sqrt{|{g_{1,1}\left(x_{1},x_{2}\right)}|}\\\ \displaystyle
x_{2}\cdot\sqrt{|{g_{2,2}\left(x_{1},x_{2}\right)}|}\\\ \end{array}\right)$

is a local $C^{\infty}$-diffeomorphism leaving $\mathbb{S}$ invariant. In new
local coordinates induced by $\Psi$ we obtain:

$f\left(x_{1},x_{2}\right)=\varepsilon_{1}x_{1}^{2}+G\left(x_{1},x_{2}\right)x_{1}x_{2}+\varepsilon_{2}x_{2}^{2},$

where $\varepsilon_{1}=\mbox{sign}\left(g_{1,1}(0,0)\right)$,
$\varepsilon_{2}=\mbox{sign}\left(g_{2,2}(0,0)\right)$. Since
$G\left(x_{1},x_{2}\right)x_{1}x_{2}=0$ on $\mathbb{S}$, we can perturb $f$ by
means of a real parameter as in Example 4.3 to get a bifurcation of $0$ as a
W-stationary point.

Case II: $\displaystyle\frac{\partial f}{\partial x_{1}}(0)\neq 0$,
$\displaystyle\frac{\partial f}{\partial x_{2}}(0)=0$.

We can write

$f\left(x_{1},x_{2}\right)=g_{1,1}\left(x_{1},x_{2}\right)x_{1}+g_{2,2}\left(x_{1},x_{2}\right)x_{2}^{2}$

with $g_{1,1},g_{2,2}\in C^{\infty}\left(\mathbb{R}^{2},\mathbb{R}\right)$ and
$g_{1}(0,0)\neq 0$. Adding to $f$ an arbitrarily small quadratic term
$bx_{2}^{2}$, $b\in\mathbb{R}$ we can also ensure that $g_{2,2}(0,0)\not=0$.
Hence,

$\Psi\left(x_{1},x_{2}\right)=\left(\begin{array}[]{l}\displaystyle x_{1}\cdot
g_{1,1}\left(x_{1},x_{2}\right)\\\ \displaystyle
x_{2}\cdot\sqrt{|{g_{2,2}\left(x_{1},x_{2}\right)}|}\\\ \end{array}\right)$

is a local $C^{\infty}$-diffeomorphism leaving $\mathbb{S}$ invariant. In new
local coordinates induced by $\Psi$ we obtain:

$f\left(x_{1},x_{2}\right)=x_{1}+\varepsilon x_{2}^{2},$

where $\varepsilon=\mbox{sign}\left(g_{2,2}(0,0)\right)$. We can perturb $f$
by means of a real parameter as in Example 4.4 to get a bifurcation of $0$ as
a W-stationary point.

The case $\displaystyle\frac{\partial f}{\partial x_{1}}(0)=0$,
$\displaystyle\frac{\partial f}{\partial x_{2}}(0)\neq 0$ can be treated
analogously.

Finally, performing all perturbations described above we ensure that $0$ is
not a strongly stable W-stationary point. $\square$

Next result is a direct consequences of Theorem 4.6.

###### Corollary 4.2

Any nondegenerate W-stationary point of MPSC is strongly stable.

Additionally, it is important to note that ND3 is necessary for strong
stability of W-stationary points due to Theorem 4.6, i. e. both bi-active
Lagrange multipliers cannot vanish. This new issue is in strong contrast e. g.
with the characterization of strong stability of C-stationary points in MPCC,
see [9]. In MPCC, strong stability includes cases where one of the bi-active
Lagrange multipliers may vanish. In other words, there is an essential
discrepancy between nondegeneracy and strong stability of C-stationary points
in MPCC. In MPSC, the situation is rather different: in absence of active
inequality constraints, nondegeneracy of W-stationary points is equivalent to
their strong stability.

###### Corollary 4.3

Let inequality constraints be inactive at a W-stationary point $\bar{x}\in M$,
i. e. $J_{0}(\bar{x})=\emptyset$. Then, $\bar{x}$ is nondegenerate if and only
if it is strongly stable and satisfies LICQ.

## References

  * [1] D. Dorsch, V. Shikhman, O. Stein Mathematical programs with vanishing constraints: Critical Point Theory, Journal of Global Optimization, Vol. 52, No. 3, pp. 591-605, 2012.
  * [2] C.A. Floudas, H.Th. Jongen, Global optimization: local minima and transition points, Journal of Global Optimization, Vol. 32, No. 3, pp. 409-415, 2005.
  * [3] M. Goresky, R. MacPherson Stratified Morse Theory, Springer, Berlin-Heidelberg-New York, 1988.
  * [4] M. W. Hirsch, Differential topology, Springer, Berlin-Heidelberg-New York, 1976.
  * [5] H. Th. Jongen, On non-convex optimization, Dissertation, University of Twente, The Netherlands, 1977.
  * [6] H.Th. Jongen, P. Jonker, F. Twilt, Nonlinear Optimization in Finite Dimensions, Kluwer Academic Publishers, Dordrecht, 2000.
  * [7] H.Th. Jongen, K. Meer, E. Triesch, Optimization Theory, Kluwer Academic Publishers, Dordrecht, 2004.
  * [8] H. Th. Jongen, Jan.-J. Rückmann, V. Shikhman, MPCC: Critical Point Theory, SIAM J. Optim., Vol. 20, No. 1, pp. 473-484, 2009.
  * [9] H. Th. Jongen, V. Shikhman, S. Steffensen Characterization of Strong Stability for C-stationary Points in MPCC, Mathematical Programming, Vol. 132, No. 1-2, pp. 295-308, 2012.
  * [10] C. Kanzow, P. Mehlitz, D. Steck, Relaxation schemes for mathematical programmes with switching constraints, Optimization Methods and Software, DOI: 10.1080/10556788.2019.1663425
  * [11] D. Klatte, B. Kummer, Strong stability in nonlinear programming revisited, J. Austral. Math. Soc. Ser. B, Vol. 40, No. 3, pp. 336-352, 1999.
  * [12] D. Klatte, K. Tammer, Strong stability of stationary solutions and Karush-Kuhn-Tucker points in nonlinear optimization, Annals of Operations Research, Vol. 27, No. 1, pp. 285-308, 1990.
  * [13] M. Kojima, Strongly stable stationary solutions in nonlinear programs, In: Analysis and computation of fixed points, S.M. Robinson (ed.), Academic Press, New York, pp. 93 - 138, 1980.
  * [14] P. Mehlitz, Stationarity conditions and constraint qualifications for mathematical programs with switching constraints, Mathematical Programming, Vol. 181, pp. 1-38, 2019.
  * [15] J. Milnor, Morse Theory, Annals of Mathematic Studies, Princeton University Press, Princeton, New Jersey, Vol. 51, pp. 1-153, 1963.
  * [16] D. Ralph, O. Stein The C-Index: A New Stability Concept for Quadratic Programs with Complementarity Constraint, Mathematics of Operations Research, Vol. 36, No. 3, pp. 504-526, 2011.
  * [17] V. Shikhman, Topological Aspects of Nonsmooth Optimization, Springer, New York, 2012.
  * [18] E.H. Spanier, Algebraic Topology, McGraw-Hill Book Company, New York, 1966.


# No contextual advantage in non-paradoxical scenarios of two state vector
formalism

Jaskaran Singh<EMAIL_ADDRESS>Departamento de Física Aplicada II,
Universidad de Sevilla, E-41012 Sevilla, Spain  Rajendra Singh Bhati
<EMAIL_ADDRESS>Department of Physical Sciences, Indian Institute of
Science Education and Research (IISER) Mohali, Sector 81 SAS Nagar, Manauli PO
140306 Punjab India.  Arvind<EMAIL_ADDRESS>Department of Physical
Sciences, Indian Institute of Science Education and Research (IISER) Mohali,
Sector 81 SAS Nagar, Manauli PO 140306 Punjab India.  Vice Chancellor, Punjabi
University Patiala, 147002, Punjab, India

###### Abstract

The two state vector formalism (TSVF) was proposed by Aharonov, Bergmann, and
Lebowitz (ABL) to provide a way for the counterfactual assignment of the
probabilities of outcomes of contemplated but unperformed measurements on
quantum systems. This formalism underlies various aspects of foundations of
quantum theory and has been used significantly in the development of weak
values and several proofs of quantum contextuality. We consider the
application of TSVF, with pre- and post-selection (PPS) and the corresponding
ABL rule, as a means to unearth quantum contextuality. We use the principle of
exclusivity to classify the resultant pre- and post-selection scenarios as
either paradoxical or non-paradoxical. In light of this, we find that several
previous proofs of the emergence of contextuality in PPS scenarios are only
possible if the principle of exclusivity is violated and are therefore
classified as paradoxical. We argue that these do not constitute a proper test
of contextuality. Furthermore, we provide a numerical analysis for the KCBS
scenario as applied in the paradigm of TSVF and find that non-paradoxical
scenarios do not offer any contextual advantage. Our approach can be easily
generalized for other contextual scenarios as well.

##  I Introduction

The standard quantum theory does not provide a framework for making
predictions about the measurements in the past (retrodiction) of a quantum
system once it has been measured in a definite state. Aharonov, Bergmann, and
Lebowitz (ABL), in their seminal work on the time symmetry in successive
quantum measurements, introduced a reformulation of the standard quantum
theory where one can meaningfully talk about statistical predictions of a
measurement on a pre-and post-selected (PPS) ensemble at an intermediate time
Aharonov  _et al._ (1964). The retrodiction formula derived by ABL (ABL rule)
is the probability of a measurement outcome conditioned on the outcomes of a
preceding and a succeeding measurement.

A generalized framework for PPS ensembles in terms of ‘weak values’ was
formulated as two state vector formalism (TSVF) Aharonov  _et al._ (1988);
Aharonov and Vaidman (1990, 1991) in order to experimentally validate the ABL
formulation Ritchie  _et al._ (1991); Pryde  _et al._ (2005). In TSVF, the
complete description of a quantum system is specified by two state vectors,
one evolving forward in time and the other one evolving backwards. Here the
arrow of time is described by the order of preceding and succeeding
measurements. TSVF finds intriguing applications in quantum foundations
Steinberg (1995); Kocsis  _et al._ (2011); Mahler  _et al._ (2016); Aharonov
_et al._ (2002); Lundeen and Steinberg (2009); Williams and Jordan (2008);
Lundeen  _et al._ (2011) and quantum information processing Dressel  _et al._
(2014). The ABL retrodiction, more specifically the TSVF, has resulted in
various counter intuitive results commonly called PPS paradoxes Resch  _et
al._ (2004); Vaidman (2013); Danan  _et al._ (2013); Aharonov  _et al._ (2017,
2013); Denkmayr  _et al._ (2014); Bancal (2013); Das and Pati (2020); Liu  _et
al._ (2020). In a recent work Bhati and Arvind (2022) counterfactual use of
ABL retrodiction has been shown to run into a direct contradiction with
operational quantum mechanics challenging the completeness of TSVF. Therefore
further investigations on the appropriateness of ABL retrodiction in
connection with various non-classical aspects of quantum theory is critical in
order to pinpoint the exact role of TSVF in the studies of quantum
foundations.

Contrary to the Born rule, probabilities assigned by the ABL formula are
determined by the specification of the measurement setting of an observable
and on pre and post selected states in context of which the observable is
being measured. This sort of context dependency of measurements has led to
connections between PPS paradoxes and contextuality Albert  _et al._ (1985):
since the probabilities assigned to measurement outcomes are explicitly
context dependent, there is no motivation to consider a non-contextual hidden
variable theory as a realistic extension of operational quantum theory.
Nevertheless, this reasoning has been disputed based on the fact that Bell-
type correlations can be simulated using post-selections in local hidden
variable theories Bub and Brown (1986). Therefore, the mere presence of
context dependent elements in ABL formula should not be sufficient to prove
Bell-Kochen-Specker (BKS) theorem Simon Kochen (1968); Mermin (1993) or the
various statistical versions of contextuality Cabello  _et al._ (2014). It is
required to dive deeper in order to establish a valid connection between
contextuality and the ABL retrodiction formula.

Mermin Mermin (1995) showed the existence of a strong connection between the
two by illustrating how measurements used in a proof of BKS theorem can give
birth to unsolvable PPS paradoxes indicating a kind of impossibility of non-
contextual hidden variable theories. Leifer and Spekkens Leifer and Spekkens
(2005) later logically showed that for every PPS paradox with a scenario
involving non-orthogonal pre-and post-selection states, there exists an
associated proof of BKS theorem. Their proof is based on the fact that ABL
probability assignments of certain sets of projectors in a variant of 3-box
paradox violate algebraic constraints dictated by classical probability
theory. An exhaustive discussion on the same in relation with weak values was
presented by Tollaksen Tollaksen (2007). Another important contribution in
this direction was recently made by establishing a direct connection between
anomalous weak values and contextuality where it has been suggested that
anomalous weak values can be taken as proofs of contextuality Pusey (2014);
Kunjwal  _et al._ (2019). So far the studies in this avenue of research have
been focused on logical proofs of contextuality invoking only the paradoxical
nature of ABL probability assignments. In these logical proofs of
contextuality one arrives at a contradiction while making assignment of
probabilities to various outcomes following the ABL rule. Such proofs
generally involve the paradoxes generated by the application of the ABL rule.
Therefore, it is natural to ask whether there is any contextual advantage in
situations with “non-paradoxical assignments” of ABL probabilities.

In this paper, by analyzing the Klyachko-Can-Binicioğlu-Shumovsky (KCBS)
scenario Klyachko  _et al._ (2008) (which comprises a statistical proof of
contextuality) with the ABL formula, we show that non-paradoxical ABL
probability assignments do not give rise to any contextual advantage.
Furthermore, in order to produce an advantage one needs to renounce the
exclusivity principle which is central to any operational theory Cabello
(2013); Amaral  _et al._ (2014); Chiribella  _et al._ (2020). Our result
raises serious questions about the ABL-contextuality connections that have
been advocated by previous authors: is this connection merely an illusion
created by post-selection just like the detection efficiency loophole in Bell
non-locality tests? Since the paradoxical sector of ABL probabilities requires
abandoning the notion of principle of exclusivity can ABL retrodiction be
considered an appropriate description of quantum systems at all?

The paper is organized as follows: In Sec. II.1 we introduce the concept of
PPS scenarios and briefly discuss the ABL formula and consequently the TSVF.
In Sec. II.2 we present our main result that the ABL rule is unable to
correctly predict the statistics of the KCBS scenario. In Sec. V we offer some
concluding remarks.

##  II ABL rule, TSVF and PPS paradoxes

In this section we describe the TSVF and ABL retrodiction rule. We define PPS
scenarios and introduce the notion of paradoxical and non-paradoxical nature
of them. This classification depends on whether the probability assignments
are properly conditioned by the exclusivity principle or not.

###  II.1 TSVF and ABL retrodiction

In this subsection we illustrate a general pre- and post-selected scenario and
elucidate how the ABL rule can be used to assign probabilities to intermediate
measurements.

A pre- and post-selection scenario deals with statistical assignment of
probabilities to the outcomes of the measurement of an observable $A$ at time
$t$ when the system is pre-selected to be in the state $\ket{\psi}$ at some
time $t_{i}<t$ and post-selected in the state $\ket{\phi}$ at a later moment
in time $t_{f}>t$. Pre-selection is achieved by performing a projective
measurement
$\mathcal{P}_{1}\equiv\\{\outerproduct{\psi}{\psi},\mathds{1}-\outerproduct{\psi}{\psi}\\}$
at time $t_{i}$ on the initial state of the system $\rho$ (which can be chosen
arbitrarily) and selecting only the outcomes corresponding to
$\outerproduct{\psi}{\psi}$. Similarly for post-selection one can perform a
projective measurement of
$\mathcal{P}_{2}\equiv\\{\outerproduct{\phi}{\phi},\mathds{1}-\outerproduct{\phi}{\phi}\\}$
at time $t_{f}$ where outcomes corresponding to $\outerproduct{\phi}{\phi}$
are filtered (see Fig. 1). It is apparent that such probability assignments
are conditioned on PPS states $\ket{\psi}$ and $\ket{\phi}$ and therefore time
symmetric.

Figure 1: A PPS scenario with a measurement of an observable $\mathcal{A}$ at
an intermediate instance of time. System is pre-selected in state $\ket{\psi}$
by performing a projective measurement $\mathcal{P}_{1}$ and filtering the
outcome corresponding to the state $\ket{\psi}$ and post selected in state
$\ket{\phi}$ by filtering outcome $\tilde{\ket{\phi}}$ of measurement
$\mathcal{P}_{2}$. $\\{\ket{a}_{i}\\}$ is the set of all possible outcomes of
an intermediate observable $\mathcal{A}$

Consider an observable $\mathcal{A}$ with outcomes
$\\{\outerproduct{a_{i}}{a_{i}}\\}$ which is measured after pre-selecting a
state $\ket{\psi}$ and afterwards post-selecting a state $\ket{\phi}$. The
probability of obtaining the outcome $\outerproduct{a_{i}}{a_{i}}$ conditioned
on pre-and post-selections is given as

$\zeta_{i}=\frac{|\braket{\phi}{a_{i}}|^{2}|\braket{a_{i}}{\psi}|^{2}}{\sum_{j}|\braket{\phi}{a_{j}}|^{2}|\braket{a_{j}}{\psi}|^{2}},$
(1)

which can be simplified as

$\zeta_{i}=\frac{|\langle\phi|\Pi_{i}|\psi\rangle|^{2}}{\sum_{j}|\langle\phi|\Pi_{j}|\psi\rangle|^{2}},$
(2)

where $\Pi_{i}=\outerproduct{a_{i}}{a_{i}}$. As one can see, $\zeta_{i}$ for a
projector $\Pi_{i}$ is dependent on PPS states $\ket{\psi}$ and $\ket{\phi}$.
A different choice of these will yield different probability assignments.
Furthermore, the measurement context of the projector $\Pi_{i}$ also plays a
major role. If the set of measurement settings in which $\Pi_{i}$ appears is
chosen differently, the term $\sum_{j}|\langle\phi|\Pi_{j}|\psi\rangle|^{2}$
will also change. All of the aforementioned choices form a context for the
projector $\Pi_{i}$.

This makes ABL formula given in Eq. (2) inherently context dependent and led
Albert et al. to draw a parallel between ABl retrodiction and quantum
contextuality.

There are two ways to interpret Eq. (2). In the first case, the observable
$\mathcal{A}$ is actually measured after performing a pre-selection. Post
selection is then performed on the state after the measurement of
$\mathcal{A}$. In this case there are a total of three different sequential
measurements being performed. This case is known as non-counterfactual
assignment of probabilities Kastner (1999); Miller (1996); Cohen (1995).

In the second case, the observable $\mathcal{A}$ is not actually measured, but
rather a probability distribution over its outcomes is assigned
counterfactually depending on the PPS states Aharonov and Vaidman (1991). This
case is known as counterfactual assignment of probabilities. It has been
argued by Aharonov and collaborators that simultaneous counterfactual
probability assignments, in accordance with Eq. (2), to any number of
arbitrary observables is possible. This in general produces the various PPS
paradoxes, as we will define in next subsection.

For the remainder of this paper we consider only counterfactual measurement
setting of the observable $\mathcal{A}$. This rule (Eq. (2)) is eponymously
known as the ABL rule and is the same for both the aforementioned cases.
However, the interpretation for both the cases is entirely different and leads
to some interesting results, especially when linked to counterfactual
assignments of projectors in the KCBS scenario.

###  II.2 Paradoxical and non-paradoxical PPS scenarios

In this subsection we provide a classification of PPS scenarios into
paradoxical and non-paradoxical. We then proceed to show how the KCBS scenario
can be modified to fit within the paradigm of TSVF and whether the latter can
help in predicting the correct statistics of the former. We then provide a
general algorithm to check for contextual advantages for other contextuality
scenarios.

######  Definition 1 (Counterfactual PPS scenario).

A counterfactual PPS scenario is specified by
$(\langle\phi||\psi\rangle,\mathcal{M})$ where $\langle\phi||\psi\rangle$ is a
two-state describing the PPS ensemble and a projective valued measure (PVM),
$\mathcal{M}=\\{\Pi_{i}\\}\,\,(i=1,2\cdots n)$ is the counterfactual
measurement setting at an intermediate time. The corresponding
$\\{\zeta_{i}\\}$ given by Eq. (2) are then the counterfactual probability
assignments for the PVM $\mathcal{M}$.

For certain pre- and post-selections counterfactual probability assignments
can lead to paradoxical situations. The 3-box paradox is a case in point :
consider a particle that is pre-selected in state
$(\ket{A}+\ket{B}+\ket{C})/\sqrt{3}$ and post-selected in the state
$(\ket{A}+\ket{B}-\ket{C})/\sqrt{3}$, where $\ket{A},\ket{B},\ket{C}$
represent the states of the particle being in boxes $A,B$ and $C$
respectively. Now consider two possible counterfactual measurement settings
$\mathcal{A}=\\{\outerproduct{A}{A},\mathds{1}-\outerproduct{A}{A}\\}$ and
$\mathcal{B}=\\{\outerproduct{B}{B},\mathds{1}-\outerproduct{B}{B}\\}$. It is
easy to visualize $\mathcal{A}$ and $\mathcal{B}$ as being the actions of
opening the boxes $A$ and $B$ respectively at an intermediate time in order to
check whether the particle was present there. A counterfactual probability
assignment to both the projectors $\outerproduct{A}{A}$ and
$\outerproduct{B}{B}$ can be made according to ABL formula (2). However, it
can be seen that such an assignment leads to a situation in which the particle
is present in box $A$ with unit probability and box $B$ with unit probability
Kastner (1999).

The exclusivity principle states that the sum of probabilities of mutually
exclusive events cannot be greater than $1$. Therefore, such scenarios in
which two mutually exclusive events are assigned unit probabilities is
paradoxical. This motivates the following definition.

######  Definition 2 (Logical PPS paradox).

A logical PPS paradox consists of at least two counterfactual PPS scenarios
$(\langle\phi||\psi\rangle,\mathcal{M}_{1})$ and
$(\langle\phi||\psi\rangle,\mathcal{M}_{2})$ where
$\mathcal{M}_{i}=\\{\Pi_{i},\mathds{1}-\Pi_{i}\\}$ for $i=1,2$ and
$\tr(\Pi_{1}\Pi_{2})=0$ such that $\zeta_{1}+\zeta_{2}>1$ where $\zeta_{i}$ is
counterfactual probability assigned to $\Pi_{i}$.

The logical PPS paradox is defined for PPS scenarios which violate the As
shown in Ref. Leifer and Spekkens (2005), to every corresponding logical PPS
paradox there exists a proof of BKS theorem. However, the relation between
non-paradoxical PPS scenarios and contextuality is still left unexplored. To
that end we make the following definition to distinguish between the
paradoxical and non-paradoxical sector of PPS scenarios.

######  Definition 3 (Paradoxical and non-paradoxical sector).

The set of all two-states that generate logical PPS paradoxes for given two
counterfactual measurement settings
$\mathcal{M}_{1}=\\{\Pi_{1},\mathds{1}-\Pi_{1}\\}$ and
$\mathcal{M}_{2}=\\{\Pi_{2},\mathds{1}-\Pi_{2}\\}$ such that
$\tr(\Pi_{1}\Pi_{2})=0$ is called the paradoxical sector corresponding to pair
$\\{\mathcal{M}_{1},\mathcal{M}_{2}\\}$. We term the set of all two-states
that are not elements of the above as the non-paradoxical sector corresponding
to the pair $\\{\mathcal{M}_{1},\mathcal{M}_{2}\\}$.

##  III KCBS construction and non-contextuality

We now analyze whether the non-paradoxical sector of PPS scenarios can offer a
proof of contextuality. We first focus on the minimal proof of state dependent
contextuality, namely the KCBS scenario and construct an ontological
description of the same via the TSVF.

Consider a scenario consisting of $5$ tests $e_{i}$, $i\in\\{0,1,2,3,4\\}$. A
test is an experiment which yields some statistics for a given preparation.
These tests are assumed to be cyclically exclusive, i.e.,

$P(e_{i})+P(e_{i\oplus 1})\leq 1,$ (3)

where $i\oplus 1$ is taken modulo $5$. This scenario is eponymously named as
KCBS, in honor of the people who first studied it. The KCBS scenario can be
represented on a graph, whose vertices correspond to tests and two vertices
are connected by an edge if they are exclusive. This scenario is capable of
revealing quantum contextuality if the following inequality is violated,

$\mathcal{K}:=\sum_{i=0}P(e_{i})\leq 2,$ (4)

where the underlying ontic probability distribution, $P(e_{i})$ is assumed to
be non-contextual. This is the well known KCBS inequality.

A valid construction of the KCBS scenario for the quantum case is as follows.
Consider $5$ different PVMs:
$\mathcal{M}_{i}=\\{\Pi_{i},\mathds{1}-\Pi_{i}\\}$, $i\in\\{0,1,2,3,4\\}$ and
tr$(\Pi_{i}\Pi_{i\oplus 1})=0$. Each projector corresponds to a test in the
KCBS scenario and cyclic orthogonality ensures the required exclusivity
conditions given in Eq. (3). The maximum quantum value of the KCBS inequality
(4) for the aforementioned settings and a state $|\psi\rangle$ is

$\text{Max}(\mathcal{K}):=\text{Max}\left(\sum_{i=0}P(\Pi_{i}=1)\right)=\sqrt{5},$
(5)

which is greater than the non-contextual bound. This is an indication of
contextual advantage of quantum probability distributions.

It is to be noted that any valid construction of the KCBS scenario in any
formalism must necessarily ensure the exclusivity conditions (3).

Figure 2: The KCBS scenario with $5$ projectors. Projectors connected by an
edge are orthogonal.

##  IV ABL rule and KCBS inequality

The foremost requirement to check whether the non-paradoxical sector of ABL
formalism offers any contextual advantage is to setup the KCBS scenario with
the proper exclusivity conditions given in Eq. (3) by assigning a probability
distribution $\zeta_{i}$ to the projectors under a PPS scenario. We choose the
PPS as $|\psi\rangle$ and $|\phi\rangle$ respectively to assign a
counterfactual probability distribution to the projector $\Pi_{i}$ according
to the ABL rule as

$\zeta_{i}=\frac{|\langle\phi|\Pi_{i}|\psi\rangle|^{2}}{|\langle\phi|\Pi_{i}|\psi\rangle|^{2}+|\langle\phi|(\mathds{1}-\Pi_{i})|\psi\rangle|^{2}},$
(6)

where we the measurement setting is of the form
$\\{\Pi_{i},\mathds{1}-\Pi_{i}\\}$.

By careful selection of a PPS, such counterfactual assignments can lead to a
logical paradox in which $\Pi_{i}$ and $\Pi_{i\oplus 1}$ are assigned
probabilities leading to $\zeta_{i}+\zeta_{i\oplus 1}>1$. This is a direct
violation of the exclusivity conditions (3). Furthermore, in order to analyse
the non-paradoxical sector of the KCBS scenario, it is required that
$\zeta_{i}+\zeta_{i\oplus 1}\leq 1$ for all two-states $\bra{\phi}\ket{\psi}$.

We now propose the following setup to test the KCBS inequality using the ABL
formalism. Without loss of generality we assume a pre-selected state
$|\psi\rangle$ as

$|\psi\rangle=(0,0,1)^{T},$ (7)

and a post-selected state as

$|\phi\rangle=(\cos\theta,\sin\theta\cos\phi,\sin\theta\sin\phi)^{T},$ (8)

where $\theta\in[0,\pi]$ and $\phi\in[0,2\pi]$. The projectors
$\Pi_{i}=|v_{i}\rangle\langle v_{i}|$ are of the form,

$\displaystyle|v_{0}\rangle$
$\displaystyle=\left(1,0,\sqrt{\cos\pi/5}\right)^{T},$ (9)
$\displaystyle|v_{1}\rangle$ $\displaystyle=\left(\cos 4\pi/5,-\sin
4\pi/5,\sqrt{\cos\pi/5}\right)^{T},$ $\displaystyle|v_{2}\rangle$
$\displaystyle=\left(\cos 2\pi/5,\sin 2\pi/5,\sqrt{\cos\pi/5}\right)^{T},$
$\displaystyle|v_{3}\rangle$ $\displaystyle=\left(\cos 2\pi/5,-\sin
2\pi/5,\sqrt{\cos\pi/5}\right)^{T},$ $\displaystyle|v_{4}\rangle$
$\displaystyle=\left(\cos 4\pi/5,\sin 4\pi/5,\sqrt{\cos\pi/5}\right)^{T}.$

We then optimize $|\phi\rangle$ for maximum value of $\mathcal{K}$ with the
exclusivity conditions (3) imposed on $\zeta_{i}$. We evaluate $\mathcal{K}$
using the rule (6) for the measurement $\\{\Pi_{i},\mathds{1}-\Pi_{i}\\}$ to
assign $P(\Pi_{i}=1)=\zeta_{i}$ accordingly.

By imposing the exclusivity conditions we found that no post-selection can
lead to a violation of the KCBS inequality. In Fig 3 we plot the intersection
of the solutions that satisfy the inequalities (3) and (4) for various minimum
values of $\mathcal{K}$ over the entire region of post-selected states.
Incidentally we do not find any set of states for which KCBS inequality is
violated. This provides a clear evidence of the fact that the ABL formalism
does not provide a complete description under the non-paradoxical sector of
PPS scenario.

In order to achieve a violation it is necessary to violate at least a single
exclusivity constraint. If all the constraints are satisfied, the resultant
distribution, even from the ABL retrodiction formula is necessarily non-
contextual.

Therefore, any violation of the KCBS inequality observed via the ABL rule,
must necessarily arise from the paradoxical sector of PPS scenarios. As a
consequence, the maximum violation can even go above the algebraic bound. This
is because, the exclusivity conditions are not properly satisfied.

It is a natural consequence of this work that a valid PPS-KCBS scenario can be
modelled using a non-contextual ontological model.

Figure 3: A region plot corresponding to a set of post-selected states (8)
(shaded blue) for which Eq. (3) is satisfied $\forall i$ with (a)
$\mathcal{K}>1.4$, (b) $\mathcal{K}>1.5$, (c) $\mathcal{K}>1.6$ and (d)
$\mathcal{K}>1.7$. No set of states were found for $\mathcal{K}>2.0$.

Our analysis can be extended to arbitrary contextuality scenarios too Araújo
_et al._ (2013). Following our analysis, it is required to firstly identify
the proper exclusivity conditions according to Eq. (3). These conditions
demarcate the set of non-paradoxical PPS scenarios from the paradoxical ones
according to definition $3$. Within this set of counterfactual PPS scenario
one can then vary the pre-selected and post-selected states for a given set of
PVMs (which define the corresponding contextuality scenario) to make
counterfactual probability assignments. A violation of the corresponding
contextuality inequality would then indicate a contextual advantage of the
TSVF.

The KCBS scenario requires a set of $5$ PVMs, and imposes $5$ exclusivity
constraints on the ABL rule. Any $n$-cycle scenario Araújo  _et al._ (2013)
would then consequently impose $n$ such exclusivity constraints. This in turn
reduces the non-paradoxical sector of PPS scenarios possible for this
contextual inequality. While a solution for all $n$-cycle scenarios with $n$
exclusivity constraints applied to TSVF is not possible, we conjecture with
good confidence that no $n$-cycle contextual inequality can exhibit a
violation under the TSVF paradigm.

##  V Conclusion

In this work we have focused on unearthing quantum contextuality as identified
by the violation of KCBS inequality in the PPS scenarios where ABL rule
provides a way to assign counterfactual probabilities to measurement outcomes.
We provide a classification of PPS scenarios into paradoxical and non-
paradoxical sectors. We then show that the non-paradoxical sector of the ABL
rule to evaluate probability distribution over the outcomes of an observable
in a PPS scenario does not provide a contextual violation of the KCBS
inequality. Since, the ABL rule is applied in a counterfactual manner, the ABL
rule acts as an ontic model of the KCBS inequality. By imposing proper
exclusivity conditions on the ABL probabilities, we find that it is not able
to reproduce the statistics that are observed in nature.

It should be noted that the KCBS scenario, and the pentagram graph in general,
underly many other contextual scenarios as well Badzia̧g  _et al._ (2011).
Apart from KCBS, our result also implies a non-contextual behavior of these
scenarios under the paradigm of TSVF.

Our results show that the ABL rule is essentially non-contextual contrary to
recent studies Leifer and Spekkens (2005); Pusey (2014); Kunjwal  _et al._
(2019). Most of the recent studies deal with probability assignments which are
not properly conditioned and lead to scenarios where the sum of probabilities
of exclusive events can be greater than $1$ leading to false signatures of
contextuality. Any such signature arises from definition $2$ and therefore
violates the principle of exclusivity which is at the heart of operational
theories Cabello (2013); Amaral  _et al._ (2014); Chiribella  _et al._ (2020).
Therefore, in order to observe a violation, the principle of exclusivity needs
to be abandoned.

###### Acknowledgements.

JS acknowledges support by Universidad de Sevilla Project Qdisc (Project No.
US-15097), with FEDER funds, MCINN/AEI Projet No. PID2020-113738GB-I00, and
QuantERA grant SECRET, by MCINN/AEI (Project No. PCI2019-111885-2). A.
acknowledges financial support from DST/ICPS/QuST/Theme-1/2019/Q-68.

## References

  * Aharonov  _et al._ (1964) Y. Aharonov, P. G. Bergmann, and J. L. Lebowitz, Phys. Rev. 134, B1410 (1964).
  * Aharonov  _et al._ (1988) Y. Aharonov, D. Z. Albert, and L. Vaidman, Phys. Rev. Lett. 60, 1351 (1988).
  * Aharonov and Vaidman (1990) Y. Aharonov and L. Vaidman, Phys. Rev. A 41, 11 (1990).
  * Aharonov and Vaidman (1991) Y. Aharonov and L. Vaidman, Journal of Physics A: Mathematical and General 24, 2315 (1991).
  * Ritchie  _et al._ (1991) N. W. M. Ritchie, J. G. Story, and R. G. Hulet, Phys. Rev. Lett. 66, 1107 (1991).
  * Pryde  _et al._ (2005) G. J. Pryde, J. L. O’Brien, A. G. White, T. C. Ralph, and H. M. Wiseman, Phys. Rev. Lett. 94, 220405 (2005).
  * Steinberg (1995) A. M. Steinberg, Phys. Rev. Lett. 74, 2405 (1995).
  * Kocsis  _et al._ (2011) S. Kocsis, B. Braverman, S. Ravets, M. J. Stevens, R. P. Mirin, L. K. Shalm, and A. M. Steinberg, Science 332, 1170 (2011).
  * Mahler  _et al._ (2016) D. H. Mahler, L. Rozema, K. Fisher, L. Vermeyden, K. J. Resch, H. M. Wiseman, and A. Steinberg, Science Advances 2 (2016), 10.1126/sciadv.1501466.
  * Aharonov  _et al._ (2002) Y. Aharonov, A. Botero, S. Popescu, B. Reznik, and J. Tollaksen, Physics Letters A 301, 130 (2002).
  * Lundeen and Steinberg (2009) J. S. Lundeen and A. M. Steinberg, Phys. Rev. Lett. 102, 020404 (2009).
  * Williams and Jordan (2008) N. S. Williams and A. N. Jordan, Phys. Rev. Lett. 100, 026804 (2008).
  * Lundeen  _et al._ (2011) J. S. Lundeen, B. Sutherland, A. Patel, C. Stewart, and C. Bamber, Nature 474, 188 EP (2011).
  * Dressel  _et al._ (2014) J. Dressel, M. Malik, F. M. Miatto, A. N. Jordan, and R. W. Boyd, Rev. Mod. Phys. 86, 307 (2014).
  * Resch  _et al._ (2004) K. Resch, J. Lundeen, and A. Steinberg, Physics Letters A 324, 125 (2004).
  * Vaidman (2013) L. Vaidman, Phys. Rev. A 87, 052104 (2013).
  * Danan  _et al._ (2013) A. Danan, D. Farfurnik, S. Bar-Ad, and L. Vaidman, Phys. Rev. Lett. 111, 240402 (2013).
  * Aharonov  _et al._ (2017) Y. Aharonov, E. Cohen, A. Landau, and A. C. Elitzur, Scientific Reports 7, 531 (2017).
  * Aharonov  _et al._ (2013) Y. Aharonov, S. Popescu, D. Rohrlich, and P. Skrzypczyk, New Journal of Physics 15, 113015 (2013).
  * Denkmayr  _et al._ (2014) T. Denkmayr, H. Geppert, S. Sponar, H. Lemmel, A. Matzkin, J. Tollaksen, and Y. Hasegawa, Nature Communications 5, 4492 EP (2014), article.
  * Bancal (2013) J.-D. Bancal, Nature Physics 10, 11 EP (2013).
  * Das and Pati (2020) D. Das and A. K. Pati, New Journal of Physics 22, 063032 (2020).
  * Liu  _et al._ (2020) Z.-H. Liu, W.-W. Pan, X.-Y. Xu, M. Yang, J. Zhou, Z.-Y. Luo, K. Sun, J.-L. Chen, J.-S. Xu, C.-F. Li, and G.-C. Guo, Nature Communications 11, 3006 (2020).
  * Bhati and Arvind (2022) R. S. Bhati and Arvind, Physics Letters A 429, 127955 (2022).
  * Albert  _et al._ (1985) D. Z. Albert, Y. Aharonov, and S. D’Amato, Phys. Rev. Lett. 54, 5 (1985).
  * Bub and Brown (1986) J. Bub and H. Brown, Phys. Rev. Lett. 56, 2337 (1986).
  * Simon Kochen (1968) E. S. Simon Kochen, Indiana Univ. Math. J. 17, 59 (1968).
  * Mermin (1993) N. D. Mermin, Rev. Mod. Phys. 65, 803 (1993).
  * Cabello  _et al._ (2014) A. Cabello, S. Severini, and A. Winter, Phys. Rev. Lett. 112, 040401 (2014).
  * Mermin (1995) N. D. Mermin, Phys. Rev. Lett. 74, 831 (1995).
  * Leifer and Spekkens (2005) M. S. Leifer and R. W. Spekkens, Phys. Rev. Lett. 95, 200405 (2005).
  * Tollaksen (2007) J. Tollaksen, Journal of Physics A: Mathematical and Theoretical 40, 9033 (2007).
  * Pusey (2014) M. F. Pusey, Phys. Rev. Lett. 113, 200401 (2014).
  * Kunjwal  _et al._ (2019) R. Kunjwal, M. Lostaglio, and M. F. Pusey, Phys. Rev. A 100, 042116 (2019).
  * Klyachko  _et al._ (2008) A. A. Klyachko, M. A. Can, S. Binicioğlu, and A. S. Shumovsky, Phys. Rev. Lett. 101, 020403 (2008).
  * Cabello (2013) A. Cabello, Phys. Rev. Lett. 110, 060402 (2013).
  * Amaral  _et al._ (2014) B. Amaral, M. T. Cunha, and A. Cabello, Phys. Rev. A 89, 030101 (2014).
  * Chiribella  _et al._ (2020) G. Chiribella, A. Cabello, M. Kleinmann, and M. P. Müller, Phys. Rev. Research 2, 042001 (2020).
  * Kastner (1999) R. E. Kastner, Foundations of Physics 29, 851 (1999).
  * Miller (1996) D. Miller, Physics Letters A 222, 31 (1996).
  * Cohen (1995) O. Cohen, Phys. Rev. A 51, 4373 (1995).
  * Araújo  _et al._ (2013) M. Araújo, M. T. Quintino, C. Budroni, M. T. Cunha, and A. Cabello, Phys. Rev. A 88, 022118 (2013).
  * Badzia̧g  _et al._ (2011) P. Badziag, I. Bengtsson, A. Cabello, H. Granström, and J.-Å. Larsson, Foundations of Physics 41, 414 (2011).