11institutetext: Liping Pang 22institutetext: Dalian University of Technology
Dalian, China
<EMAIL_ADDRESS>33institutetext: Menglong Xue, Corresponding author
44institutetext: Dalian University of Technology
Dalian, China
<EMAIL_ADDRESS>55institutetext: Na Xu 66institutetext: Liaoning
Normal University
Dalian, China
<EMAIL_ADDRESS>
# A New Sequential Optimality Condition of Cardinality-Constrained
Optimization Problems and Application

Liping Pang  Menglong Xue  Na Xu

(Received: date / Accepted: date)

###### Abstract

In this paper, we consider the cardinality-constrained optimization problems
and propose a new sequential optimality condition for the continuous
relaxation reformulation which is popular recently. It is stronger than the
existing results and is still a first-order necessity condition for the
cardinality constraint problems without any additional assumptions. Meanwhile,
we provide a problem-tailored weaker constraint qualification, which can
guarantee that new sequential conditions are Mordukhovich-type stationary
points. On the other hand, we improve the theoretical results of the augmented
Lagrangian algorithm. Under the same condition as the existing results, we
prove that any feasible accumulation point of the iterative sequence generated
by the algorithm satisfies the new sequence optimality condition. Furthermore,
the algorithm can converge to the Mordukhovich-type (essentially strong)
stationary point if the problem-tailored constraint qualification is
satisfied.

###### Keywords:

Sequential optimality condition Cardinality constraints Augmented Lagrangian
algorithm Constraint qualification

##  1 Introduction

In recent years, $cardinality$-$constrained~{}optimization~{}problems$ (CCOP)
have attracted great attention, due to its wide application in $portfolio$
protfolio_1 ; protfolio_2 ; protfolio_3 , $compressed~{}sensing$ compress_1 ,
$statistical~{}regression$ statistic_1 ; statistic_2  and other fields, and a
large number of scholars have tried to solve these problems from different
perspectives. According to whether a model transformation is carried out, the
existing methods are mainly divided into direct methods and indirect methods.
While CCOP is non-convex and non-continuous, solving directly is extremely
difficult. Therefore, this paper mainly focuses on the indirect methods, in
which Schwartz_2016_siam.J  presents a new relaxed reformulation with
orthogonal constraints by introducing an auxiliary variable $y$.

The paper Schwartz_2016_siam.J  studied the relationship between problems the
relaxation problem and CCOP, and proved that the two are equivalent in terms
of global solution and feasibility. Compared with CCOP, the relaxation problem
has a better structure property, such as continuity and smoothness, which
allows us to have more tools to deal with the problem. But the relaxation
problem is an optimization problem with orthogonal constraints, which means it
is highly non-convex and difficult to solve. Because of the similarity between
the relaxation problem and
$mathematical~{}programs~{}with~{}complementarity~{}constraints$ (MPCC), a
natural idea is to directly use MPCC’s rich theoretical and numerical methods
to solve the problem. However, this idea is often not feasible. For example,
most of the MPCC’s constraint qualification (CQ) cannot be directly applied to
the relaxation problem (such as MPCC-LICQ). Even if it can be applied, it will
often lead to better conclusions than MPCC. Literature Schwartz_2016_MP
remark 5.7 detailed summary of the difference between the two. This means that
we cannot simply treat the relaxation problem as a special case of MPCC, but
should develop problem-tailored theories and numerical algorithms. In recent
years, as a large number of scholars continue to pay attention to this model,
some results have been achieved.

With the help of the $tightened~{}nonlinear~{}program$ of CCOP, denoted by
$TNLP(x^{*})$. Červinka et al. developed the classic constraint qualification
to the CCOP in Schwartz_2016_MP , proposed some CCOP customized constraint
qualification (CC-CQ), and discussed the relationship between them. In
addition, Kanzow et al. Schwartz_2021_ALA  adapted the quasi-normality CQ in
Bertsekas_2002  and obtained a form corresponding to CCOP. And
Schwartz_2021_Sequ  proposed a cone-continuity constraint qualification. At
the same time, Schwartz_2016_siam.J  defines the first-order stationarity
concept of the relaxation problem, called CC-Strong-stationary (CC-S-
stationary) and CC-Mordukhovich-stationary (CC-M-stationary), where CC-S-
stationary is equivalent to the $Karush$-$Kuhn$-$Tucker$ (KKT) condition of
the relaxation problem, and the CC-M-stationary is equivalent to the KKT
condition of $TNLP(x^{*})$; Ribeiro_2020  provides a Weak-type stationarity.
It is worth mentioning that, unlike CC-S-stationary and Weak-type
stationarity, CC-M-stationary is only related to the original variable $x$,
and Schwartz_2021_ALA  proves that CC-S-stationary and CC-M-stationary are
equivalence in the original variable space. Consequently, this paper will
focus on CC-M-stationarity.

Because of the similarity between the relaxation problem and MPCC, some
researchers try to apply the classic algorithm of MPCC to solve the relaxation
problem. Schwartz_2016_siam.J  and Schwartz_2018  respectively applied two
classic MPCC’s regularization methods to the relaxation problem, and both
obtained better convergence than general MPCC. However, the regularization
strategy is actually to further relax the relaxation problem into a sequence
of regular subproblems and obtain the solution of the relaxation problem by
solving the regular subproblems. Can the relaxation problem be solved directly
without further relaxation? This is an issue worthy of attention. In this
paper, we have made a great answer to this. The main contributions of this
paper are as follows:

  1. $\bullet$

We propose a new sequential optimality condition: CC-PAM-stationarity. In
recent years, the application of sequential optimality condition to stop
criteria and uniform convergence analysis of algorithms has received great
attention. In this area, several sequential optimality conditions have been
proposed for $nonlinear~{}programming$ (NLP) Andreani_2011_AKKT ;
Andreani_2010_CAKKT ; Haeser_2011_SAKKT ; Andreani_2019_PAKKT , where
Andreani_2019_PAKKT  gives the relationship between them. However, there are
still very few relevant results about CCOP. Ribeiro_2020  establishes a
sequential optimality condition, called CC-approximate weak stationarity (CC-
AW-stationarity), but this condition is based on the $(x,y)$ space. Therefore,
Kanzow et al. Schwartz_2021_Sequ  proposed CC-approximate Mordukhovich
stationarity (CC-AM-stationarity), which is only related to $x$, and a proof
is given that it is equivalent to CC-AW-stationary. However, for some
problems, the number of CC-AM-stationary points is numerous, and these points
are often far from the optimal solutions (e.g. Example 3.1). In order to
obtain fewer optimal candidate points, we propose CC-PAM-stationarity, which
is strictly stronger than CC-AM-stationarity, and we show that it is a
necessary condition of CCOP without any assumptions.

  2. $\bullet$

We define a new problem-tailored constraint qualification, called CC-PAM-
regularity, which is weaker than CC-AM-regularity proposed in
Schwartz_2021_Sequ . We prove that any CC-M-stationary point is CC-PAM-
stationary, and conversely, CC-PAM-stationary point is CC-M-stationary if CC-
PAM-regularity condition is satisfied. In other words, CC-PAM-regularity
condition is a CC-CQ. Borrowing the notation of reference ALGENCAN , this
constraint qualification is called strict constraint qualification (SCQ).
Furthermore, we show that CC-PAM-regularity condition is the weakest SCQ
relative to CC-PAM-stationarity.

  3. $\bullet$

We apply CC-PAM-stationarity to safeguarded augmented Lagrangian method and
further improve its convergence. Different from the regularization methods,
the literature Schwartz_2021_ALA  and Schwartz_2021_Sequ  try to directly
apply the safeguarded augmented Lagrangian method of the general NLP to the
relaxation problem and Schwartz_2021_ALA  uses the corresponding solver
ALGENCANALGENCAN ; ALGENCAN_1 ; ALGENCAN_2  to solve the $portfolio$ problem
verify the advantages of the augmented Lagrangian algorithm over the
regularization methods. In addition, the above two regularization methods both
require accurate KKT points for their subproblems, while the safeguarded
augmented Lagrangian method only requires subproblems to be solved
inaccurately. Kanzow et al. Schwartz_2021_Sequ  show that any feasible limit
point of safeguarded augmented Lagrangian method is CC-AM-stationary. And we
proved that under mild conditions such as semialgebraic properties (or the
same conditions as Schwartz_2021_Sequ ), these points are CC-PAM-stationary,
which is strictly better than CC-AM-stationary. If additional conditions of
CC-PAM-regularity hold, they will be CC-M-stationary points.

The organization is as follows: we give some basic definitions and preliminary
conclusions in Sect.2; propose a new sequential optimality condition in
Sect.3, and defines a new problem-tailored constraint qualification in Sect.4.
The convergence of safeguarded augmented Lagrangian method is discussed in
Sect.5, and Sect.6 is a simple summary.

Notation: $I_{g}(x)=\\{i:g_{i}(x)=0,~{}i=1,\dots,m\\}$,
$I_{0}(x)=\\{\imath:x_{\imath}=0,~{}\imath=1,\dots,n\\}$,
$I_{\pm}(x)=\\{\imath:x_{\imath}\neq 0,~{}\imath=1,\dots,n\\}$,
$x_{+}=\max\\{x,0\\}$, $|\cdot|$ denotes $l_{1}$-$norm$,
$\parallel\cdot\parallel$ is Euclidean norm,
$\parallel\cdot\parallel_{\infty}$ denote infinity norm,
$\parallel\cdot\parallel_{0}$ denotes $l_{0}$ norm (the number of non-zero
elements), $e=(1,\dots,1)^{T}\in\mathbb{R}^{n}$, $e_{i}$ is a vector where
only the ith component is 1 and all the others are 0, $x\circ y$ denotes
Hadamard product of $x$ and $y$.

##  2 Preliminaries

In this paper, we consider the optimization problems

$\min~{}f(x)\quad s.t.\hskip 10.00002ptg(x)\leq 0,\quad h(x)=0,\quad\parallel
x\parallel_{0}\ \leq\kappa,$ (1)

