# Almost simple groups as flag-transitive automorphism groups of $2$-designs
with $\lambda=2$

Seyed Hassan Alavi  Seyed Hassan Alavi, Department of Mathematics, Faculty of
Science, Bu-Ali Sina University, Hamedan, Iran<EMAIL_ADDRESS>and
<EMAIL_ADDRESS>
###### Abstract.

In this article, we study $2$-designs with $\lambda=2$ admitting a flag-
transitive almost simple automorphism group with socle a finite simple
exceptional group of Lie type, and we prove that such a $2$-design does not
exist. In conclusion, we present a classification of $2$-designs with
$\lambda=2$ admitting flag-transitive and point-primitive automorphism groups
of almost simple type, which states that such a $2$-design belongs to an
infinite family of $2$-designs with parameter set $((3^{n}-1)/2,3,2)$ and
$X=\mathrm{PSL}_{n}(3)$ for some $n\geqslant 3$, or it is isomorphic to the
$2$-design with parameter set $(6,3,2)$, $(7,4,2)$, $(10,4,2)$, $(10,4,2)$,
$(11,5,2)$, $(28,7,2)$, $(28,3,2)$, $(36,6,2)$, $(126,6,2)$ or $(176,8,2)$.

###### Key words and phrases:

$2$-design, automorphism group, flag-transitive, point-primitive, finite
exceptional simple group

######  Mathematics Subject Classification:

05B05; 05B25; 20B25

##  1\. Introduction

In $1990$, Buekenhout, Delandtsheer, Doyen, Kleidman, Liebeck and Saxl [10]
classified all flag-transitive linear spaces apart from those admitting a one-
dimensional affine automorphism group. Since then, there have been numerous
efforts to classify $2$-designs $\mathcal{D}$ with parameters $(v,k,2)$
admitting flag-transitive automorphisms group $G$. In the case where
$\mathcal{D}$ is symmetric, in a series of papers, Regueiro [31, 27, 29, 30,
28] proved that either $(v,k)\in\\{(7,4),(11,5),(16,6)\\}$, or
$G\leqslant\mathrm{A}\Gamma\mathrm{L}_{1}(q)$ for some odd prime power $q$.
Liang and Zhou [23] proved that, if $\mathcal{D}$ is non-symmetric and $G$ is
point-primitive, then $G$ is affine or almost simple. The case when $G$ is
point-imprimitive has recently been treated by Devillers, Liang, Praeger and
Xia [16], and they proved that if $G$ is flag-transitive and point-
imprimitive, then $\mathcal{D}$ is one of the two known symmetric
$2$-$(16,6,2)$ designs, one with automorphism group $2^{4}\mathrm{S}_{6}$ and
point-stabiliser
$(\mathbb{Z}_{2}\times\mathbb{Z}_{8})(\mathrm{S}_{4}{\cdot}2)$ and the other
with automorphism group $\mathrm{S}_{6}$ and point-stabiliser
$\mathrm{S}_{4}{\cdot}2$, see also [28, Examples 1.2]. Therefore, by [16,
Theorem 1.1], the study of flag-transitive $2$-$(v,k,2)$ designs reduces to
the case where the automorphism group $G$ is point-primitive of affine or
almost simple type. This paper is devoted to studying $2$-$(v,k,\lambda)$
designs admitting flag-transitive automorphism groups of almost simple type.

Regueiro [31, 27, 29, 30, 28] classified all such examples when the design is
symmetric (up to those admitting a one-dimensional affine automorphism group).
In the non-symmetric case, Liang and Zhou [24, 23] have dealt with the cases
where the socle of $G$ is a sporadic simple group or an alternating group.
Devillers, Liang, Praeger and Xia [16] have studied the case where $G$ has
socle $\mathrm{PSL}_{n}(q)$ with $n\geqslant 3$, and proved that either
$\mathcal{D}$ is the complement of the Fano plane, or $\mathcal{D}$ is the
unique $2$-design with parameters $(v,3,2)$, where $G$ has socle
$\mathrm{PSL}_{n}(3)$ and $v=(3^{n}-1)/2$ for some $n\geqslant 3$, see [16,
Theorem 1.2]. The case where $G$ has socle a finite classical group has been
treated recently in [7]. In this paper, we finish the almost simple case, and
prove that we have no example when the socle is a finite simple exceptional
group:

######  Theorem 1.1.

Let $\mathcal{D}=(\mathcal{P},\mathcal{B})$ be a nontrivial $(v,k,2)$ design,
and let $G$ be a flag-transitive and point-primitive automorphism group of
$\mathcal{D}$ whose socle $X$ is a non-abelian finite simple group. Then $X$
cannot be a finite simple exceptional group of Lie type.

Theorem 1.1 together with the main results in [7, 16, 23, 24] gives a
classification of nontrivial $2$-designs with $\lambda=2$ admitting flag-
transitive and point-primitive almost simple classical automorphism groups:

######  Corollary 1.2.

Let $\mathcal{D}$ be a nontrivial $2$-design with parameters $(v,k,2)$ and let
$G$ be a flag-transitive and point-primitive almost simple automorphism group
with socle $X$. Then $(\mathcal{D},X)$ is as in one of the lines in Table 1,
or $\mathcal{D}$ is the $2$-design with parameters $((3^{n}-1)/2,3,2)$ and
$X=\mathrm{PSL}_{n}(3)$ for some $n\geqslant 3$ constructed as in [16, Theorem
1.2].

Table 1. Some flag-transitive and point-primitive nontrivial $2$-design with $\lambda=2$ Line | $v$ | $b$ | $r$ | $k$ | $\lambda$ | $X$ | $\mathrm{Aut}(\mathcal{D})$ | References
---|---|---|---|---|---|---|---|---
$1$ | $6$ | $10$ | $5$ | $3$ | $2$ | $\mathrm{PSL}_{2}(4)\cong\mathrm{PSL}_{2}(5)\cong\mathrm{Alt}_{5}$ | $\mathrm{PSL}_{2}(5)$ | [4, 5]
$2$ | $7$ | $7$ | $4$ | $4$ | $2$ | $\mathrm{PSL}_{2}(7)\cong\mathrm{PSL}_{3}(2)$ | $\mathrm{PSL}_{2}(7)$ | [3, 11, 18, 29]
$3$ | $10$ | $15$ | $6$ | $4$ | $2$ | $\mathrm{PSL}_{2}(4)\cong\mathrm{PSL}_{2}(5)\cong\mathrm{Alt}_{5}$ | $\mathrm{PSL}_{2}(4):2$ | [24]
$4$ | $10$ | $15$ | $6$ | $4$ | $2$ | $\mathrm{PSL}_{2}(9)\cong\mathrm{Alt}_{6}$ | $\mathrm{PSL}_{2}(9):2$ | [24]
$5$ | $11$ | $11$ | $5$ | $5$ | $2$ | $\mathrm{PSL}_{2}(11)$ | $\mathrm{PSL}_{2}(11)$ | [3, 4, 5]
$6$ | $28$ | $36$ | $9$ | $7$ | $2$ | $\mathrm{PSL}_{2}(8)$ | $\mathrm{PSL}_{2}(8):3$ | [4, 5]
$7$ | $28$ | $252$ | $27$ | $3$ | $2$ | $\mathrm{PSU}_{3}(3)$ | $\mathrm{PSU}_{3}(3):2$ | [4, 5]
$8$ | $36$ | $84$ | $14$ | $6$ | $2$ | $\mathrm{PSL}_{2}(8)$ | $\mathrm{PSL}_{2}(8):3$ | [7]
$9$ | $126$ | $1050$ | $50$ | $6$ | $2$ | $\mathrm{PSU}_{3}(5)$ | $\mathrm{PSU}_{3}(5):2$ | [7]
$10$ | $176$ | $1100$ | $50$ | $8$ | $2$ | $\mathrm{HS}$ | $\mathrm{HS}$ | [23]

In order to prove Theorem 1.1 in Section 3, we first observe that the group
$G$ is point-primitive, and so the point-stabiliser $H$ is maximal in $G$. In
particular, flag-transitivity of $G$ implies that $H$ is large, that is to
say, $|G|\leqslant|H|^{3}$, and then we can apply [6, Theorem 1.6] and [8] in
which the large maximal subgroups of almost simple groups whose socle $X$ is a
finite simple exceptional group of Lie type are determined. We then analyse
all possible cases and prove that the only possible designs are those given in
Theorem 1.1.

###  1.1. Definitions and notation

All groups and incidence structures in this paper are finite. We here write
$\mathrm{Alt}_{n}$ and $\mathrm{Sym}_{n}$ for the alternating group and the
symmetric group on $n$ letters, respectively, and we denote by “$[n]$” a group
of order $n$. Recall that we in this paper adopt the standard Lie notation for
groups of Lie type. For example, we sometimes write $A_{n-1}(q)$ and
$A_{n-1}^{-}(q)$ in place of $\mathrm{PSL}_{n}(q)$ and $\mathrm{PSU}_{n}(q)$,
respectively, $D_{n}^{-}(q)$ instead of $\mathrm{P}\Omega_{2n}^{-}(q)$, and
$E_{6}^{-}(q)$ for ${}^{2}\\!E_{6}(q)$. We assume that $q>2$ when $G=G_{2}(q)$
since $G_{2}(2)$ is not simple and $G_{2}(2)^{\prime}\cong A^{-}_{2}(3)$.
Moreover, we view the Tits group ${}^{2}\\!F_{4}(2)^{\prime}$ as a sporadic
group. We write $P_{i}$ to denote a standard maximal parabolic subgroup
corresponding to deleting the $i$-th node in the Dynkin diagram of $X$, where
we label the Dynkin diagram in the usual way, following [19, p. 180]. We also
use $P_{i,j}$ to denote the intersection of appropriate parabolic subgroups of
type $P_{i}$ and $P_{j}$. For a given positive integer $n$ and a prime divisor
$p$ of $n$, we denote the $p$-part of $n$ by $n_{p}$, that is to say,
$n_{p}=p^{t}$ if $p^{t}\mid n$ but $p^{t+1}\nmid n$. Further notation and
definitions in both design theory and group theory are standard and can be
found, for example, in [12, 17, 19, 21].

##  2\. Preliminaries

In this section, we state some useful facts in both design theory and group
theory.

######  Lemma 2.1.

Let $\mathcal{D}$ be a $2$-design with parameters set $(v,k,\lambda)$. Then

  1. (a)

$r(k-1)=\lambda(v-1)$;

  2. (b)

$vr=bk$;

  3. (c)

$v\leqslant b$ and $k\leqslant r$;

  4. (d)

$\lambda v<r^{2}$.

###### Proof.

Parts (a) and (b) follow immediately by simple counting. The inequality
$v\leqslant b$ is the Fisher’s inequality [15, p. 57], and so by applying part
(b), we have that $k\leqslant r$. By part (a) and (c), we easily observe that
$r^{2}>r(k-1)=\lambda(v-1)>\lambda v$, and so $\lambda v<r^{2}$, as desired. ∎

Lemma 2.2 below is an elementary result on maximal subgroups of finite almost
simple groups.

######  Lemma 2.2.

[3, Lemma 2.2] Let $G$ be an almost simple group with socle $X$, and let $H$
be maximal in $G$ not containing $X$. Then $G=HX$ and $|H|$ divides
$|\mathrm{Out}(X)|\cdot|H\cap X|$.

######  Lemma 2.3.

Suppose that $\mathcal{D}$ is block design with parameters $(v,k,\lambda)$
admitting a flag-transitive and point-primitive almost simple automorphism
group $G$ with socle $X$ of Lie type in characteristic $p$. Suppose also that
the point-stabiliser $G_{\alpha}$ does not contain $X$ and is not a parabolic
subgroup of $G$. Then $\gcd(p,v-1)=1$.

###### Proof.

Note that $G_{\alpha}$ is maximal in $G$, then by Tits’ Lemma [34, 1.6], $p$
divides $|G:G_{\alpha}|=v$, and so $\gcd(p,v-1)=1$. ∎

If a group $G$ acts on a set $\mathcal{P}$ and $\alpha\in\mathcal{P}$, the
_subdegrees_ of $G$ are the sizes of the orbits of the action of the point-
stabiliser $G_{\alpha}$ on $\mathcal{P}$.

######  Lemma 2.4.

[26, 3.9] If $X$ is a group of Lie type in characteristic $p$, acting on the
set of cosets of a maximal parabolic subgroup, and $X$ is not $A_{n-1}(q)$,
$D_{n}(q)$ (with $n$ odd), or $E_{6}(q)$, then there is a unique subdegree
which is a power of $p$.

######  Remark 2.5.

We remark that even in the cases excluded in Lemma 2.4, many of the maximal
parabolic subgroups still have the property as asserted, see the proof of
Lemma 2.6 in [33]. In particular, for an almost simple group $G$ with socle
$X=E_{6}(q)$, if $G$ contains a graph automorphism or $H=P_{i}$ with $i=2$ or
$4$, the conclusion of Lemma 2.4 is still true.

######  Lemma 2.6.

Let $\mathcal{D}$ be a $2$-design with parameters set $(v,k,\lambda)$, and let
$\alpha$ be a point of $\mathcal{D}$. If $G$ a flag-transitive automorphism
group of $\mathcal{D}$, then

  1. (a)

$r\mid|G_{\alpha}|$;

  2. (b)

$r\mid\lambda d$, for all nontrivial subdegrees $d$ of $G$.

###### Proof.

Since $G$ is flag-transitive, the point stabiliser $G_{\alpha}$ is transitive
on the set of all blocks containing $\alpha$, and so
$r=|G_{\alpha}:G_{\alpha,B}|$. Thus $r$ divides $|G_{\alpha}|$. Part (b) is
proved in [14, p. 9]. ∎

######  Lemma 2.7.

[15, 2.2.5] Let $\mathcal{D}$ be a $2$-$(v,k,\lambda)$ design. If
$\mathcal{D}$ satisfies $r=k+\lambda$ and $\lambda\leqslant 2$, then
$\mathcal{D}$ embeds into a symmetric $2$-$(v+k+\lambda,k+\lambda,\lambda)$
design.

