基数约束优化问题的松弛正线性约束规范

A Relaxed Constant Positive Linear Dependence Constraint Qualification for Cardinality-Constrained Optimization Problems

摘要: 基数约束优化问题在投资组合和统计回归等领域都有着广泛的应用。由于基数约束优化问题带有非凸非连续的约束，所以这类问题往往是难于求解的。为了处理较难的基数约束，可以通过引入连续变量将其改写为连续的非线性规划问题。但是大多数标准的约束规范并不适用于改写后的问题，因此有必要研究基数约束优化问题的约束规范。本文给出了基数约束优化问题的一个新的约束规范并证明了该约束规范可以保证最优性条件的成立。此外，还进一步讨论了新旧约束规范之间的强弱关系。

Abstract: Cardinality-Constrained (CC) optimization problems are widely used in many fields such as portfolio optimization and statistical regression. Such problems are difficult to deal with, because it involves a constraint that is not continuous neither convex. A classical way to deal with this difficult cardi-nality constraint consists of introducing continuous variables and then rewriting this kind of prob-lem as a continuous nonlinear problem. The standard constraint qualifications are usually violated for the NLP-reformulation. It is necessary to consider suitable constraint qualifications for cardinal-ity-constrained optimization problems. In this paper, we first define a new constraint qualification for cardinality constrained problems. We show that this constraint qualification ensures optimality conditions for constrained problems. Moreover, we discuss the relations between the old and new constraint qualifications.

1. 引言

本文主要研究基数约束优化问题(cardinality constrained optimization problems，简称CCOP)：

$\begin{array}{l}\underset{x}{\min }f\left(x\right)\\ \text{s}\text{.t}\text{.}{g}_i\left(x\right)\le 0\text{,}i=1,\cdots ,m,\\ h_i\left(x\right)=0\text{,}i=1,\cdots ,p,\\ {\Vert x\Vert }_0\le \kappa .\end{array}$ (1.1)

其中， $f,g_i,h_i:R^n\to R$ 是连续可微的， ${\Vert x\Vert }_0$ 表示向量x的非零分量的数量。

基数约束优化问题在许多方面有所应用，包括用于约束分类优化问题 [1] ，资产数量约束下的投资组合优化问题 [2] 等。由于基数约束 ${\Vert x\Vert }_0\le \kappa$ 的存在很难求解，所以1996年Bienstock [3] 提出通过引入合适的二进制变量来重新表述，使得基数约束优化问题通常可以被视为一个混合整数问题。2016年Oleg P. Burdakov等人 [4] 将混合整数问题改写为以下形式的连续优化问题：

$\begin{array}{l}\underset{x,y}{\min }f\left(x\right)\\ \text{s}\text{.t}\text{.}{g}_i\left(x\right)\le 0\text{,}i=1,\cdots ,m,\\ h_i\left(x\right)=0\text{,}i=1,\cdots ,p,\\ e^{{\rm T}}y\ge n-\kappa ,\\ \text{0}\le y_i\le 1,i=1,\cdots ,n,\\ x_i{y}_i=0,i=1,\cdots ,n.\end{array}$ (1.2)

文献 [4] 指出，问题(1.1)和问题(1.2)之间存在着非常紧密的联系： $x^{*}$ 是问题(1.1)的一个解(全局极小点)当且仅当存在一个向量 $y^{*}$ 使得 $\left(x^{*},y^{*}\right)$ 是问题(1.2)的解(全局极小点)。进一步，问题(1.1)的每个局部极小点可以推出问题(1.2)的局部极小点，在适当的条件下反过来也成立。

由于问题(1.2)不满足标准非线性规划(nonlinear program，简称NLP)问题和带有互补约束的数学规划(mathematical programs with complementarity constraints，简称MPCC)问题的约束规范，所以在2016年Michal Cervinka等人 [5] 提出了CC-LICQ、CC-MFCQ、CC-CPLD、CC-ACQ等约束规范并证明CC-CPLD强于CC-ACQ。2021年Christian Kanzow等人 [6] 提出了CC-AM-正则性概念。2022年薛梦龙等人 [7] 分别提出了CC-PAM-和CC-PCAM-正则性概念。与NLP问题和MPCC问题相比，基数约束优化问题的约束规范仍然较少，所以本文提出了新的约束规范CC-rCPLD并给出证明，讨论了CC-rCPLD与CC-ACQ之间的强弱关系，进一步完善了约束规范之间的关系并给出完整的关系图。