where $\kappa$ is an integer and $\kappa<n$,
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}$,
$g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$,
$h:\mathbb{R}^{n}\rightarrow\mathbb{R}^{p}$ is continuously differentiable,
and $\parallel x\parallel_{0}$ is also called cardinality of $x$. Thus, the
problem (1) is called a $cardinality$-$constrained~{}optimization~{}problems$
(CCOP). Let $x^{*}\in\mathbb{R}^{n}$, the tightened NLP problem
($TNLP(x^{*})$) of CCOP defined as

$\min~{}f(x)\quad s.t.\hskip 10.00002ptg(x)\leq 0,\quad h(x)=0,\quad
x_{\imath}=0,\hskip 5.0pt\imath\in I_{0}(x^{*}).$ (2)

And the relaxation problem of CCOP is defined as

$\left\\{\begin{aligned} &\min\quad f(x)\\\ &~{}s.t.\hskip 10.00002ptg(x)\leq
0,\quad h(x)=0,\\\ &\qquad x\circ y=0,\quad n-\kappa-e^{T}y\leq 0,\quad y\leq
e.\end{aligned}\right.$ (3)

Note that the problem (3) is one less non-negative constraint than the form in
Schwartz_2016_siam.J . The literature Schwartz_2021_ALA  shows that this
change will not affect the original conclusion and can lead to a larger
feasible set. In the introduction, we have mentioned the relationship between
CCOP and the problem (3). Below we will give specific conclusions.

###### Proposition 1

Schwartz_2016_siam.J  Let $x\in\mathbb{R}^{n}$, then the following statements
hold.

  * •

If $x$ is a feasible point (or golbal minimizer) of CCOP if and only if there
exists $y\in\mathbb{R}^{n}$ such that $(x,y)$ is feasible point (or golbal
minimizer) of the problem (3).

  * •

If $x$ is a local minimizer of CCOP, then there exists $y\in\mathbb{R}^{n}$
such that $(x,y)$ is local minimizer of the problem (3); Conversely, if
$(x,y)$ is a local minimizer of the problem (3) and $\|x\|_{0}=\kappa$ holds,
then $x$ is a local minimizer of CCOP.

There are several stationarity concepts with the relaxation problem (3).

###### Definition 1

Schwartz_2016_siam.J  Let $(x^{*},y^{*})$ be feasible for (3), then it is
called

  1. (1)

CC-S-stationary, if there exists
$\\{(\lambda,\mu,\gamma)\\}\in\mathbb{R}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n}$
such that

    1. $\bullet$

$\nabla f(x^{*})+\nabla g(x^{*})\lambda+\nabla h(x^{*})\mu+\gamma=0$;

    2. $\bullet$

$\lambda_{i}=0,~{}\forall i\notin
I_{g}(x^{*});~{}\gamma_{\imath}=0,~{}for~{}all~{}\imath~{}such~{}that~{}y_{\imath}^{*}=0$.

  2. (2)

CC-M-stationary, if there exists
$\\{(\lambda,\mu,\gamma)\\}\in\mathbb{R}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n}$
such that

    1. $\bullet$

$\nabla f(x^{*})+\nabla g(x^{*})\lambda+\nabla h(x^{*})\mu+\gamma=0$;

    2. $\bullet$

$\lambda_{i}=0,~{}\forall i\notin
I_{g}(x^{*});~{}\gamma_{\imath}=0,~{}\forall~{}\imath\in I_{\pm}(x^{*})$.

Obviously, CC-M-stationarity is weaker than CC-S-stationarity, but it only
depends on the variable $x$, which can be used as the optimality measure of
CCOP. Another important reason to focus on CC-M-stationary points in this
paper is because of the validity of the following conclusion.

###### Proposition 2

Schwartz_2021_ALA  Let $(x,y)$ is feasible for (3), if $(x,y)$ is a CC-M-
stationary point, then there exists $z\in\mathbb{R}^{n}$ such that $(x,z)$ is
a CC-S-stationary point.

Let us now recall a basic concepts that needed for theoretical analysis
Variational . The upper limit of set-valued maps
$\Theta:~{}\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is

$\limsup_{x\rightarrow x^{*}}\Theta(x):=\left\\{z:\exists x^{k}\rightarrow
x^{*},~{}\exists z^{k}\rightarrow z,~{}z^{k}\in\Theta(x^{k})\right\\}.$

For a function $l:\mathbb{R}^{n}\rightarrow\mathbb{R}$, the (lower) level set
$l_{\alpha}$ is defined as

$l_{\alpha}:=\left\\{~{}x\in\mathbb{R}^{n}:~{}l(x)\leq\alpha\right\\}.$

If any level set of the function $l$ is bounded, then the function $l$ is said
to be level bounded. Since some of the conclusions of this article are
obtained under the assumption of semialgebraic, let us briefly introduce the
basic definition and properties of semialgebraic. We say the set
$C\subseteq\mathbb{R}^{n}$ is semialgebraic if it can be written as a finite
union of sets of the form

$\left\\{x\in\mathbb{R}^{n}:u_{i}(x)=0,~{}v_{i}(x)<0,~{}i=1,\ldots,p\right\\},$

where $u_{i}(x)$, $v_{i}(x)$ are polynomial functions. A function is called
semialgebraic if its graph is a semialgebraic set, obviously polynomial
functions are semialgebraic. Because of their strong stability, semialgebraic
functions are a very broad class of functions.

###### Lemma 1

Attouch_2010  The following properties hold.

  * •

Linear combination of finite number of semialgebraic functions is
semialgebraic.

  * •

Composition of semialgebraic functions is semialgebraic.

  * •

Generalized inverse of a semi-algebraic function is semialgebraic.

  * •

Let $F(x)=\sup\limits_{y\in C}f(x,y)$ and $G(x)=\inf\limits_{y\in C}f(x,y)$,
if the set $C$ and function $f$ are semialgebraic, then both F and G are
semialgebraic.

Semialgebraic functions have another important property, they satisfy the
Kurdyka-Łojasiewicz property.

######  Definition 2 (KL property)

Attouch_2009  We say the function $f$ satisfy the Kurdyka-Łojasiewicz
property, if for any limiting-critical point $x^{*}$ ($0\in\partial
f(x^{*})$), there exist $\epsilon,~{}C>0$, $\theta\in[0,1)$ such that

$C\hskip 1.00006pt|f(x)-f(x^{*})|^{\theta}\leq\|v\|,\quad\forall\hskip
1.00006pt\|x-x^{*}\|\leq\epsilon,~{}v\in\partial f(x^{*}).$ (4)

And if the constraint set of NLP is denoted as

$X:=\\{x:~{}g_{i}(x)\leq 0,~{}i=1,\dots,m;~{}h_{j}(x)=0,~{}j=1,\dots,p\\},$

then standard MFCQ is defined as follows.

######  Definition 3 (MFCQ)

Let $x\in X$, then we say $x$ satisfies Mangasarian-Fromovitz CQ, if the
gradient vectors $\nabla h_{j}(x)~{}(j=1,\dots,p)$ are linearly independent,
and there exists $d\in\mathbb{R}^{n}$ such that

$\nabla h_{j}(x)^{T}d=0,~{}\forall j=1,\dots,p,\qquad\nabla
g_{i}(x)^{T}d<0,~{}\forall i\in I_{g}(x).$

##  3 A New Sequential Optimality Condition

Recently, due to its excellent properties, sequential optimality conditions
are very popular. Although there have been many theoretical results on NLP
problems, to avoid auxiliary variables, we did not directly apply the results
of NLP to problem (3) but proposed new problem-tailed sequential optimality
conditions.

######  Definition 4 (CC-PAM-stationary)

Let $x^{*}$ is feasible for CCOP, we say that $x^{*}$ is CC-positive
approximate Mordukhovich stationary, if there exist
$\\{(x^{k},\lambda^{k},\mu^{k},\gamma^{k})\\}\in\mathbb{R}^{n}\times\mathbb{R}_{+}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n}$
such that:

  1. $(a)$

$x^{k}\rightarrow x^{*}$, $\nabla f(x^{k})+\nabla g(x^{k})\lambda^{k}+\nabla
h(x^{k})\mu^{k}+\gamma^{k}\rightarrow 0$;

  2. $(b)$

$\lambda_{i}^{k}=0,~{}\forall i\notin
I_{g}(x^{*}),~{}\gamma_{\imath}^{k}=0,~{}\forall\imath\in I_{\pm}(x^{*})$;

  3. $(c)$

$\lambda_{i}^{k}g_{i}(x^{k})>0$, if
$\lim\limits_{k}\frac{\lambda_{i}^{k}}{\pi_{k}}>0$;

  4. $(d)$

$\mu_{j}^{k}h_{j}(x^{k})>0$, if
$\lim\limits_{k}\frac{|\mu_{j}^{k}|}{\pi_{k}}>0$;

  5. $(e)$

$\gamma_{\imath}^{k}x_{\imath}^{k}>0$, if
$\lim\limits_{k}\frac{|\gamma_{\imath}^{k}|}{\pi_{k}}>0$;

where $\pi_{k}=\parallel(1,\lambda^{k},\mu^{k},\gamma^{k})\parallel_{\infty}$,
the sequence that satisfy the conditions $(a)$-$(e)$ are called a CC-PAM
sequence.

The condition in Definition 4 only needs to be true for sufficiently large k.
For example, if there is $N$, the conditions $(a)$-$(e)$ are satisfied when
$k\geq N$, then you can set $\hat{x}^{k}=x^{N+k}$, and the new sequence
obtained is the CC-PAM sequence. Observe that, the conditions $(a)$-$(b)$ are
the same as CC-AM-stationarity, so there are the following conclusions.

###### Proposition 3

Let $x^{*}$is feasible for CCOP, if $x^{*}$ is a CC-PAM-stationary point, then
it’s a CC-AM-stationary point.

The converse of the above conclusion is untenable, as shown in the following
example.

###### Example 3.1

We consider

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

Obviously, the problem (5) has the only global optimal solution $(1,1,0)^{T}$.
Let $x=(a,1,0)^{T}$, where $0<a<1$. Take

$x^{k}=(a,1,\frac{1-a}{k}),\quad\lambda^{k}=k,\quad\gamma^{k}=(0,0,-ka)^{T}.$

