基数约束优化问题的内罚函数法

An Interior Penalty Algorithm for Cardinality-Constrained Optimization Problems

摘要: 基数约束优化问题是一类重要的优化问题，这类问题在很多领域都有着广泛的应用。由于其具有较难处理的基数约束，所以对基数约束优化问题的算法研究较少。本文将介绍基数约束优化问题的内罚函数法，并证明了该算法产生点列收敛到AM-稳定点。进一步证明在AM-正则性条件下，可以得到基数约束优化问题的M-稳定点。

Abstract: The cardinality-constrained optimization problems are an important class of optimization problems which have been applied in many fields. Due to the special structure of the cardinality constraints, there are few researches on the algorithm of cardinality-constraint optimization problems. We in-troduce an interior penalty algorithm for cardinality-constrained optimization problems and prove that the algorithm reaches an approximate Mordukhovich stationary. Furthermore, under the AM-regularity condition, we can obtain the Mordukhovich stationary of cardinality-constrained op-timization problems.

1. 引言

本文主要研究基数约束(cardinality-constrained，简称CC)优化问题，具体形式如下

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{.}g\left(x\right)\le 0,\\ h\left(x\right)=0,\\ {\Vert x\Vert }_0\le \kappa ,\end{array}$ (1.1)

其中， $\kappa$ 是整数且 $\kappa <n$ ， $f:R^n\to R,g:R^n\to R^m,h:R^n\to R^p$ 是连续可微的。 ${\Vert x\Vert }_0$ 表示x的基数，但 ${\Vert \cdot \Vert }_0$ 不是范数，它既不是连续的也不是凸的。

为了处理难于求解的基数约束优化问题，可以将它改写为连续优化问题 [1]

$\begin{array}{l}\min f\left(x\right)\\ \text{s}.\text{t}.g\left(x\right)\le 0,h\left(x\right)=0,\\ x\circ y=0,n-\kappa -e^{\text{T}}y\le 0,0\le y\le e,\end{array}$ (1.2)

其中， $\circ$ 表示哈达玛积， $e={\left(1,\cdots ,1\right)}^{\text{T}}\in R^n$ ，这个问题被称为(1.1)的松弛问题。问题(1.1)和(1.2)在全局最优解的意义下是等价的，即问题(1.1)的全局最优解对应于问题(1.2)的全局最优解，并且如果 $x^{\ast }$ 是问题(1.1)的局部最优解，则每个可行点 $\left(x^{\ast },y^{\ast }\right)$ 是问题(1.2)的局部最优解 [1] 。

近年来，基数约束优化问题因其在投资组合 [2] 、统计回归 [3] 等领域的广泛应用而备受关注，并有大量学者尝试从不同角度解决这些问题 [4] [5] 。由于基数约束的特殊结构，往往不能直接应用标准非线性规划的理论和算法直接处理基数约束优化问题。2016年Burdakov O. P.等人 [1] 提出了正则方法并证明其能收敛到M-稳定点。2021年Kanzow C.等人 [6] 介绍了另一种正则方法以及拉格朗日方法，这两种算法都能收敛到AM-稳定点。2022年Xue Menglong等人 [7] 提出了带有安全域的增广拉格朗日方法并证明其能收敛到PCAM-稳定点。本文主要研究基数约束优化问题的求解方法，将求解MPCC问题的内罚函数法推广至基数约束优化问题，并对算法进行收敛性分析，证明了在较弱的条件下可得到CC-AM-稳定点，若还满足较弱的约束规范，则我们可得到CC-M-稳定点。

本文基本结构如下：第二章介绍一些用到的基本知识，第三章介绍基数约束优化问题的内罚函数法，第四章证明内罚函数法的收敛性结果，第五章给出最后的总结。

2. 基础知识

为了更好地呈现松弛的基数约束问题(1.2)，引入函数 $\theta :R^n\to R$ 和 $G,H,\tilde{H}:R^n\to R^n$ ，分别为

$\theta \left(y\right)=n-\kappa -e^{\text{T}}y,G\left(x\right)=x,H\left(y\right)=-y,\tilde{H}\left(y\right)=y-e,$

则松弛的基数约束优化问题(1.2)可以改写为