######  Lemma 2.8.

[16, Proposition 4.1] Let $\mathcal{S}=(\mathcal{P},\mathcal{L})$ be a
$2$-$(v,k,1)$ design with $k\geqslant 3$, and $\ell\in\mathcal{L}$, and let
$G\leqslant\mathrm{Aut}(\mathcal{S})$. Let also
$\mathcal{B}=\\{\ell\setminus\\{\alpha\\}\mid\ell\in\mathcal{L},\
\alpha\in\ell\\}$. Then $\mathcal{D}(\mathcal{S})=(\mathcal{P},\mathcal{B})$
is a non-symmetric $2$-$(v,k-1,k-2)$ design and $G$ is a subgroup of
$\mathrm{Aut}(\mathcal{D}(\mathcal{S}))$. Moreover, if $G$ is flag-transitive
on $\mathcal{S}$ and $G_{\ell}$ is $2$-transitive on $\ell$, then $G$ is flag-
transitive and point-primitive on $\mathcal{D}(\mathcal{S})$.

##  3\. Proof of the main result

Suppose that $\mathcal{D}$ is a nontrivial $(v,k,\lambda)$ design admitting a
flag-transitive almost simple automorphism group $G$ with socle $X$ being a
finite simple exceptional group of Lie type. If $r$ is odd, then $r$ is
coprime to $\lambda=2$, and so by [1, Theorem 1.1], we have that
$X={}^{2}\\!B_{2}(q)$ or $X={}^{2}\\!G_{2}(q)$ but in each of these cases
$\lambda$ cannot be $2$ (see also [2]). Therefore, in what follows, we may
assume that $r$ is even.

Since $G$ is point-transitive, it follows from Lemma 2.2 and the point-
stabiliser Theorem that

$\displaystyle v=\frac{|X|}{|H\cap X|}.$ (3.1)

For a point-stabiliser $H=G_{\alpha}$ of the automorphism group $G$ of a flag-
transitive design $\mathcal{D}$, the subgroup $H$ is transitive on the set of
blocks containing $\alpha$, and so $r$ divides $|H|$. On the other hand, the
facts that $r(k-1)=\lambda(v-1)$ and $r>k$ imply that $\lambda v<r^{2}$. Thus
$\lambda|G|\leqslant|H|^{3}$, and hence the subgroup $H$ is _large_ in $G$,
that is to say, $|H|^{3}\geqslant|G|$. We now apply [6, Theorem 1.6] and
obtain the list of possibilities for the point-stabiliser subgroup $H$ of $G$,
and in conclusion, $H$ is either parabolic, or one of the subgroups recorded
in [1, Tables 2-3]. For each such a possibility, we note by Lemmas 2.1(a) and
2.6 that $r$ divides $|H|$, $2(v-1)$ and $2d$ for all nontrivial subdegrees
$d$ of $G$. This enables us to find an upper bound $u_{r}$ for $r/2$. We can
moreover obtain a lower bound $\ell_{v}$ for $v$. The values $\ell_{v}$ and
$u_{r}$ can be read of from [1, Tables 2-3] with noting that in Table 3 of
[1], the values of $v$ and $r$ are listed for small $q$.

If $X$ and $H\cap X$ are as in Table 3 of [1], then the possibilities of the
parameters $v$ and $r$ are as in the third and fourth columns of the same
table, respectively. For each $v$, we know that $r$ divides $2(v-1)$, and so
for each pair $(v,r)$, the parameter $b$ must divide $vr$. For each divisor
$b$ of $vr$, we obtain the parameter $k$ by $k=vr/b$, and finally, for each
$(v,b,r,k)$, we can then find $\lambda:=r(k-1)/(v-1)$ which has to be $2$.
However, the possibilities recorded in [1, Table 3] give rise to no possible
parameter set.

For each case recorded in Table 2 of [1], we know a lower bound $\ell_{v}$ of
$v$ and an upper bound $u_{r}$ of $r/2$. Thus, $r\leqslant 2u_{r}$, and since
$2v\leqslant r^{2}$ by Lemma 2.1(d), it follows that $\ell_{v}<2u_{r}^{2}$.
Running through all the possibilities recorded in [1, Table 2], we observe
that $2u_{r}^{2}<\ell_{v}$ except for the case where $X=G_{2}(q)$ and $H\cap
X=A_{2}^{\epsilon}:2$. In this case $v=q^{3}(q^{3}+\epsilon 1)/2$ and $r$
divides $2(q^{3}-\epsilon 1)/\gcd(2,q-1)$. Then there exists a positive
integer $m$ such that $rm\cdot\gcd(2,q-1)=2(q^{3}-\epsilon 1)$, and so the
condition $\lambda v<r^{2}$ implies that

$\displaystyle q^{3}(q^{3}+\epsilon 1)<\frac{4(q^{3}-\epsilon
1)^{2}}{m^{2}\cdot\gcd(2,q-1)^{2}}.$

This inequality is true when $m=1$, or $(m,\epsilon)=(2,-)$ and $q$ is even.
Let $q$ be odd and $(m,\epsilon)=(1,+)$. Then $r=q^{3}-1$ and $k=q^{3}+3$,
which contradicts Lemma 2.1(c). Let $q$ be odd and $(m,\epsilon)=(1,-)$, or
$q$ be even and $(m,\epsilon)=(2,-)$. Then $v=q^{3}(q^{3}-1)/2$,
$b=q^{3}(q^{3}+1)/2$, $r=q^{3}+1$ and $k=q^{3}-1$, and so $r=k+\lambda$ which
is impossible by Lemma 2.7 and [31]. Let now $q$ be even and
$(m,\epsilon)=(1,+)$. Then $v=q^{3}(q^{3}+1)/2$, $r=2(q^{3}-1)$ and
$k=(q^{3}+4)/2$, and so Lemma 2.1(b) implies that
$b=(2q^{9}-2q^{3})/(q^{3}+4)$. Since
$2q^{9}-2q^{3}=(2q^{6}-8q^{3}+30)(q^{3}+4)-120$ and $b$ is a positive integer,
it follows that $q^{3}+4$ is a divisor of $120$, which is correct if $q=2$,
however, $G_{2}(2)$ is not simple, which is a contradiction. Let finally $q$
be even and $(m,\epsilon)=(1,-)$. Then $v=q^{3}(q^{3}-1)/2$, $b=2(q^{6}-1)$,
$r=2(q^{3}+1)$ and $k=q^{3}/2$ and $\lambda=2$, when $H_{0}:=H\cap
X=\mathrm{SU}_{3}(q):2$ with $q$ even. Let $B$ be a block of $\mathcal{D}$
containing $\alpha$, and let $N$ be a maximal subgroup of $G$ containing the
block-stabiliser $K:=G_{B}$. Then $|G:N|$ is divisible by $b=2(q^{6}-1)$. By
inspecting the index of maximal subgroups of $G$ from [13], we conclude that
$N\cap X$ is (isomorphic) to a parabolic subgroup $q^{1+4}:\mathrm{GL}_{2}(q)$
or $q^{2+3}:\mathrm{GL}_{2}(q)$. Suppose now that $H=H_{0}:T$, where
$T\leqslant\mathrm{Out}(X)$ and $H_{0}=\mathrm{SU}_{3}(q):2$, and let
$L:=H\cap K$. Then $L\cap\mathrm{SU}_{3}(q)$ is a subgroup of
$\mathrm{SU}_{3}(q)$ of index $(q^{3}+1)/|T|$, and so by [9, Table 8.5], we
conclude that $L\cap\mathrm{SU}_{3}(q)$ is (isomorphic) to a maximal parabolic
subgroup $q^{1+3}:(q^{2}-1)$ of index $q^{3}+1$ in $\mathrm{SU}_{3}(q)$. This
implies that $|T|=1$, and so $G=X$ and $H=H_{0}=\mathrm{SU}_{3}(q):2$,
$N=[q^{5}]:\mathrm{GL}_{2}(q)$ and $L=q^{1+2}:(q^{2}-1)$. Hence, $L$ contains
an element of order $q^{2}-1$, however $N$ has no such an element, which is a
contradiction.

It remains to consider the case where $H$ is a parabolic subgroup of $G$. In
what follows, we further assume that $K=G_{B}$ and $K_{0}=K\cap X$, where $B$
is a block containing $\alpha$. We now continue our argument by case by case
analysis. We note here that the value of the parameter $v$ in each case, can
be read off from [6, Table 4].

Suppose that $X={}^{2}\\!B_{2}(q)$ and $H\cap X=q^{2}{:}(q-1)$ with $q=2^{a}$
for some odd $a\geqslant 3$. Then by (3.1), we have that $v=q^{2}+1$, and so
$r(k-1)=2(v-1)=2q^{2}=2^{2a+1}$. Let $r=2^{c}$. Then $k=2^{2a-c+1}+1$. Note
that $b=rv/k$, $v=q^{2}+1$ and $G$ is transitive on the set of blocks of
$\mathcal{D}$. Then $|G:K|=b=2^{c}(q^{2}+1)/k$, where $K=G_{B}$ with
$\alpha\in B$. Assume now that $N_{0}$ is a maximal subgroup of $X$ containing
$K_{0}=K\cap X$. Then $|X:N_{0}|$ must divide $b$. The knowledge of maximal
subgroups of $X={}^{2}\\!B_{2}(q)$ shows that $K_{0}$ embeds into a parabolic
subgroup $N_{0}\cong q^{2}{:}(q-1)$ of index $q^{2}+1$. Moreover, $|X:K_{0}|$
divides $b=2^{c}(q^{2}+1)/k$, and since $|X:N_{0}|=q^{2}+1$ divides
$|X:K_{0}|$, it follows that $k$ divides $2^{c}$, which is impossible as $k$
is odd.

Suppose that $X={}^{2}\\!G_{2}(q)$ and $H\cap X=q^{3}{:}(q-1)$ with
$q=p^{a}=3^{2m+1}\geqslant 27$. By (3.1), we have that $v=q^{3}+1$. Since $r$
is even, it follows from Lemma 2.1(a) that $r$ divides $\lambda(v-1)=2q^{3}$,
and so $r=2\cdot 3^{c}$ for some $1\leqslant c\leqslant 3a$. Again Lemma
2.1(a) implies that $k=3^{t}+1$, where $t:=3a-c$. We first observe that
$t\geqslant 1$ as $k\geqslant 3$. Since $v=q^{3}+1$ and $k=3^{t}+1$, it
follows that $|G:K|=b=vr/k=2\cdot 3^{c}\cdot(q^{3}+1)/(3^{t}+1)$, where
$K=G_{B}$ with $\alpha\in B$. Assume now that $N$ is a maximal subgroup of $X$
containing $K$. Then $|G:N|$ divides $b$. The list of maximal subgroups of
$X=\\!^{2}\\!G_{2}(q)$ can be read off from [9, Table 8.43] (see also [22]),
and so by inspecting the index of the maximal subgroups $N$ in $G$, we
conclude that $K$ is contained in $N=(\langle z\rangle\times A_{1}(q)):T$,
where $T\leqslant\mathrm{Out}(X)$ and $z$ is an involution in $X$. In this
case, as $|G:N|=q^{2}(q^{2}-q+1)$ divides $b=2\cdot 3^{c}\cdot(q^{3}+1)/k$, it
follows that $k=3^{t}+1$ divides $2(q+1)$. Then $t\leqslant a$, or
equivalently, $c\geqslant 2a$. Moreover, if $N_{0}=N\cap X$, then
$N_{0}=\langle z\rangle\times A_{1}(q)$ is a maximal subgroup of $X$
containing $K_{0}=K\cap X$. Let $\beta$ and $\gamma$ be two distinct points in
$B\setminus\\{\alpha\\}$. Then $X_{\alpha,\beta}$ is isomorphic to a cyclic
group of order $q-1$ which has index $q^{3}$ in $H_{0}$, see [35] or [32,
Lemma 3.2]. Moreover, $X_{\alpha,\beta,\gamma}$ is generated by an involution,
and hence the nontrivial $X_{\alpha,\beta}$-orbits are of length $q-1$ or
$(q-1)/2$ depending on whether $\gamma$ is fixed by $X_{\alpha,\beta}$ or not,
respectively. Let now $C\neq B$ be the block of $\mathcal{D}$ passing through
both $\alpha$ and $\beta$. Then $B\cup C$ is fixed by $X_{\alpha,\beta}$, and
so $J:=(B\cup C)\setminus\\{\alpha,\beta\\}$ is a union of nontrivial
$X_{\alpha,\beta}$-orbits. Thus $(q-1)/2$ divides $|J|=2(k-1)-|B\cap C|=2\cdot
3^{t}-|B\cap C|$. As $|B\cap C|\geqslant 2$, we have that $|J|\leqslant 2\cdot
3^{t}-2$, and so $(q-1)/2\leqslant 2\cdot 3^{t}-2$. Thus $3^{a}+3\leqslant
4\cdot 3^{t}$. Since $t\leqslant a$, this inequality holds only for $t=a-1$ or
$a$, and so $k=(q+3)/3$ or $q+1$, respectively. If $k=(q+3)/3$, then
$b=18q^{2}(q^{3}+1)/(q+3)$, and so $(q+3)/3=3^{a-1}+1$ must divide
$2(3^{3a}+1)$. Since $\gcd(3^{a-1}+1,3^{3a}+1)=2$, it follows that $3^{a-1}+1$
divides $4$, and so $a=1$ or $2$, which is impossible. Thus, $k=q+1$, and
hence $r=2q^{2}$ and $b=2q^{2}(q^{2}-q+1)$. This also requires
$K_{0}=A_{1}(q)$ and $K=A_{1}(q):T$. Therefore, $N_{0}\cap H_{0}=\langle
z\rangle\times(q:\frac{q-1}{2})$ by [32, Lemma 3.2], and so
$L_{0}:=X_{\alpha,B}=H_{0}\cap K_{0}=q:\frac{q-1}{2}$ and $L:=H\cap
K=(q:\frac{q-1}{2}):T$. Note that $K_{0}$ acts $2$-transitively on $B$. Then
$X$ is also flag-transitive. Note also that $N_{0}=C_{X}(z)$ is the line-
stabiliser $X_{\ell}$ of the Ree Unital $\mathcal{U}_{R}(q)$, where the line
$\ell$ contains all $q+1$ fixed points of the involution $z$. Since
$K_{0}=X_{B}$ is a normal subgroup of $X_{\ell}=N_{0}$, it follows that $\ell$
is a union of $X_{B}$-orbits. Since $|\ell|=|B|=q+1$ and $z$ fixes $\alpha\in
B$ (in fact it fixes at least two points in $B$), we conclude that $B=\ell$,
and so $z$ fixes $B$, that is to say, $z\in X_{B}=K_{0}$, which is a
contradiction.