It is easy to verify that the above sequence satisfies the conditions
$(a)$-$(b)$, that is, $x$ is a CC-AM-stationary point; but it is not CC-PAM-
stationary, because the sequence meets the conditions $(a)$-$(b)$,
$\gamma_{3}^{k}$ and $x_{3}^{k}$ must have different signs, which violates the
condition $(e)$.

As can be seen from Example 3.1, the number of CC-AM-stationary points is
numerous, and these points are far from the optimal solution. While CC-PAM-
stationary points contain fewer candidate points, that is, it is strictly
superior to CC-AM-stationarity. The following Theorem 3.1 states that CC-PAM-
stationarity is a necessary optimality condition for CCOP without any
additional assumptions.

###### Theorem 3.1

Let $x^{*}$ is a local minimizer of CCOP, then $x^{*}$ is a CC-PAM-stationary
point.

Proof If $x^{*}$ is a local minimizer of CCOP, then it is also a local
minimizer of $TNLP(x^{*})$, there exist $\epsilon>0$ such that $x^{*}$ is the
only global minimizer for the following problem

$\left\\{\begin{aligned} \min\quad&f(x)+\frac{1}{2}\parallel
x-x^{*}\parallel^{2}&\\\ ~{}s.t.\hskip 10.00002pt&g(x)\leq 0,\quad
h(x)=0,\quad\\\ &x_{\imath}=0,\hskip 5.0pt\imath\in
I_{0}(x^{*}),\quad\parallel x-x^{*}\parallel\leq\epsilon.\end{aligned}\right.$
(6)

Let $p(x)=\parallel h(x)\parallel^{2}+\parallel
g(x)_{+}\parallel^{2}+\sum\limits_{\imath\in I_{0}(x^{*})}x_{\imath}^{2}$, we
define the local penalized problem

$\left\\{\begin{aligned} \min\quad&f(x)+\frac{1}{2}\parallel
x-x^{*}\parallel^{2}+\frac{M_{k}}{2}p(x)&\\\ ~{}s.t.\hskip
10.00002pt&\parallel x-x^{*}\parallel\leq\epsilon,\end{aligned}\right.$ (7)

where $0<M_{k}\rightarrow+\infty$. For all $M_{k}$, the objective function of
the problem (7) is continuous and the feasible set is compact, there must
exist a global minimizer, denoted as $x^{k}$. Meanwhile, the sequence
$\\{x^{k}\\}$ is bounded, there must be a convergent subsequence. For
simplicity, let us set $x^{k}\rightarrow\bar{x}$. The following proves that
$\bar{x}=x^{*}$.

Since $x^{k}$ is the global minimizer of the problem (7), then

$f(x^{k})+\frac{1}{2}\parallel
x^{k}-x^{*}\parallel^{2}+\frac{M_{k}}{2}p(x^{k})\leq f(x^{*}).$ (8)

Divide both sides of (8) by $M_{k}$ and take the limit, we obtain
$p(\bar{x})\leq 0$. So $\bar{x}$ is feasible for the local problem (6). In
addition, from (8)

$f(x^{k})+\frac{1}{2}\parallel x^{k}-x^{*}\parallel^{2}\leq f(x^{*}).$

Letting $k\rightarrow+\infty$ yields

$f(\bar{x})+\frac{1}{2}\parallel\bar{x}-x^{*}\parallel^{2}\leq f(x^{*}),$

but $x^{*}$ is the only global minimum point of the problem (6), there must be
$\bar{x}=x^{*}$, that is, $x^{k}\rightarrow x^{*}$.

When $k$ is sufficiently large, there is obviously $\parallel
x^{k}-x^{*}\parallel\leq\epsilon$. For simplicity, let’s set
$\\{x^{k}\\}\subseteq\\{x:\parallel x^{k}-x^{*}\parallel\leq\epsilon\\}$. From
the necessary optimality condition of the problem (7) we obtain

$\nabla f(x^{k})+\nabla g(x^{k})(M_{k}g(x^{k})_{+})+\nabla
h(x^{k})(M_{k}h(x^{k}))+\sum_{\imath\in
I_{0}(x^{*})}M_{k}x_{\imath}^{k}e_{\imath}=x^{*}-x^{k}.$

And we define

$\lambda^{k}=M_{k}g(x^{k})_{+},\quad\mu^{k}=M_{k}h(x^{k}),\quad\gamma_{\imath}^{k}=M_{k}x_{\imath}^{k},\imath\in
I_{0}(x^{*}),\quad\gamma_{\imath}^{k}=0,\imath\in I_{\pm}(x^{*}),$

then

$\nabla f(x^{k})+\nabla g(x^{k})\lambda^{k}+\nabla
h(x^{k})\mu^{k}+\gamma^{k}\rightarrow 0.$

For all $i\notin I_{g}(x^{*})$, there is $g_{i}(x^{*})<0$, then
$g_{i}(x^{k})<0$ when $k$ is sufficiently large, so $\lambda_{i}^{k}=0$.
Meanwhile, by the definition of $\gamma^{k}$, obviously

$\gamma_{\imath}^{k}=0,\quad\forall\imath\in I_{\pm}(x^{*}).$

If $\lambda_{i}^{k}>0$, since $\lambda_{i}^{k}=M_{k}g_{i}(x^{k})_{+}$ then
$g_{i}(x^{k})>0$, so

$\lambda_{i}^{k}g_{i}(x^{k})>0.$

Similarly, if $\mu_{j}^{k}\neq 0$, then $h_{j}(x^{k})\neq 0$; and if
$\gamma_{\imath}^{k}\neq 0$, we obtain $x_{\imath}^{k}\neq 0$. So

$\mu_{j}^{k}h_{j}(x^{k})=M_{k}(h_{j}(x^{k}))^{2}>0~{}~{}and~{}~{}\gamma_{\imath}^{k}x_{\imath}^{k}=M_{k}(x_{\imath}^{k})^{2}>0.$

In summary, $\\{(x^{k},~{}\lambda^{k},~{}\mu^{k},~{}\gamma^{k})\\}$ is a CC-
PAM sequence, that is, $x^{*}$ is a CC-PAM-stationary point. ∎

Theorem 3.1 and Example 3.1 show that CC-PAM-stationary point we proposed can
be used as a candidate point for the optimal solution, and it is more suitable
as a measure of optimality than CC-AM-stationarity. On the other hand, another
advantage of the sequential optimality condition is that it has nothing to do
with the specific algorithm. That is, CC-PAM-stationary point has some
theoretical properties, and any algorithm that can generate the CC-PAM-
stationary point also has the same nature. Therefore, the existence of
sequential optimality conditions provides a tool for establishing a unified
framework for optimality theory.

The converse of the above conclusion is untenable, as shown in the following
example.

###### Example 3.2

In two-dimensional space, consider a simple geometric problem, set
$z=(1,1)^{T}$, find the point closest to $z$ on the coordinate axis. This
problem can be modeled as

$\min~{}\frac{1}{2}\left[(x_{1}-1)^{2}+(x_{2}-1)^{2}\right]\quad
s.t.~{}\|x\|_{0}\leq 1.$ (9)

Obviously, $(1,0)^{T}$ and $(0,1)^{T}$ are the two global optimal solutions of
the problem. The following shows that $x^{*}=(0,0)^{T}$ is a CC-PAM-stationary
point. Take

$x^{k}=(\frac{1}{k+1},\frac{1}{k+1})^{T}\quad\gamma^{k}=(1-\frac{1}{k+1},1-\frac{1}{k+1})^{T},$

it is easy to verify that $\\{(x^{k},\gamma^{k})\\}$ satisfies the conditions
$(a)$-$(e)$, that is, $x^{*}=(0,0)^{T}$ is a CC-PAM-stationary point, but it
is not a local minimizer of the problem (9).

We know that CC-M-stationarity is stronger than the CC-AM-stationarity, and
CC-PAM-stationarity we proposed is also strictly better than CC-AM-
stationarity. An interesting question is whether CC-M-stationarity is stronger
than CC-PAM-stationarity, and under what conditions are the two equivalent.
This issue will be described in detail in the next section.

##  4 A New Constraint Qualification

Let $x^{*}$ be feasible for CCOP, $\alpha\geq 0$, $\beta\geq 0$,
$x\in\mathbb{R}^{n}$, we defined the set

$\Theta(x,\alpha,\beta)=\left\\{\nabla g(x)\lambda+\nabla
h(x)\mu+\gamma\left|\begin{aligned}
(\lambda,\mu,\gamma)&\in\mathbb{R}_{+}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n},\\\
\lambda_{i}=0,~{}\forall i\notin
I_{g}&(x^{*}),~{}\gamma_{\imath}=0,~{}~{}\forall\imath\in I_{\pm}(x^{*}),\\\
\lambda_{i}g_{i}(x)\geq\alpha,~{}~{}&if~{}~{}\lambda_{i}~{}>\beta\parallel(1,\lambda,\mu,\gamma)\parallel_{\infty},\\\
\mu_{j}h_{j}(x)\geq\alpha,~{}~{}&if~{}|\mu_{j}|>\beta\parallel(1,\lambda,\mu,\gamma)\parallel_{\infty},\\\
\gamma_{\imath}x_{\imath}\geq\alpha,~{}~{}&if~{}|\gamma_{\imath}|>\beta\parallel(1,\lambda,\mu,\gamma)\parallel_{\infty}\\\
\end{aligned}\right.\right\\}.$

Obviously, if $x^{*}$ is a CC-M-stationary point, then it can be written as

$-\nabla f(x^{*})\in\Theta(x^{*},0,0).$ (10)

In addition, CC-PAM-stationarity can be expressed as the limit form of the set
sequence, and the following conclusions are established.

###### Lemma 2

$x^{*}$ is CC-PAM-stationary $\iff-\nabla
f(x^{*})\in\limsup\limits_{x^{k}\rightarrow x^{*},\alpha\downarrow
0,\beta\downarrow 0}\Theta(x,\alpha,\beta).$

Proof ”$\Rightarrow$” If $x^{*}$ is CC-PAM-stationary, from Definition 4,
there is a sequence $\\{(x^{k},\lambda^{k},\mu^{k},\gamma^{k})\\}$ such that
the conditions $(a)$-$(e)$ holds. Take

$\theta^{k}=\nabla g(x^{k})\lambda^{k}+\nabla h(x^{k})\mu^{k}+\gamma^{k},$

we know $\nabla f(x^{k})+\theta^{k}\rightarrow 0$, by the condition $(a)$,
then $\theta^{k}\rightarrow\theta^{*}=-\nabla f(x^{*})$.

To prove the conclusion, just find the appropriate $\\{\alpha_{k}\\}$,
$\\{\beta_{k}\\}$ such that $\alpha_{k}\downarrow 0$, $\beta_{k}\downarrow 0$
and $\theta^{k}\in\Theta(x^{k},\alpha_{k},\beta_{k})$.

Let $\pi_{k}=\parallel(1,\lambda^{k},\mu^{k},\gamma^{k})\parallel_{\infty}$,
then the sequence
$\left\\{\frac{(\lambda^{k},\mu^{k},\gamma^{k})}{\pi_{k}}\right\\}$ must have
a convergent subsequence. For simplicity, let’s set it to converge. Let

$I=\left\\{i\left|\lim\limits_{k\rightarrow\infty}\frac{\lambda_{i}^{k}}{\pi_{k}}>0\right.\right\\},~{}~{}J=\left\\{j\left|\lim\limits_{k\rightarrow\infty}\frac{|\mu_{j}^{k}|}{\pi_{k}}>0\right.\right\\},~{}~{}K=\left\\{\imath\left|\lim\limits_{k\rightarrow\infty}\frac{|\gamma_{\imath}^{k}|}{\pi_{k}}>0\right.\right\\},$

so we can take

$\alpha_{k}=\min\left\\{(\lambda_{i}^{k}g_{i}(x^{k}))_{i\in
I},~{}(\mu_{j}^{k}h_{j}(x^{k}))_{j\in
J},~{}(\gamma_{\imath}^{k}x_{\imath}^{k})_{\imath\in
K},~{}\frac{1}{k}\right\\}.$

Obviously there is $\alpha_{k}\rightarrow 0$, and when k is sufficiently
large, we obtain

$\frac{\lambda_{i}^{k}}{\pi_{k}}>\max\left\\{(\frac{\lambda_{i}^{k}}{\pi_{k}})_{i\notin
I},~{}(\frac{|\mu_{j}^{k}|}{\pi_{k}})_{j\notin
J},~{}(\frac{|\gamma_{\imath}^{k}|}{\pi_{k}})_{\imath\notin
K},~{}\frac{1}{k}\right\\}\quad\forall i\in I.$

Regarding $\mu$, $\gamma$ has a similar conclusion. And let

$\beta_{k}=\max\left\\{(\frac{\lambda_{i}^{k}}{\pi_{k}})_{i\notin
I},~{}(\frac{|\mu_{j}^{k}|}{\pi_{k}})_{j\notin
J},~{}(\frac{|\gamma_{\imath}^{k}|}{\pi_{k}})_{\imath\notin
K},~{}\frac{1}{k}\right\\},$

Obviously there is $\beta_{k}\rightarrow 0$. Combining the non-negativity of
$\\{\alpha_{k}\\}$ and $\\{\beta_{k}\\}$, we can set $\alpha_{k}\downarrow 0$
and $\beta_{k}\downarrow 0$ (if necessary, subsequence can be taken). And we
obtain

$\theta^{k}\in\Theta(x^{k},\alpha_{k},\beta_{k}).$

”$\Leftarrow$” By hypothesis, there is $\\{x^{k}\\}$, $\\{\alpha_{k}\\}$,
$\\{\beta_{k}\\}$ such that

$x^{k}\rightarrow 0,~{}\alpha_{k}\downarrow 0,~{}\beta_{k}\downarrow
0,~{}\Theta(x^{k},\alpha_{k},\beta_{k})\ni\theta^{k}\rightarrow-\nabla
f(x^{*}).$

Therefore, there is $\\{(\lambda^{k},\mu^{k},\gamma^{k})\\}$ such that

$\theta^{k}=\nabla g(x^{k})\lambda^{k}+\nabla h(x^{k})\mu^{k}+\gamma^{k},$

so $\nabla f(x^{k})+\theta^{k}\rightarrow 0$, that is

$\nabla f(x^{k})+\nabla g(x^{k})\lambda^{k}+\nabla
h(x^{k})\mu^{k}+\gamma^{k}\rightarrow 0.$

Since $\theta^{k}\in\Theta(x^{k},\alpha_{k},\beta_{k})$, we obtain
$\lambda_{i}^{k}=0~{}(\forall i\notin
I_{g}(x^{*})),~{}\gamma_{\imath}^{k}=0~{}(\forall\imath\in I_{\pm}(x^{*}))$.
In addition, if
$\lim\limits_{k\rightarrow\infty}\frac{|\mu_{j}^{k}|}{\pi_{k}}>0$, then
$\frac{|\mu_{j}^{k}|}{\pi_{k}}>\beta_{k}$ for all $k$ large enough, this
implies

$\mu_{j}^{k}h_{j}(x^{k})\geq\alpha_{k}>0,$

that is the condition (b) is satisfied. There are similar conclusions about
$\lambda$ and $\gamma$, so $x^{*}$ is CC-PAM-stationary. ∎

Now, we give a new regularity condition.

######  Definition 5 (CC-PAM-regularity)

We say a feasible point $x^{*}$ of CCOP satisfies the CC-PAM-regularity
condition, if

$\limsup\limits_{x\rightarrow x^{*},~{}\alpha\downarrow 0,~{}\beta\downarrow
0}\Theta(x,\alpha,\beta)\subseteq\Theta(x^{*},0,0).$

###### Remark 4.1

CC-PAM-regularity condition is weaker than CC-AM-regularity condition. Take

$\hat{\Theta}(x)=\left\\{\nabla g(x)\lambda+\nabla
h(x)\mu+\gamma\left|\begin{aligned}
(\lambda,\mu,\gamma)&\in\mathbb{R}_{+}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n},\\\
\lambda_{i}=0,~{}\forall i\notin
I_{g}&(x^{*}),~{}\gamma_{\imath}=0,~{}~{}\forall\imath\in
I_{\pm}(x^{*})\end{aligned}\right.\right\\}.$

