# Optimality conditions and constraint qualifications for
cardinality constrained optimization problems

Zhuoyu Xiao and Jane J. Ye Department of Industrial and Manufacturing
Engineering, Pennsylvania State University, State College, PA, USA 168022.
E-mail<EMAIL_ADDRESS>author, Department of Mathematics and
Statistics, University of Victoria, Victoria, B.C., Canada V8W 2Y2. E-mail:
<EMAIL_ADDRESS>The research of this author was partially supported by NSERC.

Abstract. The cardinality constrained optimization problem (CCOP) is an
optimization problem where the maximum number of nonzero components of any
feasible point is bounded. In this paper, we consider CCOP as a mathematical
program with disjunctive subspaces constraints (MPDSC). Since a subspace is a
special case of a convex polyhedral set, MPDSC is a special case of the
mathematical program with disjunctive constraints (MPDC). Using the special
structure of subspaces, we are able to obtain more precise formulas for the
tangent and (directional) normal cones for the disjunctive set of subspaces.
We then obtain first and second order optimality conditions by using the
corresponding results from MPDC. Thanks to the special structure of the
subspace, we are able to obtain some results for MPDSC that do not hold in
general for MPDC. In particular we show that the relaxed constant positive
linear dependence (RCPLD) is a sufficient condition for the metric
subregularity/error bound property for MPDSC which is not true for MPDC in
general. Finally we show that under all constraint qualifications presented in
this paper, certain exact penalization holds for CCOP.

Key Words. cardinality constrained optimization problems, disjunctive
subspaces constraints, necessary optimality conditions, constraint
qualifications, metric subregularity, error bounds property, RCPLD.

2020 Mathematics Subject Classification. 49J52, 49J53, 90C26, 90C46.

##  1 Introduction

In this paper, we consider the cardinality constrained optimization problem
(CCOP) in the following form:

$\displaystyle\min_{x}$ $\displaystyle f(x)$ (1) s.t. $\displaystyle g(x)\leq
0,\>h(x)=0,\quad\|x\|_{0}\leq s,$

where $f:\mathbb{R}^{n}\to\mathbb{R}$, $g:\mathbb{R}^{n}\to\mathbb{R}^{m}$ and
$h:\mathbb{R}^{n}\to\mathbb{R}^{p}$ and $\|x\|_{0}$ is the number of nonzero
elements in the vector $x$ (also called $l_{0}$-norm). We assume $s<n$,
otherwise the cardinality constraint would be superfluous. Unless otherwise
mentioned, we assume that all functions are smooth. Two simple examples about
the cardinality constraint are given in Figure 1.

Figure 1: Feasible set for the cardinality constraints: (i) $\|x\|_{0}\leq 1$
in $\mathbb{R}^{2}$; (ii) $\|x\|_{0}\leq 2$ in $\mathbb{R}^{3}$.

CCOPs have many applications such as image processing, portfolio optimization,
machine learning, and other related problems; see e.g. [38] and the references
within for a survey of recent developments.

CCOPs are intrinsically nonconvex since even when all functions involved are
convex, the feasible region is still nonconvex. Moreover problem (1) can not
be treated as a nonlinear program since $\|x\|_{0}$ is a discontinuous
function. For the case where $X:=\\{x\in\mathbb{R}^{n}\>|\>g(x)\leq
0,\>h(x)=0\\}=\mathbb{R}^{n}$, Beck and Eldar [6] introduced three concepts of
stationarity conditions for CCOP, and proposed some efficient numerical
algorithms aimed at finding these stationary points. The results are extended
to include a so-called symmetric set constraint in [7, 28]. Pan et al. [35]
studied CCOP where $X=\mathbb{R}^{n}$ by reformulating the problem as
$\min_{x}f(x)\quad\mbox{s.t. }x\in S,$ where
$S:=\\{x\in\mathbb{R}^{n}|\|x\|_{0}\leq s\\}$. They then give the expressions
for the Bouligrand/Clarke tangent cone and the regular/Clarke normal cone to
$S$ and present corresponding first and second order optimality conditions. In
[5], the formula for the limiting normal cone to $S$ is given. Recently Pan et
al. [36], formulated CCOP as the following mathematical program:

$\displaystyle\min_{x}$ $\displaystyle f(x)$ (2) s.t. $\displaystyle g(x)\leq
0,h(x)=0,x\in
S:=\bigcup\limits_{\mathcal{I}\in\mathcal{I}_{s}}\mathbb{R}_{\mathcal{I}},$

where
$\mathcal{I}_{s}:=\\{\mathcal{I}\subseteq\\{1,2,\dots,n\\}\>|\>|\mathcal{I}|=s\\}$
represents all subsets of $\\{1,2,\dots,n\\}$ with cardinality equal to $s$
and $\mathbb{R}_{\mathcal{I}}:=\textrm{span}\\{e_{i}\>|\>i\in\mathcal{I}\\}$.
By using some tools from variational analysis, they obtained some first and
second order optimality conditions and studied constraint qualifications for
the necessary optimality conditions. Note that each $\mathbb{R}_{\mathcal{I}}$
is a subspace and hence problem (2) is a special case of the mathematical
program with disjunctive constraints (MPDC). Recently Burdakov et al. [16]
introduced a relaxed complementarity-type reformulation of CCOP and proposed
some numerical algorithms. Based on this continuous reformulation, some
constraint qualifications and stationarity conditions for CCOP were introduced
in Červinka et al. [17]. Some second-order necessary and sufficient optimality
conditions for CCOP based on such reformulation are also introduced in Bucher
and Kanzow [15]. The relaxed complementarity-type reformulation is more
computationally friendly than its original formulation. But due to the extra
variable introduced in the reformulation, the relaxed complementarity-type
reformulation are not equivalent to the original problem in the sense of local
optimality [16].

In this paper, we study optimality conditions and constraint qualifications
for problem (1) by its equivalent reformulation (2). Recently there are many
developments in the optimality conditions and constraint qualifications for
MPDC [21, 8, 4, 39], see [27] and the references within for a survey.

The main contributions of this paper are summarized as follows:

  * (i)

We study the mathematical programs with disjunctive subspaces constraints
(MPDSC) which include CCOP as well as the mathematical programs with switching
constraints (MPSC) [31] as special cases. We explore the structure of the
disjunctive set of subspaces to obtain formulas for various tangent and normal
cones which do not hold if one of the subspaces is only a convex polyhedral
set. Unlike in smooth systems with equality and inequality constraints, RCPLD
may not imply the error bound property for the disjunctive system. Recently Xu
and Ye [39, Section 5.3] proposed RCPLD and the piecewise RCPLD for MPDCs, and
showed that the piecewise RCPLD is a sufficient condition for the error bound
property. Inspired by the fact that RCPLD coincides with the piecewise RCPLD
for MPSC [39, Section 5.3], we show that this result actually holds for any
system that can be formulated as a constraint system of MPDSC. Based on such
result, we prove that for MPDSC, RCPLD is a sufficient condition for error
bounds.

  * (ii)

Applying the results from MPDSC, we obtain first and second order optimality
conditions for CCOP and some new sufficient conditions for the error bound for
CCOP. The first order necessary and the second order necessary and sufficient
optimality conditions we present are sharper and hold under weaker constraint
qualifications than the corresponding results in Pan et al. [36]. Moreover
under all constraint qualifications presented in this paper, the exact penalty
holds for CCOP. That is, if $x^{*}$ is a local minimizer of CCOP and one of
the constraint qualifications discussed in this paper holds, then there exists
a constant $\mu\geq 0$ such that $x^{*}$ is also a local minimizer of the
exact penalty problem:

$\displaystyle\min_{x}$ $\displaystyle
f(x)+\mu\Bigl{(}\sum\limits_{i=1}^{m}\max\\{g_{i}(x),0\\}+\sum\limits_{i=1}^{p}|h_{i}(x)|\Bigr{)}$
(3) s.t. $\displaystyle\|x\|_{0}\leq s.$

The remainder of this paper is organized as follows. In Section 2, we derive
formulas for various tangent and normal cones that will be used in this paper.
In Section 3, we study optimality conditions and constraint qualifications for
MPDSC. We also show that RCPLD is a sufficient condition for error bounds for
MPDSC, an important result which does not hold for MPDC in general. In Section
4, we first reformulate CCOP as MPDSC, then apply the results in Section 3 to
CCOP.

##  2 Notation and preliminary results

The notations we adopt are standard. Given a point $x\in\mathbb{R}^{n}$,
$\mathbb{B}_{\varepsilon}(x)$ stands for the open ball of radius $\varepsilon$
centered at $x$, while the symbol $\mathbb{B}$ simply stands for the open unit
ball centered at the origin. We denote by $\nabla f(x)$ the gradient of a
continuously differentiable function $f:\mathbb{R}^{n}\to\mathbb{R}$ at $x$
and by $d_{\Omega}(x)$ the distance between the point $x$ and the set
$\Omega$. Unless otherwise stated, $\|\cdot\|$ denotes an arbitrary norm in
$\mathbb{R}^{n}$ and the notation $\langle\cdot,\cdot\rangle$ denotes the
inner product. For a given nonempty set $A\subseteq\mathbb{R}^{n}$, we use
notations cl$A$, cone$A$, and span$A$ to represent the closure of $A$, the
conic hull of $A$, and the span of $A$, that is, the smallest subspace of
$\mathbb{R}^{n}$ comprising $A$. For any given set $B$ with finite elements,
we denote the number of elements in $B$ by $|B|$. Given finite index sets
$I,J$, a pair $(\\{v_{i}\\}_{i\in I},\\{u_{i}\\}_{i\in J})$ of family of
vectors $\\{v_{i}\\}_{i\in I},\\{u_{i}\\}_{i\in J}$ is said to be positive
linearly dependent if there exist scalars $\\{\alpha_{i}\\}_{i\in I}$ and
$\\{\beta_{i}\\}_{i\in J}$ with $\alpha_{i}\geq 0$ for any $i\in I$, not all
equal to zero such that $\sum_{i\in I}\alpha_{i}v_{i}+\sum_{i\in
J}\beta_{i}u_{i}=0$.

The main purpose of this section is to derive some formulas for various
tangent cones and normal cones to the disjunctive set of subspaces
$S=\bigcup_{r=1}^{R}S_{r}$ where each $S_{r}$ is a subspace of
$\mathbb{R}^{n}$. These formulas will be needed in the next sections of the
paper.

###  2.1 Formulas for tangent and normal cones

Given a closed set $\Omega\subseteq\mathbb{R}^{n}$ and $x\in\Omega$, we denote
the Bouligand tangent cone, the Fréchet/regular normal cone and the
Mordukhovich/limiting normal cone to $\Omega$ at $x$ by $T_{\Omega}(x)$,
$\hat{N}_{\Omega}(x)$ and $N_{\Omega}(x)$, respectively. When $\Omega$ is
convex, we denote by ${N}_{\Omega}(x)$ the normal cone in the sense of convex
analysis. We refer the reader to the standard reference of variational
analysis in [14, 18, 33, 34, 37] for their precise definitions.

######  Proposition 2.1.

Let $x^{\ast}\in S$. Then

$\displaystyle T_{S}(x^{\ast})$ $\displaystyle=\bigcup\limits_{r\in
I(x^{\ast})}T_{S_{r}}(x^{\ast})=\bigcup\limits_{r\in I(x^{\ast})}S_{r},$ (4)
$\displaystyle\hat{N}_{S}(x^{\ast})$ $\displaystyle=\bigcap\limits_{r\in
I(x^{\ast})}{N}_{S_{r}}(x^{\ast})=\bigcap\limits_{r\in
I(x^{\ast})}S_{r}^{\perp},$ (5) $\displaystyle N_{S}(x^{\ast})$
$\displaystyle=\bigcup\limits_{r\in
I(x^{\ast})}N_{S_{r}}(x^{\ast})=\bigcup\limits_{r\in
I(x^{\ast})}S_{r}^{\perp},$ (6)

respectively, where $I(x^{\ast}):=\\{r\in\\{1,\dots,R\\}\>|\>x^{\ast}\in
S_{r}\\}$ is the active index set for $S$ at $x^{\ast}$.

###### Proof.

The first equation in (4) is from [1, Table 4.1] and the second equation in
(4) is obvious since each $S_{r}$ is a subspace and hence
$T_{S_{r}}(x^{*})=S_{r}$ provided that $x^{*}\in S_{r}$. The proof of (5)
follows from the one for the tangent cone by polarization.