文章的结构如下：第2章我们首先介绍一些NLP问题上的约束规范及约束规范之间的关系，第3章提出新的基数约束优化问题的约束规范CC-rCPLD并给出证明，第4章讨论基数约束优化问题上新的约束规范与现有的约束规范之间的关系，最后一章我们进行总结。

2. 基础知识

本节介绍一些基础知识，这些知识在后文中起到重要作用。我们首先回顾NLP问题常用的约束规范和几个锥的定义，让我们从考虑NLP问题开始：

$\begin{array}{l}\underset{x}{\min }f\left(x\right)\\ \text{s}\text{.t}\text{.}{g}_i\left(x\right)\le 0\text{,}i=1,\cdots ,m,\\ h_i\left(x\right)=0\text{,}i=1,\cdots ,p.\end{array}$ (2.1)

设S为问题(2.1)的可行集，定义 $I_g\left(x\right)=\left\{i\in \left\{1,\cdots ,m\right\}|g_i\left(x\right)=0\right\}$ ，则在 $x^{*}\in S$ 处的切锥定义为：

$T_S\left(x^{*}\right)=\left\{d\in R^n|\exists \left\{x^k\right\}\subseteq S,\exists \left\{t_k\right\}\searrow 0:x^k\to x^{*},\underset{k\to \infty }{\lim }\frac{x^k-x^{*}}{t_k}=d\right\}.$

在 $x^{*}$ 处线性化锥为：

$L_S\left(x^{*}\right)=\left\{d\in R^n|\nabla h_j{\left(x^{*}\right)}^{{\rm T}}d=0\left(j=1,\cdots ,p\right),\nabla g_i{\left(x^{*}\right)}^{{\rm T}}d\le 0\left(i\in I_g\left(x^{*}\right)\right)\right\}.$

定义2.1 设 $x^{*}$ 是问题(2.1)的可行点。

(i) 称LICQ在 $x^{*}$ 成立 [5] ：如果梯度组

$\nabla g_i\left(x^{*}\right)\left(i\in I_g\left(x^{*}\right)\right),\nabla h_i\left(x^{*}\right)\left(i=1,\cdots ,p\right)$

是线性无关的。

(ii) 称CPLD在 $x^{*}$ 成立 [5] ：如果对于任意子集 $I_1\subseteq I_g\left(x^{*}\right)$ ， $I_2\subseteq \left\{1,\cdots ,p\right\}$ 使得向量

$\nabla g_i\left(x^{\text{*}}\right)\left(i\in I_1\right),\nabla h_i\left(x^{\text{*}}\right)\left(i\in I_2\right)$

是正线性相关的，则存在 $x^{*}$ 的邻域 $N\left(x^{\text{*}}\right)$ ，对于任意 $x\in N\left(x^{*}\right)$ ，满足

$\nabla g_i\left(x\right)\left(i\in I_1\right),\nabla h_i\left(x\right)\left(i\in I_2\right)$

是线性相关的。

(iii) 称RCPLD在 $x^{*}$ 成立 [8] ：设 $I_2\subseteq \left\{1,\cdots ,p\right\}$ 使得 $\nabla h_i\left(x^{*}\right)\left(i\in I_2\right)$ 是 $\text{span}{\left\{\nabla h_i\left(x^{*}\right)\right\}}_{i=1}^p$ 的一组基。存在 $x^{\text{*}}$ 的邻域 $N\left(x^{\text{*}}\right)$ 使得

(a) 对于任意的 $x\in N\left(x^{\text{*}}\right)$ ， $\nabla h_i\left(x\right)\left(i=1,\cdots ,p\right)$ 有相同的秩。

(b) 对于任意的 $I_1\subseteq I_g\left(x^{*}\right)$ ，如果

$\nabla g_i\left(x^{\text{*}}\right)\left(i\in I_1\right),\nabla h_i\left(x^{\text{*}}\right)\left(i\in I_2\right)$

是正线性相关的，则对于任意 $x\in N\left(x^{*}\right)$ ，满足

$\nabla g_i\left(x\right)\left(i\in I_1\right),\nabla h_i\left(x\right)\left(i\in I_2\right)$

是线性相关的。

(iv) 称ACQ在 $x^{*}$ 成立 [5] ： $T_S\left(x^{*}\right)=L_S\left(x^{\text{*}}\right)$ 。

以上约束规范之间的关系见图1：

Figure 1. Relations among several constraint qualifications for nonlinear program

图1. NLP问题的约束规范之间的关系

其中，RCPLD强于ACQ，可参见文章 [5] 。其他关系可以由各约束规范的定义直接得到。