Obviously there is $\hat{\Theta}(x^{*})=\Theta(x^{*},0,0)$, and for all
$\alpha\geq 0$, $\beta\geq 0$, $\forall x\in\mathbb{R}^{n}$ we have
$\Theta(x,\alpha,\beta)\subseteq\hat{\Theta}(x)$. Therefore, if CC-AM-
regularity condition is established, that is, $\limsup_{x\rightarrow
x^{*}}\hat{\Theta}(x)\subseteq\hat{\Theta}(x^{*})=\Theta(x^{*},0,0)$, we
obtain $\limsup_{x\rightarrow x^{*},~{}\alpha\downarrow 0,~{}\beta\downarrow
0}\Theta(x,\alpha,\beta)\subseteq\Theta(x^{*},0,0)$.

Now we give the relationship between CC-PAM-stationarity and CC-M-
stationarity.

###### Theorem 4.1

Let $x^{*}$ is feasible for CCOP, the following statements hold.

  1. $(i)$

If $x^{*}$ is a CC-M-stationary point, then it is a CC-PAM-stationary point.

  2. $(ii)$

If $x^{*}$ is a CC-PAM-stationary point, and CC-PAM-regularity condition holds
at $x^{*}$, then $x^{*}$ is a CC-M-stationary point.

  3. $(iii)$

If for any continuous differentiable function $f$, the following relationship
holds:

$x^{*}~{}\text{CC-PAM-}stationary\quad\Longrightarrow\quad
x^{*}~{}\text{CC-M-}stationary,$

then CC-PAM-regularity condition holds at $x^{*}$.

Proof $(i)$ If $x^{*}$ is a CC-M-stationary point, then

$-\nabla f(x^{*})\in\Theta(x^{*},0,0)\subseteq\limsup\limits_{x\rightarrow
x^{*},~{}\alpha\downarrow 0,~{}\beta\downarrow 0}\Theta(x,\alpha,\beta).$

$(ii)$ By Lemma 2, we obtain

$-\nabla f(x^{*})\in\limsup\limits_{x\rightarrow x^{*},~{}\alpha\downarrow
0,~{}\beta\downarrow 0}\Theta(x,\alpha,\beta)\subseteq\Theta(x^{*},0,0),$

so $x^{*}$ is CC-M-stationary.

$(iii)$ We take $\theta^{*}\in\limsup\limits_{x\rightarrow
x^{*},~{}\alpha\downarrow 0,~{}\beta\downarrow 0}\Theta(x,\alpha,\beta)$, and
define $f=x^{T}\theta^{*}$, then $\nabla f(x^{*})=\theta^{*}$. Since

$\theta^{*}\in\limsup\limits_{x\rightarrow x^{*},~{}\alpha\downarrow
0,~{}\beta\downarrow
0}\Theta(x,\alpha,\beta)\quad\Longrightarrow\quad\theta^{*}\in\Theta(x^{*},0,0),$

then $\limsup\limits_{x\rightarrow x^{*},~{}\alpha\downarrow
0,~{}\beta\downarrow 0}\Theta(x,\alpha,\beta)\subseteq\Theta(x^{*},0,0)$. ∎

In Theorem 3.1, we have proved that any local minimizer of CCOP (or
$TNLP(x^{*})$) satisfies the sequential optimality condition (CC-PAM-
stationarity), and Theorem 4.1$~{}(ii)$ explains

$\text{CC-PAM}~{}+~{}\text{CC-PAM-
regularity}\quad\Longrightarrow\quad\text{CC-M},$ (11)

in other words, CC-PAM-regularity condition is a CC-CQ. Literature ALGENCAN
calls the constraint qualification that satisfies the property (11) as the
strict constraint qualification (SCQ). And the conclusion $(iii)$ means that
the CC-PAM-regularity condition is the weakest SCQ relative to CC-PAM-
stationarity. Next, we will apply CC-PAM-stationarity and CC-PAM-regularity
condition to enhance the theoretical results of the augmented Lagrangian
method.

##  5 Convergence of Safeguarded Augmented Lagrangian Method