$\begin{array}{l}\min f\left(x\right)\\ \text{s}.\text{t}.g\left(x\right)\le 0,h\left(x\right)=0,\\ \theta \left(y\right)\le 0,\\ H\left(y\right)\le 0,\tilde{H}\left(y\right)\le 0,\\ G\left(x\right)\circ H\left(y\right)=0.\end{array}$ (2.1)

由 [8] 可知，松弛问题(2.1)每个可行点都是AKKT点，根据这个结果可为这类问题定义近似条件。为此，考虑松弛问题(2.1)的拉格朗日函数

$\begin{array}{l}L\left(x,y,{\lambda }^g,{\lambda }^h,{\lambda }^{\theta },{\lambda }^G,{\lambda }^H,{\lambda }^{\tilde{H}}\right)\\ =f\left(x\right)+{\left({\lambda }^g\right)}^{\text{T}}g\left(x\right)+{\left({\lambda }^h\right)}^{\text{T}}h\left(x\right)+{\left({\lambda }^G\right)}^{\text{T}}G\left(x\right)+{\lambda }^{\theta }\theta \left(y\right)+{\left({\lambda }^H\right)}^{\text{T}}H\left(y\right)+{\left({\lambda }^{\tilde{H}}\right)}^{\text{T}}\tilde{H}(\; y\; )\end{array}$

以及

${\nabla }_{x,y}L\left(x,y,{\lambda }^g,{\lambda }^h,{\lambda }^{\theta },{\lambda }^G,{\lambda }^H,{\lambda }^{\tilde{H}}\right)=\left(\begin{array}{l}\nabla f\left(x\right)+\nabla g\left(x\right){\lambda }^g+\nabla h\left(x\right){\lambda }^h+\nabla G\left(x\right){\lambda }^G\\ \nabla \theta \left(y\right){\lambda }^{\theta }+\nabla H\left(y\right){\lambda }^H+\nabla \tilde{H}\left(y\right){\lambda }^{\tilde{H}}\end{array}\right).$

对于松弛问题(2.1)可行域内任意点 $\left(x^{\ast },y^{\ast }\right)$ ，我们定义如下指标集

$\begin{array}{l}I=\left\{i\in \left\{1,\cdots ,n\right\}:H_i\left(y^{\ast }\right)=0,G_i\left(x^{\ast }\right)\ne 0\right\},\\ J=\left\{i\in \left\{1,\cdots ,n\right\}:H_i\left(y^{\ast }\right)=0,G_i\left(x^{\ast }\right)=0\right\},\\ M=\left\{i\in \left\{1,\cdots ,n\right\}:H_i\left(y^{\ast }\right)<0,G_i\left(x^{\ast }\right)=0\right\}.\end{array}$

定义2.1 [8] (AW-稳定点)令 $\left(x^{\ast },y^{\ast }\right)$ 是松弛问题(2.1)的可行点，则 $\left(x^{\ast },y^{\ast }\right)$ 是该问题的近似弱稳定点(AW-稳定点)，如果存在 $\left(x^k,y^k\right)\subseteq R^n\times R^n$ 和 $\left({\lambda }^k\right)=\left({\lambda }^{g,k},{\lambda }^{h,k},{\lambda }^{\theta ,k},{\lambda }^{G,k},{\lambda }^{H,k},{\lambda }^{\tilde{H},k}\right)\subseteq R_{+}^m\times R^p\times R_{+}\times R^n\times R^n\times R_{+}^n$ ，

使得 $\left(x^k,y^k\right)\to \left(x^{\ast },y^{\ast }\right)$ ，

1) ${\nabla }_{x,y}L\left(x^k,y^k,{\lambda }^k\right)\to 0$ ，

2) $\min \left\{-g\left(x^k\right),{\lambda }^{g,k}\right\}\to 0$ ，

3) $\min \left\{-\theta \left(y^k\right),{\lambda }^{\theta ,k}\right\}\to 0$ ，

4) $\min \left\{\left|G_i\left(x^k\right)\right|,\left|{\lambda }_i^{G,k}\right|\right\}\to 0$ $\forall i=1,\cdots ,n$ ，