下面我们先给出NLP问题的一个序列最优性条件。

定义2.2 [9] (AKKT)我们说 $x^{*}\in S$ 满足AKKT条件，如果存在序列 $x^k\to x^{*}$ ， $\left\{{\lambda }^k\right\}\subseteq R^m$ ， ${\lambda }^k\ge 0$ ， $\left\{{\mu }^k\right\}\subseteq R^p$ ，使得

$\begin{array}{l}\nabla f\left(x^k\right)+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i^k\nabla g_i\left(x^k\right)}+\underset{j=1}{\overset{p}{{\displaystyle \sum }}}{\mu }_j^k\nabla h_j\left(x^k\right)\to 0,\\ \min \left\{{\lambda }_i^k,-g_i\left(x^k\right)\right\}\to 0,i=1,\cdots ,m.\end{array}$

3. 基数约束优化的约束规范

为了研究基数约束优化问题的约束规范，从问题(1.2)出发，先引入下列指标集：

$\begin{array}{l}{I}_0\left(x\right)=\left\{i\in \left\{1,\cdots ,n\right\}|x_i=0\right\},I_{\pm }\left(x\right)=\left\{i\in \left\{1,\cdots ,n\right\}|x_i\ne 0\right\},I_g\left(x\right)=\left\{i\in \left\{1,\cdots ,m\right\}|g_i\left(x\right)=0\right\},\\ I_{\pm 0}\left(x,y\right)=\left\{i\in \left\{1,\cdots ,n\right\}|x_i\ne 0,y_i=0\right\},I_{0+}\left(x,y\right)=\left\{i\in \left\{1,\cdots ,n\right\}|x_i=0,y_i\in \left(0,1\right)\right\},\\ I_{01}\left(x,y\right)=\left\{i\in \left\{1,\cdots ,n\right\}|x_i=0,y_i=1\right\},I_{00}\left(x,y\right)=\left\{i\in \left\{1,\cdots ,n\right\}|x_i=0,y_i=0\right\}.\end{array}$

为了方便后续的定义和证明，引入下列紧的非线性规划TNLP( $x^{*}$ )：

$\begin{array}{l}\underset{x}{\min }f\left(x\right)\\ \text{s}.\text{t}.g\left(x\right)\le 0,\\ h\left(x\right)=0,\\ x_i=0\text{,}i\in I_0\left(x^{*}\right),\end{array}$

其中， $g,h$ 与NLP问题的 $g,h$ 有相同的定义。

定义3.1 设 $\left(x^{*},y^{*}\right)$ 是问题(1.2)的可行点，对于 $I_2\subseteq \left\{1,\cdots ,p\right\}$ ， ${\left\{\nabla h_j\left(x^{*}\right)\right\}}_{j\in I_2}$ 是 $\text{span}{\left\{\nabla h_j\left(x^{*}\right)\right\}}_{j=1}^p$ 的一组基，我们称CC-rCPLD在 $\left(x^{*},y^{*}\right)$ 处成立，如果存在 $x^{\text{*}}$ 的邻域 $N\left(x^{*}\right)$ 使得

(a) 对于任意的 $x\in N\left(x^{\text{*}}\right)$ ， ${\left\{\nabla h_j\left(x\right)\right\}}_{j=1}^p$ 有相同的秩。

(b) 对于任意的 $I_1\subseteq I_g\left(x^{*}\right)$ ， $I_3\subseteq I_0\left(x^{*}\right)$ ，如果

$\nabla g_i\left(x^{\text{*}}\right)\left(i\in I_1\right),\nabla h_j\left(x^{\text{*}}\right)\left(j\in I_2\right),e_{\tau }\left(\tau \in I_3\right)$

是正线性相关的，则对于任意的 $x\in N\left(x^{*}\right)$ ，

$\nabla g_i\left(x\right)\left(i\in I_1\right),\nabla h_j\left(x\right)\left(j\in I_2\right),e_{\tau }\left(\tau \in I_3\right)$

是线性相关的。

观察可得CC-rCPLD的定义不依赖于指标集的特殊选择。接下来给出的引理是处理正线性相关向量的重要工具。

引理3.2 [9] 如果 $x=\underset{i=1}{\overset{m+p}{{\displaystyle \sum }}}{\alpha }_i{v}_i$ 对于每个i， ${\left\{v_i\right\}}_{i=1}^m$ 线性无关且对于每个 $i=m+1,\cdots ,m+p$ ， ${\alpha }_i\ne 0$ ，则