Table 2. Some parameters for some parabolic subgroups of almost simple groups with socle $X$. Line | $X$ | $H\cap X$ | $v$ | $|v-1|_{p}$ | Comments
---|---|---|---|---|---
$1$ | ${}^{3}\\!D_{4}(q)$ | $P_{1}$ | $\Phi_{2}\Phi_{3}\Phi_{6}\Phi_{12}$ | $q^{3}$ |
$2$ | ${}^{2}\\!F_{4}(q)$ | $P_{1}$ | $\Phi_{2}\Phi_{4}^{2}\Phi_{6}\Phi_{12}$ | $q^{2}$ |
$3$ | $F_{4}(q)$ | $P_{1,4}$ | $\Phi_{2}^{2}\Phi_{3}^{2}\Phi_{4}\Phi_{6}^{2}\Phi_{8}\Phi_{12}$ | $2q$ |  $q=2^{a}$, $H$ contains graph automorphism
$4$ | $F_{4}(q)$ | $P_{2,3}$ | $\Phi_{2}^{2}\Phi_{3}^{2}\Phi_{4}^{2}\Phi_{6}^{2}\Phi_{8}\Phi_{12}$ | $2q$ |  $q=2^{a}$, $H$ contains graph automorphism
$5$ | $E_{6}(q)$ | $P_{1,6}$ | $\Phi_{3}^{2}\Phi_{5}\Phi_{6}\Phi_{8}\Phi_{9}\Phi_{12}$ | $\gcd(2,p)q$ |  $H$ contains graph automorphism
$6$ | $E_{6}(q)$ | $P_{3,5}$ | $\Phi_{2}\Phi_{3}^{2}\Phi_{4}^{2}\Phi_{5}\Phi_{6}^{2}\Phi_{8}\Phi_{9}\Phi_{12}$ | $\gcd(2,p)q$ |  $H$ contains graph automorphism
Note: |  $\Phi_{n}:=\Phi_{n}(q)$ is the $n$-th cyclotomic polynomial with $q=p^{a}$ and $p$ prime.

Suppose that $X=E_{6}(q)$ and $H\cap X=P_{1}$. Then $H\cap
X=[q^{16}]{:}D_{5}(q)\cdot(q-1)$. Then $v=(q^{8}+q^{4}+1)(q^{9}-1)/(q-1)$.
Note by [25] that $G$ has nontrivial subdegrees $q(q^{8}-1)(q^{3}+1)/(q-1)$
and $q^{8}(q^{5}-1)(q^{4}+1)/(q-1)$, and so by Lemma 2.6(b), we conclude that
$r$ divides $q(q^{4}+1)$, and so Lemma 2.1(d) implies that $v<r^{2}<q^{12}$,
which is a contradiction.

Suppose that $X=E_{6}(q)$ and $H\cap X=P_{3}$. Then $H\cap
X=[q^{25}]{:}A_{1}(q)A_{4}(q){\cdot}(q-1)$. Then
$v=(q^{3}+1)(q^{4}+1)(q^{9}-1)(q^{12}-1)/(q-1)(q^{2}-1)$. It follows from [20]
that $X$ has subdegrees $q(q^{5}-1)(q^{4}-1)/(q-1)^{2}$ and
$q^{13}(q^{5}-1)/(q-1)$. Moreover, by Lemmas 2.1 and 2.6, the parameter $r$ is
a divisor of $12aq(q^{5}-1)/(q-1)$, but then $2v>r^{2}$, which is a
contradiction.

We finally consider the remaining cases. For each remaining $(X,H\cap X)$, the
$p$-part $|v-1|_{p}$ is $q$ except for those listed in Table 2 for which
$|v-1|_{p}$ is recorded in the fifth column of the same table. Note by Lemma
2.4 and Remark 2.5 that $G$ has a unique prime power subdegree $p^{n}$. Then
by Lemmas 2.1 and 2.6, $r$ must divide $2\gcd(v-1,p^{n})$ implying that $r$ is
a divisor of $2u_{r}$ where $u_{r}:=|v-1|_{p}$. Since $2v<r^{2}$, we conclude
that $v<2(|v-1|_{p})^{2}$, however, this inequality does not hold for all the
remaining cases. For example, if $X={}^{3}\\!D_{4}(q)$ and $H\cap X=P_{1}$.
Then $H\cap X=[q^{11}]{:}\mathrm{SL}_{2}(q){\cdot}(q^{3}-1)$, and so
$v=(q^{8}+q^{4}+1)(q^{3}+1)$ and $r$ divides $2|v-1|_{p}=2q^{3}$, and hence
$q^{11}<v<2r^{2}<2q^{6}$, which is a contradiction.

## Acknowledgements

The author is grateful to Alice Devillers and Cheryl E. Praeger for supporting
his visit to UWA (The University of Western Australia) during February–June
2023. He also thanks Bu-Ali Sina University for the support during his
sabbatical leave. The author thanks the reviewers for their comments and
suggestions.

##  4\. Declaration of competing interest

The author confirms that this manuscript has not been published elsewhere. It
is not also under consideration by another journal. He also confirms that
there are no known conflicts of interest associated with this publication. He
has no competing interests to declare that are relevant to the content of this
article and he confirms that availability of data and material is not
applicable. The author declares that he has no known competing financial
interests or personal relationships that could have appeared to influence the
work reported in this paper.

## References

  * [1] S. H. Alavi, Flag-transitive block designs and finite exceptional simple groups of Lie type, Graphs and Combinatorics 36 (4) (2020) 1001–1014.
URL https://doi.org/10.1007/s00373-020-02161-0

  * [2] S. H. Alavi, M. Bayat, M. Biliotti, A. Daneshkhah, E. Francot, H. Guan, A. Montinaro, F. Mouseli, P. Rizzo, D. Tian, Y. Wang, X. Zhan, Y. Zhang, S. Zhou, Y. Zhu, Block designs with ${\rm gcd}(r,\lambda)=1$ admitting flag-transitive automorphism groups, Results Math. 77 (4) (2022) Paper No. 151, 17.
URL https://doi.org/10.1007/s00025-022-01697-2

  * [3] S. H. Alavi, M. Bayat, A. Daneshkhah, Symmetric designs admitting flag-transitive and point-primitive automorphism groups associated to two dimensional projective special groups, Designs, Codes and Cryptography 79 (2) (2016) 337–351.
URL http://dx.doi.org/10.1007/s10623-015-0055-9

  * [4] S. H. Alavi, M. Bayat, A. Daneshkhah, Flag-transitive block designs and unitary groups, Monatshefte für Mathematik 193 (3) (2020) 535–553.
URL https://doi.org/10.1007/s00605-020-01421-8

  * [5] S. H. Alavi, M. Bayat, A. Daneshkhah, Correction to: Flag-transitive block designs and unitary groups, Monatsh. Math. 195 (2) (2021) 371–376.
URL https://doi.org/10.1007/s00605-021-01546-4

  * [6] S. H. Alavi, M. Bayat, A. Daneshkhah, Finite exceptional groups of Lie type and symmetric designs, Discrete Mathematics 345 (8) (2022) 112894.
URL https://www.sciencedirect.com/science/article/pii/S0012365X22001005

  * [7] S. H. Alavi, M. Bayat, A. Daneshkhah, M. Tadbirinia, Classical groups as flag-transitive automorphism groups of $2$-designs with $\lambda=2$, Submitted.
  * [8] S. H. Alavi, T. C. Burness, Large subgroups of simple groups, J. Algebra 421 (2015) 187–233.
URL http://dx.doi.org/10.1016/j.jalgebra.2014.08.026

  * [9] J. N. Bray, D. F. Holt, C. M. Roney-Dougal, The maximal subgroups of the low-dimensional finite classical groups, vol. 407 of London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 2013, with a foreword by Martin Liebeck.
URL http://dx.doi.org/10.1017/CBO9781139192576

  * [10] F. Buekenhout, A. Delandtsheer, J. Doyen, P. B. Kleidman, M. W. Liebeck, J. Saxl, Linear spaces with flag-transitive automorphism groups, Geom. Dedicata 36 (1) (1990) 89–94.
URL http://dx.doi.org/10.1007/BF00181466

  * [11] C. J. Colbourn, J. H. Dinitz (eds.), Handbook of combinatorial designs, Discrete Mathematics and its Applications (Boca Raton), 2nd ed., Chapman & Hall/CRC, Boca Raton, FL, 2007.
  * [12] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, R. A. Wilson, Atlas of finite groups, Oxford University Press, Eynsham, 1985, maximal subgroups and ordinary characters for simple groups, With computational assistance from J. G. Thackray.
  * [13] B. N. Cooperstein, Maximal subgroups of ${G}_{2}(2^{n})$, Journal of Algebra 70 (1) (1981) 23 – 36.
URL http://www.sciencedirect.com/science/article/pii/0021869381902416

  * [14] H. Davies, Flag-transitivity and primitivity, Discrete Math. 63 (1) (1987) 91–93.
URL http://dx.doi.org/10.1016/0012-365X(87)90154-3

  * [15] P. Dembowski, Finite geometries, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44, Springer-Verlag, Berlin-New York, 1968.
  * [16] A. Devillers, H. Liang, C. E. Praeger, B. Xia, On flag-transitive 2-$(v,k,2)$ designs, J. Combin. Theory Ser. A 177 (2021) 105309, 45.
URL https://doi.org/10.1016/j.jcta.2020.105309

  * [17] J. D. Dixon, B. Mortimer, Permutation groups, vol. 163 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1996.
URL http://dx.doi.org/10.1007/978-1-4612-0731-3

  * [18] W. M. Kantor, Classification of $2$-transitive symmetric designs, Graphs Combin. 1 (2) (1985) 165–166.
URL http://dx.doi.org/10.1007/BF02582940

  * [19] P. Kleidman, M. Liebeck, The subgroup structure of the finite classical groups, vol. 129 of London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 1990.
URL http://dx.doi.org/10.1017/CBO9780511629235

  * [20] V. V. Korableva, Parabolic permutation representations of groups ${E}_{6}(q)$ and ${E}_{7}(q)$, in: Combinatorial and Computational Methods in Mathematics [in Russian], Omsk Univ., Omsk, 1999, pp. 160–189.
  * [21] E. S. Lander, Symmetric designs: an algebraic approach, vol. 74 of London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 1983.
URL http://dx.doi.org/10.1017/CBO9780511662164

  * [22] V. M. Levchuk, Y. N. Nuzhin, The structure of Ree groups, Algebra i Logika 24 (1) (1985) 26–41, 122.
  * [23] H. Liang, S. Zhou, Flag-transitive point-primitive automorphism groups of nonsymmetric $2$-$(v,k,2)$ designs, J. Combin. Des. 24 (9) (2016) 421–435.
URL https://doi.org/10.1002/jcd.21516

  * [24] H. Liang, S. Zhou, Flag-transitive point-primitive non-symmetric $2$-$(v,k,2)$ designs with alternating socle, Bull. Belg. Math. Soc. Simon Stevin 23 (4) (2016) 559–571.
URL http://projecteuclid.org/euclid.bbms/1480993587

  * [25] M. W. Liebeck, J. Saxl, The finite primitive permutation groups of rank three, Bull. London Math. Soc. 18 (2) (1986) 165–172.
URL http://dx.doi.org/10.1112/blms/18.2.165

  * [26] M. W. Liebeck, J. Saxl, G. Seitz, On the overgroups of irreducible subgroups of the finite classical groups., Proc. Lond. Math. Soc. 50 (3) (1987) 507–537.
URL http://dx.doi.org/10.1112/plms/s3-50.3.426

  * [27] E. O’Reilly-Regueiro, Biplanes with flag-transitive automorphism groups of almost simple type, with alternating or sporadic socle, European J. Combin. 26 (5) (2005) 577–584.
URL http://dx.doi.org/10.1016/j.ejc.2004.05.003

  * [28] E. O’Reilly-Regueiro, On primitivity and reduction for flag-transitive symmetric designs, J. Combin. Theory Ser. A 109 (1) (2005) 135–148.
URL http://dx.doi.org/10.1016/j.jcta.2004.08.002

  * [29] E. O’Reilly-Regueiro, Biplanes with flag-transitive automorphism groups of almost simple type, with classical socle, J. Algebraic Combin. 26 (4) (2007) 529–552.
URL http://dx.doi.org/10.1007/s10801-007-0070-7

  * [30] E. O’Reilly-Regueiro, Classification of flag-transitive symmetric designs, Electronic Notes in Discrete Mathematics 28 (2007) 535 – 542, 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications.
URL http://www.sciencedirect.com/science/article/pii/S1571065307000765

  * [31] E. O’Reilly-Regueiro, Biplanes with flag-transitive automorphism groups of almost simple type, with exceptional socle of Lie type, J. Algebraic Combin. 27 (4) (2008) 479–491.
URL http://dx.doi.org/10.1007/s10801-007-0098-8

  * [32] E. Pierro, The Möbius function of the small Ree groups, Australas. J. Combin. 66 (2016) 142–176.
  * [33] J. Saxl, On finite linear spaces with almost simple flag-transitive automorphism groups, J. Combin. Theory Ser. A 100 (2) (2002) 322–348.