Now it remains to prove that (6) holds. The second equation in (6) is obvious
from the fact that each $S_{r}$ is a subspace for $r=1,\dots,R$. We only need
to prove the first equation. The inclusion
$N_{S}(x^{\ast})\subseteq\bigcup\limits_{r\in I(x^{\ast})}N_{S_{r}}(x^{\ast})$
follows from [30, Lemma 2.2]. Now we prove the converse inclusion. First from
(13) and (14) in Adam et al. [3], there exists $\delta>0$ such that

$N_{S}(x^{\ast})=\bigcup\limits_{x\in\mathbb{B}_{\delta}(x^{\ast})}\hat{N}_{S}(x).$
(7)

For each $r\in I(x^{\ast})$, since there are only finitely many subspaces we
can pick a unit vector $u_{r}$ such that $u_{r}\in S_{r}$ but $u_{r}\notin
S_{j}$ for other $j\neq r$. Consider the point $x=x^{\ast}+tu_{r}$ such that
$t<\delta$. Then $x\in\mathbb{B}_{\delta}(x^{\ast})$ and $x\in S_{r}$ but
$x\notin S_{j}$ for other $j\neq r$. In this way, for every $i\in I(x^{\ast})$
we have

${N}_{S_{r}}(x^{\ast})=S_{r}^{\perp}={N}_{S_{r}}(x)=\hat{N}_{S}(x)\subseteq\bigcup\limits_{x\in\mathbb{B}_{\delta}(x^{\ast})}\hat{N}_{S}(x),$
(8)

where the third equality follows from the first equation in (5) taking into
account that $I(x)=\\{r\\}$. Combing (7) and (8), we obtain the inclusion
$\bigcup\limits_{r\in I(x^{\ast})}N_{S_{r}}(x^{\ast})\subseteq
N_{S}(x^{\ast})$ as desired, which completes the proof. ∎

In the following proposition, we will compute the regular normal cone to
tangent cone $T_{S}(x^{\ast})$ at a tangent direction $d$.

######  Proposition 2.2.

_(The regular normal cone to the tangent cone)_ Let $x^{\ast}\in S$ and $d\in
T_{S}(x^{\ast})$. Then the regular normal cone to $T_{S}(x^{\ast})$ at $d$ is
calculated as

$\hat{N}_{T_{S}(x^{\ast})}(d)=\bigcap\limits_{r\in I(x^{\ast})\cap
I(d)}S_{r}^{\perp}.$ (9)

###### Proof.

We denote $S(x^{\ast}):=\bigcup\limits_{r\in I(x^{\ast})}S_{r}$. Combing (4)
with (5), we have

$\hat{N}_{T_{S}(x^{\ast})}(d)=\hat{N}_{S(x^{\ast})}(d)=\bigcap\limits_{r\in
I(x^{\ast})\cap I(d)}{N}_{S_{r}}(d)=\bigcap\limits_{r\in I(x^{\ast})\cap
I(d)}S_{r}^{\perp},$

which completes the proof. ∎

Recently a directional version of the limiting normal cone has been introduced
by Ginchev and Mordukhovich [23].

######  Definition 2.1.

_(Directional normal cones)[23, Definition 2.3]_ Given a closed set
$\Omega\subseteq\mathbb{R}^{n}$, $x^{\ast}\in\Omega$ and $d\in\mathbb{R}^{n}$.
The limiting normal cone to $\Omega$ at $x^{\ast}$ in direction $d$ is defined
by

$N_{\Omega}(x^{\ast};d):=\left\\{v\in\mathbb{R}^{n}\>|\>\exists
t_{k}\downarrow 0,d^{k}\to d,v^{k}\to
v,\>\emph{s.t.}\>v^{k}\in\hat{N}_{\Omega}(x^{k}+t_{k}d^{k})\right\\}.$

From the definition we have $N_{\Omega}(x^{\ast};0)=N_{\Omega}(x^{\ast})$,
$N_{\Omega}(x^{\ast};d)\subseteq N_{\Omega}(x^{\ast})$ and
$N_{\Omega}(x^{\ast};d)=\emptyset$ if $d\notin T_{\Omega}(x^{\ast})$.

If $C$ is a disjunctive set which is the union of finitely many convex
polyhedral sets, by [21, Lemma 2.1] we have the inclusion

$N_{C}(x^{\ast};d)\subseteq\\{v\in N_{C}(x^{\ast})\>|\>v^{T}d=0\\}.$ (10)

In the following proposition, we will show that the above inclusion holds as
an equality if $C=S$, the union of finitely many subspaces.

######  Proposition 2.3.

_(Directional normal cone)_ Let $x^{\ast}\in S$ and $d\in T_{S}(x^{\ast})$.
Then the directional normal cone to $S$ at $x^{\ast}$ in direction $d$ is
calculated as

$N_{S}(x^{\ast};d)=\\{v\in
N_{S}(x^{\ast})\>|\>v^{T}d=0\\}=\bigcup\limits_{r\in I(x^{\ast})\cap
I(d)}S_{r}^{\perp}.$ (11)

###### Proof.

From (6), we have

$\\{v\in N_{S}(x^{\ast})\>|\>v^{T}d=0\\}=\bigcup\limits_{r\in
I(x^{\ast})}\\{v\in N_{S_{r}}(x^{\ast})\>|\>v^{T}d=0\\}.$ (12)

By [21, Lemma 2.1], since $S_{r}$ is convex,

$\left\\{v\in{N}_{S_{r}}(x^{\ast})\>|\>v^{T}d=0\right\\}={N}_{T_{S_{r}}(x^{\ast})}(d)\qquad\forall{r\in
I(x^{\ast})}.$ (13)

Further, since $T_{S_{r}}(x^{\ast})=S_{r}$ for each $r\in I(x^{\ast})$, we
have

$\bigcup\limits_{r\in
I(x^{\ast})}{N}_{T_{S_{r}}(x^{\ast})}(d)=\bigcup\limits_{r\in
I(x^{\ast})}{N}_{S_{r}}(d)=\bigcup\limits_{r\in I(x^{\ast})\cap
I(d)}S_{r}^{\perp}.$ (14)

Combing (10), (12), (13) and (14), we establish the inclusion

$N_{S}(x^{\ast};d)\subseteq\\{v\in
N_{S}(x^{\ast})\>|\>v^{T}d=0\\}=\bigcup\limits_{r\in I(x^{\ast})\cap
I(d)}S_{r}^{\perp}.$

Reversely, for any $v\in\bigcup\limits_{r\in I(x^{\ast})\cap
I(d)}S_{r}^{\perp}$, there exists $r^{\prime}\in I(x^{\ast})\cap I(d)$ such
that $v\in S_{r^{\prime}}^{\perp}$. Since there are only finitely many
subspaces, we can find a unit vector $u^{\prime}$ such that $u^{\prime}\in
S_{r^{\prime}}$ but $u^{\prime}\notin S_{j}$ for other $j\neq r^{\prime}$. We
define the sequences $\\{d^{k}\\}$ as $d^{k}:=d+\frac{1}{k}u^{\prime}.$ Then
$d^{k}\to d$ as $k\to\infty$. Since $r^{\prime}\in I(x^{\ast})\cap I(d)$ we
have $x^{\ast}\in S_{r^{\prime}}$ and $d\in S_{r^{\prime}}$, which implies
that $d^{k}\in S_{r^{\prime}}$ but $d^{k}\notin S_{j}$ for other $j\neq
r^{\prime}$. For any sequence $\\{t_{k}\\}$ such that $t_{k}\to 0^{+}$ as
$k\to\infty$, it follows that $x^{\ast}+t_{k}d^{k}\in S_{r^{\prime}}$ but
$d^{k}\notin S_{j}$ for other $j\neq r^{\prime}$. Therefore, we have

$v\in
S_{r^{\prime}}^{\perp}={N}_{S_{r^{\prime}}}(x^{\ast}+t_{k}d^{k})=\hat{N}_{S}(x^{\ast}+t_{k}d^{k}),$

where the last equation is from (5). From the definition of the directional
normal cone in Definition 2.1, we have $v\in N_{S}(x^{\ast};d),$ which implies
$\bigcup\limits_{r\in I(x^{\ast})\cap I(d)}S_{r}^{\perp}\subseteq
N_{S}(x^{\ast};d)$ as desired. ∎

###  2.2 The generator sets for disjunctive set of subspaces

Let $A$ be a set with finitely many linearly independent vectors and $D$ be a
subspace. We say $A$ is the generator of $D$ if
$D=\mathcal{G}(A):=\emph{span}(A).$

Now we describe the regular normal cone to the disjunctive set of subspaces by
its generator set. Without loss of generality, we assume that each $S_{r}$ is
represented by

$S_{r}:=\\{x\in\mathbb{R}^{n}\>|\>\langle
a^{r}_{j},x\rangle=0,j\in\mathcal{E}_{r}\\},$ (15)

where $\mathcal{E}_{r}$ is a finite index set and vectors
$\\{a_{j}^{r}\\}_{j\in\mathcal{E}_{r}}$ are linearly independent. For
$x^{\ast}\in S_{r}$, let

$A_{S_{r}}:=\\{a^{r}_{j}\>|\>j\in\mathcal{E}_{r}\\}$

denote the generator of $S_{r}$. Then
$N_{S_{r}}(x^{\ast})=\mathcal{G}(A_{S_{r}}).$

By (5), the regular normal cone to set $S$ at $x^{\ast}\in S$ is the
intersection of finitely many subspaces, hence it is still a subspace. So we
may assume that $\hat{N}_{S}(x^{\ast})$ is generated by a set of linearly
independent vectors denoted by $\hat{A}_{S}(x^{\ast})$. That is, we have

$\hat{N}_{S}(x^{\ast})=\mathcal{G}(\hat{A}_{S}(x^{\ast})).$ (16)

We call $\hat{A}_{S}(x^{\ast})$ satisfying (16) the generator set of the
regular normal cone to $S$ at $x^{\ast}$.

By (7) and (16) we have that for some $\delta>0$,

$N_{S}(x^{\ast})=\bigcup\limits_{x\in\mathbb{B}_{\delta}(x^{\ast})}\hat{N}_{S}(x)=\bigcup\limits_{x\in\mathbb{B}_{\delta}(x^{\ast})}\mathcal{G}(\hat{A}_{S}(x)).$
(17)

We also define the set

$A_{S}(x^{\ast}):=\bigcup\limits_{x\in\mathbb{B}_{\delta}(x^{\ast})}\hat{A}_{S}(x),$
(18)

where $\delta>0$ is the constant satisfying condition (17).

By (6), we know that

$N_{S}(x^{\ast})=\bigcup\limits_{r\in I(x^{\ast})}N_{S_{r}}(x^{\ast}).$ (19)

Therefore an interesting question is, what is the relationship between
generator set $A_{S}(x^{\ast})$ and the union of all $A_{S_{r}}$ where $r\in
I(x^{\ast})$. While it is shown that the inclusion $\subseteq$ holds if each
$S_{r}\subseteq\mathbb{R}^{d}$ with $d=1,2$ is convex polyhedral by Lemma 2.1
in [39], in the following lemma, we show that the equality holds if each
$S_{r}$ is a subspace.

######  Lemma 2.1.

Let $S=\bigcup\limits_{r=1}^{R}S_{r}\subseteq\mathbb{R}^{q}$ where $S_{r}$ is
a subspace. Then for any $x^{\ast}\in S$, we have

$A_{S}(x^{\ast})=\bigcup\limits_{r\in I(x^{\ast})}A_{S_{r}}.$ (20)

###### Proof.

By the definition,
$A_{S}(x^{\ast})=\bigcup\limits_{x\in\mathbb{B}_{\delta}(x^{\ast})}\hat{A}_{S}(x).$
By (5), we have

$\hat{N}_{S}(x)=\bigcap\limits_{r\in I(x)}{N}_{S_{r}}(x)\qquad\forall x\in S,$
(21)

which implies the inclusion

$\hat{A}_{S}(x)\subseteq\bigcup\limits_{r\in I(x)}A_{S_{r}}\qquad\forall x\in
S.$ (22)

For any $v\in
A_{S}(x^{*})=\bigcup\limits_{x\in\mathbb{B}_{\delta}(x^{\ast})}\hat{A}_{S}(x)$,
there exists $x^{\prime}\in\mathbb{B}_{\delta}(x^{\ast})$ such that