存在 $J\subseteq \left\{m+1,\cdots ,m+p\right\}$ 和向量 ${\bar{\alpha }}_i$ 对于每个 $i\in \left\{1,\cdots ,m\right\}\cup J$ ，使得下列条件成立：

(a) $x=\underset{i\in \left\{1,\cdots ,m\right\}\cup J}{{\displaystyle \sum }}{\bar{\alpha }}_i{v}_i$ ；

(b) ${\alpha }_i{\bar{\alpha }}_i>0$ ， $\forall i\in J$ ；

(c) ${\left\{v_i\right\}}_{i\in \left\{1,\cdots ,m\right\}\cup J}$ 是线性无关的。

我们现在要证明CC-rCPLD是问题(1.2)的约束规范，在证明之前，我们给出TNLP ( $x^{*}$ )上的AKKT条件。

定义3.3 (AKKT)设 $x^{*}$ 是TNLP ( $x^{*}$ )上的可行点，我们说AKKT条件成立，如果存在序列 $x^k\to x^{*}$ ， $\left\{{\lambda }^k\right\}\subseteq R^m$ ， ${\lambda }^k\ge 0$ ， $\left\{{\mu }^k\right\}\subseteq R^p$ ， $\left\{{\gamma }^k\right\}\subseteq R^n$ 使得

$\begin{array}{l}\nabla f\left(x^k\right)+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i^k\nabla g_i\left(x^k\right)}+\underset{j=1}{\overset{p}{{\displaystyle \sum }}}{\mu }_j^k\nabla h_j\left(x^k\right)+{\displaystyle \underset{\tau =1}{\overset{n}{\sum }}{\gamma }_{\tau }^k{e}_{\tau }\to 0},\\ {\lambda }_i^k=0,i\notin I_g\left(x^{*}\right),\\ {\gamma }_{\tau }^k=0,\tau \in I_{\pm }\left(x^{*}\right).\end{array}$

下面我们想证明CC-rCPLD在 $\left(x^{*},y^{*}\right)$ 处是问题(1.2)的一个约束规范，我们首先证明，如果CC-rCPLD对于TNLP ( $x^{*}$ )，在可行点 $x^{*}$ 处成立，使得AKKT条件也成立，则 $x^{*}$ 是TNLP ( $x^{*}$ )的一个KKT点。

定理3.4 设 $x^{*}$ 是TNLP ( $x^{*}$ )上的可行点，使得AKKT条件成立，如果在 $x^{*}$ 点处满足CC-rCPLD，则 $x^{*}$ 是TNLP ( $x^{*}$ )的一个KKT点。

证明：由AKKT的定义，存在序列 ${\epsilon }_k\to 0$ ， $x^k\to x^{*}$ ， ${\lambda }_i^k\ge 0,\forall i\in I_g\left(x^{*}\right)$ ， ${\mu }_j^k\in R^p$ ， ${\gamma }_{\tau }^k\in R^n$ ，使

得对于任意k， $\nabla f\left(x^k\right)+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i^k\nabla g_i\left(x^k\right)}+\underset{j=1}{\overset{p}{{\displaystyle \sum }}}{\mu }_j^k\nabla h_j\left(x^k\right)+{\displaystyle \underset{\tau =1}{\overset{n}{\sum }}{\gamma }_{\tau }^k{e}_{\tau }}={\epsilon }_k$ 。考虑指标集 $I_2\subseteq \left\{1,\cdots ,p\right\}$ 使得 ${\left\{\nabla h_j\left(x^{*}\right)\right\}}_{j\in I_2}$ 是 $\text{span}{\left\{\nabla h_j\left(x^{*}\right)\right\}}_{j=1}^p$ 的一组基。则对于充分大的k， ${\left\{\nabla h_j\left(x^k\right)\right\}}_{j\in I_2}$ 是线性无关的。CC-rCPLD的等式约束梯度的秩是恒定的，因此存在一个序列 $\left\{{\bar{\mu }}^k\right\}\subseteq R^{\left|I_2\right|}$ ，使得 $\underset{j=1}{\overset{p}{{\displaystyle \sum }}}{\mu }_j^k\nabla h_j\left(x^k\right)=\underset{j\in I_2}{{\displaystyle \sum }}{\bar{\mu }}_j^k\nabla h_j\left(x^k\right)$ 。因

此，我们可以得到

$\nabla f\left(x^k\right)+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i^k\nabla g_i\left(x^k\right)}+\underset{j\in I_2}{{\displaystyle \sum }}{\bar{\mu }}_j^k\nabla h_j\left(x^k\right)+{\displaystyle \underset{\tau =1}{\overset{n}{\sum }}{\gamma }_{\tau }^k{e}_{\tau }}={\epsilon }_k.$