This section will discuss the convergence of using safeguarded augmented
Lagrangian method to directly solve the relaxation problem (3). Let
$\Lambda=(\lambda,\mu,\gamma,\delta,\eta)\in\mathbb{R}_{+}^{m}\times\mathbb{R}^{p}\times\mathbb{R}^{n}\times\mathbb{R}_{+}\times\mathbb{R}_{+}^{n}$,
$\rho>0$, then the augmented Lagrangian function of the problem (3) can be
written as

$\displaystyle\mathscr{L}(x,$ $\displaystyle
y,\Lambda,\rho)=f(x)+\frac{\rho}{2}\left[\left\|\left(g(x)+\frac{\lambda}{\rho}\right)_{+}\right\|^{2}+\left\|h(x)+\frac{\mu}{\rho}\right\|^{2}+\right.$
(12) $\displaystyle\left.\left\|x\circ
y+\frac{\gamma}{\rho}\right\|^{2}+\left\|\left(n-\kappa-e^{T}y+\frac{\delta}{\rho}\right)_{+}\right\|^{2}+\left\|\left(y-e+\frac{\eta}{\rho}\right)_{+}\right\|^{2}\right].$

Now we give safeguarded augmented Lagrangian method ALGENCAN .

###### Algorithm 5.1

Safeguarded Augmented Lagrangian Method (SALM)
Step 1(Initialization) Given
$(x^{0},y^{0})\in\mathbb{R}^{n}\times\mathbb{R}^{n}$, $\lambda_{max}>0$,
$\mu_{min}<\mu_{max}$, $\gamma_{min}<\gamma_{max}$, $\delta_{max}>0$,
$\eta_{max}>0$, $\tau>1$, $\sigma>1$, $\\{\epsilon_{k}\\}\in\mathbb{R}_{+}$
and $\epsilon_{k}\downarrow 0$. Choose initial values
$\bar{\lambda}^{0}\in[0,\lambda_{max}]^{m}$,
$\bar{\mu}^{0}\in[\mu_{min},\mu_{max}]^{p}$,
$\bar{\gamma}^{0}\in[\gamma_{min},\gamma_{max}]^{n}$,
$\bar{\delta}^{0}\in[0,\delta_{max}]$, $\bar{\eta}^{0}\in[0,\eta_{max}]^{n}$,
$\rho_{0}>0$ and set $k=1$.
Step 2(Update of the iterate) Compute $(x^{k},y^{k})$ as an approximate
solution of

$\min~{}\mathscr{L}(x,y,\bar{\Lambda}^{k-1},\rho_{k-1})$ (13)

such that

$\parallel\nabla\mathscr{L}(x^{k},y^{k},\bar{\Lambda}^{k-1},\rho_{k-1})\parallel\leq\epsilon_{k}.$
(14)

Step 3(Update of the approximate multipliers)

$\displaystyle\lambda^{k}$
$\displaystyle=(\rho_{k-1}g(x^{k})+\bar{\lambda}^{k-1})_{+},\hskip
30.00005pt\mu^{k}=\rho_{k-1}h(x^{k})+\bar{\mu}^{k-1},$ (15)
$\displaystyle\gamma^{k}$ $\displaystyle=\rho_{k-1}x^{k}\circ
y^{k}+\bar{\gamma}^{k-1},\hskip
35.00005pt\eta^{k}=(\rho_{k-1}(y^{k}-e)+\bar{\eta}^{k-1})_{+},$ (16)
$\displaystyle\delta^{k}$
$\displaystyle=(\rho_{k-1}(n-\kappa-e^{T}y^{k})+\bar{\delta}^{k-1})_{+}.\quad\
$ (17)

Step 4 (Update of the penalty parameter) Take

$\displaystyle U^{k}$
$\displaystyle:=\min\left\\{-g(x^{k}),\frac{\bar{\lambda}^{k-1}}{\rho_{k-1}}\right\\},~{}V^{k}:=\min\left\\{-(n-\kappa-e^{T}y^{k}),\frac{\bar{\delta}^{k-1}}{\rho_{k-1}}\right\\},$
$\displaystyle R^{k}$
$\displaystyle:=\min\left\\{-(y^{k}-e),\frac{\bar{\eta}^{k-1}}{\rho_{k-1}}\right\\},$

if $k=1$ or

$\displaystyle\max\\{\parallel U^{k-1}\parallel,\parallel
h(x^{k-1})\parallel,\parallel x^{k-1}\circ y^{k-1}\parallel,\parallel
V^{k-1}\parallel,\parallel R^{k-1}\parallel\\}$ (18)
$\displaystyle\geq\tau\max\\{\parallel U^{k}\parallel,\parallel
h(x^{k})\parallel,\parallel x^{k}\circ y^{k}\parallel,\parallel
V^{k}\parallel,\parallel R^{k}\parallel\\},$

set $\rho_{k}=\rho_{k-1}$, otherwise set $\rho_{k}=\sigma\rho_{k-1}$.
Step 5 (Update of the safeguarded multipliers) Choose
$\bar{\lambda}^{k}\in[0,\lambda_{max}]^{m}$,
$\bar{\mu}^{k}\in[\mu_{min},\mu_{max}]^{p}$,
$\bar{\gamma}^{k}\in[\gamma_{min},\gamma_{max}]^{n}$,
$\bar{\delta}^{k}\in[0,\delta_{max}]$, $\bar{\eta}^{k}\in[0,\eta_{max}]^{n}$.

Set $k\leftarrow k+1$, go to Step 1.

Algorithm 5.1 introduces the safeguard multiplier based on the classic
augmented Lagrangian method. The convergence is further improved, and the
whole sequence convergence required in the classic methods is relaxed to the
subsequence convergence Kanzow_2017 . The updated way of safeguard multiplier
in Step 5 is not unique, such as the most popular projection method. In
addition, it should be emphasized that the stopping criterion is not set in
Algorithm 5.1, and we will explore this issue in the subsequent convergence
analysis.

Before proceeding to the analysis of convergence, a useful assumption is
given.

###### Assumption 5.1

Assuming that $g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ and
$h:\mathbb{R}^{n}\rightarrow\mathbb{R}^{p}$ in CCOP are semialgebraic
function.

In Sect.2, we have introduced the basic concepts and properties of
semialgebraic, explaining that Assumption 5.1 is a relatively mild condition,
which covers a large class of problems. In the subsequent analysis, we will
see that the ”semialgebraic” assumption can be further relaxed. Let
$p(x,y,\Lambda,\rho)=\frac{1}{\rho}\left[\mathscr{L}(x,y,\Lambda,\rho)-f(x)\right]$,
it is actually the second penalty part of (12) (excluding penalty parameters).
Under the assumption 5.1, the following conclusions can be easily obtained by
Lemma 1.

###### Lemma 3

If Assumption 5.1 holds, then for any given $\Lambda$, $\rho$,
$p(x,y,\Lambda,\rho)$ semialgebraic.

Let $\\{(x^{k},y^{k})\\}$ be the iterative sequence generated by Algorithm
5.1. We already know that if $\\{x^{k}\\}$ is bounded on a subsequence, then
$\\{y^{k}\\}$ is bounded on the corresponding subsequence (for detailed proof,
see Schwartz_2021_ALA ). This property shows that the boundedness of the
entire iteration sequence can be obtained only by ensuring that it is bounded
in the $x$ space (that is, in the original problem). A sufficient condition is
given below.

###### Lemma 4

If $f$ is level bounded, then for any given $\Lambda$, $\rho$,
$\mathscr{L}(x,y,\Lambda,\rho)$ is also level bounded.

Proof Let

$T(y,\delta,\eta,\rho)=\frac{\rho}{2}\left[\left\|\left(n-\kappa-e^{T}y+\frac{\delta}{\rho}\right)_{+}\right\|^{2}+\left\|\left(y-e+\frac{\eta}{\rho}\right)_{+}\right\|^{2}\right].$

Meanwhile, for any $\alpha\in\mathbb{R}$, set $f_{\alpha}$, $T_{\alpha}$ as
their respective levels under the $\alpha$ level set. By hypothesis,
$f_{\alpha}$ is bounded, and for $T(y,\delta,\eta,\rho)$, we have

$\parallel y\parallel\rightarrow\infty\quad\Longrightarrow\quad
T(y,\delta,\eta,\rho)\rightarrow\infty,$

therefore, $T_{\alpha}$ is also bounded. Because of

$\\{(x,y):\mathscr{L}(x,y,\Lambda,\rho)\leq\alpha\\}\subseteq f_{\alpha}\times
T_{\alpha},$

then $\mathscr{L}(x,y,\Lambda,\rho)$ is level bounded. ∎

Lemma 4 shows that $\mathscr{L}$ is consistent level bounded about $\Lambda$
and $\rho$. If the subproblem (13) is solved using a descent algorithm, then
the sequence generated by Algorithm 5.1 must be bounded. Let us now discuss
the convergence of Algorithm 5.1.

###### Theorem 5.1

Let $(x^{*},y^{*})$ be an accumulation point of $\\{(x^{k},y^{k})\\}$
generated by Algorithm 5.1, that is feasible for the problem (3), and
Assumption 5.1 holds, then $x^{*}$ is a CC-PAM-stationary point.

Proof For simplicity, we assum, $(x^{k},y^{k})\rightarrow(x^{*},y^{*})$. By
(14), we obtain

$\nabla f(x^{k})+\nabla g(x^{k})\lambda^{k}+\nabla
h(x^{k})\mu^{k}+\gamma^{k}\circ y^{k}\rightarrow 0.$

Now let’s do the proof in two cases.
$i)~{}\\{\rho_{k}\\}$ is bounded.

If $\\{\rho_{k}\\}$ is bounded, combined with $\\{\bar{\Lambda}^{k}\\}$ being
bounded and (15)-(17), we know that $\\{\Lambda^{k}\\}$ is also bounded. To
avoid repeatedly taking subsequence, we assum $\Lambda^{k}\rightarrow\Lambda$,
then

$\nabla f(x^{*})+\nabla g(x^{*})\lambda+\nabla h(x^{*})\mu+\gamma\circ
y^{*}=0.$