$v\in\hat{A}_{S}(x^{\prime})\subseteq\bigcup\limits_{r\in
I(x^{\prime})}A_{S_{r}}\subseteq\bigcup\limits_{r\in I(x^{\ast})}A_{S_{r}}.$
(23)

Indeed, the first inclusion in (23) is from (22) directly. It is not difficult
to see that we can take $\delta>0$ sufficiently small to guarantee
$I(x^{\prime})\subseteq I(x^{\ast}).$ Hence we justify the second inclusion in
(23). Therefore,

$A_{S}(x^{\ast})=\bigcup\limits_{x\in\mathbb{B}_{\delta}(x^{\ast})}\hat{A}_{S}(x)\subseteq\bigcup\limits_{r\in
I(x^{\ast})}A_{S_{r}}.$ (24)

Now we prove the reverse inclusion. Take any $v\in\bigcup\limits_{r\in
I(x^{\ast})}A_{S_{r}}$. Then there exists $r\in I(x^{\ast})$ such that $v\in
A_{S_{r}}.$ Since the set $S$ is the union of finitely many subspaces, we can
pick a unit vector $u_{r}$ such that $u_{r}\in S_{r}$ but $u_{r}\notin S_{j}$
for other $j\neq r$. In this way, for any $0<t<\delta$ we know that the point
$x_{r}:=x^{\ast}+tu_{r}\in\mathbb{B}_{\delta}(x^{\ast})$ satisfies $x_{r}\in
S_{r}$ but $x_{r}\notin S_{j}$ for other $j\neq r$. Therefore, it follows from
(5) that $\hat{N}_{S}(x_{r})={N}_{S_{r}}(x_{r}),$ which implies that
$\hat{A}_{S}(x_{r})=A_{S_{r}}$ and hence we have

$v\in
A_{S_{r}}=\hat{A}_{S}(x_{r})\subseteq\bigcup\limits_{x\in\mathbb{B}_{\delta}(x^{\ast})}\hat{A}_{S}(x).$

Then, we have

$\bigcup\limits_{r\in
I(x^{\ast})}A_{S_{r}}\subseteq\bigcup\limits_{x\in\mathbb{B}_{\delta}(x^{\ast})}\hat{A}_{S}(x)=A_{S}(x^{*}),$
(25)

and hence the proof is complete. ∎

##  3 Optimality conditions and constraint qualifications for MPDSC

In this section we study optimality conditions for MPDSC of the form:

$\displaystyle\min_{x}$ $\displaystyle f(x)$ (26) s.t. $\displaystyle g(x)\leq
0,h(x)=0,\Phi_{i}(x)\in S,\>i=1,\dots,l,$

where $f:\mathbb{R}^{n}\to\mathbb{R}$, $g:\mathbb{R}^{n}\to\mathbb{R}^{m}$,
$h:\mathbb{R}^{n}\to\mathbb{R}^{p}$,
$\Phi_{i}:\mathbb{R}^{n}\to\mathbb{R}^{q}$, and constraint set
$S:=\bigcup_{r=1}^{R}S_{r}\subseteq\mathbb{R}^{q}$ with $S_{r}$ being a
subspace, $r=1,\dots,R$. Unless otherwise mentioned, we assume that all
functions are smooth. We denote the feasible region of problem (26) by
$\mathcal{F}$ and the active set for inequality constraints at $x^{\ast}$ by
$\mathcal{I}_{g}(x^{\ast}):=\\{i\in\\{1,\dots,m\\}\>|\>g_{i}(x^{\ast})=0\\}$.
Problem (26) is more general than what we will need to study CCOP in the form
(2). We could also study CCOP in the more general form as in (26). But for
simplicity in comparison with other results for CCOP, we do not state CCOP in
the more general form.

###  3.1 Optimality conditions for MPDSC

According to the popular terminology in the mathematical program with
equilibrium constraints (MPEC), one normally associate the strong (S-)
stationarity with the regular normal cone and the Mordukhovich (M-)
stationarity with the limiting normal cone (see e.g. [19, Definition 1]).
Hence if $x^{\ast}$ is a feasible point of MPDSC we say that $x^{\ast}$ is
S-/M-stationary if there exists
$\lambda=(\lambda^{g},\lambda^{h},\lambda^{\Phi})$ with $\lambda^{g}_{i}\geq
0,\>\forall i\in\mathcal{I}_{g}(x^{*})$ satisfying

$\nabla
f(x^{\ast})+\sum\limits_{i\in\mathcal{I}_{g}(x^{*})}\lambda^{g}_{i}\nabla
g_{i}(x^{\ast})+\sum\limits_{i=1}^{p}\lambda^{h}_{i}\nabla
h_{i}(x^{\ast})+\sum\limits_{i=1}^{l}\nabla\Phi_{i}(x^{*})^{T}\lambda^{\Phi}_{i}=0,$
(27)

such that

$\displaystyle\lambda^{\Phi}_{i}$ $\displaystyle\in$
$\displaystyle\hat{N}_{S}(\Phi_{i}(x^{\ast}))\equiv\bigcap_{r\in
I(\Phi_{i}(x^{\ast}))}S_{r}^{\perp},\>\forall i=1,\dots,l;$ (28)
$\displaystyle\lambda^{\Phi}_{i}$ $\displaystyle\in$ $\displaystyle
N_{S}(\Phi_{i}(x^{\ast}))\equiv\bigcup_{r\in
I(\Phi_{i}(x^{\ast}))}S_{r}^{\perp},\>\forall i=1,\dots,l,$ (29)

respectively.

Recently the directional versions of S- and M-stationarity for MPDC have been
introduced and studied by Gfrerer [21]. We denote the linearization cone of
MPDSC (26) at $x^{*}$ as

$L_{\mathcal{F}}^{lin}(x^{\ast})=\left\\{d\in\mathbb{R}^{n}\middle|\begin{array}[]{cl}\nabla
g_{i}(x^{\ast})d\leq 0,&i\in\mathcal{I}_{g}(x^{\ast})\\\ \nabla
h_{i}({x}^{\ast})d=0,&i\in\\{1,\ldots,p\\}\\\
\nabla\Phi_{i}(x^{\ast})d\in\bigcup\limits_{r\in
I(\Phi_{i}(x^{\ast}))}S_{r},&i\in\\{1,\ldots,l\\}\end{array}\right\\},$

and the critical cone at $x^{*}$ as

$\mathcal{C}(x^{\ast}):=\left\\{d\in
L^{lin}_{\mathcal{F}}(x^{\ast})\>|\>\nabla f(x^{\ast})d\leq 0\right\\}.$

We also denote the active set for inequality constraints at $x^{\ast}$ in
direction $d$ by

$\mathcal{I}_{g}^{*}(d):=\\{i\in\mathcal{I}_{g}(x^{\ast})\>|\>\nabla
g_{i}(x^{\ast})d=0\\}.$ (30)

According to [27, Propositions 3.8 and 3.6], we may define the directional
S-/M-stationarity as follows.

######  Definition 3.1.

Let $x^{\ast}$ be a feasible point of MPDSC _( 26)_ and
$d\in\mathcal{C}(x^{\ast})$. We say $x^{\ast}$ is S-/M-stationary $(d)$ if
there exists $\lambda=(\lambda^{g},\lambda^{h},\lambda^{\Phi})$ with
$\lambda^{g}_{i}\geq 0,\>\forall i\in\mathcal{I}_{g}^{*}(d)$ satisfying

$\nabla
f(x^{\ast})+\sum\limits_{i\in\mathcal{I}_{g}^{*}(d)}\lambda^{g}_{i}\nabla
g_{i}(x^{\ast})+\sum\limits_{i=1}^{p}\lambda^{h}_{i}\nabla
h_{i}(x^{\ast})+\sum\limits_{i=1}^{l}\nabla\Phi_{i}(x^{*})^{T}\lambda^{\Phi}_{i}=0,$
(31)

such that

$\displaystyle\lambda^{\Phi}_{i}$ $\displaystyle\in$
$\displaystyle\hat{N}_{T_{S}(\Phi_{i}(x^{\ast}))}(\nabla\Phi_{i}(x^{\ast})d)\equiv\bigcap_{r\in
I(\Phi_{i}(x^{\ast}))\cap I(\nabla\Phi_{i}(x^{\ast})d)}S_{r}^{\perp},\>\forall
i=1,\dots,l;$ $\displaystyle\lambda^{\Phi}_{i}$ $\displaystyle\in$
$\displaystyle
N_{S}(\Phi_{i}(x^{\ast});\nabla\Phi_{i}(x^{\ast})d)\equiv\bigcup_{r\in
I(\Phi_{i}(x^{\ast}))\cap I(\nabla\Phi_{i}(x^{\ast})d)}S_{r}^{\perp},\>\forall
i=1,\dots,l,$

respectively. We call the above multiplier $\lambda$ the S-/M- multiplier in
direction d respectively.

In fact, if we take direction $d=0$ in Definition 3.1, then since
$\mathcal{I}_{g}^{*}(0)=\mathcal{I}_{g}(x^{*})$,$I(0)=\\{1,\dots,R\\}$, we
will recover S-/M-stationarity for MPDSC (26).

We now discuss under what conditions a local minimizer are S-stationary $(d)$
or M-stationary $(d)$, respectively. When $d\not=0$, it is easy to see that
the M- stationarity (d) are stronger than the standard M- stationarity while
S- stationarity are stronger than the standard S- stationarity (d).

First we recall the following well-known condition.

######  Definition 3.2 (Metric subregularity constraint qualification/error
bound property for MPDSC).

([20, Definition 2.1]) Given $x^{\ast}\in\mathcal{F}$ and
$d\in\mathbb{R}^{n}$, we say that the metric subregularity constraint
qualification (MSCQ) holds at $x^{\ast}$ in direction $d$ for MPDSC if there
exists $\alpha\geq 0$ and $\rho>0$ such that

$d_{\mathcal{F}}(x)\leq\alpha\Bigl{(}\sum\limits_{i=1}^{m}\max\\{g_{i}(x),0\\}+\sum\limits_{i=1}^{p}|h_{i}(x)|+\sum\limits_{i=1}^{l}d_{S}(\Phi_{i}(x))\Bigr{)},\>\quad\forall
x\in x^{\ast}+V_{\rho,\delta}(d)$

where
$V_{\rho,\delta}(d):=\Big{\\{}z\in\rho\mathbb{B}\>\Big{|}\>\big{\|}\|d\|{z}-\|z\|d\big{\|}\leq\delta\|z\|\|d\|\Big{\\}}$
is the so-called directional neighborhood in direction $d$. If $d=0$ in the
above, we say that the metric subregularity constraint qualification holds at
$x^{*}$.

######  Remark 3.1.

Since the metric subregularity is an abstract condition, in practice, one
needs to use some verifiable sufficient conditions to ensure its validity.
There are some verifiable sufficient conditions in the literature such as the
(directional) quasi-/pseudo normality _[4, Definition 4.1]_ and the
first/second-order sufficient condition for metric subregularity _[20, Theorem
4.3]_.

We now give the first/second-order sufficient condition for metric
subregularity introduced in [20, Theorem 4.3] and the directional MPDC-LICQ
[21, Definition 3.6] to our problem setting.

######  Definition 3.3.

Let $x^{*}\in{\cal F}$.

  * _(a)_

We say that the MPDSC first-order sufficient condition for metric
subregularity (MPDSC-FOSCMS) holds at $x^{*}$ in direction $d\in
L_{\mathcal{F}}^{lin}(x^{\ast})$ if there is no nonzero vector
$(\lambda^{g},\lambda^{h},$
$\lambda^{\Phi})\in\mathbb{R}^{m}\times\mathbb{R}^{n}\times\prod_{i=1}^{l}\mathbb{R}^{q}$
with $\lambda^{g}_{i}\geq 0,\>\forall i\in\mathcal{I}_{g}^{*}(d)$ and
$\lambda^{\Phi}_{i}\in\bigcup\limits_{r\in I(\Phi_{i}(x^{\ast}))\cap
I(\nabla\Phi_{i}(x^{\ast})d)}S_{r}^{\perp}$ satisfying

$\sum\limits_{i\in\mathcal{I}_{g}^{*}(d)}\lambda^{g}_{i}\nabla
g_{i}(x^{\ast})+\sum\limits_{i=1}^{p}\lambda^{h}_{i}\nabla
h_{i}(x^{\ast})+\sum\limits_{i=1}^{l}\nabla\Phi_{i}(x^{*})^{T}\lambda^{\Phi}_{i}=0.$
(32)

  * _(b)_