应用引理3.2可得子集 $I_{1,k}\subseteq I_g\left(x^{*}\right),I_{3,k}\subseteq I_0\left(x^{*}\right)$ 和乘子 ${\tilde{\lambda }}_i^k\ge 0$ ， ${\tilde{\mu }}_j^k\in R^{\left|I_2\right|}$ ， ${\tilde{\gamma }}_{\tau }^k\in R^{I_{3,k}}$ ，使得：

$\nabla f\left(x^k\right)+\underset{i\in I_{1,k}}{{\displaystyle \sum }}{\tilde{\lambda }}_i^k\nabla g_i\left(x^k\right)+\underset{j\in I_2}{{\displaystyle \sum }}{\tilde{\mu }}_j^k\nabla h_j\left(x^k\right)+\underset{\tau \in I_{3,k}}{{\displaystyle \sum }}{\tilde{\gamma }}_{\tau }^k{e}_{\tau }={\epsilon }_k.$ (3.1)

且 $\left\{\nabla g_i\left(x^k\right),\nabla h_j\left(x^k\right),e_{\tau }|i\in I_{1,k},j\in I_2,\tau \in I_{3,k}\right\}$ 线性无关。我们将考虑一个子序列使得 $I_{1,k},I_{3,k}$ 对于每

个k都与集合 $I_1,I_3$ 相同。假设 $\left\{\left({\tilde{\lambda }}^k,{\tilde{\mu }}^k,{\tilde{\gamma }}^k\right)\right\}$ 是无界的，可令 $\frac{\left({\tilde{\lambda }}^k,{\tilde{\mu }}^k,{\tilde{\gamma }}^k\right)}{{\Vert \left({\tilde{\lambda }}^k,{\tilde{\mu }}^k,{\tilde{\gamma }}^k\right)\Vert }_2}\to \left(\tilde{\lambda },\tilde{\mu },\tilde{\gamma }\right)\ne 0,\tilde{\lambda }\ge 0$ ，(3.1)

两边同时除以 ${\Vert \left({\tilde{\lambda }}^k,{\tilde{\mu }}^k,{\tilde{\gamma }}^k\right)\Vert }_2$ 并取极限，可得：

$\underset{i\in I_1}{{\displaystyle \sum }}{\tilde{\lambda }}_i\nabla g_i\left(x^{*}\right)+\underset{j\in I_2}{{\displaystyle \sum }}{\tilde{\mu }}_j\nabla h_j\left(x^{*}\right)+\underset{\tau \in I_3}{{\displaystyle \sum }}{\tilde{\gamma }}_{\tau }{e}_{\tau }=0.$

因此在 $x^{*}$ 点处 $\left\{\nabla g_i\left(x^{*}\right),\nabla h_j\left(x^{*}\right),e_{\tau }|i\in I_1,j\in I_2,\tau \in I_3\right\}$ 是线性相关的，由于在 $x^{*}$ 的邻域中， $\left\{\nabla g_i\left(x^k\right),\nabla h_j\left(x^k\right),e_{\tau }|i\in I_1,j\in I_2,\tau \in I_3\right\}$ 是线性无关的，所以这违背了CC-rCPLD定义，因此 ${\Vert \left({\tilde{\lambda }}^k,{\tilde{\mu }}^k,{\tilde{\gamma }}^k\right)\Vert }_2$ 是有界序列。对一个适当的子序列取极限，使得 ${\lambda }^k\to {\lambda }^{*},{\mu }^k\to {\mu }^{*},{\gamma }^k\to {\gamma }^{*}$ 我们有：

$\nabla f\left(x^{*}\right)+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i^{*}\nabla g_i\left(x^{*}\right)}+\underset{j=1}{\overset{p}{{\displaystyle \sum }}}{\mu }_j^{*}\nabla h_j\left(x^{*}\right)+{\displaystyle \underset{\tau =1}{\overset{n}{\sum }}{\gamma }_{\tau }^{*}{e}_{\tau }}=0.$

对于任意的k， ${\lambda }_i^k\ge 0$ ，对于任意的 $i\notin I_g\left(x^{*}\right)$ ， ${\lambda }_i^k=0$ ，故当k充分大时，可以得到 ${\lambda }_i^{*}=0,\forall i\notin I_g\left(x^{*}\right)$ ，根据AKKT的定义，明显可以得到 ${\gamma }_{\tau }^{*}=0,\forall \tau \in I_{\pm }\left(x^{*}\right)$ 这可证得 $x^{*}$ 是TNLP ( $x^{*}$ )的一个KKT点。