URL http://dx.doi.org/10.1006/jcta.2002.3305

  * [34] G. M. Seitz, Flag-transitive subgroups of Chevalley groups, Ann. of Math. (2) 97 (1973) 27–56.
  * [35] J. Tits, Collectif, Les groupes simples de Suzuki et de Ree, in: Séminaire Bourbaki : années 1960/61, exposés 205-222, No. 6 in Séminaire Bourbaki, Société mathématique de France, 1961, pp. 65–82, talk:210.
URL http://www.numdam.org/item/SB_1960-1961__6__65_0


# Global aspects of the continuous reformulation
for cardinality-constrained optimization problems

S. Lämmel  Department of Mathematics, Chemnitz University of Technology,
Reichenhainer Str. 41, 09126 Chemnitz, Germany; e-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>chemnitz.de.  V. Shikhman11footnotemark: 1

###### Abstract

The main goal of this paper is to relate the topologically relevant stationary
points of a cardinality-constrained optimization problem and its continuous
reformulation up to their type. For that, we focus on the nondegenerate M- and
T-stationary points, respectively. Their so-called M- and T-indices, which
uniquely determine the global and local structure of optimization problems
under consideration in algebraic terms, are traced. As novelty, we suggest to
regularize the continuous reformulation for this purpose. The main consequence
of our analysis is that the number of saddle points of the regularized
continuous reformulation grows exponentially as compared to that of the
initial cardinality-constrained optimization problem. Additionally, we obtain
the Morse theory for the regularized continuous reformulation by using the
corresponding results on mathematical programs with orthogonality type
constraints.

Keywords: cardinality-constrained optimization problem, continuous
reformulation, orthogonality type constraints, nondegenerate T-stationarity,
index, genericity

MSC-classification: 90C26, 49M20

##  1 Introduction

We consider the class of cardinality-constrained optimization problems:

$\mbox{CCOP}:\quad\min_{x}\,\,f(x)\quad\mbox{s.\,t.}\quad h(x)=0,\quad
g(x)\geq 0,\quad\left\|x\right\|_{0}\leq s$

with the feasible set given by equality, inequality, and cardinality
constraints, where the so-called zero ”norm” is counting non-zero entries of
$x$:

$\left\|x\right\|_{0}=\left|\left\\{i\in\\{1,\ldots,n\\}\;|\;x_{i}\neq
0\right\\}\right|.$

Here, we assume that the objective function $f\in
C^{2}(\mathbb{R}^{n},\mathbb{R})$, as well as the equality and inequality
constraints $h=\left(h_{p},p\in P\right)\in
C^{2}(\mathbb{R}^{n},\mathbb{R}^{|P|})$, $g=\left(g_{q},q\in Q\right)\in
C^{2}(\mathbb{R}^{n},\mathbb{R}^{|Q|})$ are twice continuously differentiable,
and $s\in\\{0,1,\ldots,n-1\\}$ is an integer. The bounded zero norm of the
decision variable $x$ induces sparsity, which is motivated by various
applications, such as compressed sensing, model selection, image processing
etc., see e. g. [3], [8], and [7].

Let us start by recalling the continuous reformulation of CCOP from [1].
There, auxiliary binary $y$-variables were used in order to rewrite the
sparsity constraints. After relaxing the binary constraints in a standard way,
the authors arrive at

$\begin{array}[]{rl}\displaystyle\min_{x,y}\,\,f(x)\quad\mbox{s.\,t.}&h(x)=0,\quad
g(x)\geq 0,\\\ &\displaystyle\sum_{i=1}^{n}y_{i}\geq n-s,\quad
x_{i}y_{i}=0,\quad 0\leq y_{i}\leq 1,\quad i=1,\ldots,n.\end{array}$ (1)

As pointed out in [1], $\bar{x}$ solves CCOP if and only if there exists a
vector $\bar{y}$ such that $\left(\bar{x},\bar{y}\right)$ solves (1). The
question on the global structure of the continuous reformulation (1) and the
initial CCOP arises quite naturally. For that, we focus on the stationary
points – minimizers, but also all kinds of saddle points – which are
topologically relevant in the sense of Morse theory, see e.g. [4]. Morse
theory typically provides deformation and cell-attachment results for the
lower level sets. Deformation means that outside the set of stationary points
the topology of lower level sets remains unchanged if the level varies. Cell-
attachment describes the topological changes of the lower level sets if
passing a nondegenerate stationary point. As a consequence, it becomes
possible to relate the numbers of minimizers and saddle points, thus, to
adequately capture the global structure of the underlying optimization
problem. While doing so, the notion of nedegeneracy becomes crucial.
Nondegeneracy refers to some tailored versions of linear independence
constraint qualification, strict complementarity and second-order regularity.
It is justified by the fact that all stationary points are generically
nondegenerate, i.e. this property holds on an open and dense subset of
defining functions. Assuming nondegeneracy, stationary points can be
classified according to their index which encodes the local structure of the
optimization problem in algebraic terms.

In [5], M-stationary points were identified to adequately describe the global
structure of CCOP. The attempt to establish Morse theory also for its
continuous reformulation (1) has been undertaken in our recent paper [6].
There, the class of mathematical problems with orthogonality type constraints
(MPOC) has been introduced for the latter purpose. By using the notion of
T-stationarity, the deformation and cell-attachment results for MPOC were
shown. Although (1) is a subclass of MPOC, and its T-stationary points
naturally correspond to the M-stationary points of CCOP, the results from [6]
are not applicable. The reason is that all T-stationary points of (1) turn out
to be degenerate and, thus, the cell-attachment cannot be performed. This is
even the case if we start from a CCOP with all its M-stationary points being
nondegenerate. In order to nevertheless examine the global structure of (1),
we suggest to study its regularized version. Our main idea is not only to
linearly perturb the objective function in (1) with respect to $y$-variables,
but also to additionally relax the upper bounds on them:

$\begin{array}[]{rl}\displaystyle\mathcal{R}(c,\varepsilon):\quad\min_{x,y}\,\,f(x)+c^{T}y\quad\mbox{s.\,t.}&h(x)=0,\quad
g(x)\geq 0,\\\ &\displaystyle\sum_{i=1}^{n}y_{i}\geq n-s,\quad
x_{i}y_{i}=0,\quad 0\leq y_{i}\leq 1+\varepsilon,\quad
i=1,\ldots,n,\end{array}$

where $c\in\mathbb{R}^{n}$ and $\varepsilon>0$. By doing so, the proposed
regularization $\mathcal{R}$ remains an MPOC, whose T-stationary points now
become generically nondegenerate. This follows from the derived relation
between M-stationary points of CCOP and T-stationary points of $\mathcal{R}$.
We also successfully trace their corresponding M- and T-indices by imposing –
except of nondegeneracy – an additional condition on $\mathcal{R}$. The latter
requires that in presence of biactive orthogonality type constraints, the
multipliers of a T-stationary point corresponding to zero $x$-variables and
nonzero $y$-variables do not vanish. Fortunately, this additional condition
can be shown to hold generically, thus, it is far from being restrictive. As a
consequence of our analysis, the Morse theory for the regularized continuous
reformulation $\mathcal{R}$ can be deduced from the corresponding results on
MPOC from [6]. More importantly, we estimate the number of its saddle points.
Namely, each saddle point of CCOP generates exponentially many saddle points
of $\mathcal{R}$, all of them having the same index.

The article is organized as follows. In Section 2 we discuss some preliminary
notions for CCOP. Section 3 is devoted to the analysis of the regularized
continuous reformulation $\mathcal{R}$. In Section 4 we compare our findings
with those for the continuous reformulation (1) known from the literature.

Our notation is standard. The cardinality of a finite set $A$ is denoted by
$|A|$. The $n$-dimensional Euclidean space is denoted by $\mathbb{R}^{n}$ with
the coordinate vectors $e_{i},i=1,\ldots,n$. Given a twice continuously
differentiable function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$, $\nabla f$
denotes its gradient, and $D^{2}f$ stands for its Hessian.

##  2 Cardinality-constrained optimization problems

We start by recalling details on the class of CCOP from the literature. The
following notation for a CCOP feasible point $\bar{x}$ will be used:

$Q_{0}(\bar{x})=\left\\{q\in Q\,\left|\,g_{q}(\bar{x})=0\right.\right\\}$

denotes the index set of active inequality constraints, and the index set of
its vanishing components is set to be

$I_{0}(\bar{x})=\left\\{i\in\\{1,\ldots,n\\}\,\left|\,\bar{x}_{i}=0\right.\right\\}.$

Let us mention the CCOP-tailored linear independence constraint qualification.
It is known to hold generically on the whole CCOP feasible set, see [5].

######  Definition 1 (CC-LICQ, see [2]).

We say that a CCOP feasible point $\bar{x}$ of CCOP satisfies the cardinality-
constrained linear independence constraint qualification (CC-LICQ) if the
following gradients are linearly independent:

$\nabla h_{p}(\bar{x}),p\in P,\quad\nabla g_{q}(\bar{x}),q\in
Q_{0}(\bar{x}),\quad e_{i},i\in I_{0}(\bar{x}).$

The topologically relevant concept of M-stationarity for CCOP is stated as
follows.

######  Definition 2 (M-stationarity, see [1]).

A CCOP feasible point $\bar{x}$ is called M-stationary if there exist
multipliers

$\bar{\lambda}_{p},p\in P,\bar{\mu}_{q},q\in
Q_{0}(\bar{x}),\bar{\gamma}_{i},i\in I_{0}(\bar{x}),$

such that the following conditions hold:

$\nabla f(\bar{x})=\sum\limits_{p\in P}\bar{\lambda}_{p}\nabla
h_{p}(\bar{x})+\sum\limits_{q\in Q_{0}(\bar{x})}\bar{\mu}_{q}\nabla
g_{q}(\bar{x})+\sum\limits_{i\in I_{0}(\bar{x})}\bar{\gamma}_{i}e_{i},$ (2)
$\bar{\mu}_{q}\geq 0\mbox{ for all }q\in Q_{0}(\bar{x}).$ (3)

Since the multipliers are unique under CC-LICQ, it is convenient to define the
Lagrange function:

$L(x)=f\left(x\right)-\sum\limits_{p\in
P}\bar{\lambda}_{p}h_{p}\left(x\right)-\sum\limits_{q\in
Q_{0}(\bar{x})}\bar{\mu}_{q}g_{q}\left(x\right)-\sum\limits_{i\in
I_{0}(\bar{x})}\bar{\gamma}_{i}x_{i}.$

We also use the corresponding tangent space:

$\mathcal{T}_{\bar{x}}=\left\\{\xi\in\mathbb{R}^{n}\,\left|\,Dh_{p}(\bar{x})\xi=0,p\in
P,Dg_{q}(\bar{x})\xi=0,q\in Q_{0}(\bar{x}),\xi_{i}=0,i\in
I_{0}(\bar{x})\right.\right\\}.$

Let us proceed with the definition of nondegeneracy for M-stationary points as
introduced in [5]. It is justified there by showing that all M-stationary
points of CCOP are generically nondegenerate.

######  Definition 3 (Nondegenerate M-stationarity, see [5]).

An Mstationary point $\bar{x}$ of CCOP is called nondegenerate if

  * NDM1: CC-LICQ holds at $\bar{x}$,

  * NDM2: $\bar{\mu}_{q}>0$ for all $q\in Q_{0}(\bar{x})$,

  * NDM3: if $\left\|\bar{x}\right\|_{0}<s$ then $\bar{\gamma}_{i}\neq 0$ for all $i\in I_{0}(\bar{x})$,

  * NDM4: the matrix $D^{2}L(\bar{x})\restriction_{\mathcal{T}_{\bar{x}}}$ is nonsingular.

The nondegeneracy conditions NDM1-NDM4 are tailored for the CCOP class. Note
that NDM2 corresponds to the strict complementarity and NDM4 to the second-
order regularity as they are typically defined in the context of nonlinear
programming. NDM1 substitutes the usual linear independence constraint
qualification. NDM3 is new and says that, unless the sparsity constraint is
active, the corresponding Lagrange multipliers should not vanish. With a
nondegenerate M-stationary point $\bar{x}$ an M-index can be associated.
M-index captures the structure of CCOP locally around $\bar{x}$ and defines
the type of an M-stationary point, see [5] for details. In particular,
nondegenerate minimizers of CCOP are characterized by the vanishing M-index.
If M-index does not vanish, we get all kinds of saddle points.

######  Definition 4 (M-Index, see [5]).

Let $\bar{x}$ be a nondegenerate Mstationary point of CCOP. The number of
negative eigenvalues of the matrix
$D^{2}L(\bar{x})\restriction_{\mathcal{T}_{\bar{x}}}$ is called its quadratic
index ($QI$). The number $s-\left\|\bar{x}\right\|_{0}$ is called the sparsity
index ($SI$) of $\bar{x}$. We define the M-index ($MI$) as the sum of both, i.
e. $MI=SI+BI$.

Let us mention the role M-stationary points and their M-indices play for
capturing the global structure of CCOP. In [5], deformation and cell-
attachment in the sense of Morse theory are proved for a generic CCOP.
Deformation says that lower level sets are homeomorphic if passing a level
which does not correspond to any M-stationary point. Cell-attachment
algebraically describes topological differences between lower level sets if a
level corresponding to a nondegenerate M-stationary is crossed. Exponentially
many cells of the same dimension need to be attached to a lower level set in
order to obtain another lower level set up to homotopy-equivalence. The
dimension of those cells to be attached coincides with the M-index of a
nondegenerate M-stationary point. A global interpretation of deformation and
cell-attachment can be given in form of a mounting pass result, see again [5]
for details.

##  3 Regularized continuous reformulation

Let us associate with CCOP the regularized continuous reformulation , cf. (1):

$\begin{array}[]{rl}\displaystyle\mathcal{R}(c,\varepsilon):\quad\min_{x,y}\,\,f(x)+c^{T}y\quad\mbox{s.\,t.}&h(x)=0,\quad
g(x)\geq 0,\\\ &\displaystyle\sum_{i=1}^{n}y_{i}\geq n-s,\quad
x_{i}y_{i}=0,\quad 0\leq y_{i}\leq 1+\varepsilon,\quad
i=1,\ldots,n,\end{array}$