5) $\min \left\{-H_i\left(y^k\right),\left|{\lambda }_i^{H,k}\right|\right\}\to 0$ $\forall i=1,\cdots ,n$ ，

6) $\min \left\{-\tilde{H}\left(y^k\right),{\lambda }^{\tilde{H},k}\right\}\to 0$ 。

为了更好的定义稳定点结果，我们首先给出一些常用指标集：

$I_g\left(x^{\ast }\right)=\left\{i:g_i\left(x^{\ast }\right)=0\right\},I_0\left(x^{\ast }\right)=\left\{i:x_i^{\ast }=0\right\},I_{\pm }\left(x^{\ast }\right)=\left\{i:x_i^{\ast }\ne 0\right\}.$

定义2.2 [6] (CC-M-稳定点)令 $x^{\ast }$ 是问题(1.1)的可行点，称 $x^{\ast }$ 是基数约束优化问题的M-稳定点(CC-M-稳定点)，如果存在乘子 ${\lambda }^g\in R^m,{\lambda }^h\in R^p$ 和 ${\lambda }^G\in R^n$ 使得下列条件成立

1) $0=\nabla f\left(x^{\ast }\right)+\nabla g\left(x^{\ast }\right){\lambda }^g+\nabla h\left(x^{\ast }\right){\lambda }^h+{\lambda }^G$ ，

2) ${\lambda }_i^g=0$ $\forall i\notin I_g\left(x^{\ast }\right)$ 且 ${\lambda }_i^G=0$ $\forall i\in I_{\pm }\left(x^{\ast }\right)$ 。

定义2.3 [6] (CC-AM-稳定点)令 $x^{\ast }$ 是问题(1.1)的可行点，称 $x^{\ast }$ 是基数约束优化问题的近似M-稳定点(CC-AM-稳定点)，如果存在序列 $\left\{x^k\right\}\subseteq R^n,\left\{{\lambda }^{g,k}\right\}\subseteq R_{+}^m,\left\{{\lambda }^{h,k}\right\}\subseteq R^p,\left\{{\lambda }^{G,k}\right\}\subseteq R^n$ 使得 $\left\{x^k\right\}\to x^{\ast }$ ，

1) $\left\{\nabla f\left(x^k\right)+\nabla g\left(x^k\right){\lambda }^{g,k}+\nabla h\left(x^k\right){\lambda }^{h,k}+{\lambda }^{G,k}\right\}\to 0$ ，

2) ${\lambda }_i^{g,k}=0$ $\forall i\notin I_g\left(x^{\ast }\right)$ 且 ${\lambda }_i^{G,k}=0$ $\forall i\in I_{\pm }\left(x^{\ast }\right)$ 。

定义2.4 [9] (外半连续)称集值映射 $S:R^n\to R^m$ 在 $x^{\ast }$ 处是外半连续的，如果

$\underset{x\to x^{\ast }}{\lim \sup }S\left(x\right)\subseteq S\left(x^{\ast }\right)$ .

为了给出约束规范的定义，我们先给出和定义中用到的锥的具体形式。令 $x^{\ast }\in R^n$ 是问题(1.1)的可行点，则对于任意 $x\in R^n$ 有

$K_{x^{\ast }}\left(x\right)=\left\{\nabla g\left(x\right){\lambda }^g+\nabla h\left(x\right){\lambda }^h+{\lambda }^G|\begin{array}{l}\left({\lambda }^g,{\lambda }^h,{\lambda }^G\right)\in R_{+}^m\times R^p\times R^n,\\ {\lambda }_i^g=0\forall i\notin I_g\left(x^{\ast }\right),\\ {\lambda }_i^G=0\forall i\in I_{\pm }\left(x^{\ast }\right)\end{array}\right\}.$

值得注意的是，指标集 $I_g\left(x^{\ast }\right)$ 和 $I_{\pm }\left(x^{\ast }\right)$ 依赖的是 $x^{\ast }$ 而不是x。

定义2.4 [6] (CC-AM-正则性) 问题(1.1)的可行点 $x^{\ast }$ 满足CC-AM-正则性条件，如果下述条件成立

$\underset{x\to x^{\ast }}{\lim \sup }{K}_{x^{\ast }}\left(x\right)\subseteq K_{x^{\ast }}\left(x^{\ast }\right).$