定理3.5 设 $x^{*}$ 是TNLP ( $x^{*}$ )上的局部极小点，则 $x^{*}$ 是TNLP ( $x^{*}$ )上的AKKT点。

证明：由于 $x^{*}$ 是TNLP ( $x^{*}$ )上的局部极小点，故存在 $\epsilon >0$ ，使得 $x^{*}$ 是下列问题唯一的全局极小点。

$\begin{array}{l}\text{min}f\left(x\right)+\frac{1}{2}{\Vert x-x^{*}\Vert }^2\\ \text{s}\text{.t}\text{.}g\left(x\right)\le 0,\\ h\left(x\right)=0,\\ x_i=0,i\in I_0\left(x^{*}\right),\\ \Vert x-x^{*}\Vert \le \epsilon ,\end{array}$ (3.2)

设 $p\left(x\right)={\Vert g{\left(x\right)}_{+}\Vert }^2+{\Vert h\left(x\right)\Vert }^2+{\displaystyle \underset{i\in I_0\left(x^{*}\right)}{\sum }{x}_i^2}$ 。我们定义罚问题，

$\begin{array}{l}\min f\left(x\right)+\frac{1}{2}{\Vert x-x^{*}\Vert }^2+\frac{{\delta }_k}{2}p\left(x\right)\\ \text{s}\text{.t}\text{.}\Vert x-x^{*}\Vert \le \epsilon ,\end{array}$ (3.3)

其中， $0<{\delta }_k\to +\infty$ ，由于问题(3.3)的目标函数是连续可微的且可行集是紧致的。因此必存在一个全局极小点，不妨设为 $x^k$ ，因为 $\left\{x^k\right\}$ 是有界的，所以一定存在一个收敛子列，不失一般性，假设 $x^k\to \bar{x}$ ，下面证明 $\bar{x}=x^{*}$ 。

因为是问题(3.3)的全局极小点，所以

$f\left(x^k\right)+\frac{1}{2}{\Vert x^k-x^{*}\Vert }^2+\frac{{\delta }_k}{2}p\left(x^k\right)\le f\left(x^{*}\right).$ (3.4)

不等式两边同时除以 ${\delta }_k$ 并取极限，可得 $p\left(\bar{x}\right)\le 0$ 。因此， $\bar{x}$ 是问题(3.2)的可行点。因为 $p\left(x^k\right)\ge 0$ ，所以根据问题(3.4)可得

$f\left(x^k\right)+\frac{1}{2}{\Vert x^k-x^{*}\Vert }^2\le f\left(x^{*}\right).$

不等式两边同时取极限可得 $f\left(\bar{x}\right)+\frac{1}{2}{\Vert \bar{x}-x^{*}\Vert }^2\le f\left(x^{*}\right)$ 。由于 $x^{*}$ 是问题(3.2)的唯一全局极小点，所以

一定存在 $\bar{x}=x^{*}$ ，即 $x^k\to x^{*}$ 。

根据问题(3.3)的必要最优性条件可得

$\nabla f\left(x^k\right)+\nabla g\left(x^k\right)\left({\delta }_{k}g{\left(x^k\right)}_{+}\right)+\nabla h\left(x^k\right)\left({\delta }_{k}h\left(x^k\right)\right)+{\displaystyle \underset{i\in I_0\left(x^{*}\right)}{\sum }{\delta }_k{x}_i^k{e}_i}=x^{*}-x^k.$

定义 ${\lambda }^k={\delta }_{k}g{\left(x^k\right)}_{+},{\mu }^k={\delta }_{k}h\left(x^k\right),{\gamma }_i^k={\delta }_k{x}_i^k,i\in I_0\left(x^{*}\right)$ 。有下列式子成立

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

对于所有的 $i\notin I_g\left(x^{*}\right)$ ，有 $g_i\left(x^{*}\right)<0$ ，则对于充分大的k， $g_i\left(x^k\right)<0$ ，因此 ${\lambda }_i^k=0$ 。同时，根据 ${\gamma }^k$ 的定义，显然 ${\gamma }_i^k=0,\forall i\in I_{\pm }\left(x^{*}\right)$ 。即 $x^{*}$ 是TNLP ( $x^{*}$ )上的AKKT点。