where $c\in\mathbb{R}^{n}$ and $\varepsilon>0$. Given a feasible point
$(\bar{x},\bar{y})$ of $\mathcal{R}$, we define the index sets which
correspond to the orthogonality type constraints $x_{i}y_{i}=0$, $y_{i}\geq
0$, $i=1,\ldots,n$:

$a_{00}\left(\bar{x},\bar{y}\right)=\left\\{i\in\left\\{1,\ldots,n\right\\}\,\left|\,\bar{x}_{i}=0,\bar{y}_{i}=0\right.\right\\},$
$a_{01}\left(\bar{x},\bar{y}\right)=\left\\{i\in\left\\{1,\ldots,n\right\\}\,\left|\,\bar{x}_{i}=0,\bar{y}_{i}>0\right.\right\\},$
$a_{10}\left(\bar{x},\bar{y}\right)=\left\\{i\in\left\\{1,\ldots,n\right\\}\,\left|\,\bar{x}_{i}\neq
0,\bar{y}_{i}=0\right.\right\\}.$

The $y$-components which attain the upper bound are stored in

$\mathcal{E}(\bar{y})=\left\\{i\in\\{1,\ldots,n\\}\left|\,\bar{y}_{i}=1+\varepsilon\right.\right\\}.$

The index set of the active inequality constraints remains to be denoted by

$Q_{0}(\bar{x})=\left\\{q\in Q\,\left|\,g_{q}(\bar{x})=0\right.\right\\}.$

The following assumption on the regularization parameters $c$ and
$\varepsilon$ will be helpful in what follows. Note that it is not restrictive
since a randomly generated vector $c$ with positive components fulfills
Assumption 1 with probability one. The upper bound on $\varepsilon$ depends
just on $n$ and $s$, but not on the CCOP defining functions. If not stated
otherwise, Assumption 1 holds throughout the whole paper.

######  Assumption 1.

Let the components of $c$ be positive and pairwise different, and
$\varepsilon\leq\frac{1}{n-s}$.

The regularized continuous reformulation $\mathcal{R}$ is a special case of
mathematical programs with orthogonality type constraints (MPOC). The latter
class was examined in [6], where the MPOC-tailored linear independence
constraint qualification, the topologically relevant notion of (nondegenerate)
T-stationary points with the corresponding T-index were introduced. We apply
these concepts to the regularization $\mathcal{R}$.

######  Definition 5 (MPOC-LICQ).

We say that a feasible point $(\bar{x},\bar{y})$ of $\mathcal{R}$ satisfies
the MPOC-tailored linear independence constraint qualification (MPOC-LICQ) if
the following vectors are linearly independent:

$\begin{pmatrix}\nabla h_{p}(\bar{x})\\\ 0\end{pmatrix},p\in
P,\quad\begin{pmatrix}\nabla g_{q}(\bar{x})\\\ 0\end{pmatrix},q\in
Q_{0}(\bar{x}),\quad\begin{pmatrix}0\\\
e_{i}\end{pmatrix},i\in\mathcal{E}(\bar{y}),\quad\begin{pmatrix}0\\\
e\end{pmatrix}\mbox{ if }\sum\limits_{i=1}^{n}\bar{y}_{i}=n-s,$
$\begin{pmatrix}e_{i}\\\ 0\end{pmatrix},i\in
a_{01}\left(\bar{x},\bar{y}\right)\cup
a_{00}\left(\bar{x},\bar{y}\right),\quad\begin{pmatrix}0\\\
e_{i}\end{pmatrix},i\in a_{10}\left(\bar{x},\bar{y}\right)\cup
a_{00}\left(\bar{x},\bar{y}\right).$

Let us relate CCOP- and MPOC-tailored linear independence constraint
qualifications.

######  Theorem 1 (CC-LICQ vs. MPOC-LICQ).

A feasible point $\bar{x}$ of CCOP fulfills CC-LICQ if and only if MPOC-LICQ
holds at any feasible point $\left(\bar{x},\bar{y}\right)$ of $\mathcal{R}$.

###### Proof.

CC-LICQ holds at $\bar{x}$ if the following vectors are linearly independent:

$\nabla h_{p}(\bar{x}),p\in P,\quad\nabla g_{q}(\bar{x}),q\in
Q_{0}(\bar{x}),\quad e_{i},i\in I_{0}(\bar{x}).$

Since $I_{0}(\bar{x})=a_{01}\left(\bar{x},\bar{y}\right)\cup
a_{00}\left(\bar{x},\bar{y}\right)$, the vectors

$\begin{pmatrix}\nabla h_{p}(\bar{x})\\\ 0\end{pmatrix},p\in
P,\quad\begin{pmatrix}\nabla g_{q}(\bar{x})\\\ 0\end{pmatrix},q\in
Q_{0}(\bar{x}),\quad\begin{pmatrix}e_{i}\\\ 0\end{pmatrix},i\in
a_{01}\left(\bar{x},\bar{y}\right)\cup a_{00}\left(\bar{x},\bar{y}\right),$

are linearly independent. In order to prove that MPOC-LICQ is indeed fulfilled
at $\left(\bar{x},\bar{y}\right)$, it remains therefore to show that the
following vectors are also linearly independent:

$\begin{pmatrix}0\\\
e_{i}\end{pmatrix},i\in\mathcal{E}(\bar{y}),\quad\begin{pmatrix}0\\\
e\end{pmatrix}\mbox{ if
}\sum\limits_{i=1}^{n}\bar{y}_{i}=n-s,\quad\begin{pmatrix}0\\\
e_{i}\end{pmatrix},i\in a_{10}\left(\bar{x},\bar{y}\right)\cup
a_{00}\left(\bar{x},\bar{y}\right).$ (4)

Since $\mathcal{E}\left(\bar{y}\right)\subset
a_{01}\left(\bar{x},\bar{y}\right)$, we have that $\begin{pmatrix}0\\\
e_{i_{1}}\end{pmatrix}$ and $\begin{pmatrix}0\\\ e_{i_{2}}\end{pmatrix}$ are
linearly independent for all $i_{1}\in\mathcal{E}\left(\bar{y}\right)$ and all
$i_{2}\in a_{10}\left(\bar{x},\bar{y}\right)\cup
a_{00}\left(\bar{x},\bar{y}\right)$. It is enough to ensure that we have at
most $n$ vectors in (4). We distinguish the following cases:

a) $\sum\limits_{i=1}^{n}\bar{y}_{i}>n-s$. Due to the feasibility of
$(\bar{x},\bar{y})$, we have

$\left|a_{01}\left(\bar{x},\bar{y}\right)\right|+\left|a_{10}\left(\bar{x},\bar{y}\right)\right|+\left|a_{00}\left(\bar{x},\bar{y}\right)\right|=n.$

Hence, MPOC-LICQ holds if and only if
$\left|\mathcal{E}\left(\bar{y}\right)\right|\leq\left|a_{01}\left(\bar{x},\bar{y}\right)\right|$,
which is obviously true.

b) $\sum\limits_{i=1}^{n}\bar{y}_{i}=n-s$. Assume that MPOC-LICQ does not hold
at $(\bar{x},\bar{y})$. Consequently, we must have
$\mathcal{E}\left(\bar{y}\right)=a_{01}\left(\bar{x},\bar{y}\right)$. However,
we obtain then:

$n-s=\sum\limits_{i=1}^{n}\bar{y}_{i}=\left|a_{01}\left(\bar{x},\bar{y}\right)\right|\left(1+\varepsilon\right)=\left|a_{01}\left(\bar{x},\bar{y}\right)\right|+\left|a_{01}\left(\bar{x},\bar{y}\right)\right|\varepsilon.$

In particular, $\left|a_{01}\left(\bar{x},\bar{y}\right)\right|\varepsilon$ is
an integer. Due to $\varepsilon\leq\frac{1}{n-s}$ it must, thus, hold either
$\left|a_{01}\left(\bar{x},\bar{y}\right)\right|=0$ or
$\left|a_{01}\left(\bar{x},\bar{y}\right)\right|\geq n-s$. The former implies

$\sum\limits_{i=1}^{n}\bar{y}_{i}=0<n-s,$

whereas the latter implies

$\sum\limits_{i=1}^{n}\bar{y}_{i}\geq(n-s)(1+\varepsilon)>n-s.$

Both cases yield a contradiction. The reverse implication of the assertion is
straightforward.

Now, we turn our attention to the topologically relevant concept of
T-stationarity for $\mathcal{R}$.

######  Definition 6 (T-stationary point).

A feasible point $(\bar{x},\bar{y})$ of $\mathcal{R}$ is called T-stationary
if there exists multipliers

$\begin{array}[]{l}\bar{\lambda}_{p},p\in P,\bar{\mu}_{1,q},q\in
Q_{0}(\bar{x}),\bar{\mu}_{2,i},i\in\mathcal{E}(\bar{y}),\bar{\mu}_{3},\\\
\bar{\sigma}_{1,i_{01}},i_{01}\in
a_{01}\left(\bar{x},\bar{y}\right),\bar{\sigma}_{2,i_{10}},i_{10}\in
a_{10}\left(\bar{x},\bar{y}\right),\bar{\varrho}_{1,i_{00}},\bar{\varrho}_{2,i_{00}},i_{00}\in
a_{00}\left(\bar{x},\bar{y}\right),\end{array}$

such that the following conditions hold:

$\begin{array}[]{rcl}\begin{pmatrix}\nabla f(\bar{x})\\\
c\end{pmatrix}&=&\displaystyle\sum\limits_{p\in
P}\bar{\lambda}_{p}\begin{pmatrix}\nabla h_{p}(\bar{x})\\\
0\end{pmatrix}+\sum\limits_{q\in
Q_{0}(\bar{x})}\bar{\mu}_{1,q}\begin{pmatrix}\nabla g_{q}(\bar{x})\\\
0\end{pmatrix}-\sum\limits_{i\in\mathcal{E}(\bar{y})}\bar{\mu}_{2,i}\begin{pmatrix}0\\\
e_{i}\end{pmatrix}+\bar{\mu}_{3}\begin{pmatrix}0\\\ e\end{pmatrix}\\\ \\\
&&\displaystyle+\sum\limits_{i_{01}\in
a_{01}\left(\bar{x},\bar{y}\right)}\bar{\sigma}_{1,i_{01}}\begin{pmatrix}e_{i_{01}}\\\
0\end{pmatrix}+\sum\limits_{i_{10}\in
a_{10}\left(\bar{x},\bar{y}\right)}\bar{\sigma}_{2,i_{10}}\begin{pmatrix}0\\\
e_{i_{10}}\end{pmatrix}\\\ \\\ &&\displaystyle+\sum\limits_{i_{00}\in
a_{00}\left(\bar{x},\bar{y}\right)}\left(\bar{\varrho}_{1,i_{00}}\begin{pmatrix}e_{i_{00}}\\\
0\end{pmatrix}+\bar{\varrho}_{2,i_{00}}\begin{pmatrix}0\\\
e_{i_{00}}\end{pmatrix}\right),\end{array}$ (5) $\bar{\mu}_{1,q}\geq 0\mbox{
for all }q\in Q_{0}\left(\bar{x}\right),\bar{\mu}_{2,i}\geq 0\mbox{ for all
}i\in\mathcal{E}(\bar{y}),\bar{\mu}_{3}\geq
0,\bar{\mu}_{3}\cdot\left(\sum\limits_{i=1}^{n}\bar{y}_{i}-(n-s)\right)=0,$
(6) $\bar{\varrho}_{1,i_{00}}=0\mbox{ or }\bar{\varrho}_{2,i_{00}}\leq 0\mbox{
for all }i_{00}\in a_{00}\left(\bar{x},\bar{y}\right).$ (7)

We again define the appropriate Lagrange function:

$\begin{array}[]{rcl}L^{\mathcal{R}}(x,y)&=&\displaystyle
f(x)+c^{T}y-\sum\limits_{p\in P}\bar{\lambda}_{p}h_{p}(x)-\sum\limits_{q\in
Q_{0}(\bar{x})}\bar{\mu}_{1,q}g_{q}(x)+\sum\limits_{i\in\mathcal{E}(\bar{y})}\bar{\mu}_{2,i}\left(y_{i}-(1+\varepsilon)\right)\\\
\\\
&&\displaystyle-\bar{\mu}_{3}\left(\sum\limits_{i=1}^{n}y_{i}-(n-s)\right)-\sum\limits_{i_{01}\in
a_{01}\left(\bar{x},\bar{y}\right)}\bar{\sigma}_{1,i_{01}}x_{i_{01}}-\sum\limits_{i_{10}\in
a_{10}\left(\bar{x},\bar{y}\right)}\bar{\sigma}_{2,i_{10}}y_{i_{10}}\\\ \\\
&&\displaystyle-\sum\limits_{i_{00}\in
a_{00}\left(\bar{x},\bar{y}\right)}\left(\bar{\varrho}_{1,i_{00}}x_{i_{00}}+\bar{\varrho}_{2,i_{00}}y_{i_{00}}\right).\end{array}$

Moreover, we set for the corresponding tangential space:

$\mathcal{T}^{\mathcal{R}}_{(\bar{x},\bar{y})}=\left\\{\xi\in\mathbb{R}^{2n}\,\left|\,\begin{array}[]{l}\begin{pmatrix}Dh_{p}(\bar{x}),0\end{pmatrix}\xi=0,p\in
P,\begin{pmatrix}Dg_{q}(\bar{x}),0\end{pmatrix}\xi=0,q\in Q_{0}(\bar{x}),\\\
\begin{pmatrix}0,e_{i}\end{pmatrix}\xi=0,i\in\mathcal{E}(\bar{y}),\begin{pmatrix}0,e\end{pmatrix}\xi=0\mbox{
if }\displaystyle\sum_{i=1}^{n}\bar{y}_{i}=n-s,\\\
\begin{pmatrix}e_{i},0\end{pmatrix}\xi=0,i\in a_{00}(\bar{x},\bar{y})\cup
a_{01}(\bar{x},\bar{y}),\\\ \begin{pmatrix}0,e_{i}\end{pmatrix}\xi=0,i\in
a_{00}(\bar{x},\bar{y})\cup
a_{10}(\bar{x},\bar{y})\end{array}\right.\right\\}.$