Let $\mathcal{I}=\\{i:\lambda_{i}>0\\}$, $\mathcal{J}=\\{j:\mu_{j}\neq 0\\}$,
$\mathcal{K}=\\{\imath:\gamma_{\imath}y_{\imath}^{*}\neq 0\\}\subseteq
I_{0}(x^{*})$. If the three are all empty sets, then let $\hat{x}^{k}=x^{*}$,
$\hat{\lambda}^{k}=\hat{\mu}^{k}=\hat{\gamma}^{k}=0$, it can be concluded that
$x^{*}$ is a CC-PAM-stationary point. Conversely, if there is at least one
non-empty, it can be obtained from Lemma 1 of Andreani_2012 , there exist
$I\subseteq\mathcal{I}$, $J\subseteq\mathcal{J}$, $K\subseteq\mathcal{K}$ and
$(\hat{\lambda}_{I},\hat{\mu}_{J},\hat{\gamma}_{K})$ such that

$\displaystyle\nabla f(x^{*})+\sum_{i\in I}\hat{\lambda}_{i}\nabla
g_{i}(x^{*})+\sum_{j\in J}\hat{\mu}_{j}\nabla h_{j}(x^{*})+\sum_{\imath\in
K}\hat{\gamma}_{\imath}e_{\imath}=0;$ (19)
$\displaystyle\hat{\lambda}_{i}\cdot\lambda_{i}>0,~{}i\in I;$ (20)
$\displaystyle\hat{\mu}_{j}\cdot\mu_{j}>0,~{}j\in J;$ (21)
$\displaystyle\hat{\gamma}_{\imath}\cdot(\gamma_{\imath}y_{\imath}^{*})>0,~{}\imath\in
K;$ (22)

And the vector group

$\mathcal{F}=\\{\nabla g_{i}(x^{*})~{}(i\in I),~{}\nabla h_{j}(x^{*})~{}(j\in
J),~{}e_{\imath}~{}(\imath\in K)\\}$

is linearly independent.

Take