3. 基数约束优化问题的内罚函数法

为了避免 $G\left(x\right)\circ H\left(y\right)=0$ 带来的困难，我们用 ${\mathcal{l}}_{\text{1}}$ -罚问题 [10] 来代替松弛问题(2.1)

$\begin{array}{l}\min f\left(x\right)+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\gamma }_i}{G}_i\left(x\right)H_i\left(y\right)\\ \text{s}\text{.t}\text{.}g\left(x\right)\le 0,h\left(x\right)=0,\\ \theta \left(y\right)\le 0,H\left(y\right)\le 0,\tilde{H}\left(y\right)\le 0,\end{array}$ (3.1)

其中， $\gamma =\left({\gamma }_1,\cdots ,{\gamma }_n\right)\in {ℝ}_{+}^n$ 是惩罚参数。因为问题(3.1)是光滑的，我们可以应用标准的非线性规划的算法来解决它，比如内部方法。通过引入松弛变量 $s,t,v$ ，问题(3.1)可以改写为如下问题

$\begin{array}{l}\min f\left(x\right)+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\gamma }_i}{G}_i\left(x\right)H_i\left(y\right)\\ \text{s}\text{.t}\text{.}{g}_i\left(x\right)+s_i=0,s_i>0,i=1,\cdots ,m,\\ h_i\left(x\right)=0,i=1,\cdots ,p,\\ \theta \left(y\right)+t=0,t>0,\\ H_i\left(y\right)\le 0,i=1,\cdots ,n,\\ {\tilde{H}}_i\left(y\right)+v_i=0,v_i>0,i=1,\cdots ,n.\end{array}$

上述问题的罚问题是

$\begin{array}{l}\min f\left(x\right)+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\gamma }_i}{G}_i\left(x\right)H_i\left(y\right)-\mu {\displaystyle \underset{i=1}{\overset{m}{\sum }}\ln s_i}-\mu \ln t-\mu {\displaystyle \underset{i=1}{\overset{n}{\sum }}\ln v_i-\mu {\displaystyle \underset{i=1}{\overset{n}{\sum }}\ln \left(-H_i\left(y\right)\right)}}\\ \text{s}\text{.t}\text{.}{g}_i\left(x\right)+s_i=0,i=1,\cdots ,m,\\ h_i\left(x\right)=0,i=1,\cdots ,p,\\ \theta \left(y\right)+t=0,\\ {\tilde{H}}_i\left(y\right)+v_i=0,i=1,\cdots ,n,\end{array}$ (3.2)

其中， $\mu >0$ 是障碍参数。问题(3.2)的拉格朗日函数为

$\begin{array}{l}L\left(x,y,s,t,v,\gamma ,\mu ,{\lambda }^h,{\lambda }^g,{\lambda }^{\theta },{\lambda }^{\tilde{H}}\right)\\ =f\left(x\right)+\gamma G\left(x\right)\circ H\left(y\right)-\mu {\displaystyle \underset{i=1}{\overset{m}{\sum }}\ln s_i}-\mu \ln t-\mu {\displaystyle \underset{i=1}{\overset{n}{\sum }}\ln v_i}-\mu {\displaystyle \underset{i=1}{\overset{n}{\sum }}\ln \left(-H_i\left(y\right)\right)}\\ +{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i^g}\left(g_i\left(x\right)+s_i\right)+{\displaystyle \underset{i=1}{\overset{p}{\sum }}{\lambda }_i^h}{h}_i\left(x\right)+{\lambda }^{\theta }\left(\theta \left(y\right)+t\right)+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i^{\tilde{H}}}\left({\tilde{H}}_i\left(y\right)+v_i\right),\end{array}$ (3.3)

问题(3.2)的一阶KKT条件可以写为

$\begin{array}{l}\nabla f\left(x\right)+\nabla g\left(x\right){\lambda }^g+\nabla h\left(x\right){\lambda }^h+\nabla G\left(x\right)\left(\gamma H\left(y\right)\right)=0,\\ \nabla \theta \left(y\right){\lambda }^{\theta }+\nabla \tilde{H}\left(y\right){\lambda }^{\tilde{H}}+\nabla H\left(y\right)\left(\gamma G\left(x\right)-\frac{\mu }{H\left(y\right)}\right)=0,\\ s_i{\lambda }_i^g-\mu =0,i=1,\cdots ,m,\\ t{\lambda }^{\theta }-\mu =0,\end{array}$