######  Definition 7 (Nondegenerate T-stationary point).

A T-stationary point $(\bar{x},\bar{y})$ of $\mathcal{R}$ with multipliers
$(\bar{\lambda},\bar{\mu},\bar{\sigma},\bar{\varrho})$ is called nondegenerate
if

  * NDT1: MPOC-LICQ holds at $(\bar{x},\bar{y})$,

  * NDT2: the strict complementarity (SC) holds for active inequality constraints, i. e. $\bar{\mu}_{1,q}>0$ for all $q\in Q_{0}\left(\bar{x}\right)$, $\bar{\mu}_{2,i}>0$ for all $i\in\mathcal{E}\left(\bar{y}\right)$, and if $\sum\limits_{i=1}^{n}\bar{y}_{i}=n-s$ then also $\bar{\mu}_{3}>0$,

  * NDT3: the multipliers corresponding to biactive orthogonality type constraints do not vanish, i. e. $\bar{\varrho}_{1,i_{00}}\neq 0$ and $\bar{\varrho}_{2,i_{00}}<0$ for all $i_{00}\in a_{00}\left(\bar{x},\bar{y}\right)$,

  * NDT4: the matrix $D^{2}L^{\mathcal{R}}(\bar{x},\bar{y})\restriction_{\mathcal{T}^{\mathcal{R}}_{(\bar{x},\bar{y})}}$ is nonsingular.

For a nondegenerate T-stationary point we eventually use an additional
condition:

  * NDT5: if $a_{00}\left(\bar{x},\bar{y}\right)\not=\emptyset$, then $\bar{\sigma}_{1,i_{01}}\neq 0$ for all $i_{01}\in a_{01}(\bar{x},\bar{y})$.

######  Definition 8 (T-index).

Let $(\bar{x},\bar{y})$ be a nondegenerate T-stationary point of $\mathcal{R}$
with unique multipliers
$\left(\bar{\lambda},\bar{\mu},\bar{\sigma},\bar{\varrho}\right)$. The number
of negative eigenvalues of the matrix
$D^{2}L^{\mathcal{R}}(\bar{x},\bar{y})\restriction_{\mathcal{T}^{\mathcal{R}}_{(\bar{x},\bar{y})}}$
is called its quadratic index ($QI$). The cardinality of
$a_{00}\left(\bar{x},\bar{y}\right)$ is called the biactive index ($BI$) of
$(\bar{x},\bar{y})$. We define the T-index ($TI$) as the sum of both, i. e.
$TI=QI+BI$.

The following Lemma 1 provides insights into the structure of auxiliary
$y$-variables corresponding to a T-stationary point of $\mathcal{R}$.

######  Lemma 1 (Auxiliary $y$-variables in $\mathcal{R}$).

Let $(\bar{x},\bar{y})$ be a T-stationary point of $\mathcal{R}$, then it
holds:

  * a)

the summation inequality constraint is active, i. e.
$\sum\limits_{i=1}^{n}\bar{y}_{i}=n-s$,

  * b)

the index set $a_{01}(\bar{x},\bar{y})$ consists of exactly $n-s$ elements,

  * c)

$n-s-1$ components of $\bar{y}$ are equal to $1+\varepsilon$, one component is
equal to $1-(n-s-1)\varepsilon$, and $s$ remaining components vanish.

###### Proof.

a) Let $(\bar{x},\bar{y})$ be a T-stationary point of $\mathcal{R}$ and
$\sum_{i=1}^{n}\bar{y}_{i}>n-s$. Then, there exist multipliers
$(\bar{\lambda},\bar{\mu},\bar{\sigma},\bar{\varrho})$ such that (5)–(7) are
fulfilled. Since $\bar{\mu}_{3}=0$, we have that the $(n+i)$-th row of (5)
reads as

$c_{i}=\left\\{\begin{array}[]{ll}-\bar{\mu}_{2,i},&\mbox{for
}i\in\mathcal{E}(\bar{y}),\\\ \bar{\sigma}_{2,i},&\mbox{for }i\in
a_{10}\left(\bar{x},\bar{y}\right),\\\ \bar{\varrho}_{2,i},&\mbox{for }i\in
a_{00}\left(\bar{x},\bar{y}\right),\\\ 0,&\mbox{else}.\end{array}\right.$

Due to $c>0$, the sets $a_{01}\left(\bar{x},\bar{y}\right)$ and
$\mathcal{E}(\bar{y})$ have to be equal and, moreover, due to
$\bar{\mu}_{2,i}\geq 0$, they have to be empty. But then, clearly,
$\sum_{i=1}^{n}\bar{y}_{i}=0<n-s$, a contradiction.

b) Since $(\bar{x},\bar{y})$ is a T-stationary point, there exist
$(\bar{\lambda},\bar{\mu},\bar{\sigma},\bar{\varrho})$ such that (5)–(7). By
the proof of statement a) we can conclude that $\bar{\mu}_{3}>0$. Hence, the
$(n+i)$-th row reads as

$c_{i}=\left\\{\begin{array}[]{ll}-\bar{\mu}_{2,i}+\bar{\mu}_{3},&\mbox{for
}i\in\mathcal{E}(\bar{y}),\\\ \bar{\sigma}_{2,i}+\bar{\mu}_{3},&\mbox{for
}i\in a_{10}\left(\bar{x},\bar{y}\right),\\\
\bar{\varrho}_{2,i}+\bar{\mu}_{3},&\mbox{for }i\in
a_{00}\left(\bar{x},\bar{y}\right),\\\
\bar{\mu}_{3},&\mbox{else}.\end{array}\right.$ (8)

Let us assume that the index set $a_{01}(\bar{x},\bar{y})$ consists of fewer
than $n-s$ elements. Then, we have by using Assumption 1:

$\sum_{i=1}^{n}\bar{y}_{i}\leq(n-s-1)\cdot(1+\varepsilon)\leq
n-s-1+\frac{n-s-1}{n-s}<n-s,$

a contradiction to feasibility. Let us assume that the index set
$a_{01}(\bar{x},\bar{y})$ consists of more than $n-s$ elements instead. Since
the components of $c$ are assumed to be pairwise different, we see from (8)
that there exists at most one element in
$a_{01}\left(\bar{x},\bar{y}\right)\backslash\mathcal{E}(\bar{y})$ and,
consequently, there are at least $n-s$ elements in $\mathcal{E}(\bar{y})$.
Therefore, we have:

$\sum_{i=1}^{n}\bar{y}_{i}\geq(n-s)\cdot(1+\varepsilon)>n-s,$

which contradicts a).

c) Due to b), $a_{01}(\bar{x},\bar{y})$ consists of exactly $n-s$ elements. We
conclude as in b) that there is at most one element in
$a_{01}\left(\bar{x},\bar{y}\right)\backslash\mathcal{E}(\bar{y})$. In view of
statement a), $\mathcal{E}(\bar{y})$ cannot consist of $n-s$ elements and,
thus, must consist of $n-s-1$ elements. Hence, the statement follows
immediately.

We are ready to identify how many T-stationary points of $\mathcal{R}$ are
generated by an M-stationary point of CCOP, and of what type they are.

######  Theorem 2 (Stationarity from CCOP to $\mathcal{R}$).

If $\bar{x}$ is an M-stationary point of CCOP, then there exist at least
$\binom{n-\left\|\bar{x}\right\|_{0}-1}{n-s-1}$ choices of $\bar{y}$ such that
$(\bar{x},\bar{y})$ is a T-stationary point of $\mathcal{R}$. If $\bar{x}$ is
additionally nondegenerate with M-index $m$, then all corresponding
T-stationary points $(\bar{x},\bar{y})$ are also nondegenerate with T-index
$m$. Moreover, their number is exactly
$\binom{n-\left\|\bar{x}\right\|_{0}-1}{n-s-1}$, and NDT5 holds at any of
them.

###### Proof.

Since $\bar{x}$ is an M-stationary point, there exist multipliers
$(\bar{\lambda},\bar{\mu},\bar{\gamma})$ with (2), (3). We set

$\bar{i}=\mbox{argmax}\left\\{c_{i}\left|i\in
I_{0}\left(\bar{x}\right)\right.\right\\}$

to be the index of $I_{0}\left(\bar{x}\right)$ for which $c_{i}$ is maximal.
Furthermore, let
$\mathcal{\bar{E}}\subset{I_{0}}\left(\bar{x}\right)\backslash\left\\{\bar{i}\right\\}$
be an index subset with $n-s-1$ elements, i. e.
$\left|\mathcal{\bar{E}}\right|=n-s-1$. Note that this is always possible
since $I_{0}\left(\bar{x}\right)$ consists of at least $n-s$ elements. Next,
we set

$\bar{y}_{i}=\left\\{\begin{array}[]{ll}1+\varepsilon,&\mbox{for
}i\in\mathcal{\bar{E}},\\\ 1-(n-s-1)\varepsilon,&\mbox{for }i=\bar{i},\\\
0,&\mbox{else}.\end{array}\right.$

Consequently, the point $(\bar{x},\bar{y})$ is feasible for $\mathcal{R}$. Let
the multipliers $\bar{\lambda}_{p}$, $p\in P$, corresponding to the equality
constraints remain unchanged. We set the other multipliers as follows:

$\bar{\mu}_{1,q}=\bar{\mu}_{q},q\in
Q_{0}(\bar{x}),\quad\bar{\mu}_{2,i}=c_{\bar{i}}-c_{i},i\in\mathcal{\bar{E}},\quad\bar{\mu}_{3}=c_{\bar{i}},$
$\bar{\sigma}_{1,i_{01}}=\bar{\gamma}_{i_{01}},i_{01}\in\mathcal{\bar{E}}\cup\left\\{\bar{i}\right\\},\quad\bar{\sigma}_{2,i_{10}}=c_{i_{10}}-c_{\bar{i}},i_{10}\in\\{1,\ldots,n\\}\backslash
I_{0}\left(\bar{x}\right),$
$\bar{\varrho}_{1,i_{00}}=\bar{\gamma}_{i_{00}},\quad\bar{\varrho}_{2,i_{00}}=c_{i_{00}}-c_{\bar{i}},i_{00}\in
I_{0}\left(\bar{x}\right)\backslash\left(\mathcal{\bar{E}}\cup\left\\{\bar{i}\right\\}\right).$

We note that

$\mathcal{E}(\bar{y})=\mathcal{\bar{E}},\quad
a_{01}(\bar{x},\bar{y})=\mathcal{\bar{E}}\cup\left\\{\bar{i}\right\\},\quad
a_{10}(\bar{x},\bar{y})=\\{1,\ldots,n\\}\backslash
I_{0}\left(\bar{x}\right),\quad
a_{00}(\bar{x},\bar{y})=I_{0}\left(\bar{x}\right)\backslash\left(\mathcal{\bar{E}}\cup\left\\{\bar{i}\right\\}\right).$

Since $\bar{x}$ is M-stationary and $\sum\limits_{i=1}^{n}\bar{y}_{i}=n-s$, we
obtain the T-stationarity condition (5) for $(\bar{x},\bar{y})$. Let us check
the signs of the multipliers. Due to the M-stationarity of $\bar{x}$ or by
construction, we have:

$\bar{\mu}_{1,q}\geq 0,q\in Q_{0}(\bar{x}),\quad\bar{\mu}_{2,i}\geq
0,i\in\mathcal{\bar{E}},\quad\bar{\mu}_{3}\geq
0,\quad\bar{\varrho}_{2,i_{00}}\leq 0,i_{00}\in
I_{0}\left(\bar{x}\right)\backslash\left(\mathcal{\bar{E}}\cup\left\\{\bar{i}\right\\}\right).$

Thus, T-stationarity conditions (6), (7) are also fulfilled.

It remains to show that there are at least
$\binom{n-\left\|x\right\|_{0}-1}{n-s-1}$ possibilities to choose $\bar{y}$.
This is exactly the number of possible choices for $\mathcal{\bar{E}}$. Hence,
the number of possible choices for $\bar{y}$ cannot be less. We assume that
for $\bar{x}$ nondegenerate there is another $\tilde{y}$ which cannot be
constructed as above, but so that $(\bar{x},\tilde{y})$ is a T-stationary
point of $\mathcal{R}$. Obviously, we have $\tilde{y}_{i}=0$ for $i\notin
I_{0}(\bar{x})$. Additionally, we know due to Lemma 1a) that
$\sum\limits_{i=1}^{n}\tilde{y}_{i}=n-s$ as well as from Lemma 1c) that there
exists exactly one $\tilde{i}$ such that
$0<\tilde{y}_{\tilde{i}}<1+\varepsilon$. Since $(\bar{x},\tilde{y})$ is
T-stationary, conditions (5)–(7) hold with multipliers
$(\tilde{\lambda},\tilde{\mu},\tilde{\sigma},\tilde{\varrho})$. According to
the aforementioned, the $(n+i)$-th row of (5) reads as

$c_{i}=\left\\{\begin{array}[]{ll}-\tilde{\mu}_{2,i}+\tilde{\mu}_{3},&\mbox{for
}i\in\mathcal{E}(\tilde{y}),\\\ \tilde{\mu}_{3},&\mbox{for }i=\tilde{i},\\\
\tilde{\sigma}_{2,i}+\tilde{\mu}_{3},&\mbox{for }i\in
a_{10}\left(\bar{x},\tilde{y}\right),\\\
\tilde{\varrho}_{2,i}+\tilde{\mu}_{3},&\mbox{for }i\in
a_{00}\left(\bar{x},\tilde{y}\right).\\\ \end{array}\right.$

Due to (6) we have that $c_{i}\leq c_{\tilde{i}}$ for all
$i\in\mathcal{E}(\tilde{y})$. We show that it also holds $c_{i}\leq
c_{\tilde{i}}$ for all $i\in a_{00}\left(\bar{x},\tilde{y}\right)$. In case of
$\left\|\bar{x}\right\|_{0}=s$ we have
$\left|I_{0}(\bar{x})\right|=n-s=|a_{01}\left(\bar{x},\tilde{y}\right)|$,
where the second equality follows from Lemma 1b). Consequently, it follows
from $I_{0}(\bar{x})=a_{01}\left(\bar{x},\tilde{y}\right)\cup
a_{00}\left(\bar{x},\tilde{y}\right)$ that
$a_{00}(\bar{x},\tilde{y})=\emptyset$. Instead we suppose
$\left\|\bar{x}\right\|_{0}<s$. Since $\bar{x}$ is a nondegenerate
M-stationary point we have