Suppose that all functions are twice continuously differentiable. We say that
the MPDSC second-order sufficient condition for metric subregularity (MPDSC-
SOSCMS) holds at $x^{*}$ in direction $d\in L_{\mathcal{F}}^{lin}(x^{\ast})$
if there is no nonzero vector $(\lambda^{g},\lambda^{h},$
$\lambda^{\Phi})\in\mathbb{R}^{m}\times\mathbb{R}^{n}\times\prod_{i=1}^{l}\mathbb{R}^{q}$
with $\lambda^{g}_{i}\geq 0,\>\forall i\in\mathcal{I}_{g}^{*}(d)$ and
$\lambda^{\Phi}_{i}\in\bigcup\limits_{r\in I(\Phi_{i}(x^{\ast}))\cap
I(\nabla\Phi_{i}(x^{\ast})d)}S_{r}^{\perp}$ satisfying (32) and the following
second-order condition

$d^{T}\nabla^{2}_{x}\mathcal{L}^{0}(x^{\ast},\lambda^{g},\lambda^{h},\lambda^{\Phi})d\geq
0,$

where

$\mathcal{L}^{0}(x,\lambda^{g},\lambda^{h},\lambda^{\Phi}):=\langle\lambda^{g},g(x)\rangle+\langle\lambda^{h},h(x)\rangle+\langle\lambda^{\Phi},\Phi(x)\rangle.$

  * _(c)_

We say that MPDSC linear independence constraint qualification (MPDSC-LICQ)
holds at $x^{*}$ in direction $d\in L_{\mathcal{F}}^{lin}(x^{\ast})$ if there
is no nonzero vector
$(\lambda^{g},\lambda^{h},\lambda^{\Phi})\in\mathbb{R}^{m}\times\mathbb{R}^{n}\times\prod_{i=1}^{l}\mathbb{R}^{q}$
with $\lambda^{\Phi}_{i}\in\sum\limits_{r\in I(\Phi_{i}(x^{\ast}))\cap
I(\nabla\Phi_{i}(x^{\ast})d)}S_{r}^{\perp}$ such that (32) holds.

When $d=0$, MPDSC-FOSCMS (d) reduces to MPDSC-NNAMCQ, MPDSC-LICQ (d) reduces
to MPDSC-LICQ defined in Definition 3.4 repsectively. It is obvious that
MPDSC-FOSCMS (d) and MPDSC-LICQ (d) with $d\not=0$ are weaker than NNAMCQ and
MPDSC-LICQ, respectively.

We denote the Lagrangian function of problem (26) by

$\mathcal{L}(x,\lambda^{g},\lambda^{h},\lambda^{\Phi}):=f(x)+\langle\lambda^{g},g(x)\rangle+\langle\lambda^{h},h(x)\rangle+\langle\lambda^{\Phi},\Phi(x)\rangle.$

Similarly as in [27, Section 4], the following theorem can be obtained
directly from the optimality conditions for the disjunctive program originally
obtained by Gfrerer in [21, Theorems 3.3 and 3.17, Corollary 3.20] and
summarized in [12, Theorem 6.1] with the calculus rules of Cartisian product
rules of tangent and directional normal cones in [41, Proposition 3.3].

######  Theorem 3.1.

Let $x^{\ast}$ be a local optimal solution of MPDSC _( 26)_ and
$d\in\mathcal{C}(x^{\ast})$.

  * _(i)_

If MSCQ in direction $d$ holds at $x^{*}$, then $x^{*}$ must be M-stationary
(d). Moreover if all functions are twice continuously differentiable, then
there exists an M-stationary $(d)$ multiplier
$(\lambda^{g},\lambda^{h},\lambda^{\Phi})$ such that the second-order
necessary optimality condition holds:

$d^{T}\nabla^{2}_{x}\mathcal{L}(x^{\ast},\lambda^{g},\lambda^{h},\lambda^{\Phi})d\geq
0.$ (33)

  * _(ii)_

If MPDSC-LICQ $(d)$ is fulfilled at $x^{\ast}$, then $x^{*}$ must be
S-stationary (d). Moreover if all functions are twice continuously
differentiable, then there exists an S-stationary $(d)$ multiplier
$(\lambda^{g},\lambda^{h},\lambda^{\Phi})$ such that the second-order
necessary optimality condition _( 33)_ holds.

Conversely, let $x^{\ast}$ be a feasible solution of MPDSC _( 26)_. Suppose
that all functions are twice continuously differentiable and for every nonzero
critical direction $0\neq d\in\mathcal{C}(x^{\ast})$ there exists an
S-stationary $(d)$ multiplier $(\lambda^{g},\lambda^{h},\lambda^{\Phi})$ such
that the second-order condition strictly holds:

$d^{T}\nabla^{2}_{x}\mathcal{L}(x^{\ast},\lambda^{g},\lambda^{h},\lambda^{\Phi})d>0.$

Then $x^{\ast}$ is a strict local minimizer of MPDSC _( 26)_.

###  3.2 Constraint qualifications for MPDSC from MPDC

Now using the formulas for tangent and normal cones in Proposition 2.1, we
obtain some constraint qualifications for MPDSC from the corresponding ones
for MPDC (see e.g., [39, Definitions 3.1 and 4.2]).

######  Definition 3.4.

Let $x^{\ast}\in\mathcal{F}$ be a feasible point for MPDSC _( 26)_.

  1. 1.

We say that $x^{\ast}$ satisfies MPDSC linear independence constraint
qualification (MPDSC-LICQ) if there is no nonzero vector
$(\lambda^{g},\lambda^{h},$
$\lambda^{\Phi})\in\mathbb{R}^{m}\times\mathbb{R}^{n}\times\prod_{i=1}^{l}\mathbb{R}^{q}$
with $\lambda^{\Phi}_{i}\in\sum\limits_{r\in
I(\Phi_{i}(x^{\ast}))}S_{r}^{\perp}$ satisfying

$\displaystyle
0=\sum\limits_{i\in\mathcal{I}_{g}(x^{\ast})}\lambda_{i}^{g}\nabla
g_{i}(x^{\ast})+\sum\limits_{i=1}^{p}\lambda_{i}^{h}\nabla
h_{i}(x^{\ast})+\sum\limits_{i=1}^{l}\nabla\Phi_{i}(x^{\ast})^{T}\lambda^{\Phi}_{i}.$
(34)

  2. 2.

We say that $x^{\ast}$ satisfies MPDSC no nonzero abnormal multiplier
constraint qualification (MPDSC-NNAMCQ) if there is no nonzero vector
$(\lambda^{g},\lambda^{h},$
$\lambda^{\Phi})\in\mathbb{R}^{m}\times\mathbb{R}^{n}\times\prod_{i=1}^{l}\mathbb{R}^{q}$
with $\lambda^{g}_{i}\geq 0,\>i\in\mathcal{I}_{g}(x^{\ast})$,
$\lambda^{\Phi}_{i}\in\bigcup\limits_{r\in
I(\Phi_{i}(x^{\ast}))}S_{r}^{\perp}$ satisfying (34).

  3. 3.

We say that $x^{\ast}$ satisfies MPDSC relaxed constant positive linear
dependence constraint qualification (MPDSC-RCPLD) if the following conditions
hold.

     * _(i)_

The vectors $\\{\nabla h_{i}(x)\\}^{p}_{i=1}$ have the same rank for all
$x\in\mathbb{B}_{\varepsilon}(x^{\ast})$ for some $\varepsilon>0$;

     * _(ii)_

Let $J\subseteq\\{1,\dots,p\\}$ be such that the set of vectors $\\{\nabla
h_{i}(x^{\ast})\\}_{i\in J}$ is a basis for _span_ $\\{\nabla
h_{i}(x^{\ast})\\}_{i=1}^{p}$. If there exist index sets
$I\subseteq\mathcal{I}_{g}(x^{\ast})$, a nonzero vector
$(\lambda^{g},\lambda^{h},\lambda^{\Phi})\in\mathbb{R}^{m}\times\mathbb{R}^{n}\times\prod_{i=1}^{l}\mathbb{R}^{q}$
with $\lambda^{g}_{i}\geq 0,i\in I$ and
$\lambda^{\Phi}_{i}\in\bigcup\limits_{r\in
I(\Phi_{i}(x^{\ast}))}S_{r}^{\perp}$, $i\in\\{1,\dots,l\\}$ satisfying

$\displaystyle 0=\sum\limits_{i\in I}\lambda_{i}^{g}\nabla
g_{i}(x^{\ast})+\sum\limits_{i\in J}\lambda_{i}^{h}\nabla
h_{i}(x^{\ast})+\sum\limits_{i=1}^{l}\nabla\Phi_{i}(x^{\ast})^{T}\lambda^{\Phi}_{i},$
(35)

then the set of vectors

$\\{\nabla g_{i}(x^{k})\\}_{i\in I}\cup\\{\nabla h_{i}(x^{k})\\}_{i\in
J}\cup\bigcup\limits_{\beta_{i}\in
A_{i},i\in\\{1,\dots,l\\}}\\{\nabla\Phi_{i}(x^{k})^{T}\beta_{i}\\}$ (36)

is linearly dependent for $k$ sufficiently large, for all sequences
$\\{x^{k}\\}$ satisfying $x^{k}\to x^{\ast},x^{k}\neq x^{\ast}$ as
$k\to\infty$ and any set of linearly independent vectors $A_{i}$ with the
following conditions:

$\begin{array}[]{ll}\mbox{ if }\lambda^{\Phi}_{i}\not=0,&\mbox{ then
}A_{i}\subseteq
A_{S}(\Phi_{i}(x^{\ast})),\quad\lambda^{\Phi}_{i}\in\mathcal{G}(A_{i})\subseteq\bigcup\limits_{r\in
I(\Phi_{i}(x^{\ast}))}S_{r}^{\perp};\\\ \mbox{ if
}\lambda^{\Phi}_{i}=0,&\mbox{ then }A_{i}=\emptyset.\end{array}$ (37)

  4. 4.

We say that $x^{\ast}$ satisfies MPDSC constant positive linear dependence
constraint qualification (MPDSC-CPLD) if all condition (ii) in MPDSC-RCPLD
hold with the index set $J$ is taken as a arbitrary subset of
$\\{1,\dots,p\\}$.

  5. 5.

We say that $x^{\ast}$ satisfies MPDSC constant rank constraint qualification
(MPDSC-CRCQ) if for every index sets
$I\subseteq\mathcal{I}_{g}(x^{\ast}),J\subseteq\\{1,\dots,p\\}$,
$L\subseteq\\{1,\dots,l\\}$ and $\lambda^{\Phi}_{i}\in\bigcup\limits_{r\in
I(\Phi_{i}(x^{\ast}))}S_{r}^{\perp},i\in L$, the set of vectors

$\\{\nabla g_{i}(x^{\ast})\\}_{i\in I}\cup\\{\nabla h_{i}(x^{\ast})\\}_{i\in
J}\cup\bigcup\limits_{\beta_{i}\in A_{i},i\in
L}\\{\nabla\Phi_{i}(x^{\ast})^{T}\beta_{i}\\}$

and the set of vectors

$\\{\nabla g_{i}(x^{k})\\}_{i\in I}\cup\\{\nabla h_{i}(x^{k})\\}_{i\in
J}\cup\bigcup\limits_{\beta_{i}\in A_{i},i\in
L}\\{\nabla\Phi_{i}(x^{k})^{T}\beta_{i}\\}$

have the same rank for $k$ sufficiently large, for all sequences $\\{x^{k}\\}$
satisfying $x^{k}\to x^{\ast},x^{k}\neq x^{\ast}$ as $k\to\infty$ and any set
of linearly independent vectors $A_{i}$ satisfying condition (37).

  6. 6.

We say that $x^{\ast}$ satisfies MPDSC relaxed constant rank constraint
qualification (MPDSC-RCRCQ) if the index set $J$ is taken as $\\{1,\dots,p\\}$
in MPDSC-CRCQ.

  7. 7.

We say that $x^{\ast}$ satisfies MPDSC-ERCPLD if the following conditions
hold.

     * _(i)_

The vectors $\\{\nabla h_{i}(x)\\}^{p}_{i=1}$ have the same rank for all
$x\in\mathbb{B}_{\varepsilon}(x^{\ast})$ for some $\varepsilon>0$;

     * _(ii)_