推论3.6 设 $x^{*}$ 是TNLP ( $x^{*}$ )的局部极小点且CC-rCPLD在点 $x^{*}$ 处成立，那么 $x^{*}$ 是TNLP ( $x^{*}$ )的KKT点。

根据推论3.6可知，TNLP ( $x^{*}$ )的CC-rCPLD在 $x^{*}$ 点处成立，因此问题(1.2)的相应的约束规范在 $\left(x^{*},y^{*}\right)$ 点处成立。值得注意的是，CC-rCPLD的定义只依赖于 $x^{*}$ ，所以可以直接看作基数约束优化问题(1.1)的约束规范 [5] 。

4. 基数约束优化约束规范之间的关系

为了研究基数约束优化问题的约束规范之间的关系，我们首先回顾现有的基数约束优化问题的约束规范。

定义4.1 [5] 设 $\left(x^{*},y^{*}\right)$ 是问题(1.2)的可行点，则 $\left(x^{*},y^{*}\right)$ 满足

(i) CC-LICQ：梯度组

$\nabla g_i\left(x^{\text{*}}\right)\left(i\in I_g\left(x^{\text{*}}\right)\right),\nabla h_i\left(x^{\text{*}}\right)\left(i=1,\cdots ,p\right),e_i\left(i\in I_0\left(x^{\text{*}}\right)\right)$

是线性无关的。

(ii) CC-CPLD：对任意子集 $I_1\subseteq I_g\left(x^{*}\right),I_2\subseteq \left\{1,\cdots ,p\right\},I_3\subseteq I_0\left(x^{\text{*}}\right)$ ，

$\nabla g_i\left(x^{\text{*}}\right)\left(i\in I_1\right),\nabla h_i\left(x^{\text{*}}\right)\left(i\in I_2\right),e_i\left(i\in I_3\right)$

是正线性相关的，存在 $x^{*}$ 的邻域 $N\left(x^{\text{*}}\right)$ ，对于 $x\in N\left(x^{\text{*}}\right)$ ，

$\nabla g_i\left(x\right)\left(i\in I_1\right),\nabla h_i\left(x\right)\left(i\in I_2\right),e_i\left(i\in I_3\right)$

是线性相关的。

为了表述CC-ACQ的定义 [5] ，我们需要引入几个概念。根据问题(1.2)的结构，我们首先引入CC-线性化锥：

$\begin{array}{l}{\mathcal{L}}_Z^{CC}\left(x^{*},y^{*}\right)=\{d=\left(d_x,d_y\right)|\nabla g_i{\left(x^{*}\right)}^{{\rm T}}{d}_x\le 0,i\in I_g\left(x^{*}\right),\\ \nabla h_i{\left(x^{*}\right)}^{{\rm T}}{d}_x=0,i=1,\cdots ,p,\\ e^{{\rm T}}{d}_y\ge 0若e^{{\rm T}}{y}^{*}=n-\kappa ,\\ e_i^{{\rm T}}{d}_y=0,i\in I_{\pm 0}\left(x^{*},y^{*}\right),\\ e_i^{{\rm T}}{d}_y\ge 0\text{,}i\in I_{00}\left(x^{*},y^{*}\right),\\ e_i^{{\rm T}}{d}_y\le 0\text{,}i\in I_{01}\left(x^{*},y^{*}\right),\\ e_i^{{\rm T}}{d}_x=0,i\in I_{01}\left(x^{*},y^{*}\right),\\ e_i^{{\rm T}}{d}_x=0\text{,}i\in I_{0+}\left(x^{*},y^{*}\right),\\ \left(e_i^{{\rm T}}{d}_x\right)\left(e_i^{{\rm T}}{d}_y\right)=0\text{,}i\in I_{00}\left(x^{*},y^{*}\right)\}.\end{array}$

设 $\left(x^{*},y^{*}\right)$ 是问题(1.2)的可行点，对于一个任意的子集 $I\subseteq I_{00}\left(x^{*},y^{*}\right)$ ，我们定义限制可行集

$\begin{array}{l}{Z}_I=\{\left(x,y\right)|g_i\left(x\right)\le 0,i=1,\cdots ,m{,}_{}^{{}^{}}\\ h_i\left(x\right)=0,i=1,\cdots ,p,\\ e^{{\rm T}}y\ge n-\kappa ,\\ x_i=0,y_i\in \left[0,1\right],i\in I_{0+}\left(x^{*},y^{*}\right)\cup I_{01}\left(x^{*},y^{*}\right)\cup I,\\ y_i=0,i\in I_{\pm 0}\left(x^{*},y^{*}\right)\cup \left(I_{00}\left(x^{*},y^{*}\right)\backslash I\right)\}.\end{array}$