$\nabla f(\bar{x})=\sum\limits_{p\in P}\bar{\lambda}_{p}\nabla
h_{p}(\bar{x})+\sum\limits_{q\in Q_{0}(\bar{x})}\bar{\mu}_{q}\nabla
g_{q}(\bar{x})+\sum\limits_{i_{01}\in
a_{01}\left(\bar{x},\tilde{y}\right)}\bar{\gamma}_{i_{01}}e_{i_{01}}+\sum\limits_{i_{00}\in
a_{00}\left(\bar{x},\tilde{y}\right)}\bar{\gamma}_{i_{00}}e_{i_{00}},$

where $\bar{\gamma}_{i}\neq 0$ for all $i\in
I_{0}(\bar{x})=a_{01}\left(\bar{x},\tilde{y}\right)\cup
a_{00}\left(\bar{x},\tilde{y}\right).$ Additionally, we have due to
$\left(\bar{x},\tilde{y}\right)$ being T-stationary:

$\nabla f(\bar{x})=\sum\limits_{p\in P}\tilde{\lambda}_{p}\nabla
h_{p}(\bar{x})+\sum\limits_{q\in Q_{0}(\bar{x})}\tilde{\mu}_{1,q}\nabla
g_{q}(\bar{x})+\sum\limits_{i_{01}\in
a_{01}\left(\bar{x},\tilde{y}\right)}\tilde{\sigma}_{1,i_{01}}e_{i_{01}}+\sum\limits_{i_{00}\in
a_{00}\left(\bar{x},\tilde{y}\right)}\tilde{\varrho}_{1,i_{00}}e_{i_{00}}.$

Then, CC-LICQ implies $\tilde{\varrho}_{1,i_{00}}=\bar{\gamma}_{i_{00}}\neq 0$
for all $i\in a_{00}\left(\bar{x},\tilde{y}\right)$. But then (7) implies
$\tilde{\varrho}_{2,i_{00}}\leq 0$ for all $i\in
a_{00}\left(\bar{x},\tilde{y}\right)$. Overall, it follows
$\tilde{i}=\mbox{argmax}\left\\{c_{i}\left|i\in
I_{0}\left(\bar{x}\right)\right.\right\\}$. According to Lemma 1, there have
to be $n-s-1$ elements in $\mathcal{E}(\tilde{y})$ and we have
$\mathcal{E}(\tilde{y})\subset{I_{0}}\left(\bar{x}\right)\backslash\left\\{\tilde{i}\right\\}$
due to the choice of $\tilde{i}$. This leads to the conclusion that
$\tilde{y}$ could have been constructed as $\bar{y}$, a contradiction.

We show that each of the constructed T-stationary points $(\bar{x},\bar{y})$
of $\mathcal{R}$ is nondegenerate if $\bar{x}$ has been a nondegenerate
M-stationary point of CCOP. CC-LICQ at $\bar{x}$ provides MPOC-LICQ at
$(\bar{x},\bar{y})$ in view of Theorem 1. Hence, the multipliers for
$(\bar{x},\bar{y})$ defined above are unique. By virtue of NDM2, we have
$\bar{\mu}_{q}>0$ for all $q\in Q_{0}(\bar{x})$. Moreover, since the
components of $c$ are assumed to be positive and pairwise different, we have:

$\bar{\mu}_{2,i}=c_{\bar{i}}-c_{i}>0,i\in\mathcal{\bar{E}},\quad\bar{\mu}_{3}=c_{\bar{i}}>0.$

Thus, NDT2 is shown. In case of $\left\|\bar{x}\right\|_{0}<s$, NDM3 provides:

$\bar{\varrho}_{1,i_{00}}=\bar{\gamma}_{i_{00}}\not=0,i_{00}\in
I_{0}\left(\bar{x}\right)\backslash\left(\left\\{\bar{i}\right\\}\cup\mathcal{\bar{E}}\right).$

By using Assumption 1 once again, we also have:

$\bar{\varrho}_{2,i_{00}}=c_{i_{00}}-c_{\bar{i}}<0,i_{00}\in
I_{0}\left(\bar{x}\right)\backslash\left(\mathcal{\bar{E}}\cup\left\\{\bar{i}\right\\}\right).$

Hence, NDT3 is fulfilled whenever $\left\|\bar{x}\right\|_{0}<s$. If the
sparsity constrained is active, $a_{00}(\bar{x},\bar{y})=\emptyset$ and NDT3
trivially holds. It is left to show that NDT4 holds. Due to MPOC-LICQ, we
immediately obtain the following representation of the tangential space:

$\begin{array}[]{rcl}\mathcal{T}^{\mathcal{R}}_{(\bar{x},\bar{y})}\par&=&\left\\{\xi\in\mathbb{R}^{2n}\,\left|\,\begin{array}[]{l}\begin{pmatrix}Dh_{p}(\bar{x}),0\end{pmatrix}\xi=0,p\in
P,\begin{pmatrix}Dg_{q}(\bar{x}),0\end{pmatrix}\xi=0,q\in Q_{0}(\bar{x}),\\\
\xi_{i}=0,i\in
I_{0}(\bar{x}),\xi_{i}=0,i\in\\{n+1,\ldots,2n\\}\end{array}\right.\right\\}\end{array}.$

Therefore,
$D^{2}L^{\mathcal{R}}(\bar{x},\bar{y})\restriction_{\mathcal{T}^{\mathcal{R}}_{(\bar{x},\bar{y})}}$
is nonsingular if and only if
$D^{2}L(\bar{x})\restriction_{\mathcal{T}_{\bar{x}}}$ is nonsingular. The
latter holds due to NDM4, consequently, NDT4 is also fulfilled. Altogether,
the T-stationary point $(\bar{x},\bar{y})$ is shown to be nondegenerate. It
remains to prove that the T-index of $(\bar{x},\bar{y})$ equals the M-index of
$\bar{x}$. The above representation of
$\mathcal{T}^{\mathcal{R}}_{(\bar{x},\bar{y})}$ tells us that the number of
negative eigenvalues of
$D^{2}L^{\mathcal{R}}(\bar{x},\bar{y})\restriction_{\mathcal{T}^{\mathcal{R}}_{(\bar{x},\bar{y})}}$
is the same as that of $D^{2}L(\bar{x})\restriction_{\mathcal{T}_{\bar{x}}}$,
i.e. the quadratic indices of $(\bar{x},\bar{y})$ and $\bar{x}$ coincide. In
order to show that the biactive index $BI$ of $(\bar{x},\bar{y})$ equals to
the sparsity index $SI$ of $\bar{x}$, we first note:

$\left|a_{00}(\bar{x},\bar{y})\right|=n-\left|a_{10}(\bar{x},\bar{y})\right|-\left|a_{01}(\bar{x},\bar{y})\right|.$

By definition,
$\left|a_{10}(\bar{x},\bar{y})\right|=\left\|\bar{x}\right\|_{0}$, and by
construction, $\left|a_{01}(\bar{x},\bar{y})\right|=n-s$. Therefore, we
obtain:

$BI=\left|a_{00}(\bar{x},\bar{y})\right|=n-\left\|\bar{x}\right\|_{0}-(n-s)=s-\left\|\bar{x}\right\|_{0}=SI.$

Now, we turn our attention to the additional property NDT5. If
$a_{00}\left(\bar{x},\bar{y}\right)\not=\emptyset$, then as above:

$\left\|\bar{x}\right\|_{0}=\left|a_{10}(\bar{x},\bar{y})\right|=n-\left|a_{00}(\bar{x},\bar{y})\right|-\left|a_{01}(\bar{x},\bar{y})\right|=n-\left|a_{00}(\bar{x},\bar{y})\right|-(n-s)=s-\left|a_{00}(\bar{x},\bar{y})\right|<s.$

Hence, the conclusion from NDM3 can be applied and we obtain by recalling
$a_{01}(\bar{x},\bar{y})=\mathcal{\bar{E}}\cup\left\\{\bar{i}\right\\}$:

$\bar{\sigma}_{1,i_{01}}=\bar{\gamma}_{i_{01}}\neq 0,i_{01}\in
a_{01}(\bar{x},\bar{y}).$

The reverse implication of Theorem 2 is also valid. From a nondegenerate
T-stationary point of $\mathcal{R}$ it can be likewise concluded that the
corresponding M-stationary point of CCOP is of the same type.

######  Theorem 3 (Stationarity from $\mathcal{R}$ to CCOP).

If $(\bar{x},\bar{y})$ is a T-stationary point of $\mathcal{R}$, then
$\bar{x}$ is an M-stationary point of CCOP. If $(\bar{x},\bar{y})$ is
additionally nondegenerate with T-index $m$ and satisfies NDT5, then $\bar{x}$
is also nondegenerate with M-index $m$.

###### Proof.

Since $(\bar{x},\bar{y})$ is a T-stationary point, there exist
$(\bar{\lambda},\bar{\mu},\bar{\sigma},\bar{\varrho})$ with (5)–(7). The first
$n$ rows of (5) read as

$\begin{array}[]{rcl}\nabla f(\bar{x})&=&\displaystyle\sum\limits_{p\in
P}\bar{\lambda}_{p}\nabla h_{p}(\bar{x})+\sum\limits_{q\in
Q_{0}(\bar{x})}\bar{\mu}_{1,q}\nabla g_{q}(\bar{x})+\sum\limits_{i_{01}\in
a_{01}\left(\bar{x},\bar{y}\right)}\bar{\sigma}_{1,i_{01}}\cdot
e_{i_{01}}+\sum\limits_{i_{00}\in
a_{00}\left(\bar{x},\bar{y}\right)}\bar{\varrho}_{1,i_{00}}\cdot
e_{i_{00}},\\\ \\\ &=&\displaystyle\sum\limits_{p\in P}\bar{\lambda}_{p}\nabla
h_{p}(\bar{x})+\sum\limits_{q\in Q_{0}(\bar{x})}\bar{\mu}_{q}\nabla
g_{q}(\bar{x})+\sum\limits_{i\in
I_{0}\left(\bar{x}\right)}\bar{\gamma}_{i}\cdot e_{i},\end{array}$

where we set:

$\bar{\mu}_{q}=\bar{\mu}_{1,q},q\in
Q_{0}(\bar{x}),\quad\bar{\gamma}_{i}=\left\\{\begin{array}[]{ll}\bar{\sigma}_{1,i},&\mbox{for
}i\in a_{01}\left(\bar{x},\bar{y}\right),\\\ \bar{\varrho}_{1,i},&\mbox{for
}i\in a_{00}\left(\bar{x},\bar{y}\right).\end{array}\right.$

It follows that $\bar{x}$ is an M-stationary point.

Let $(\bar{x},\bar{y})$ be additionally nondegenerate and fulfill NDT5. First,
we note that MPOC-LICQ at $(\bar{x},\bar{y})$ implies CC-LICQ at $\bar{x}$ in
view of Theorem 1. NDM2, i. e. $\bar{\mu}_{q}>0$ for all $q\in
Q_{0}\left(\bar{x}\right)$, is also fulfilled as an immediate consequence of
NDT2. In order to show NDM3, we assume that the sparsity constraint is not
active, i.e. $\left\|\bar{x}\right\|_{0}<s$. Due to Lemma 1c),
$a_{00}\left(\bar{x},\bar{y}\right)\not=\emptyset$ must hold. NDT5 is
applicable and we get $\bar{\sigma}_{1,i_{01}}\neq 0$ for all $i_{01}\in
a_{01}(\bar{x},\bar{y})$. NDT3 also provides $\bar{\varrho}_{1,i_{00}}\neq 0$
for all $i_{00}\in a_{00}\left(\bar{x},\bar{y}\right)$. Recalling
$I_{0}(\bar{x})=a_{01}\left(\bar{x},\bar{y}\right)\cup
a_{00}\left(\bar{x},\bar{y}\right)$ and the definition of $\bar{\gamma}_{i}$,
$i\in I_{0}(\bar{x})$, NDM3 immediately follows. Finally, we have that NDM4
coincides with NDT4. This follows exactly as in the proof of Theorem 2. From
there it can be also seen that the quadratic indices of $\bar{x}$ and
$(\bar{x},\bar{y})$ coincide. Moreover, for the sparsity index $SI$ of
$\bar{x}$ and for the biactive index $BI$ of $(\bar{x},\bar{y})$ it is
possible to analogously prove $SI=BI$, by using Lemma 1c) where needed.
Overall, the M-index of $\bar{x}$ coincides with the T-index of
$(\bar{x},\bar{y})$.

It turns out that, if condition NDT5 is violated, the assertion on the
nondegeneracy in Theorem 3 does not necessary hold. This becomes clear from
the following Example 1.

######  Example 1 (Theorem 3 does not hold without NDT5).

We consider the regularized continuous reformulation of CCOP with $n=2$,
$s=1$, and $c=(c_{1},c_{2})^{T}$ fulfilling $0<c_{1}<c_{2}$:

$\begin{array}[]{rl}\mathcal{R}:\quad\min\limits_{x,y}&(x_{1}-1)^{2}+x_{2}^{2}+c_{1}\cdot
y_{1}+c_{2}\cdot y_{2}\\\ \mbox{s.t.}&y_{1}+y_{2}\geq 1,\quad
x_{i}y_{i}=0,\quad 0\leq y_{i}\leq 1+\varepsilon,\quad i=1,2.\end{array}$