Let $J\subseteq\\{1,\dots,p\\}$ be such that the set of vectors $\\{\nabla
h_{i}(x^{\ast})\\}_{i\in J}$ is a basis for _span_ $\\{\nabla
h_{i}(x^{\ast})\\}_{i=1}^{p}$. If there exist index sets
$I\subseteq\mathcal{I}_{g}(x^{\ast})$ and $L\subseteq\\{1,\dots,l\\}$,
$\lambda^{\Phi}_{i}\in\bigcup\limits_{r\in
I(\Phi_{i}(x^{\ast}))}S_{r}^{\perp},i\in L$ such that the set of vectors

$\\{\nabla g_{i}(x^{\ast})\\}_{i\in I}\cup\Bigl{\\{}\\{\nabla
h_{i}(x^{\ast})\\}_{i\in J}\cup\bigcup\limits_{\beta_{i}\in A_{i},i\in
L}\\{\nabla\Phi_{i}(x^{\ast})^{T}\beta_{i}\\}\Bigr{\\}}$

is positive linearly dependent, then the set of vectors

$\\{\nabla g_{i}(x^{k})\\}_{i\in I}\cup\\{\nabla h_{i}(x^{k})\\}_{i\in
J}\cup\bigcup\limits_{\beta_{i}\in A_{i},i\in
L}\\{\nabla\Phi_{i}(x^{k})^{T}\beta_{i}\\}$

is linearly dependent for $k$ sufficiently large, for all sequences
$\\{x^{k}\\}$ satisfying $x^{k}\to x^{\ast},x^{k}\neq x^{\ast}$ as
$k\to\infty$ and any set of linearly independent vectors $A_{i}$ satisfying
condition (37).

###  3.3 RCPLD as a sufficient condition for MSCQ

Unlike the differentiable nonlinear program, RCPLD for MPDC is not a
sufficient condition for MSCQ in general. In order to obtain a RCPLD type
sufficent condition for MSCQ, Xu and Ye introduced MPDC-piecewise RCPLD and
show that it is a sufficient condition for error bounds [39, Theorem 4.2]. It
turns out that for MPDSC many constraint qualifications such as CRCQ, RCRCQ,
CPLD, ERCPLD, and RCPLD coincide with their piecewise versions, respectively.
Here we only focus on the discussions on RCPLD and the piecewise RCPLD and
omit discussions on other constraint qualifications as well as their piecewise
versions since the derivation would be similar. Consequently, since RCPLD
coincides with piecewise RCPLD, RCPLD implies error bounds for MPDSC.

First we present a simple example to illustrate the equivalence of RCPLD and
the piecewise RCPLD for MPDSC.

######  Example 3.1.

Consider the following cardinality constrained system in $\mathbb{R}^{3}$:

$g(x)\leq 0,h(x)=0,\|x\|_{0}\leq 2.$ (38)

From _Figure 1_ we know that problem _( 38)_ is equivalent to

$g(x)\leq 0,h(x)=0,\Phi(x):=x\in S,$

with $S=S_{1}\cup S_{2}\cup S_{3}$ such that
$S_{1}=\\{0\\}\times\mathbb{R}\times\mathbb{R}$,
$S_{2}=\mathbb{R}\times\\{0\\}\times\mathbb{R}$ and
$S_{3}=\mathbb{R}\times\mathbb{R}\times\\{0\\}$. Assume that point
$x^{\ast}=(0,0,1)$ is feasible for system _( 38)_. According to Definition
3.4(7), we say that RCPLD holds at $x^{*}$ if

  * _(i)_

The vectors $\\{\nabla h_{i}(x)\\}^{p}_{i=1}$ have the same rank for all
$x\in\mathbb{B}_{\varepsilon}(x^{\ast})$ for some ${\varepsilon}>0$;

  * _(ii)_

Let $J\subseteq\\{1,\dots,p\\}$ be such that the set of vectors $\\{\nabla
h_{i}(x^{\ast})\\}_{i\in J}$ is a basis for _span_ $\\{\nabla
h_{i}(x^{\ast})\\}_{i=1}^{p}$. If there exist index an index set
$I\subseteq\mathcal{I}_{g}(x^{\ast})$, a multiplier
$\lambda=(\lambda^{g},\lambda^{h},\lambda^{\Phi})\in\mathbb{R}^{m}\times\mathbb{R}^{n}\times\mathbb{R}^{3}$
with $\lambda^{g}_{i}\geq 0,i\in I$ and $\lambda^{\Phi}\in
N_{S}(x^{*})=S_{1}^{\perp}\cup S_{2}^{\perp}$ such that

$0=\sum\limits_{i\in I}\lambda_{i}^{g}\nabla g_{i}(x^{\ast})+\sum\limits_{i\in
J}\lambda_{i}^{h}\nabla h_{i}(x^{\ast})+\lambda^{\Phi},$ (39)

then the set of vectors

$\\{\nabla g_{i}(x^{k})\\}_{i\in I}\cup\\{\nabla h_{i}(x^{k})\\}_{i\in J}\cup
A$

is linearly dependent for $k$ sufficiently large, for all sequences
$\\{x^{k}\\}$ satisfying $x^{k}\to x^{\ast},x^{k}\neq x^{\ast}$ as
$k\to\infty$ and any set of linearly independent vectors $A\subseteq
A_{S}(x^{*})=\\{e_{1},e_{2}\\}$ such that

$\begin{array}[]{ll}\mbox{ if }\lambda^{\Phi}\not=0&\mbox{ then
}\lambda^{\Phi}\in{\cal G}(A)\subseteq S_{1}^{\perp}\cup S_{2}^{\perp},\\\
\mbox{ if }\lambda^{\Phi}=0&\mbox{ then }A=\emptyset.\end{array}$

If $\lambda^{\Phi}\not=0$, then since $\lambda^{\Phi}\in S_{1}^{\perp}\cup
S_{2}^{\perp}$, either $\lambda^{\Phi}\in{\cal G}(e_{1})\subseteq
S_{1}^{\perp}=\mathbb{R}\times\\{0\\}\times\\{0\\}$ or $\lambda^{\Phi}\in{\cal
G}(e_{2})\subseteq S_{2}^{\perp}=\\{0\\}\times\mathbb{R}\times\\{0\\}$. Hence
the set $A$ above must be taken as $e_{1}$ if $\lambda^{\Phi}\in
S_{1}^{\perp}$ and $e_{2}$ if $\lambda^{\Phi}_{2}\in S_{2}^{\perp}$.

We now consider the piecewise RCPLD. There are three partitions of index set
$\\{1\\}$ into sets $P=\\{P_{1},P_{2},P_{3}\\}$: _(i)_
$P_{1}=\\{1\\},P_{2}=\emptyset,P_{3}=\emptyset$; _(ii)_
$P_{1}=\emptyset,P_{2}=\\{1\\},P_{3}=\emptyset$; _(iii)_
$P_{1}=\emptyset,P_{2}=\emptyset,P_{3}=\\{1\\}$. Since $x^{\ast}\notin S_{3}$,
we only have two possible subsystems. Therefore, the piecewise RCPLD holds for
system _( 38)_ at $x^{*}$ if RCPLD holds for each of the following two
subsystems at $x^{*}$:

$(\text{$\mathcal{P}_{1}$})\left\\{\begin{gathered}g(x)\leq 0,\\\ h(x)=0,\\\
x\in
S_{1}.\end{gathered}\qquad\qquad\emph{and}\qquad\qquad(\text{$\mathcal{P}_{2}$})\right\\{\begin{gathered}g(x)\leq
0,\\\ h(x)=0,\\\ x\in S_{2}.\end{gathered}$

But RCPLD for subsystem $\mathcal{P}_{1}$ holding at $x^{*}$ if condition (i)
above holds and the following conditions hold. Let $J\subseteq\\{1,\dots,p\\}$
be such that the set of vectors $\\{\nabla h_{i}(x^{\ast})\\}_{i\in J}$ is a
basis for _span_ $\\{\nabla h_{i}(x^{\ast})\\}_{i=1}^{p}$. If there exist an
index set $I\subseteq\mathcal{I}_{g}(x^{\ast})$, a multiplier
$\lambda=(\lambda^{g},\lambda^{h},\lambda^{\Phi})\in\mathbb{R}^{m}\times\mathbb{R}^{n}\times\mathbb{R}^{3}$
with $\lambda^{g}_{i}\geq 0,i\in I$ and $\lambda^{\Phi}\in S_{1}^{\perp}$ such
that (39) holds, then the set of vectors $\\{\nabla g_{i}(x^{k})\\}_{i\in
I}\cup\\{\nabla h_{i}(x^{k})\\}_{i\in J}\cup A$ is linearly dependent for $k$
sufficiently large, for all sequences $\\{x^{k}\\}$ satisfying $x^{k}\to
x^{\ast},x^{k}\neq x^{\ast}$ as $k\to\infty$ and any set of linearly
independent vectors $A\subseteq A_{S_{1}}=\\{e_{1}\\}$ such that

$\begin{array}[]{ll}\mbox{ if }\lambda^{\Phi}\not=0&\mbox{ then
}\lambda^{\Phi}\in{\cal G}(A)\subseteq S_{1}^{\perp},\\\ \mbox{ if
}\lambda^{\Phi}=0&\mbox{ then }A=\emptyset.\end{array}$

RCPLD for subsystem $\mathcal{P}_{2}$ holding at $x^{*}$ if the RCPLD for
subsystem $\mathcal{P}_{1}$ with $S_{1}^{\perp}$ replaced by $S_{2}^{\perp}$
and $e_{1}$ replaced by $e_{2}$. Hence obviously RCPLD coincides with the
piecewise RCPLD.

Now we consider the general case and let $x^{\ast}$ be feasible for MPDSC
(26). Let sets $P_{1},\dots,P_{R}$ (sometimes some of them may be empty) be a
partition of $\\{1,\dots,l\\}$. We denote such partition by
$P:=\\{P_{1},\dots,P_{R}\\}$ and consider the subsystem for partition $P$:

$\begin{cases}g(x)\leq 0,\>h(x)=0,\\\ \Phi_{i}(x)\in S_{1},\>i\in P_{1},\\\
\quad\quad\quad\vdots\\\ \Phi_{i}(x)\in S_{R},\>i\in P_{R}.\end{cases}$ (40)

We denote the feasible region of subsystem (40) by $\mathcal{F}_{P}$. Applying
the definition for MPDC [39, Definition 4.1] to MPDSC we have the following
definition.

######  Definition 3.5.

_(MPDSC-PRCPLD)_ We say that the piecewise RCPLD holds for MPDSC _( 26)_ at
$x^{\ast}\in\mathcal{F}$, if MPDSC-RCPLD holds for subsystem _( 40)_ for any
partition $P=\\{P_{1},\dots,P_{R}\\}$ such that $x^{\ast}\in\mathcal{F}_{P}$.
That is, the following conditions hold for any partition
$P=\\{P_{1},\dots,P_{R}\\}$ such that $x^{\ast}\in\mathcal{F}_{P}$.

  * _(i)_

The vectors $\\{\nabla h_{i}(x)\\}^{p}_{i=1}$ have the same rank for all
$x\in\mathbb{B}_{\varepsilon}(x^{\ast})$ for some $\varepsilon>0$;

  * _(ii)_

Let $J\subseteq\\{1,\dots,p\\}$ be such that the set of vectors $\\{\nabla
h_{i}(x^{\ast})\\}_{i\in J}$ is a basis for _span_ $\\{\nabla
h_{i}(x^{\ast})\\}_{i=1}^{p}$. If there exist index sets
$I\subseteq\mathcal{I}_{g}(x^{\ast})$, a nonzero vector
$(\lambda^{g},\lambda^{h},\lambda^{\Phi})^{T}\in\mathbb{R}^{m}\times\mathbb{R}^{n}\times\prod_{i=1}^{l}\mathbb{R}^{q}$
with $\lambda^{g}_{i}\geq 0,i\in I$ and $\lambda^{\Phi}_{i}\in S_{r}^{\perp}$
for $i\in P_{r}$, $r=1,\dots,R$ such that

$0=\sum\limits_{i\in I}\lambda_{i}^{g}\nabla g_{i}(x^{\ast})+\sum\limits_{i\in
J}\lambda_{i}^{h}\nabla h_{i}(x^{\ast})+\sum\limits_{i\in
P_{1}}\nabla\Phi_{i}(x^{\ast})^{T}\lambda^{\Phi}_{i}+\cdots+\sum\limits_{i\in
P_{R}}\nabla\Phi_{i}(x^{\ast})^{T}\lambda^{\Phi}_{i},$ (41)

then the set of vectors

$\\{\nabla g_{i}(x^{k})\\}_{i\in I}\cup\\{\nabla h_{i}(x^{k})\\}_{i\in
J}\bigcup\limits_{\beta^{r}_{i}\in A^{r}_{i},i\in
P_{r},r=1,\dots,R}\\{\nabla\Phi_{i}(x^{k})^{T}\beta^{r}_{i}\\}$ (42)

is linearly dependent for $k$ sufficiently large, for all sequences
$\\{x^{k}\\}$ satisfying $x^{k}\to x^{\ast},x^{k}\neq x^{\ast}$ as
$k\to\infty$ and any set of linearly independent vectors $A^{r}_{i}$ with
$r\in I(\Phi_{i}(x^{\ast}))$ satisfying the following condition

$\begin{array}[]{ll}\mbox{ if }\lambda^{\Phi}_{i}\not=0,&\mbox{ then
}\quad\lambda^{\Phi}_{i}\in\mathcal{G}(A^{r}_{i})\subseteq S_{r}^{\perp},\quad
A^{r}_{i}\subseteq A_{S_{r}}\\\ \mbox{ if }\lambda^{\Phi}_{i}=0,&\mbox{ then
}\quad A^{r}_{i}=\emptyset.\end{array}$ (43)

Now we show that MPDSC-RCPLD coincides with MPDSC-piecewise RCPLD. As we can
see as follows, the following two equalities from Proposition 2.1 and Lemma
2.1 play key roles in the proof of Theorem 3.2:

$\displaystyle N_{S}(\Phi_{i}(x^{\ast}))$ $\displaystyle=\bigcup\limits_{r\in
I(\Phi_{i}(x^{\ast}))}N_{S_{r}}(\Phi_{i}(x^{\ast})),$ (44) $\displaystyle
A_{S}(\Phi_{i}(x^{\ast}))$ $\displaystyle=\bigcup\limits_{r\in
I(\Phi_{i}(x^{\ast}))}A_{S_{r}}.$ (45)

In fact, we can give a more accurate description of generator sets
$A_{i},\>i=1,\dots,l$ when we consider MPDSC instead of general MPDC. The
following lemma is useful in what follows.

######  Lemma 3.1.

For $0\neq\lambda\in N_{S}(y)=\bigcup\limits_{r\in I(y)}S_{r}^{\perp}$,
suppose that $\lambda$ is generated by a set of linearly independent vectors
$A$ which is a subset of the generator set of the limiting normal cone of $S$
at $y$, i.e.,

$\lambda\in\mathcal{G}(A)\subseteq N_{S}(y)=\bigcup\limits_{r\in
I(y)}S_{r}^{\perp},\quad A\subseteq A_{S}(y)=\bigcup\limits_{r\in
I(y)}A_{S_{r}}.$

Then if $\lambda\in N_{S_{r}}(y)=S_{r}^{\perp}$, $\lambda$ is also generated
by a subset of linearly independent vectors $A$ which is a subset of the
generator of $S_{r}$, i.e.,

$\lambda\in\mathcal{G}(A)\subseteq\mathcal{G}(A_{S_{r}})=S_{r}^{\perp},\quad
A\subseteq A_{S_{r}},$ (46)

###### Proof.

Suppose on the contrary that (46) does not hold. Without loss of generality,
we assume there are $r_{1},r_{2}\in I(y)$ such that

$A\subseteq A_{S_{r_{1}}}\cup A_{S_{r_{2}}}\>\>\textrm{but}\>\>A\nsubseteq
A_{S_{r_{1}}}\>\>\textrm{and}\>\>A\nsubseteq A_{S_{r_{2}}}.$

Since both $S_{r_{1}}$ and $S_{r_{2}}$ are subspaces, it follows that

$\mathcal{G}(A)\subseteq\textrm{span}\\{S_{r_{1}}^{\perp}\cup
S_{r_{2}}^{\perp}\\}\>\>\textrm{but}\>\>\mathcal{G}(A)\nsubseteq
S_{r_{1}}^{\perp}\>\>\textrm{and}\>\>\mathcal{G}(A)\nsubseteq
S_{r_{2}}^{\perp},$

which contradicts the fact that

$\mathcal{G}(A)\subseteq N_{S}(y)=\bigcup\limits_{r\in I(y)}S_{r}^{\perp}.$

In this way, we complete the proof. ∎

######  Theorem 3.2.

For _(MPDSC)_ , RCPLD coincides with the piecewise RCPLD.

###### Proof.

Without loss of generality assume that the number of subspaces are more than
$2$. Condition (i) is identical for both RCPLD and the piecewise RCPLD. In
condition (ii), (35) is also identical to (41). Hence (35) holds for
$\lambda=(\lambda^{g},\lambda^{h},\lambda^{\Phi})$ with
$\lambda^{\Phi}_{i}\in\bigcup\limits_{r\in
I(\Phi_{i}(x^{\ast}))}S_{r}^{\perp}$ if and only if (41) for the same
$\lambda$ when $\lambda^{\Phi}_{i}\in S_{r}^{\perp},r\in
I(\Phi_{i}(x^{\ast}))$. The rest of the proof follows from applying Lemma 3.1.

∎

The discussions on other constraint qualifications are similar as that of
RCPLD, hence we have the following corollary.

######  Corollary 3.1.

For mathematical programs with disjunctive subspaces constraints _(MPDSC)_ ,
their constraint qualifications such as CRCQ, RCRCQ, CPLD, ERCPLD, and RCPLD
coincide with their piecewise versions, respectively.

Based on Theorem 3.2, now we show that for MPDSC the constraint qualification
RCPLD implies error bounds for MPDSC.

######  Theorem 3.3.

Suppose that MPDSC-RCPLD holds at $x^{\ast}$ which is feasible for problem _(
26)_. Then, the error bound property holds at $x^{\ast}$.

###### Proof.

The proof is rather straightforward by combining Theorem 3.2 and [39, Theorem
4.2]. The constraint qualification MPDSC-RCPLD implies the error bound
property since MPDSC-RCPLD coincides with MPDSC-piecewise RCPLD. ∎

We conclude Section 3 with Figure 2 which summarizes the relations among
various constraint qualifications for MPDSC.

Error bounds for MPDSCMPDSC-RCPLDMPDSC-CPLDMPDSC-RCRCQMPDSC-NNAMCQMPDSC-
CRCQMPDSC-LICQMPDSC-ERCPLD Figure 2: Relations among various constraint
qualifications for MPDSC

##  4 Optimality conditions and sufficient condition for error bounds for CCOP

In this section we apply main results obtained for MPDSC to CCOP. Recall that
$\mathcal{I}_{s}:=\\{\mathcal{I}\subseteq\\{1,2,\dots,n\\}\>|\>|\mathcal{I}|=s\\}$
and $\mathbb{R}_{\mathcal{I}}:=\textrm{span}\\{e_{i}\>|\>i\in\mathcal{I}\\}$.
In this section
$S:=\bigcup\limits_{\mathcal{I}\in\mathcal{I}_{s}}\mathbb{R}_{\mathcal{I}}$
and use the notation $I_{\pm}(x):=\\{i\in\\{1,\dots,n\\}\>|\>x_{i}\neq 0\\}$
and $I_{0}(x):=\\{i\in\\{1,\dots,n\\}\>|\>x_{i}=0\\}$ for a given vector
$x\in\mathbb{R}^{n}$.

The following proposition is immediate from Propositions 2.1-2.3 taking into
account that $r\in I(x^{*})$ here means that $x^{*}\in\mathbb{R}_{\cal I}$ and
$I_{\pm}(x^{\ast})\subseteq{\cal I}\in{\cal I}_{s}$.

######  Proposition 4.1.

Let $x^{\ast}$ and $d\in\mathbb{R}^{n}$. Then, we have the expressions of
various tangent and normal cones in _Table 1_.

Cones | $|I_{\pm}(x^{\ast})|<s$ (or $|I_{\pm}(x^{\ast})\cup I_{\pm}(d)|<s$) |  $|I_{\pm}(x^{\ast})|=s$ (or $|I_{\pm}(x^{\ast})\cup I_{\pm}(d)|=s$)
---|---|---
$T_{S}(x^{\ast})$ | $\bigcup\limits_{\scriptsize{I_{\pm}(x^{\ast})\subseteq\mathcal{I}\in\mathcal{I}_{s}}}\mathbb{R}_{\mathcal{I}}$ | $\mathbb{R}_{\scriptsize{I_{\pm}(x^{\ast})}}$
$\hat{N}_{S}(x^{\ast})$ | $\\{0\\}$ | $\mathbb{R}_{\scriptsize{I_{\pm}(x^{\ast})}}^{\perp}$
$N_{S}(x^{\ast})$ | $\bigcup\limits_{\scriptsize{I_{\pm}(x^{\ast})\subseteq\mathcal{I}\in\mathcal{I}_{s}}}\mathbb{R}_{\mathcal{I}}^{\perp}$ | $\mathbb{R}_{\scriptsize{I_{\pm}(x^{\ast})}}^{\perp}$
$N_{S}(x^{\ast};d)$ | $\bigcup\limits_{\scriptsize{I_{\pm}(x^{\ast})\cup I_{\pm}(d)\subseteq\mathcal{I}\in\mathcal{I}_{s}}}\mathbb{R}_{\mathcal{I}}^{\perp}$ | $\mathbb{R}_{\scriptsize{I_{\pm}(x^{\ast})\cup I_{\pm}(d)}}^{\perp}$
$\hat{N}_{T_{S}(x^{\ast})}(d)$ | $\\{0\\}$ | $\mathbb{R}_{\scriptsize{I_{\pm}(x^{\ast})\cup I_{\pm}(d)}}^{\perp}$

Table 1: Various cones to set $S$ in CCOP

Now let us write down the constraint qualifications for CCOP from the ones for
MPDSC in Definition 3.4. In order to do that we need to specify the condition
(37) to CCOP. For problem CCOP written in the form (2), $l=1$,
$\Phi_{i}(x)=x$, $S_{r}=\mathbb{R}_{\cal I}$ and $\lambda^{\Phi}_{i}=\eta$.
Moreover, $r\in I(\Phi_{i}(x^{*}))$ here means that $x^{*}\in S_{\cal I}$ and
$I_{\pm}(x^{\ast})\subseteq{\cal I}\in{\cal I}_{s}$. Hence the condition (37)
is

$\begin{array}[]{ll}\mbox{ if }\eta\not=0,&\mbox{ then }A\subseteq
A_{S}(x^{\ast}),\quad\eta\in\mathcal{G}(A)\subseteq\bigcup\limits_{I_{\pm}(x^{\ast})\subseteq{\cal
I}\in{\cal I}_{s}}{\mathbb{R}_{\cal I}}^{\perp};\\\ \mbox{ if }\eta=0,&\mbox{
then }A=\emptyset.\end{array}$

Since for $I_{\pm}(x^{\ast})\subseteq{\cal I}\in\mathcal{I}_{s}$, we have
$N_{\mathbb{R}_{\cal I}}(x^{\ast})=\mathbb{R}_{\cal I}^{\perp}$,

$A_{\mathbb{R}_{\cal I}}=\\{e_{i}\>|\>i\in K\>\>\textrm{such
that}\>\>K\subseteq I_{0}(x^{\ast})\>\>\textrm{and}\>\>|K|\leq n-s\\}.$

Hence by (20),

$A_{S}(x^{\ast})=\bigcup\limits_{I_{\pm}(x^{\ast})\subseteq{\cal I}\in{\cal
I}_{s}}A_{\mathbb{R}_{\cal I}}$

and so in the case where $0\neq\eta\in\mathcal{G}(A)$, by Lemma 3.1 we can
take the generator set $A$ above as

$A=\\{e_{i}\>|\>i\in K\>\>\textrm{such that}\>\>I_{\pm}(\eta)\subseteq
K\subseteq I_{0}(x^{\ast})\>\>\textrm{and}\>\>|K|\leq n-s\\}.$

Therefore, we obtain the following definition. Note that the constraint
qualification CCOP-LICQ is the same as the one proposed in [30, Section 5.3].

######  Definition 4.1.

_(Constraint qualifications for CCOP)_ Let $x^{\ast}$ be feasible for CCOP. We
say that $x^{\ast}$ satisfies

  1. 1.

_CCOP-LICQ_ if the family of vectors $\\{\nabla
g_{i}(x^{\ast})\\}_{i\in\mathcal{I}_{g}(x^{\ast})}\cup\\{\nabla
h_{i}(x^{\ast})\\}_{i=1}^{p}\cup\\{e_{i}\\}_{i\in I_{0}(x^{\ast})}$ is
linearly independent;

  2. 2.

_CCOP-NNAMCQ_ if there exists no nonzero vector
$(\lambda^{g},\lambda^{h},\eta)\in\mathbb{R}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n}$
with $\lambda^{g}_{i}\geq 0,\forall i\in\mathcal{I}_{g}(x^{*})$ and

$\eta_{i}=0,\>\forall i\in I_{\pm}(x^{\ast})\>\>\emph{and}\>\>\|\eta\|_{0}\leq
n-s.$ (47)

satisfying

$\sum\limits_{i\in\mathcal{I}_{g}(x^{*})}\lambda^{g}_{i}\nabla
g_{i}(x^{\ast})+\sum\limits_{i=1}^{p}\lambda^{h}_{i}\nabla
h_{i}(x^{\ast})+\eta=0;$ (48)

  3. 3.

_CCOP-RCPLD_ if the following conditions hold.

     * _(i)_

The vectors $\\{\nabla h_{i}(x)\\}^{p}_{i=1}$ have the same rank for all
$x\in\mathbb{B}_{\varepsilon}(x^{\ast})$ for some $\varepsilon>0$;

     * _(i)_

Let $J\subseteq\\{1,\dots,p\\}$ be such that the set of vectors $\\{\nabla
h_{i}(x^{\ast})\\}_{i\in J}$ is a basis for _span_ $\\{\nabla
h_{i}(x^{\ast})\\}_{i=1}^{p}$.

If there exist an index set $I\subseteq\mathcal{I}_{g}(x^{\ast})$, a nonzero
vector
$(\lambda^{g},\lambda^{h},\eta)\in\mathbb{R}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n}$
with $\lambda^{g}_{i}\geq 0,\forall i\in\mathcal{I}_{g}(x^{*})$ and $\eta$
such that (47) and