$\begin{array}{l}{v}_i{\lambda }_i^{\tilde{H}}-\mu =0,i=1,\cdots ,n,\\ g_i\left(x\right)+s_i=0,i=1,\cdots ,m,\\ h_i\left(x\right)=0,i=1,\cdots ,p,\\ \theta \left(y\right)+t=0,\\ {\tilde{H}}_i\left(y\right)+v_i=0,i=1,\cdots ,n.\end{array}$ (3.4)

定义 ${\lambda }^G=\gamma H\left(y\right),{\lambda }^H=\gamma G\left(x\right)-\frac{\mu }{H\left(y\right)},\lambda =\left({\lambda }^g,{\lambda }^h,{\lambda }^{\theta },{\lambda }^G,{\lambda }^H,{\lambda }^{\tilde{H}}\right)$ ，e是一个适当维数的向量，S表示对角线上是s的对角矩阵，对 $T,V$ 有相同的定义方式。

KKT条件(3.4)可以简洁地表示为

${\nabla }_{x,y}L\left(x,y,s,t,v,\gamma ,\mu ,\lambda \right)=0,$ (3.5a)

$S{\lambda }^g-\mu e=0,T{\lambda }^{\theta }-\mu e=0,V{\lambda }^{\tilde{H}}-\mu e=0,$ (3.5b)

$c\left(x,y,s,t,v\right)=0,$ (3.5c)

其中，

$c\left(x,y,s,t,v\right)=\left(\begin{array}{l}g\left(x\right)+s\\ h\left(x\right)\\ \theta \left(y\right)+t\\ \tilde{H}\left(y\right)+v\end{array}\right).$ (3.6)

在下面将介绍基数约束优化问题基于 ${\mathcal{l}}_1$ -惩罚公式的内部方法。在算法以及后文中， ${\Vert \cdot \Vert }_{\infty }$ 表示无穷范数。

算法1. 基数约束优化问题的内罚函数法

除了要求近似满足边界问题的最优性条件(3.7)外，我们还通过(3.8)对 $G\left(x\right)\circ H\left(y\right)=0$ 进行了刻画。目前，对序列 $\left\{{\mu }^k\right\}$ 和 $\left\{{\epsilon }_{pen}^k\right\},\left\{{\epsilon }_{comp}^k\right\}$ 的要求是当 $k\to \infty$ 时它们都收敛到0。

在(3.8)中使用 ${\Vert \min \left\{-H\left(y^k\right),\left|G\left(x^k\right)\right|\right\}\Vert }_{\infty }$ 作为互补性的度量 [10] ，而不是 $G\left(x^k\right)\circ H\left(y^k\right)$ ，是因为它对问题的规模不敏感且与变量的数量无关。而且，即使当 $G_i\left(x^k\right)$ 和 $H_i\left(y^k\right)$ 都收敛到0时，该度量也是准确的。

算法I的公式足够通用，以允许在步骤2中对惩罚参数进行各种更新策略。一种方法是选择 ${\mu }^k$ 并用 ${\gamma }^k={\gamma }^{k-1}$ 求解(3.2)，直到满足条件(3.7)。如果条件(3.8)也成立，那么我们进入步骤3，否则，增加 ${\gamma }^k$ 并使用相同的障碍参数 ${\mu }^k$ 再次求解(3.2)。如果有必要，重复该过程，直到(3.8)被满足。

4. 内罚函数法的收敛性分析

本章将介绍内罚函数法的全局收敛性分析。已经提出了许多算法来解决步骤2中的问题，例如文献 [11] 和其中的参考文献。众所周知，这些内部方法可能无法满足(3.7)，因此算法I可能无法完成步骤2。对内部方法的分析超过了本文的范围，我们假设内部方法总是成功的，并且算法I生成一个满足条件(3.7)和(3.8)的无限迭代序列 $\left\{x^k,y^k,s^k,t^k,v^k,{\gamma }^k,{\mu }^k,{\lambda }^k\right\}$ 。下面定理将证明算法I的收敛性结果。