We show that, although $(\bar{x},\bar{y})=(0,0,0,1)$ is a nondegenerate
T-stationary point for $\mathcal{R}$, the point $\bar{x}=(0,0)$ is degenerate
as an M-stationary point for the corresponding CCOP. We start with the former,
where we have $a_{00}(\bar{x},\bar{y})=\\{1\\}$,
$a_{01}(\bar{x},\bar{y})=\\{2\\}$, $a_{10}(\bar{x},\bar{y})=\emptyset$,
$\mathcal{E}(\bar{y})=\emptyset$, $\bar{y}_{1}+\bar{y}_{2}=n-s=1$. It holds
for the T-stationarity condition:

$\begin{array}[]{rcl}\begin{pmatrix}-2\\\ 0\\\ c_{1}\\\
c_{2}\end{pmatrix}&=&\bar{\mu}_{3}\cdot\begin{pmatrix}0\\\ 0\\\ 1\\\
1\end{pmatrix}+\bar{\sigma}_{1,2}\cdot\begin{pmatrix}0\\\ 1\\\ 0\\\
0\end{pmatrix}+\bar{\varrho}_{1,1}\cdot\begin{pmatrix}1\\\ 0\\\ 0\\\
0\end{pmatrix}+\bar{\varrho}_{2,1}\cdot\begin{pmatrix}0\\\ 0\\\ 1\\\
0\end{pmatrix},\end{array}$

with the multipliers

$\bar{\mu}_{3}=c_{2}>0,\quad\bar{\sigma}_{1,2}=0,\quad\bar{\varrho}_{1,1}=-2\neq
0,\quad\bar{\varrho}_{2,1}=c_{1}-c_{2}<0.$

Thus, $(0,0,0,1)$ is a T-stationary point fulfilling NDT1-NDT4, but not NDT5.
For $\bar{x}=(0,0)$ we further have:

$\begin{pmatrix}-2\\\ 0\end{pmatrix}=\bar{\gamma}_{1}\cdot\begin{pmatrix}1\\\
0\end{pmatrix}+\bar{\gamma}_{2}\cdot\begin{pmatrix}0\\\ 1\end{pmatrix}$

with the unique multipliers $\bar{\gamma}_{1}=-2,\bar{\gamma}_{2}=0$. Thus,
$\bar{x}$ is an M-stationary point of CCOP, but it is degenerate due to the
violation of NDM3.

Let us discuss the consequences of Theorems 1, 2 and 3 for the regularized
continuous reformulation $\mathcal{R}$ from the global optimization
perspective. We start by looking at the generic properties of $\mathcal{R}$.
Here, genericity refers to the fact that a property of $\mathcal{R}$ holds on
an open and dense subset of defining functions $f$, $h$, and $g$ with respect
to the strong (or Whitney-) topology, cf. [4].

######  Remark 1 (Genericity for $\mathcal{R}$).

We recall from [5] that CC-LICQ holds generically on the CCOP feasible set.
From Theorem 1 we deduce that MPOC-LICQ also holds on the feasible set of a
generic regularized continuous reformulation $\mathcal{R}$. Moreover, it is
known that all M-stationary points of CCOP are generically nondegenerate, see
[5]. In view of Theorem 3, any T-stationary point of $\mathcal{R}$ is induced
by an M-stationary point of CCOP. Hence, Theorem 2 provides that all
T-stationary points of $\mathcal{R}$ are also generically nondegenerate and
additionally fulfill NDT5. This suggests that the assumption of NDT5 is not
restrictive.

We turn our attention to the Morse theory for the regularized continuous
reformulation $\mathcal{R}$.

######  Remark 2 (Morse theory for $\mathcal{R}$).

Since we know by Remark 1 that all T-stationary points of $\mathcal{R}$ are
generically nondegenerate, the Morse theory developed for MPOC in [6] can be
successively applied for its subclass $\mathcal{R}$. Morse theory typically
provides deformation and cell-attachment results for the lower level sets of
an underlying optimization problem. Deformation means in our context that
outside the set of T-stationary points the topology of lower level sets of
$\mathcal{R}$ remains unchanged if the level varies. Cell-attachment describes
the topological changes of the lower level sets if passing a nondegenerate
T-stationary point. Namely, a cell of dimension equal to the T-index needs to
be attached to the lower level set. By doing so, we get the lower level set
corresponding to the T-stationary point up to a homotopy. Based on deformation
and cell-attachment results, it is possible to relate the numbers of
minimizers and saddle points, thus, to adequately capture the global structure
of $\mathcal{R}$. E.g., the so-called mountain pass result from global
optimization says that there exist at least $(k-1)$ T-stationary points of
$\mathcal{R}$ with T-index equal to one, where $k$ denotes the number of local
minimizers of $\mathcal{R}$. These saddle points can be of two types: either
(I) $BI=0$ and $QI=1$ or (II) $BI=1$ and $QI=0$. Whereas the saddle points of
type (I) appear quite similarly in the nonlinear programming, type (II) is
characteristic for the regularization $\mathcal{R}$. In particular, at the
saddle points of type (II) the biactive index set does not vanish. This
phenomenon cannot thus be neglected if studying T-stationary points of
$\mathcal{R}$.

For the global structure of $\mathcal{R}$, it is valuable to make a comparison
to CCOP concerning the numbers of their nondegenerate M- and T-stationary
points with the same M- and T-index, respectively. Let us start by considering
minimizers.

######  Corollary 1 (Minimizers of CCOP and of $\mathcal{R}$).

It holds:

  * a)

If $\bar{x}$ is a nondegenerate minimizer of CCOP, then there exists unique
$\bar{y}$, such that $(\bar{x},\bar{y})$ is a minimizer of $\mathcal{R}$,
moreover, it is nondegenerate.

  * b)

If $(\bar{x},\bar{y})$ is a nondegenrate minimizer of $\mathcal{R}$, then
$\bar{x}$ is a nondegenerate minimizer of CCOP.

###### Proof.

Lemma 3 from [5] says that a nondegenerate minimizer $\bar{x}$ of CCOP has
zero M-index and, in particular, $\left\|\bar{x}\right\|_{0}=s$. In view of
Theorem 2, we immediately obtain the assertion. For the reverse implication,
we apply Corollary 1 from [6] saying that the T-index of a nondegenerate
minimizer $(\bar{x},\bar{y})$ of an MPOC must vanish. In particular, it holds
$a_{00}(\bar{x},\bar{y})=\emptyset$. Then, NDT5 is trivially satisfied, and by
Theorem 3 we are done.

From Corollary 1 we conclude that the numbers of minimizers of CCOP and
$\mathcal{R}$ coincide, at least in a generic situation where they are
nondegenerate. However, the numbers of saddle points with nonvanishing M- and
T-index, respectively, differ.

######  Remark 3 (Saddle points of CCOP and of $\mathcal{R}$).

If at an nondegenerate M-stationary point $\bar{x}$ the sparsity constraint is
not active, i.e. $\left\|\bar{x}\right\|_{0}<s$, it induces multiple
T-stationary points $(\bar{x},\bar{y})$ of $\mathcal{R}$. Due to Theorem 2,
their precise number is $\binom{n-\left\|\bar{x}\right\|_{0}-1}{n-s-1}$.
Moreover, the quadratic indices of $\bar{x}$ and $(\bar{x},\bar{y})$ coincide.
The sparsity index $SI=s-\left\|\bar{x}\right\|_{0}$ of $\bar{x}$ and the
biactive index $BI=\left|a_{00}(\bar{x},\bar{y})\right|$ of
$(\bar{x},\bar{y})$ are equal. The appearance of exponentially many
T-stationary points of the same type can be explained in terms of the cell-
attachment for CCOP. In [5], it is shown that for describing topological
changes of the CCOP lower level sets the attachment of multiple cells of
dimension equal to the M-index is needed. The number of cells to be attached
amounts to
$\binom{n-\left\|\bar{x}\right\|_{0}-1}{s-\left\|\bar{x}\right\|_{0}}$.
However, it holds:

$\binom{n-\left\|\bar{x}\right\|_{0}-1}{n-s-1}=\binom{n-\left\|\bar{x}\right\|_{0}-1}{n-\left\|\bar{x}\right\|_{0}-1-(n-s-1)}=\binom{n-\left\|\bar{x}\right\|_{0}-1}{s-\left\|\bar{x}\right\|_{0}}.$

We see that the number of induced T-stationary points of $\mathcal{R}$
corresponds to the number of cells to be attached if passing the corresponding
M-stationary level in CCOP. This observation suggests that the involved
structure of saddle points in CCOP translates into the increasing number of
saddle points in $\mathcal{R}$.

##  4 Comparison to the literature

At the end of this section we compare our results on the regularized
continuous reformulation $\mathcal{R}$ with those achieved in the literature
for the original continuous reformulation (1). Note that $\mathcal{R}$ becomes
(1) if we set $c=0$ and $\varepsilon=0$. In [1], it has been shown how
minimizers of CCOP and of (1) are related.

######  Proposition 1 (Minimizers of CCOP and of (1), see [1]).

It holds:

  * a)

If $\bar{x}$ is a minimizer of CCOP, then there exists $\bar{y}$, such that
$(\bar{x},\bar{y})$ is a minimizer of (1). If additionally,
$\left\|\bar{x}\right\|_{0}=s$, then $\bar{y}$ is unique.

  * b)

If $(\bar{x},\bar{y})$ is a minimizer of (1) with
$\left\|\bar{x}\right\|_{0}=s$, then $\bar{x}$ is a minimizer of CCOP.

From here we see that there is a one-to-one correspondence between the
minimizers of CCOP and of (1), whenever the sparsity constraint is active. A
similar result follows for the regularized continuous reformulation
$\mathcal{R}$ from Corollary 1, since at a nondegenerate minimizer of CCOP the
cardinality constraint is active. Concerning the general relation between the
M-stationary points of CCOP and the T-stationary points of (1), the following
has been shown in [6].

######  Proposition 2 (Stationarity relations between CCOP and (1), see [6]).

A feasible point $(\bar{x},\bar{y})$ of (1) is T-stationary if and only if the
point $\bar{x}$ is M-stationary for CCOP.

Although this appealing relation holds for (1), cf. a similar result for
$\mathcal{R}$ in Theorems 2 and 3, the original continuous reformulation is
intrinsically degenerate.

######  Proposition 3 (Degeneracy of (1), see [6]).

All Tstationary points of (1) are degenerate.

The degeneracy of T-stationary points of (1) prevails even when we start by a
CCOP with all its M-stationary points being nondegenerate. We emphasize that
this hampers the study of (1) from the global optimization perspective. In
particular, it is not possible to develop the Morse theory for (1) and,
finally, to conclude that the price to pay for reformulating the cardinality
constraint is the appearance of exponentially many additional saddle points,
cf. Remark 3. Actually, the saddle points of (1) may well constitute a
continuum, rather than to be isolated as it is generically the case for
$\mathcal{R}$.

######  Example 2 (Continuum of T-stationary points, see [6]).

We consider the following CCOP:

$\min_{x\in\mathbb{R}^{2}}\,\,\left(x_{1}-1\right)^{2}+\left(x_{2}-1\right)^{2}\quad\mbox{s.\,t.}\quad\left\|{x}\right\|_{0}\leq
1.$

Its M-stationary points are $(1,0)$, $(0,1)$, and $(0,0)$, all of them being
nondegenerate. The corresponding continuous reformulation (1) reads as

$\min_{x,y\in\mathbb{R}^{2}}\,\,\left(x_{1}-1\right)^{2}+\left(x_{2}-1\right)^{2}\quad\mbox{s.\,t.}\quad
y_{1}+y_{2}\geq 1,\quad y_{1},y_{2}\in[0,1],\quad x_{1}y_{1}=0,x_{2}y_{2}=0.$

We get as its T-stationary points:

$(1,0,0,1),(0,1,1,0),\mbox{ and }(0,0,y_{1},y_{2})\mbox{ with
}y_{1},y_{2}\in[0,1],y_{1}+y_{2}\geq 1.$

By Theorem 3 all points are degenerate. Moreover, none of the saddle points is
isolated.

## Conclusions

We emphasize that the introduction of auxiliary $y$-variables shifts the
complexity of dealing with the cardinality constraint in CCOP into the
appearance of multiple saddle points for its continuous reformulation. For
this conclusion to make, we appropriately regularized the original continuous
reformulation (1). The regularized continuous reformulation $\mathcal{R}$
turns out to have the same favorable properties in regard to the minimizers of
CCOP. In addition, we could successively apply the Morse theory developped for
MPOC in [6] to $\mathcal{R}$. This is possible due to the generic
nondegeneracy of its T-stationary points, whereas the T-stationary points of
(1) are intrinsically degenerate. The global structure of the (regularized)
continuous reformulation is therefore fully understood. Next step would be to
study the global structure of the so-called Scholtes-type regularization of
the continuous reformulation along the same lines. This is the topic of
current research.

## References

  * [1] O.P. Burdakov, C. Kanzow, and A. Schwartz.  Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method.  SIAM Journal on Optimization, 26:397–425, 2016.
  * [2] M. Červinka, C. Kanzow, and A. Schwartz.  Constraint qualifications and optimality conditions for optimization problems with cardinality constraints.  Mathematical Programming, 160:353–377, 2016.
  * [3] D. L. Donoho.  Compressed sensing.  IEEE Transactions on Information Theory, 52:1289–1306, 2006.
  * [4] H. Th. Jongen, P. Jonker, and F. Twilt.  Nonlinear Optimization in Finite Dimensions.  Kluwer Academic Publishers, Dordrecht, 2000.
  * [5] S. Lämmel and V. Shikhman.  Cardinality-constrained optimization problems in general position and beyond.  Pure and Applied Functional Analysis, 2021.  to appear, arXiv:2106.08083.
  * [6] S. Lämmel and V. Shikhman.  Optimality conditions for mathematical programs with orthogonality type constraints.  Set-Valued and Variational Analysis, 2021.  to appear, arXiv:2110.11793.
  * [7] Y. Shechtman, Y. C. Eldar, A. Szameit, and M. Segev.  Sparsity-based sub-wavelength imaging with partially spatially incoherent light via quadratic compressed sensing.  Optics Express, 19:14807–14822, 2011.
  * [8] R. Tibshirani.  Regression shrinkage and selection via the lasso.  Journal of the Royal Statistical Society. Series B, 58:267–288, 1996.