$\sum\limits_{i\in I}\lambda^{g}_{i}\nabla g_{i}(x^{\ast})+\sum\limits_{i\in
J}\lambda^{h}_{i}\nabla h_{i}(x^{\ast})+\eta=0,$ (49)

hold then the set of vectors

$\\{\nabla g_{i}(x^{k})\\}_{i\in I}\cup\\{\nabla h_{i}(x^{k})\\}_{i\in
J}\cup\\{e_{i}\\}_{i\in K}$

is linearly dependent for all sequences $\\{x^{k}\\}$ satisfying $x^{k}\to
x^{\ast}$, $x^{k}\neq x^{\ast}$ as $k\to\infty$ and all set $K$ satisfying

$\begin{array}[]{ll}\mbox{ if }\eta\not=0,&\mbox{ then }I_{\pm}(\eta)\subseteq
K\subseteq I_{0}(x^{\ast}),\quad|K|\leq n-s,\\\ \mbox{ if }\eta=0,&\mbox{ then
}K=\emptyset.\end{array}$ (50)

  4. 4.

_CCOP-CPLD_ if all condition (ii) in CCOP-RCPLD hold with the index set $J$ is
taken as a arbitrary subset of $\\{1,\dots,p\\}$.

  5. 5.

_CCOP-CRCQ_ if for every index sets $I\subseteq\mathcal{I}_{g}(x^{\ast})$,
$J\subseteq\\{1,\dots,p\\}$ and any $\eta$ satifying (47) such that the family
of vectors

$\\{\nabla g(x^{\ast})\\}_{i\in I}\cup\\{\nabla h(x^{\ast})\\}_{i\in
J}\cup\\{e_{i}\\}_{i\in K}$

and the set of vectors

$\\{\nabla g(x^{k})\\}_{i\in I}\cup\\{\nabla h(x^{k})\\}_{i\in
J}\cup\\{e_{i}\\}_{i\in K}$

have the same rank for all sequences $\\{x^{k}\\}$ satisfying $x^{k}\to
x^{\ast}$, $x^{k}\neq x^{\ast}$ as $k\to\infty$ and any set $K$ satisfying
(50).

  6. 6.

_CCOP-RCRCQ_ if the index set $J$ is taken as $\\{1,\dots,p\\}$ in CCOP-CRCQ.

  7. 7.

_CCOP-ERCPLD_ if the following conditions hold.

     * _(i)_

The vectors $\\{\nabla h_{i}(x)\\}^{p}_{i=1}$ have the same rank for all
$x\in\mathbb{B}_{\varepsilon}(x^{\ast})$ for some $\varepsilon>0$;

     * _(ii)_

Let $J\subseteq\\{1,\dots,p\\}$ be such that the set of vectors $\\{\nabla
h_{i}(x^{\ast})\\}_{i\in J}$ is a basis for _span_ $\\{\nabla
h_{i}(x^{\ast})\\}_{i=1}^{p}$. If there exists an index set
$I\subseteq\mathcal{I}_{g}(x^{\ast})$, $\eta$ satifying (47) such that the set
of vectors

$\\{\nabla g_{i}(x^{\ast})\\}_{i\in I}\cup\Bigl{\\{}\\{\nabla
h_{i}(x^{\ast})\\}_{i\in J}\cup\\{e_{i}\\}_{i\in K}\Bigr{\\}}$

is positive linearly dependent, then the set of vectors

$\\{\nabla g_{i}(x^{k})\\}_{i\in I}\cup\\{\nabla h_{i}(x^{k})\\}_{i\in
J}\cup\\{e_{i}\\}_{i\in K}$

is linearly dependent for all sequences $\\{x^{k}\\}$ satisfying $x^{k}\to
x^{\ast}$, $x^{k}\neq x^{\ast}$ as $k\to\infty$, and any set $K$ satisfying
(50).

In Figure 3 we summarize the relations among constraint qualifications for
CCOP we discussed above.

Error bounds for CCOPCCOP-RCPLDCCOP-CPLDCCOP-RCRCQCCOP-NNAMCQCCOP-CRCQCCOP-
LICQCCOP-ERCPLD Figure 3: Relations among new constraint qualifications for
CCOP

We now study optimality conditions for CCOP. The critical cone of CCOP at
$x^{*}$ is

$\mathcal{C}(x^{\ast})=\left\\{d\in\mathbb{R}^{n}\middle|\begin{array}[]{cl}\nabla
g_{i}(x^{\ast})d\leq 0,&i\in\mathcal{I}_{g}(x^{\ast})\\\ \nabla
h_{i}(x^{*})d=0,&i\in\\{1,\ldots,p\\}\\\
\nabla\Phi_{i}(x^{\ast})d\in\bigcup\limits_{\scriptsize{I_{\pm}(x^{\ast})\subseteq\mathcal{I}\in\mathcal{I}_{s}}}\mathbb{R}_{\gamma},&i\in\\{1,\ldots,l\\}\\\
\nabla f(x^{*})d\leq 0&\end{array}\right\\}.$

Applying Definition 3.1 to CCOP (2), with the help of Proposition 4.1, we
obtain the following directional S-/M-stationary conditions for CCOP. Recall
that the active set $\mathcal{I}_{g}^{*}(d)$ is defined in (30).

######  Definition 4.2.

Let $x^{\ast}\in\mathbb{R}^{n}$ be a feasible point of CCOP and
$d\in\mathcal{C}(x^{\ast})$.

  * _(i)_

We say $x^{\ast}$ is S-stationary in direction $d$ if there exists
$(\lambda^{g},\lambda^{h},\eta)\in\mathbb{R}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n}$
with $\lambda^{g}_{i}\geq 0,\forall i\in\mathcal{I}_{g}^{*}(d)$ satisfying

$\displaystyle\nabla
f(x^{\ast})+\sum\limits_{i\in\mathcal{I}_{g}^{*}(d)}\lambda^{g}_{i}\nabla
g_{i}(x^{\ast})$ $\displaystyle+\sum\limits_{i=1}^{p}\lambda^{h}_{i}\nabla
h_{i}(x^{\ast})+\eta=0,$ (51)

such that

    * _(a)_

if $|I_{\pm}(x^{\ast})\cup I_{\pm}(d)|=s$, then $\eta_{i}=0,\>\forall i\in
I_{\pm}(x^{\ast})\cup I_{\pm}(d)$.

    * _(b)_

if $|I_{\pm}(x^{\ast})\cup I_{\pm}(d)|<s$, then $\eta_{i}=0,\>\forall
i\in\\{1,\dots,n\\}$.

  * _(ii)_

We say $x^{\ast}$ is M-stationary $(d)$ if there exists
$(\lambda^{g},\lambda^{h},\eta)\in\mathbb{R}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n}$
with $\lambda^{g}_{i}\geq 0,\forall i\in\mathcal{I}_{g}^{*}(d)$ satisfying _(
51)_ such that

$\eta_{i}=0,\>\forall i\in I_{\pm}(x^{\ast})\cup
I_{\pm}(d)\>\>\emph{and}\>\>\|\eta\|_{0}\leq n-s.$

Moreover we call $\lambda=(\lambda^{g},\lambda^{h},\eta)$ satisfying (i) and
(ii) S-/M-stationary $(d)$ multiplier respectively.

Taking direction $d=0$ in Definition 4.2, we have $I(d)=\emptyset$. Hence we
recover the S-/M-stationary condition for CCOP which was first proposed by Pan
et al. in [36, Definition 3.1] under the name B-/M-KKT condition. From
Definition 4.2 it is clear that the directional M-stationary condition is in
general sharper than the standard M-stationary condition while the
S-stationary condition is in general stronger than the directional
S-stationary condition

We now specify the three conditions for MPDSC in Definition 3.3 to CCOP.

######  Definition 4.3.

Let $x^{*}$ be a feasible solution to CCOP.

  * _(a)_

We say that CCOP-FOSCMS holds at $x^{*}$ in direction
$d\in{\mathcal{C}}(x^{\ast})$ if there exists no nonzero vector
$(\lambda^{g},\lambda^{h},\eta)\in\mathbb{R}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n}$
with $\lambda^{g}_{i}\geq 0,\forall i\in\mathcal{I}_{g}^{*}(d)$ and
$\eta_{i}=0,\>\forall i\in I_{\pm}(x^{\ast})\cup
I_{\pm}(d)\>\>\emph{and}\>\>\|\eta\|_{0}\leq n-s$ satisfying

$\sum\limits_{i\in\mathcal{I}_{g}^{*}(d)}\lambda^{g}_{i}\nabla
g_{i}(x^{\ast})+\sum\limits_{i=1}^{p}\lambda^{h}_{i}\nabla
h_{i}(x^{\ast})+\eta=0.$ (52)

  * _(b)_

Suppose that all functions are twice continuously differentiable. We say that
the CCOP-SOSCMS holds at $x^{*}$ in direction $d\in{\mathcal{C}}(x^{\ast})$ if
there is no nonzero vector
$(\lambda^{g},\lambda^{h},\eta)\in\mathbb{R}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n}$
with $\lambda^{g}_{i}\geq 0,\forall i\in\mathcal{I}_{g}^{*}(d)$ and
$\eta_{i}=0,\>\forall i\in I_{\pm}(x^{\ast})\cup
I_{\pm}(d)\>\>\emph{and}\>\>\|\eta\|_{0}\leq n-s$ satisfying (52) and the
following second-order condition

$d^{T}\nabla^{2}_{x}\mathcal{L}^{0}(x^{\ast},\lambda^{g},\lambda^{h})d\geq 0,$

where
$\mathcal{L}^{0}(x,\lambda^{g},\lambda^{h}):=\langle\lambda^{g},g(x)\rangle+\langle\lambda^{h},h(x)\rangle.$

  * _(c)_

We say that CCOP-LICQ holds at $x^{*}$ in direction
$d\in{\mathcal{C}}(x^{\ast})$ if the family of vectors

$\\{\nabla g_{i}(x^{\ast})\\}_{i\in\mathcal{I}_{g}(x^{\ast})}\cup\\{\nabla
h_{i}(x^{\ast})\\}_{i=1}^{p}\cup\\{e_{i}\\}_{i\in I_{0}(x^{\ast})\cap
I_{0}(d)}$