定理4.1假设序列 $\left\{{\epsilon }_{pen}^k\right\},\left\{{\epsilon }_{comp}^k\right\},\left\{{\mu }^k\right\}$ 都收敛到0，算法I生成一个迭代序列 $\left\{x^k,y^k,s^k,t^k,v^k,{\gamma }^k,{\mu }^k,{\lambda }^k\right\}$ ，满足条件(3.7)和(3.8)。如果 $\left(x^{\ast },y^{\ast }\right)$ 是序列 $\left\{\left(x^k,y^k\right)\right\}$ 的极限点，则 $\left(x^{\ast },y^{\ast }\right)$ 是松弛问题(2.1)的可行点。如果还满足 ${\epsilon }_{comp}^k=o\left(\max {\left\{{\gamma }_i^k\right\}}^{-1}\right)$ ，则 $x^{\ast }$ 是问题(1.1)的CC-AM-稳定点。

证明：设 $\left(x^{\ast },y^{\ast }\right)$ 是算法I生成的序列 $\left\{\left(x^k,y^k\right)\right\}$ 的一个极限点，令K是一个无限指标集使得 ${\left\{\left(x^k,y^k\right)\right\}}_{k\in K}\to \left(x^{\ast },y^{\ast }\right)$ ，则对充分大的k有 $\left(x^k,y^k\right)\in U\left(x^{\ast },y^{\ast }\right)$ 。由于算法第2步保证了松弛变量 $s^k,t^k,v^k$ 是正的，再根据 $g\left(x^k\right),h\left(x^k\right),\theta \left(y^k\right),\tilde{H}\left(y^k\right)$ 的连续性，条件(3.7c)和 ${\epsilon }_{pen}^k\to 0$ 可得

$\begin{array}{l}{g}_i\left(x^{\ast }\right)=-s_i^{\ast }\le 0,i=1,\cdots ,m,\\ h_i\left(x^{\ast }\right)=0,i=1,\cdots ,p,\\ \theta \left(y^{\ast }\right)=-t^{\ast }\le 0,\\ {\tilde{H}}_i\left(y^{\ast }\right)=-v_i^{\ast }\le 0,i=1,\cdots ,n,\end{array}$

其中， $s_i^{\ast }=\underset{k\in K}{\lim }{s}_i^k,t^{\ast }=\underset{k\in K}{\lim }{t}^k,v_i^{\ast }=\underset{k\in K}{\lim }{v}_i^k$ 。由 $H\left(y^k\right)$ 的连续性以及算法I要求 $-H\left(y^k\right)>0$ ，当 $k\to \infty$ 时可以得到 $H\left(y^k\right)\to H\left(y^{\ast }\right)\le 0$ 。根据(3.8)和 ${\epsilon }_{comp}^k\to 0$ 直接可得 $G\left(x^{\ast }\right)\circ H\left(y^{\ast }\right)=0$ 。因此， $\left(x^{\ast },y^{\ast }\right)$ 是松弛问题(2.1)的可行点。

根据(3.7a)可得 ${\nabla }_{x,y}L\left(x^k,y^k,s^k,t^k,v^k,{\gamma }^k,{\mu }^k,{\lambda }^k\right)\to 0$ 。由(3.7c)可得 $g\left(x^{\ast }\right)=-s^{\ast }\le 0$ ，由(3.7b)可得 ${\left({\lambda }^g\right)}^{\text{T}}{s}^{\ast }=0$ ，则 ${\left({\lambda }^g\right)}^{\text{T}}\left(-g\left(x^{\ast }\right)\right)=0$ ，同时 ${\lambda }^{g,k}>0$ ，所以 $\min \left\{-g\left(x^k\right),{\lambda }^{g,k}\right\}\to 0$ 。同理可得 $\min \left\{-\theta \left(y^k\right),{\lambda }^{\theta ,k}\right\}\to 0$ ， $\min \left\{-\tilde{H}\left(y^k\right),{\lambda }^{\tilde{H},k}\right\}\to 0$ 。