命题4.2 设 $\left(x^{*},y^{*}\right)$ 是问题(1.2)的可行点。则CC-线性化锥满足：

${\mathcal{L}}_Z^{CC}\left(x^{*},y^{*}\right)={\displaystyle \underset{I\subseteq I_{00}\left(x^{*},y^{*}\right)}{\cup }{\mathcal{L}}_{Z_I}}\left(x^{*},y^{*}\right).$

定义4.3 设 $\left(x^{*},y^{*}\right)$ 是问题(1.2)的可行点。如果 ${\mathcal{T}}_Z\left(x^{*},y^{*}\right)={\mathcal{L}}_Z^{CC}\left(x^{*},y^{*}\right)$ ，则CC-ACQ在 $\left(x^{*},y^{*}\right)$ 处成立。

为了研究CC-rCPLD与CC-ACQ之间的强弱关系，我们先给出下列引理的证明。

引理4.4 设 $\left(x^{*},y^{*}\right)$ 是问题(1.2)的可行点，并且假设CC-rCPLD在 $\left(x^{*},y^{*}\right)$ 处成立。则对于任意的 $I\subseteq I_{00}\left(x^{*},y^{*}\right)$ ，标准的RCPLD在任何一个限制集 $Z_I$ 上都满足。

证明：在这里我们只需要考虑RCPLD定义的第(ii)条，考虑一个固定点集 $I\subseteq I_{00}\left(x^{*},y^{*}\right)$ 。相应的可行集 $Z_I$ 的约束取决于x或者y。因为所有取决于y的约束都是线性的，在文章 [5] 中得知，它们满足CPLD，因此也满足RCPLD。因此，充分说明标准的RCPLD约束规范成立只取决于x。我们可以仅限于通过对x变量求偏导而产生梯度向量，此时针对y求梯度为0。这意味着不得不说明对于所有的子集 $I_1\subseteq I_g\left(x^{*}\right)$ ， $I_2\subseteq \left\{1,\cdots ,p\right\}$ ， $I_3\subseteq I_{0+}\left(x^{*},y^{*}\right)\cup I_{01}\left(x^{*},y^{*}\right)\cup I$ ，如果梯度组 $\nabla g_i\left(x^{\text{*}}\right)\left(i\in I_1\right),\nabla h_j\left(x^{\text{*}}\right)\left(j\in I_2\right),e_{\tau }\left(\tau \in I_3\right)$ 是正线性相关的，则存在 $x^{*}$ 的邻域 $N\left(x^{\text{*}}\right)$ ，对于任意的 $x\in N\left(x^{\text{*}}\right)$ ， $\nabla g_i\left(x\right)\left(i\in I_1\right),\nabla h_j\left(x\right)\left(j\in I_2\right),e_{\tau }\left(\tau \in I_3\right)$ ，是线性相关的。特别地， $I_3$ 在这里可被当作 $I_0$ 的子集，所以结论可由CC-rCPLD概念立即得出。

定理4.5 设 $\left(x^{*},y^{*}\right)$ 是问题(1.2)的可行点，并且假设CC-rCPLD成立。则CC-ACQ在 $\left(x^{*},y^{*}\right)$ 处成立。

证明：因为CC-rCPLD在 $\left(x^{*},y^{*}\right)$ 处成立，由引理4.4，对于任意的 $I\subseteq I_{00}\left(x^{*},y^{*}\right)$ ，标准的RCPLD在任何一个限制集 $Z_I$ 上都满足。对于每个限制集 $Z_I$ ，标准的RCPLD意味着标准的ACQ。再由文章( [5] ，引理3.9)，可以得到CC-ACQ在 $\left(x^{*},y^{*}\right)$ 处成立。

由定义可直接得到CC-CPLD强于CC-rCPLD，结合定理4.5，可以得到基数约束优化问题的约束规范之间的关系，见图2：

Figure 2. Relations among several constraint qualifications for Cardinality-constrained optimization problems

图2. 基数约束优化问题的约束规范之间的关系

5. 总结

本文主要研究基数约束优化问题，提出了一个新的约束规范，即CC-rCPLD，基于转化后的连续优化问题，证明了CC-rCPLD是基数约束优化问题的约束规范。同时进一步完善了基数约束优化问题的约束规范之间的关系，并给出关系图。根据改写后的基数约束优化问题的特殊结构，对比NLP问题和MPCC问题，有可能得到更弱的约束规范，这是未来值得研究的一个有趣的话题。