is linearly independent;

When $d=0$, since $\mathcal{I}_{g}^{*}(0)=\mathcal{I}_{g}(x^{*})$ CCOP-FOSCMS
reduces to CCOP-NNAMCQ, CCOP-LICQ in direction $d$ reduces to CCOP-LICQ
defined in Definition 4.1 repsectively. It is obvious that in general we have

$\displaystyle\mbox{CCOP-NNAMCQ}\Longrightarrow\mbox{CCOP-
FOSCMS}(d)\Longrightarrow\mbox{CCOP-SOSCMS}(d)$ (53) $\displaystyle\mbox{CCOP-
LICQ}\Longrightarrow\mbox{CCOP-LICQ}(d).$ (54)

We denote the Lagrangian function of CCOP by

$\mathcal{L}(x,\lambda^{g},\lambda^{h}):=f(x)+\langle\lambda^{g},g(x)\rangle+\langle\lambda^{h},h(x)\rangle.$

The following optimality conditions are the CCOP version of Theorem 3.1.

######  Theorem 4.1.

Let $x^{\ast}$ be a local optimal solution of CCOP. Then the following first
and second order necessary optimality conditions hold:

  * _(i)_

Suppose that MSCQ holds at $x^{*}$ in direction $d\in\mathcal{C}(x^{\ast})$.
Then $x^{*}$ is M-stationary in direction $d$ and there exists an M-stationary
$(d)$ multiplier $\lambda=(\lambda^{g},\lambda^{h},\eta)$ such that the
second-order condition holds:

$d^{T}\nabla_{x}^{2}\mathcal{L}(x^{*},\lambda^{g},\lambda^{h})d\geq 0$ (55)

  * _(ii)_

For $d\in\mathcal{C}(x^{\ast})$, assume that CCOP-LICQ $(d)$ is fulfilled at
$x^{\ast}$. Then, there exists an S-stationary $(d)$ multiplier
$\lambda=(\lambda^{g},\lambda^{h},\eta)$ such that the second-order condition
_( 55)_ holds.

Conversely, let $x^{\ast}$ be a feasible solution of CCOP. Suppose that for
every nonzero critical direction $0\neq d\in\mathcal{C}(x^{\ast})$ there
exists an S-stationary $(d)$ multiplier
$\lambda=(\lambda^{g},\lambda^{h},\eta)$ such that the second-order condition
strictly holds:

$d^{T}\nabla_{x}^{2}\mathcal{L}(x^{*},\lambda^{g},\lambda^{h})d>0.$

Then $x^{\ast}$ is a strict local minimizer of CCOP _( 2)_.

Since direction M-stationary condition (d) implies M-stationary condition
while S-stationary condition implies S-stationary condition (d) respectively,
we have the following corollary.

######  Corollary 4.1.

Let $x^{\ast}$ be a local optimal solution of CCOP. Then the following first
and second order necessary optimality conditions hold: Suppose that either
CCOP-SOSCMS holds at $x^{*}$ in direction $d\in\mathcal{C}(x^{\ast})$ or one
of the constraint qualification presented in Figure 3 holds. Then $x^{*}$ is
M-stationary and there exists an M-stationary multiplier
$\lambda=(\lambda^{g},\lambda^{h},\eta)$ such that the second-order condition
(55) holds.

Conversely, let $x^{\ast}$ be a feasible solution of CCOP. Suppose that for
every nonzero critical direction $0\neq d\in\mathcal{C}(x^{\ast})$ there
exists an S-stationary $(d)$ multiplier
$\lambda=(\lambda^{g},\lambda^{h},\eta)$ associated with $x^{\ast}$ such that
the second-order condition (55) strictly holds. Then $x^{\ast}$ is a strict
local minimizer of CCOP _( 2)_.

Corollary 4.1 has improved the first order necessary optimality conditions in
Pan et al. in [36, Theorems 3.2](ii) since CCOP-SOSCMS is weaker than R-MFCQ.
It also improved the second order sufficient in Pan et al. in [36, Theorems
4.2] since S-stationarity implies S-stationarity (d).

We now conclude this section with the following application of our error bound
results.

######  Theorem 4.2.

Let $x^{*}\in\mathcal{F}_{\rm CCOP}$ where $\mathcal{F}_{\rm CCOP}$ denotes
the feasible region of CCOP. If one of the constraint qualification presented
in Figure 3 holds, then there exist $\alpha\geq 0$ and $\rho>0$ such that

$d_{\mathcal{F}_{\rm
CCOP}}(x)\leq\alpha\Bigl{(}\sum\limits_{i=1}^{m}\max\\{g_{i}(x),0\\}+\sum\limits_{i=1}^{p}|h_{i}(x)|\Bigr{)}\qquad\forall
x\in\mathbb{B}_{\rho}(x^{\ast})\cap S.$

Moreover if $x^{*}$ is a local optimal solution of CCOP then it is also a
local optimal solution of the exact penalty problem (3) for any $\mu\geq
L_{f}\alpha$ where $L_{f}$ is the Lipschitz constant of $f$ at $x^{*}$.

###### Proof.

The weakest constraint qualification in Figure 3 is CCOP-RCPLD. The error
bound property holds by Theorem 3.3. With the error bound property and the
continuous differentiability of $f$, the exact penalty result follows by using
the Clarke’s exact penalty principle; see [18, Proposition 2.4.3] or [40,
Theorem 4.2]. ∎

## References

  * [1] J-P. Aubin and H. Frankowska. _Set-valued Analysis_. Boston, Birkhäuser, 2009.
  * [2] W. Achtziger and C. Kanzow. _Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications_. Math. Program., 114, (2008), 69-99.
  * [3] L. Adam, M. Červinka, and M. Pištěk. _Normally admissible stratifications and calculation of normal cones to a finite union of polyhedral sets_. Set-Valued Var. Anal., 24, (2016), 207-229.
  * [4] K. Bai, J. J. Ye, and J. Zhang. _Directional quasi-/pseudo-normality as sufficient conditions for metric subregularity_. SIAM J. Optim., 29, (2019), 2625-2649.
  * [5] H. H. Bauschke, D. R. Luke, H. M. Phan, and X. Wang. _Restricted normal cones and sparsity optimization with affine constraints_. Found. Comput. Math., 14, (2014), 63-83.
  * [6] A. Beck and Y. C. Eldar. _Sparsity constrained nonlinear optimization: Optimality conditions and algorithms_. SIAM J. Optim., 23, (2013), 1480-1509.
  * [7] A. Beck and N. Hallak. _On the minimization over sparse symmetric sets projections, optimality conditions, and algorithms_. Math. Oper. Res., 41, (2016), 196-223.
  * [8] M. Benko, M. Červinka, and T. Hoheisel. _Sufficient conditions for metric subregularity of constraint systems with applications to disjunctive and ortho-disjunctive programs_. Set-Valued Var. Anal., 30, (2022), 143-177.
  * [9] M. Benko and H. Gfrerer. _On estimating the regular normal cone to constraint systems and stationarity conditions_. Optim., 66, (2017), 61-92.
  * [10] M. Benko and H. Gfrerer. _New verifiable stationarity concepts for a class of mathematical programs with disjunctive constraints_. Optim., 67, (2018), 1-23.
  * [11] M. Benko, H. Gfrerer, and J. Outrata. _Calculus for directional limiting normal cones and subdifferentials_. Set-Valued Var. Anal., 27, (2019), 713-745.
  * [12] M. Benko, H. Gfrerer, J. J. Ye, J. Zhang, and J. Zhou. _Second-order optimality conditions for general nonconvex optimization problems and variational analysis of disjunctive systems_. arXiv:2203.10015.
  * [13] D. Bertsimas and R. Shioda. _Algorithm for cardinality-constrained quadratic optimization_. Comput. Optim. Appl., 43, (2009), 1-22.
  * [14] J. F. Bonnans and A. Shapiro. _Perturbation Analysis of Optimization Problems_. Springer, New York, 2000.
  * [15] M. Bucher and A. Schwartz. _Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems_. J. Optim. Theory Appl., 178, (2018), 383-410.
  * [16] O. P. Burdakov, C. Kanzow, and A. Schwartz. _Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method_. SIAM J. Optim., 26, (2016), 397-425.
  * [17] M. Červinka, C. Kanzow, and A. Schwartz. _Constraint qualifications and optimality conditions for optimization problems with cardinality constraints_. Math. Program., 160, (2016), 353-377.
  * [18] F. H. Clarke. _Optimization and Nonsmooth Analysis_. Classics Appl. Math. 5, SIAM, Philadelphia, PA, 1990.
  * [19] M. L. Flegel, C. Kanzow, and J. Outrata. _Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints_. Set-Valued Var. Anal., 15, (2007), 139-162.
  * [20] H. Gfrerer. _On directional metric subregularity and second-order optimality conditions for a class of nonsmooth mathematical programs_. SIAM J. Optim. 23, (2013), 632-665.
  * [21] H. Gfrerer. _Optimality conditions for disjunctive programs based on generalized differentiation with application to mathematical programs with equilibrium constraints_. SIAM J. Optim., 24, (2014), 898-931.
  * [22] H. Gfrerer. _Linearized M-stationarity conditions for general optimization problems_. Set-Valued Var. Anal., 27, (2019), 819-840.
  * [23] I. Ginchev and B. S. Mordukhovich. _On directionally dependent subdifferentials_. C.R. Bulg. Acad. Sci., 64, (2011), 497–508.
  * [24] R. Henrion and J. Outrata. _On calculating the normal cone to a finite union of convex polyhedra_. Optim., 57, (2008), 57-78.
  * [25] C. Kanzow, A. B. Raharja, and A. Schwartz. _Sequential optimality conditions for cardinality-constrained optimization problems with applications_. Comput. Optim. Appl., 80, (2021), 185-211.
  * [26] E.H.M. Krulikovski, A.A. Ribeiro and M. Sachine. _On the weak stationarity conditions for mathematical programs with cardinality constraints: a unified approach_. Appl. Math. Optim., 84, (2021), 3451-3473.
  * [27] Y.-C. Liang and J. J. Ye. _Optimality conditions and exact penalty for mathematical programs with switching constraints_. J. Optim. Theory Appl., 190, (2021), 1-31.
  * [28] Z. Lu. _Optimization over sparse symmetric sets via a nonmonotone projected gradient method_ , ArXiv: 1509.08581, (2015).
  * [29] Z. Q. Luo, J. S. Pang, and D. Ralph. _Mathematical Programs with Equilibrium Constraints._ Cambridge University Press, Cambridge, 1996.
  * [30] P. Mehlitz. _On the linear independence constraint qualification in disjunctive programming_. Optim., 69, (2020), 2241-2277.
  * [31] P. Mehlitz. _Stationarity conditions and constraint qualifications for mathematical programs with switching constraints_. Math. Program., 181, (2020), 149-186.
  * [32] P. Mehlitz. _Asymptotic stationarity and regularity for nonsmooth optimization problems_. J. Nonsmooth Anal. Optim., 1, (2020), 6575.
  * [33] B. S. Mordukhovich. _Variational Analysis and Generalized Differentiation, Vol. 1: Basic Theory, Vol. 2: Applications_. Springer, Berlin, 2006.
  * [34] B. S. Mordukhovich. _Variational Analysis and Applications_. Monographs in Mathematics, Springer, Cham, Switzerland, 2018.
  * [35] L. L. Pan, N. H. Xiu, and S. L. Zhou. _On solutions of sparsity constrained optimization_. J. Oper. Res. Soc. China, 3, (2015), 421-439.
  * [36] L. L. Pan, N. H. Xiu, and J. Fan. _Optimality conditions for sparse nonlinear programming_. Sci. China Math., 60, (2017), 759-776.
  * [37] R. T. Rockafellar and R. J. Wets. _Variational Analysis_. Springer, Berlin, 1998.
  * [38] A. M. Tillmann, D. Bienstock, A. Lodi, and A. Schwartz. _Cardinality minimization, constraints, and regularization: a survey_. Preprint arXiv:2106.09606.
  * [39] M. Xu and J. J. Ye. _Relaxed constant positive linear dependence constraint qualification for disjunctive programs_. Preprint arXiv:2204.09869.
  * [40] J.J. Ye. _Exact penalty principle_. Nonlinear. Anal., 75, (2012), 1642-1654.
  * [41] J. J. Ye and J. Zhou. _Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems_. Math. Program., 171, (2018), 361-395.