$\hat{\lambda}_{i}^{k}=\left\\{\begin{aligned} &\hat{\lambda}_{i}\hskip
15.00002pti\in I,\hskip 8.99994pt\\\ &0\hskip
8.99994ptotherwise,\end{aligned}\right.\hskip
1.99997pt\hat{\mu}_{j}^{k}=\left\\{\begin{aligned} &\hat{\mu}_{j}\hskip
15.00002ptj\in J,\hskip 8.99994pt\\\ &0\hskip
8.99994ptotherwise,\end{aligned}\right.\hskip
1.99997pt\hat{\gamma}_{\imath}^{k}=\left\\{\begin{aligned}
&\hat{\gamma}_{\imath}~{}\hskip 15.00002pt\imath\in K,\hskip 7.5pt\\\ &0\hskip
8.99994ptotherwise,\end{aligned}\right..$ (23)

The next key problem is to find a sequence $\\{\hat{x}^{k}\\}$,
$\hat{x}^{k}\rightarrow x^{*}$ such that
$\\{(\hat{x}^{k},\hat{\lambda}^{k},\hat{\mu}^{k},\hat{\gamma}^{k})\\}$ is a
CC-PAM sequence. Let

$J_{+}:=\\{j:\hat{\mu}_{j}>0\\},~{}J_{-}:=\\{j:\hat{\mu}_{j}<0\\},~{}K_{+}:=\\{\imath:\hat{\gamma}_{\imath}>0\\},~{}K_{-}:\\{\imath:\hat{\gamma}_{\imath}<0\\},$

obviously $J_{+}\bigcup J_{-}=J$, $K_{+}\bigcup K_{-}=K$. And we define

$\displaystyle Z:=\\{x:g_{i}(x)\geq 0,$ $\displaystyle~{}h_{j_{+}}(x)\geq
0,~{}h_{j_{-}}(x)\leq 0,~{}x_{\imath_{+}}\geq 0,~{}x_{\imath_{-}}\leq 0,$
$\displaystyle i\in I,~{}j_{+}\in J_{+},~{}j_{-}\in J_{-},~{}\imath_{+}\in
K_{+},~{}\imath_{-}\in K_{-}\\}.$

Since the vector group $\mathcal{F}$ is linearly independent, then $Z$
satisfies LICQ at $x^{*}$, then MFCQ must also be satisfied. Thus, there
exists $d\in\mathbb{R}^{n}$ such that

$\nabla g_{i}(x^{*})^{T}d>0,~{}\nabla h_{j_{+}}(x^{*})^{T}d>0,~{}\nabla
h_{j_{-}}(x^{*})^{T}d<0,~{}e_{\imath_{+}}^{T}d>0,~{}e_{\imath_{-}}^{T}d<0,$

where $i\in I,~{}j_{+}\in J_{+},~{}j_{-}\in J_{-},~{}\imath_{+}\in
K_{+},~{}\imath_{-}\in K_{-}$. For simplicity, we set $\parallel
d\parallel=1$, and take

$\hat{x}^{k}=x^{*}+t_{k}d,$

where $t_{k}\downarrow 0$, this implies $\hat{x}^{k}\rightarrow x^{*}$. By
(19) and (23), we have

$\nabla f(\hat{x}^{k})+\nabla g(\hat{x}^{k})\hat{\lambda}^{k}+\nabla
h(\hat{x}^{k})\hat{\mu}^{k}+\hat{\gamma}^{k}\rightarrow 0.$

Let $i\notin I_{g}(x^{*})$, we have $g_{i}(x^{*})<0$, and $g_{i}(x^{k})<0$
when $k$ is sufficiently large. By (18), we know

$\parallel U^{k}\parallel\rightarrow
0~{}\Longrightarrow~{}\bar{\lambda}_{i}^{k-1}\rightarrow 0.$

Futhermore, (15) implies

$\lambda_{i}^{k}=(\rho_{k-1}g_{i}(x^{k})+\bar{\lambda}_{i}^{k-1})_{+}=0,\quad\text{for
all k sufficiently large},$

then $\lambda_{i}=0$, that is, $i\notin\mathcal{I}$. Hence, by (23), we have

$\hat{\lambda}_{i}^{k}=0,\quad\forall i\notin I_{g}(x^{*}).$ (24)

Take an index $\imath\in I_{\pm}(x^{*})$, we know $x_{\imath}^{*}\neq 0$,
$y_{\imath}^{*}=0$, then $\gamma_{\imath}y_{\imath}^{*}=0$, i.e.
$\imath\notin\mathcal{K}$. By (23), we have

$\hat{\gamma}_{\imath}^{k}=0,\quad\imath\in I_{\pm}(x^{*}).$ (25)

The following verifies that
$\\{(\hat{x}^{k},\hat{\lambda}^{k},\hat{\mu}^{k},\hat{\gamma}^{k})\\}$
satisfies conditions $(c)$-$(e)$ of Definition 4. Set

$\displaystyle\Gamma:=\min\\{\nabla g_{i}(x^{*})^{T}d,$
$\displaystyle~{}\nabla h_{j_{+}}(x^{*})^{T}d,~{}-\nabla
h_{j_{-}}(x^{*})^{T}d,~{}e_{\imath_{+}}^{T}d,~{}-e_{\imath_{-}}^{T}d,$
$\displaystyle i\in I,~{}j_{+}\in J_{+},~{}j_{-}\in J_{-},~{}\imath_{+}\in
K_{+},~{}\imath_{-}\in K_{-}\\}.$

If $\hat{\lambda}_{i}^{k}\neq 0$, then $i\in I$. By (24), we know $I\subseteq
I_{g}(x^{*})$. This implies

$\displaystyle g_{i}(\hat{x}^{k})$ $\displaystyle=g_{i}(x^{*})+\nabla
g_{i}(x^{*})^{T}(\hat{x}^{k}-x^{*})+r(\parallel\hat{x}^{k}-x^{*}\parallel)$
$\displaystyle=t_{k}\nabla g_{i}(x^{*})^{T}d+r(t_{k}),$

where $r(t_{k})$ represents the high-order infinitesimal of $t_{k}$. Divide
both sides of the above formula by $t_{k}$, when $k$ is sufficiently large, we
have

$\frac{g_{i}(\hat{x}^{k})}{t_{k}}=\nabla
g_{i}(x^{*})^{T}d+\frac{r(t_{k})}{t_{k}}\geq\frac{\Gamma}{2}>0,$

hence, $\hat{\lambda}_{i}^{k}g_{i}(\hat{x}^{k})>0$.

If $\hat{\mu}_{j}^{k}\neq 0$, then $j\in J$. We only discuss $j\in J_{-}$ here
(similarly available for $j\in J_{+}$). For any $j\in J_{-}$, when $k$ is
sufficiently large, we know

$\frac{h_{j}(\hat{x}^{k})}{t_{k}}=\nabla
h_{j}(x^{*})^{T}d+\frac{r(t_{k})}{t_{k}}\leq-\frac{\Gamma}{2}<0,$

then $\hat{\mu}_{j}^{k}h_{j}(\hat{x}^{k})>0$.

Analogously, if $\hat{\gamma}_{\imath}^{k}\neq 0$, by (23), we know $\imath\in
K$, then

$\displaystyle x_{\imath}^{k}$
$\displaystyle=x_{\imath}^{*}+t_{k}d_{\imath}=t_{k}e_{\imath}^{T}d_{\imath}<0,\quad$
$\displaystyle\imath\in K_{-},$ $\displaystyle x_{\imath}^{k}$
$\displaystyle=x_{\imath}^{*}+t_{k}d_{\imath}=t_{k}e_{\imath}^{T}d_{\imath}>0,\quad$
$\displaystyle\imath\in K_{+},$

hence, for any $\hat{\gamma}_{\imath}^{k}\neq 0$, obviously
$\hat{\gamma}_{\imath}^{k}x_{\imath}^{k}>0$.

In summary, we show that
$\\{(\hat{x}^{k},\hat{\lambda}^{k},\hat{\mu}^{k},\hat{\gamma}^{k})\\}$ is a
CC-PAM sequence. Therefore $x^{*}$ is CC-PAM-stationary point.
$ii)~{}\\{\rho_{k}\\}$ is unbounded.

Let $x^{k}\rightarrow x^{*}$, by (14), we know

$\left\|\nabla_{x}\mathscr{L}\left(x^{k},y^{k},\bar{\Lambda}^{k-1},\rho_{k-1}\right)\right\|=\left\|\nabla
f(x^{k})+\nabla g\left(x^{k}\right)\lambda^{k}+\nabla
h\left(x^{k}\right)\mu^{k}+\gamma^{k}\circ
y^{k}\right\|\leqslant\varepsilon_{k}.$

Set $\tilde{\gamma}^{k}=\gamma^{k}\circ y^{k}$, since $\epsilon_{k}\downarrow
0$, this implies

$\nabla f(x^{k})+\nabla g\left(x^{k}\right)\lambda^{k}+\nabla
h\left(x^{k}\right)\mu^{k}+\tilde{\gamma}^{k}\rightarrow 0.$

Let $i\notin I_{g}(x^{*})$, we have $g_{i}(x^{*})<0$, and $g_{i}(x^{k})<0$
when $k$ is sufficiently large. Since $\rho_{k}\rightarrow\infty$, then

$\lambda_{i}^{k}=(\rho_{k-1}g_{i}(x^{k})+\bar{\lambda}_{i}^{k-1})_{+}=0.$

Take an index $\imath\in I_{\pm}(x^{*})$, we have $x_{\imath}^{*}\neq 0$ and
$y_{\imath}^{*}=0$, then $y_{\imath}^{k}\rightarrow 0$. Thus

$\displaystyle\lim_{k\rightarrow\infty}\gamma_{\imath}^{k}y_{\imath}^{k}$
$\displaystyle=\lim_{k\rightarrow\infty}\rho_{k-1}x_{\imath}^{k}\left(y_{\imath}^{k}\right)^{2}+\lim_{k\rightarrow\infty}\bar{\gamma}_{\imath}^{k-1}y_{\imath}^{k}$
$\displaystyle=\lim_{k\rightarrow\infty}\frac{1}{x_{\imath}^{k}}\rho_{k-1}\left(x_{\imath}^{k}y_{\imath}^{k}\right)^{2}.$

Now, Let’s prove
$\rho_{k-1}\left(x_{\imath}^{k}y_{\imath}^{k}\right)^{2}\rightarrow 0$. For
simplicity, we abbreviate $p(x,y,\Lambda,\rho)$ in Lemma 3 as $p(x)$, and
define

$\bar{p}(x)=\frac{1}{2}\left[\left\|\left(g(x)\right)_{+}\right\|^{2}+\left\|h(x)\right\|^{2}+\left\|x\circ
y\right\|^{2}+\left\|\left(n-\kappa-e^{T}y\right)_{+}\right\|^{2}+\left\|\left(y-e\right)_{+}\right\|^{2}\right].$

Then

$\displaystyle\rho_{k-1}\nabla_{(x,y)}p(x^{k})$
$\displaystyle-\rho_{k-1}\nabla_{(x,y)}\bar{p}(x^{k})$
$\displaystyle\leq\left(\begin{array}[]{c}\nabla
g\left(x^{k}\right)\bar{\lambda}^{k-1}+\nabla
h\left(x^{k}\right)\bar{\mu}^{k-1}+\bar{\gamma}^{k-1}\circ y^{k}\\\
-\bar{\delta}^{k-1}e+\bar{\eta}^{k-1}+\bar{\gamma}^{k-1}\circ
x^{k}\end{array}\right),$

where, the inequality sign comes from the Lipschitz property of $(\cdot)_{+}$,
such as

$\lambda^{k}-(\rho_{k-1}g(x^{k}))_{+}=(\rho_{k-1}g(x^{k})+\bar{\lambda}^{k-1})_{+}-(\rho_{k-1}g(x^{k}))_{+}\leq\bar{\lambda}^{k-1},$

the others are similar. Since $\bar{\Lambda}^{k-1}$ is bounded, $g,~{}h\in
C^{1}$ and $(x^{k},y^{k})\rightarrow(x^{*},y^{*})$, then there exists
$M_{1}>0$ such that

$\rho_{k-1}\nabla_{(x,y)}p(x^{k})-\rho_{k-1}\nabla_{(x,y)}\bar{p}(x^{k})\leq
M_{1}.$

On the other hand, by (14), we know

$\displaystyle\left\|\rho_{k-1}\nabla_{(x,y)}p(x^{k})\right\|$
$\displaystyle\leq\left\|\nabla\mathscr{L}\left(x^{k},y^{k},\bar{\Lambda}^{k-1},\rho_{k-1}\right)\right\|+\left\|\nabla
f(x^{k})\right\|$ $\displaystyle\leq\epsilon_{k}+\left\|\nabla
f(x^{k})\right\|.$

Thus

$\displaystyle\left\|\rho_{k-1}\nabla_{(x,y)}\bar{p}(x^{k})\right\|$
$\displaystyle=\left\|\rho_{k-1}\nabla_{(x,y)}p(x^{k})-(\rho_{k-1}\nabla_{(x,y)}p(x^{k})-\rho_{k-1}\nabla_{(x,y)}\bar{p}(x^{k}))\right\|$
$\displaystyle\leq\epsilon_{k}+\left\|\nabla f(x^{k})\right\|+M_{1}.$

Furthermore, since $\epsilon_{k}\downarrow 0$, $f\in C^{1}$ and
$x^{k}\rightarrow x^{*}$, then there exists $M>0$ such that

$\left\|\rho_{k-1}\nabla_{(x,y)}\bar{p}(x^{k})\right\|\leq M.$ (26)

At the same time, by Assumption 5.1 and Lemma 1, we know $\bar{p}(x)$ is
semialgebraic. So there exists $C>0$, $\theta\in[0,1)$ such that

$\left\|\rho_{k-1}\nabla_{(x,y)}\bar{p}(x^{k})\right\|\geq
C\rho_{k-1}\left\|\bar{p}(x^{k})-\bar{p}(x^{*})\right\|^{\theta}=C\rho_{k-1}\left\|\bar{p}(x^{k})\right\|^{\theta}.$
(27)

By (26) and (27), we obtain

$\displaystyle 0\leq\rho_{k-1}\left\|x^{k}\circ
y^{k}\right\|^{2}\leq\left\|\rho_{k-1}\bar{p}(x^{k})\right\|$
$\displaystyle\leq
C^{-1}\left\|\rho_{k-1}\nabla_{(x,y)}\bar{p}(x^{k})\right\|\left\|\bar{p}(x^{k})\right\|^{1-\theta}$
$\displaystyle\leq C^{-1}M\left\|\bar{p}(x^{k})\right\|^{1-\theta}\rightarrow
0.$

Thus

$\lim\limits_{k\rightarrow\infty}\rho_{k-1}x_{\imath}^{k}(y_{\imath}^{k})^{2}=\lim\limits_{k\rightarrow\infty}\frac{1}{x_{\imath}^{k}}\rho_{k-1}(x_{\imath}^{k}y_{\imath}^{k})^{2}=0,$

that is $\lim\limits_{k\rightarrow\infty}\tilde{\gamma}_{\imath}^{k}=0$. Set

$\hat{\gamma}_{\imath}^{k}=\left\\{\begin{aligned} &0&\imath\in
I_{\pm}(x^{*})\\\ &\tilde{\gamma}_{\imath}^{k}&\imath\in
I_{0}(x^{*})\end{aligned}\right.,$ (28)

It’s easy to know that there are still

$\nabla f(x^{k})+\nabla g\left(x^{k}\right)\lambda^{k}+\nabla
h\left(x^{k}\right)\mu^{k}+\hat{\gamma}^{k}\rightarrow 0.$

Let
$\pi_{k}:=\left\|\left(1,\lambda^{k},\mu^{k},\hat{\gamma}^{k}\right)\right\|_{\infty}$.
If $\\{\pi_{k}\\}$ is bounded, the proof process of case $i)$ can verify that
the conditions $(c)$-$(e)$ are established. Now, we consider the case that
$\pi_{k}$ is unbounded. If
$\lim\limits_{k\rightarrow\infty}\frac{\lambda_{i}^{k}}{\pi_{k}}>0$, then

$\lim_{k\rightarrow\infty}\frac{\lambda_{i}^{k}}{\pi_{k}}=\lim_{k\rightarrow\infty}\frac{\rho_{k-1}g_{i}(x^{k})+\bar{\lambda}_{i}^{k-1}}{\pi_{k}}=\lim_{k\rightarrow\infty}\frac{\rho_{k-1}g_{i}(x^{k})}{\pi_{k}}>0.$

Obviously, we have $g_{i}(x^{k})>0$ for all $k$ sufficiently large, so

$\lambda_{i}^{k}g_{i}(x^{k})>0,\quad
if~{}\lim\limits_{k\rightarrow\infty}\frac{\lambda_{i}^{k}}{\pi_{k}}>0.$

If $\lim\limits_{k\rightarrow\infty}\frac{|\mu_{j}^{k}|}{\pi_{k}}>0$, then

$\lim_{k\rightarrow\infty}\frac{\mu_{j}^{k}}{\pi_{k}}=\lim_{k\rightarrow\infty}\frac{\rho_{k-1}h_{j}(x^{k})+\bar{\mu}_{j}^{k-1}}{\pi_{k}}=\lim_{k\rightarrow\infty}\frac{\rho_{k-1}h_{j}(x^{k})}{\pi_{k}}.$

Observe that $\mu_{j}^{k}$ has the same sign as $h_{j}(x^{k})$, this implies

$\mu_{j}^{k}h_{j}(x^{k})>0,\quad
if~{}\lim\limits_{k\rightarrow\infty}\frac{|\mu_{j}^{k}|}{\pi_{k}}>0.$

Similarly, if
$\lim\limits_{k\rightarrow\infty}\frac{|\hat{\gamma}_{\imath}^{k}|}{\pi_{k}}>0$,
by (28), we know $\imath\in I_{0}(x^{*})$, then $y_{\imath}^{k}\rightarrow
y_{\imath}^{*}\neq 0$. Meanwhile

$\lim_{k\rightarrow\infty}\frac{\hat{\gamma}_{\imath}^{k}}{\pi_{k}}=\lim_{k\rightarrow\infty}\frac{\gamma_{\imath}^{k}y_{\imath}^{k}}{\pi_{k}}=\lim_{k\rightarrow\infty}\frac{\rho_{k-1}x_{\imath}^{k}(y_{\imath}^{k})^{2}}{\pi_{k}}.$

Therefore, when $k$ is sufficiently large, $\hat{\gamma}_{\imath}^{k}$ has the
same sign as $x_{\imath}^{k}$, namely

$\hat{\gamma}_{\imath}^{k}x_{\imath}^{k}>0,\quad
if~{}\lim\limits_{k\rightarrow\infty}\frac{|\hat{\gamma}_{\imath}^{k}|}{\pi_{k}}>0.$

We have completed this proof.∎

As can be seen from the proof of Theorem 5.1, the ”semi-algebraic” hypothesis
is essentially to ensure that for any given $\Lambda$, $\rho$,
$p(x,y,\Lambda,\rho)$ has KL properties. Therefore, Assumption 5.1 can be
further relaxed to the structure of $\mathcal{O}$-$minimal$, or even to the
assumption that $p(x,y,\Lambda,\rho)$ has KL properties (that is, the same as
the conditions of Schwartz_2021_Sequ ), the conclusion of Theorem 5.1 still
holds. There are two reasons why we did not do this. One is that $y$ is an
artificial variable, so all assumptions should not be imposed on the $y$
space; in addition, through Lemma 3 and Lemma 4 can show that the introduction
of $y$ does not destroy the good properties of the hypothesis on the $x$
space.

Theorem 5.1 states that any feasible accumulation point of Algorithm 5.1 is a
CC-PAM-stationary point if Assumption 5.1 holds. And from the proof process,
it can be seen that the sequence generated by Algorithm 5.1 is not necessarily
a CC-PAM sequence. In fact, this is not contradictory, because we require the
existence of the corresponding CC-PAM sequence in Definition 4. But at least
this shows that it is not appropriate to take CC-PAM-stationarity as the stop
criterion. On the other hand, according to Theorem 4.1, if there is an
additional CC-PAM regularity condition holds at $x^{*}$, then it is a CC-M-
stationary point. In other words, when CC-PAM regularity condition is
established, CC-M-stationarity itself is a very suitable stop criterion,
Schwartz_2021_ALA  has verified the validity of this method, this paper mainly
emphasizes the theoretical improvement, not to repeat the experiment. In
addition, in conjunction with Proposition 2, it is clear that the following
conclusion holds.

###### Theorem 5.2

Let $(x^{*},y^{*})$ be an accumulation point of $\\{(x^{k},y^{k})\\}$
generated by Algorithm 5.1, Assumption 5.1 holds, that $(x^{*},y^{*})$ is
feasible for the relaxation problem (3), and meet CC-PAM regularity condition
at $x^{*}$. Then $(x^{*},y^{*})$ is a CC-M-stationary point and there exists
$z^{*}\in\mathbb{R}^{n}$ such that $(x^{*},z^{*})$ is a CC-S-stationary point.

##  6 Final Remarks

In this paper, we study the continuous relaxation form of CCOP, which is more
popular in recent years. We propose a new sequential optimality condition
called CC-PAM-stationarity. In Sect.3, we prove that CC-PAM-stationarity is
strictly superior to CC-AM-stationarity. Moreover, any local minimizer of CCOP
is a CC-PAM-stationary point without any additional assumptions. Obviously,
CC-PAM-stationarity is a better measure of optimality than CC-AM-stationarity.
In addition, we introduced a new constraint qualification called CC-PAM-
regularity in Sect.4, which is weaker than CC-AM-regularity. It is proved that
if the CC-PAM regularity condition is established, then any CC-PAM-stationary
point all are CC-M-stationary points.

In Sect. 5, we apply the new sequential optimality condition proposed in this
paper, CC-PAM-stationarity, to the safeguarded augmented Lagrangian method
(Algorithm 5.1), which further improves the existing theoretical results. We
have proved that under mild conditions such as KL properties, any feasible
convergence point of Algorithm 5.1 is a CC-PAM-stationary point; further, if
the CC-PAM-regularity condition, it can converge to a CC-M-stationary
(essentially CC-S-stationary) point. In other words, in this case, the CC-M-
stationarity is the natural termination criterion of Algorithm 5.1. Meanwhile,
we emphasize that if the same assumptions as the existing results are used,
the conclusions of this article are still valid.

###### Acknowledgements.

The research were partially supported by the Natural Science Foundation of
Shandong Province with No.ZR2019BA014, The Key Research and Development
Projects of Shandong Province with No.2019GGX104089 and the Foundation of
Liaoning Educational Committee (LQ2019019).

## References

  * (1) Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L.: Augmented lagrangian methods under the constant positive linear dependence constraint qualification.  Math. Program. 111(1), 5–32 (2007).  DOI https://doi.org/10.1007/S10107-006-0077-1
  * (2) Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L.: On augmented lagrangian methods with general lower-level constraints.  SIAM J. Optim. 18(4), 1286–1309 (2007).  DOI https://doi.org/10.1137/060654797
  * (3) Andreani, R., Fazzio, N.S., Schuverdt, M.L., Secchin, L.D.: A sequential optimality condition related to the quasi-normality constraint qualification and its algorithmic consequences.  SIAM J. Optim. 29(1), 743–766 (2019).  DOI https://doi.org/10.1137/17m1147330
  * (4) Andreani, R., Haeser, G., Martínez, J.M.: On sequential optimality conditions for smooth constrained optimization.  Optimization 60(5), 627–641 (2011).  DOI https://doi.org/10.1080/02331930903578700
  * (5) Andreani, R., Haeser, G., Schuverdt, M.L., Silva, P.J.S.: A relaxed constant positive linear dependence constraint qualification and applications.  Math. Program. 135(1-2), 255–273 (2012).  DOI https://doi.org/10.1007/s10107-011-0456-0
  * (6) Andreani, R., Martínez, J.M., Svaiter, B.F.: A new sequential optimality condition for constrained optimization and algorithmic consequences.  SIAM J. Optim. 20(6), 3533–3554 (2010).  DOI https://doi.org/10.1137/090777189
  * (7) Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features.  Math. Program. 116(1-2), 5–16 (2009).  DOI https://doi.org/10.1007/s10107-007-0133-5
  * (8) Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the kurdyka-Łojasiewicz inequality.  Math. Oper. Res. 35(2), 438–457 (2010).  DOI https://doi.org/10.1287/moor.1100.0449
  * (9) Bertsekas, D.P., Ozdaglar, A.E.: Pseudonormality and a lagrange multiplier theory for constrained optimization.  J. Optim. Theory Appl. 114(2), 287–343 (2002).  DOI https://doi.org/10.1023/A:1016083601322
  * (10) Bertsimas, D., Shioda, R.: Algorithm for cardinality-constrained quadratic optimization.  Comput. Optim. Appl. 43(1), 1–22 (2009).  DOI https://doi.org/10.1007/S10589-007-9126-9
  * (11) Bienstock, D.: Computational study of a family of mixed-integer quadratic programming problems.  Math. Program. 74(2), 121–140 (1996).  DOI https://doi.org/10.1007/BF02592208
  * (12) Birgin, E.G., Martínez, J.M.: Practical augmented Lagrangian methods for constrained optimization.  Society for Industrial and Applied Mathematics (SIAM) (2014)
  * (13) Branda, M., Bucher, M., Červinka, M., Schwartz, A.: Convergence of a scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization.  Comput. Optim. Appl. 70(2), 503–530 (2018).  DOI https://doi.org/10.1007/s10589-018-9985-2
  * (14) Burdakov, O.P., Kanzow, C., Schwartz, A.: Mathematical programs with cardinality constraints: Reformulation by complementarity-type conditions and a regularization method.  SIAM J. Optim. 26(1), 397–425 (2016).  DOI https://doi.org/10.1137/140978077
  * (15) Candes, E.J., Wakin, M.B.: An introduction to compressive sampling.  IEEE Signal Process Mag 25(2), 21–30 (2008).  DOI https://doi.org/10.1109/MSP.2007.914731
  * (16) Dong, H., Ahn, M., Pang, J.S.: Structural properties of affine sparsity constraints.  Math. Program. 176(1), 95–135 (2019).  DOI https://doi.org/10.1007/S10107-018-1283-3
  * (17) Haeser, G., Schuverdt, M.L.: On approximate kkt condition and its extension to continuous variational inequalities.  J. Optim. Theory Appl. 149(3), 528–539 (2011).  DOI https://doi.org/10.1007/S10957-011-9802-X
  * (18) Kanzow, C., Raharja, A.B., Schwartz, A.: An augmented lagrangian method for cardinality-constrained optimization problems.  J. Optim. Theory Appl. 189(3), 793–813 (2021).  DOI https://doi.org/10.1007/s10957-021-01854-7
  * (19) Kanzow, C., Raharja, A.B., Schwartz, A.: Sequential optimality conditions for cardinality-constrained optimization problems with applications.  Comput. Optim. Appl. 80(1), 185–211 (2021).  DOI https://doi.org/10.1007/s10589-021-00298-z
  * (20) Kanzow, C., Steck, D.: An example comparing the standard and safeguarded augmented lagrangian methods.  Oper. Res. Lett. 45(6), 598–603 (2017).  DOI https://doi.org/10.1016/j.orl.2017.09.005
  * (21) Krulikovski, E.H.M., Ribeiro, A.A., Sachine, M.: A sequential optimality condition for mathematical programs with cardinality constraints (2020).  DOI arXiv:2008.03158
  * (22) Miroforidis, J.: Bounds on efficient outcomes for large-scale cardinality-constrained markowitz problems.  J Glob Optim 80(3), 617–634 (2021).  DOI https://doi.org/10.1007/s10898-021-01022-1
  * (23) Rockafellar, R.T., Wets, R.J.B.: Variational analysis, vol. 317.  Springer-Verlag, Berlin (1998)
  * (24) Sun, C., Dai, R., Mesbahi, M.: Weighted network design with cardinality constraints via alternating direction method of multipliers.  IEEE Trans. Control. Netw. Syst. 5(4), 2073–2084 (2018).  DOI https://doi.org/10.1109/tcns.2018.2789726
  * (25) Červinka, M., Kanzow, C., Schwartz, A.: Constraint qualifications and optimality conditions for optimization problems with cardinality constraints.  Math. Program. 160(1-2), 353–377 (2016).  DOI https://doi.org/10.1007/s10107-016-0986-6