若 $i\in M$ ，可知 $H_i\left(y^{\ast }\right)<0$ ， $G_i\left(x^{\ast }\right)=0$ ，当k充分大可得 $G_i\left(x^k\right)\to 0$ ，由(3.8)知 ${\Vert \min \left\{-H_i\left(y^k\right),\left|G_i\left(x^k\right)\right|\right\}\Vert }_{\infty }=\left|G_i\left(x^k\right)\right|\le {\epsilon }_{comp}^k$ ，所以 ${\gamma }_i^k{G}_i\left(x^k\right)\to 0$ ，由 ${\lambda }_i^{H,k}$ 定义可知 $\left|{\lambda }_i^{H,k}\right|\to 0$ 。若 $i\in I\cup J$ ，可得 $H_i\left(y^{\ast }\right)=0$ ， $-H_i\left(y^k\right)\to 0$ 。两种情况都满足 $\min \left\{-H_i\left(y^k\right),\left|{\lambda }_i^{H,k}\right|\right\}\to 0$ $\forall i=1,\cdots ,n$ 。

若 $i\in I$ ，可知 $G_i\left(x^{\ast }\right)\ne 0$ ， $H_i\left(y^{\ast }\right)=0$ ，当k充分大可得 $\left|G_i\left(x^k\right)\right|>0$ ， $-H_i\left(y^k\right)\to 0$ ，由(3.8)知 ${\Vert \min \left\{-H_i\left(y^k\right),\left|G_i\left(x^k\right)\right|\right\}\Vert }_{\infty }=-H_i\left(y^k\right)\le {\epsilon }_{comp}^k$ ，所以 ${\gamma }_i^k{H}_i\left(y^k\right)\to 0$ ，由 ${\lambda }_i^{G,k}$ 定义可知 $\left|{\lambda }_i^{G,k}\right|\to 0$ 。若 $i\in J\cup M$ ，可得 $G_i\left(x^{\ast }\right)=0$ ， $\left|G_i\left(x^k\right)\right|\to 0$ 。两种情况都满足 $\min \left\{\left|G_i\left(x^k\right)\right|,\left|{\lambda }_i^{G,k}\right|\right\}\to 0$ $\forall i=1,\cdots ,n$ 。

因此， $\left(x^{\ast },y^{\ast }\right)$ 是松弛问题(2.1)的AW-稳定点。根据文献 [1] 可知， $\left(x^{\ast },y^{\ast }\right)\in R^n\times R^n$ 是松弛问题(2.1)的可行点意味着 $x^{\ast }$ 是问题(1.1)的可行点。由文献 [6] 定理A.3可知，若 $\left(x^{\ast },y^{\ast }\right)\in R^n\times R^n$ 是松弛问题(2.1)的可行点，并且是松弛问题(2.1)的AW-稳定点，则 $x^{\ast }$ 是问题(1.1)的CC-AM-稳定点。□

结合上述定理，在CC-AM-正则性条件下，我们可以得到如下推论。

推论4.2 假设 $\left(x^{\ast },y^{\ast }\right)$ 是由算法I生成的序列 $\left\{\left(x^k,y^k\right)\right\}$ 的极限点，并且满足定理4.1的条件，若CC-AM-正则性在 $x^{\ast }$ 处成立，则 $x^{\ast }$ 是问题(1.1)的CC-M-稳定点。

证明：若 $\left(x^{\ast },y^{\ast }\right)$ 是由算法I生成的序列 $\left\{\left(x^k,y^k\right)\right\}$ 的极限点，并且满足定理4.1的条件，则 $x^{\ast }$ 是问题(1.1)的CC-AM-稳定点。由文献 [6] 定理4.7可知，若 $x^{\ast }$ 是问题(1.1)的CC-AM-稳定点，结合CC-AM-正则性条件，则 $x^{\ast }$ 是问题(1.1)的CC-M-稳定点。□

5. 总结

本文主要研究了基数约束优化问题的内罚函数法，并对算法进行了收敛性分析，证明了在某些条件下内罚函数法产生的点列收敛到CC-AM-稳定点。进一步，在CC-AM-正则性条件下，可以得到基数约束优化问题的CC-M-稳定点，因此得到了求解基数约束优化问题的有效算法。

NOTES

^*通讯作者。