随着大数据时代的到来，越来越多的学者关注稀疏优化问题，如带有零模约束的优化问题。

$ \mathop {\min }\limits_{x \in {\mathbb{R}^n}} \;\{ f({\boldsymbol{x}}):{\boldsymbol{x}} \in {{\varOmega}} ,\;{\left\| {\boldsymbol{x}} \right\|_0} \leqslant \kappa {\text{\} }} $

(1)

式中： $ f:{\mathbb{R}}^{n}\to \mathbb{R} $ 为连续可微的函数， $ \kappa $ 为一个给定的正整数且 $ \kappa < n $ ， ${{\varOmega}} \subseteq {\mathbb{R}^n}$ 为一个给定的集合， ${\left\| {\boldsymbol{x}} \right\|_0}$ 为向量 ${\boldsymbol{x}} \in {\mathbb{R}^n}$ 的零模，即向量 ${\boldsymbol{x}}$ 中非零分量的个数。式(1)在统计、信号与图像处理、机器学习、压缩感知、基因选择与分析等领域有广泛的应用^[1-6]。由于零模函数具有组合性质，所以带有零模约束的优化模型(1)是NP(Nondeterminism Polynomial)难问题。文献[7-9]把式(1)转化为混合整数规划问题进行求解。文献[10-11]把式(1)转化为带有如下互补约束集的互补规划，或称为带有均衡约束的数学规划(Mathematical Programs, MP)。

$ \langle {\boldsymbol{e}},{\boldsymbol{y}}\rangle \geqslant n - \kappa ,\langle \left| {\boldsymbol{x}} \right|,{\boldsymbol{y}}\rangle = 0,0\leqslant{\boldsymbol{y}} \leqslant{\boldsymbol{e}},{\boldsymbol{x}} \in \mathit{{ \varOmega }},{\boldsymbol{y}} \in {\mathbb{R}^n} $

式中： ${\boldsymbol{e}}$ 为分量全为1的向量， $\left| {\boldsymbol{x}} \right|$ 为由 ${\boldsymbol{x}}$ 的对应分量的绝对值形成的向量。上述集合中，最难处理的约束是 $\langle \left|{\boldsymbol{x}}\right|,{\boldsymbol{y}}\rangle =0，{\boldsymbol{y}}\geqslant 0$ 这部分。沿用文献[10]中的叫法，本文也把这部分的约束形成的集合称之为半互补集合，即

$ \{ ({\boldsymbol{x}},{\boldsymbol{y}}) \in {\mathbb{R}^n}:\left\langle {\left| {\boldsymbol{x}} \right|,{\boldsymbol{y}}} \right\rangle = 0,\;{\boldsymbol{y}} \geqslant 0\} $

(2)

另外，文献[12]引理3.1，给出了零模函数的一个等价刻画，即零模函数可看成是一个特定带有互补约束集(2)的参数优化的最优值函数。利用零模函数的这个变分刻画，文献[13-14]研究了零模正则问题和零模极小化问题的一些等价Lipschitz代理，并讨论了它们的稳定点之间的关系。

众所周知，刻画约束集合的相依切锥和极限法锥对描述约束优化问题的最优性条件是至关重要的。文献[15]刻画了集合 $\{ {\boldsymbol{x}} \in {\mathbb{R}^n}:{\left\| {\boldsymbol{x}} \right\|_0} \leqslant \kappa \}$ 的相依切锥、Clarke切锥和法锥，借助这些切锥和法锥的刻画，给出了式(1)在 $ \mathit{\Omega } {\text{ = }}{\mathbb{R}^n} $ 时的一阶和二阶最优性条件。本文主要刻画了由零模约束诱导出来的半互补约束集(2)的相依切锥、正则法锥和极限法锥。

1 定义

任意给定正整数 $ n $ ， $ {\mathbb{R}^n} $ 记为 $ n $ 锥向量空间， $ \mathbb{R}_{\text{ + }}^n $ 记为集合 $\{ {\boldsymbol{x}} \in {\mathbb{R}^n}:{{\boldsymbol{x}}_i} \geqslant 0,\;i = 1, \cdots ,n\}$ 和 $ \mathbb{R}_ - ^n $ 记为集合 $\{ {\boldsymbol{x}} \in {\mathbb{R}^n}: {{\boldsymbol{x}}_i} \leqslant 0,\;i = 1, \cdots ,n\}$ 。对任意 ${\boldsymbol{x}},{\boldsymbol{y}} \in {\mathbb{R}^n}$ ， $\left\langle {{\boldsymbol{x}},{\boldsymbol{y}}} \right\rangle$ 为向量 ${\boldsymbol{x}},{\boldsymbol{y}}$ 的内积， $\left\| {\boldsymbol{x}} \right\|$ 为向量 ${\boldsymbol{x}}$ 的模，即 $\left\| {\boldsymbol{x}} \right\| = \sqrt {\left\langle {{\boldsymbol{x}},{\boldsymbol{x}}} \right\rangle }$ 。假设 $ C \subseteq {\mathbb{R}^n} $ 为一个锥，则用 $ {C^ \circ } $ 记为它的负极锥，即

$ {C^ \circ }: = \{ {\boldsymbol{v}} \in {\mathbb{R}^n}:\;\left\langle {{\boldsymbol{v}},{\boldsymbol{x}}} \right\rangle \leqslant 0,\;\forall {\boldsymbol{x}} \in C\} $

(3)

设 ${{\varOmega}} \subseteq {\mathbb{R}^n}$ ，对于给定的点 $\overline {\boldsymbol{x}} \in {{\varOmega}}$ ，给出集合 ${{\varOmega}}$ 在点 $\overline {\boldsymbol{x}}$ 处的相依切锥、正则法锥和法锥的定义，它们更多的性质读者可参考文献[16]。

定义1 　 ${\boldsymbol{d}_{{n}}} \in {\mathbb{R}^n}$ 为集合 ${{\varOmega}}$ 在点 $\overline {\boldsymbol{x}}$ 处的相依切向量，如果存在正数数列 $ \left\{ {{\lambda _k}} \right\} $ 和序列 $\left\{ {{{\boldsymbol{d}}_n^k}} \right\}$ 满足 $ \mathop {\lim }\limits_{k \to \infty } {\lambda _k} = 0 $ 和 $\mathop {\lim }\limits_{k \to \infty } {{\boldsymbol{d}}_n^k} = {\boldsymbol{d}_n}$ 使对任意的 $ k $ 有 $\overline x + {\lambda _k}{{\boldsymbol{d}}_n^k} \in \mathit{\Omega }$ 成立。集合 $\mathit{\Omega }$ 在 $\overline {\boldsymbol{x}}$ 处的所有相依切向量 ${\boldsymbol{d}_n}$ 组成的集合称为集合 $\mathit{\Omega }$ 在点 $ \overline {\boldsymbol{x}} $ 处的相依切锥，记为 ${T_\mathit{\Omega } }(\overline {\boldsymbol{x}} )$ 。容易验证， ${T_\mathit{\Omega } }(\overline {\boldsymbol{x}} )$ 是一个锥。

定义2 　向量 ${\boldsymbol{v}_n} \in {\mathbb{R}^n}$ 为集合 $ \varOmega $ 在点 $\overline {\boldsymbol{x}}$ 处的正则法向量，如果上极限

$ \mathop {\lim \sup }\limits_{{\boldsymbol{x}} \to \overline {\boldsymbol{x}} ,\;{\boldsymbol{x}} \in \varOmega } \frac{{\left\langle {{\boldsymbol{v}_n},{\boldsymbol{x}} - \overline {\boldsymbol{x}} } \right\rangle }}{{\| {{\boldsymbol{x}} - \overline {\boldsymbol{x}} } \|}} \leqslant 0 $

成立。所有在点 $\overline {\boldsymbol{x}}$ 处的正则法向量 ${\boldsymbol{v}_n}$ 组成的集合称为集合 $ \varOmega $ 在点 $\overline {\boldsymbol{x}}$ 处的正则法锥，记为 $N_\mathit{\Omega } ^f(\overline {\boldsymbol{x}} )$ 。

定义3 　向量 ${\boldsymbol{v}_n} \in {\mathbb{R}^n}$ 为集合 $\mathit{\Omega }$ 在点 $\overline {\boldsymbol{x}}$ 处的极限法向量，如果存在序列 $\{ {{\boldsymbol{x}}^k}\}$ 和 ${\text{\{ }}{{\boldsymbol{v}}_n^k}\}$ 满足 ${{\boldsymbol{x}}^k} \in \mathit{\Omega }$ ， $\mathop {\lim }\limits_{k \to \infty } {{\boldsymbol{x}}^k} = \overline {\boldsymbol{x}}$ 和 $\mathop {\lim }\limits_{k \to \infty } {{\boldsymbol{v}}_n^k} = {\boldsymbol{v}_n}$ ，使对任意的 $ k $ 有 ${{\boldsymbol{v}}_n^k} \in N_{\varOmega } ^f({{\boldsymbol{x}}^k})$ 成立。所有在点 $\overline {\boldsymbol{x}}$ 处的极限法向量 ${\boldsymbol{v}}_n$ 组成的集合称为集合 $\varOmega$ 在点 $\overline {\boldsymbol{x}}$ 处的极限法锥，记为 ${N_\mathit{\Omega } }(\overline {\boldsymbol{x}} )$ 。

显然，根据定义3可知式(4)的包含关系成立。

$ N_\mathit{\Omega } ^f(\overline {\boldsymbol{x}} ) \subseteq {N_\mathit{\Omega } }(\overline {\boldsymbol{x}} ) $

(4)

2 主要结论

根据文献[16]中的命题6.41可知，半互补集合(2)的相依切锥、正则法锥和极限法锥的刻画主要依赖 $ n = 1 $ 时对应的半互补集，即

$ D: = \{ (t,{{\tau }} ) \in \mathbb{R} \times {\mathbb{R}_ + }:\;\left| t \right|{ {\tau}} = 0\} $

的相依切锥、正则法锥和极限法锥的刻画。下文刻画了半互补集合 $ D $ 的相依切锥、正则法锥和极限法锥。

定理1 　假设 $(\overline t ,\overline {{ {\tau}}} ) \in D$ ，则

$ {T_D}\left( {\overline t,\overline \tau } \right) = \left\{ {\begin{array}{*{20}{l}} {\left\{ 0 \right\} \times \mathbb{R},}&{\overline t = 0,\overline \tau > 0}\\ {\left( {\mathbb{R} \times \left\{ 0 \right\}} \right) \cup \left( {\left\{ 0 \right\} \times {\mathbb{R}_ + }} \right),}&{\overline t = 0,\overline \tau = 0}\\ {\mathbb{R} \times \left\{ 0 \right\},}&{\overline t \ne 0,\overline \tau = 0} \end{array}} \right. $

证明 　根据半互补集合 $ D $ 的定义可知

$ D = (\{ 0\} \times {\mathbb{R}_ + }) \cup (\mathbb{R} \times \{ 0\} ) $

由于 $(\overline t ,\overline {{ {\tau}}} ) \in D$ ，分以下3种情况进行讨论。

情况1 　 $\overline t = 0,\;\overline {{ {\tau}}} > 0$ 。任意取定 $ d \in \mathbb{R} $ ，取序列 $ {\lambda _k} = \dfrac{1}{k} $ 和 ${{{d}}^k} \equiv {{d}}$ ，容易验证，对于足够大的 $ k $ 有

$ (\overline t ,\overline \tau ) + {\lambda _k}(0,{{{d}}^k}) = (0,\overline \tau + \frac{1}{k}{d^k}) \in D $

成立。根据定义1，可知 $ (0,d) \in {T_D}(\overline t ,\overline \tau ) $ 。结合 $ d $ 的任意性，可知

$ \{ 0\} \times \mathbb{R} \subseteq {T_D}(\overline t ,\overline {{ {\tau}}} ) $

(5)

反过来，任意从集合 $ {T_D}(\overline t ,\overline \tau ) $ 中取一点 $ (\zeta ,\eta ) $ ，则根据定义1，存在正数序列 $ \left\{ {{\lambda _k}} \right\} $ 满足 $ \mathop {\lim }\limits_{k \to \infty } {\lambda _k} = 0 $ 和序列 $ \left\{ {({\zeta ^k},{\eta ^k})} \right\} $ 满足 $ \mathop {\lim }\limits_{k \to \infty } ({\zeta ^k},{\eta ^k}) = (\zeta ,\eta ) $ 使得对任意的 $ k $ 有 $(\overline t ,\overline \tau ) + {\lambda _k} ({\zeta ^k}, {\eta ^k}) \in D$ 成立，即有

$ \overline \tau + {\lambda _k}{\eta ^k} \geqslant 0 {,}\; \;\; {\lambda _k}| {{\zeta ^k}} |(\overline \tau + {\lambda _k}{\eta ^k}) = 0 $

由于 $ \overline \tau > 0 $ ，结合 $ \overline \tau + {\lambda _k}{\eta ^k} \geqslant 0 $ 可知，存在正整数 $ {k_1} $ 使对任意 $ k > {k_1} $ 有 $ \overline \tau + {\lambda _k}{\eta ^k} > 0 $ 成立。再根据 ${\lambda _k} | {{\zeta ^k}} | (\overline \tau + {\lambda _k}{\eta ^k}) = 0$ 和 $ {\lambda _k} > 0 $ ，进而可知任意 $ k > {k_1} $ 有 $ {\zeta ^k} = 0 $ ，从而有 $\mathop {\lim }\limits_{k \to \infty } {\zeta ^k} = 0{\text{ = }}\zeta$ 。故由 $ (\zeta ,\eta ) $ 的任意性可知

$ {T_D}(\overline t ,\overline {{ {\tau}}} ) \subseteq \{ 0\} \times \mathbb{R} $

(6)

根据式(5)和式(6)可知，当 $ \overline t = 0,\overline \tau > 0 $ 时，有

$ {T_D}(\overline t ,\overline \tau ){\text{ = }}\{ 0\} \times \mathbb{R} $

情况2 　 $\overline t = 0,\overline {{ {\tau}}} = 0$ 。首先，证明包含关系

$ (\mathbb{R} \times \{ 0\} ) \cup (\{ 0\} \times {\mathbb{R}_ + }) \subseteq {T_D}(\overline t ,\overline \tau ) $

成立。任意取定 $ d \in \mathbb{R} $ ，令序列 $ {\lambda _k} = \dfrac{1}{k} $ 和 $ {d^k} \equiv d $ ，容易验证，对于任意的 $ k $ 一定有

$ (\overline t ,\overline \tau ) + {\lambda _k}({d^k},0) = (\frac{1}{k}{d^k},0) \in D $

成立。根据定义1，可知 $ (d,0) \in {T_D}(\overline t ,\overline \tau ) $ 。结合 $ d $ 的任意性，可知

$ \mathbb{R} \times {\text{\{ }}0{\text{\} }} \subseteq {T_D}(\overline t ,\overline \tau ) $

(7)

类似地，任意取定 $ v \in {\mathbb{R}_{\text{ + }}} $ ,令序列 $ {v^k} \equiv v $ 。容易验证，对于任意的 $ k $ 一定有

$ (\overline t ,\overline \tau ) + {\lambda _k}(0,{v^k}) = (0,\frac{1}{k}{v^k}) \in D $

成立。根据定义1，可知 $ (0,v) \in {T_D}(\overline t ,\overline \tau ) $ 。结合 $ v $ 的任意性，可知

$ \{ 0\} \times {\mathbb{R}_{\text{ + }}} \subseteq {T_D}(\overline t ,\overline \tau ) $

(8)

联合式(7)和式(8)，可得

$ (\mathbb{R} \times \{ 0\} ) \cup (\{ 0\} \times {\mathbb{R}_{\text{ + }}}) \subseteq {T_D}(\overline t ,\overline \tau ) $

(9)

下文主要来论证式(10)的包含关系成立。

$ {T_D}(\overline t ,\overline \tau ) \subseteq (\mathbb{R} \times \{ 0\} ) \cup (\{ 0\} \times {\mathbb{R}_ + }) $

(10)

任意从集合 $ {T_D}(\overline t ,\overline \tau ) $ 中取一点 $ (\zeta ,\eta ) $ ，则根据定义1，存在正数序列 $ \left\{ {{\lambda _k}} \right\} $ 满足 $ \mathop {\lim }\limits_{k \to \infty } {\lambda _k} = 0 $ 和序列 $ \left\{ {({\zeta ^k},{\eta ^k})} \right\} $ 满足 $ \mathop {\lim }\limits_{k \to \infty } ({\zeta ^k},{\eta ^k}) = (\zeta ,\eta ) $ 使得对任意的 $ k $ 有 $(\overline t ,\overline \tau ) + {\lambda _k}({\zeta ^k},{\eta ^k}) \in $ $D $ 成立，即有

$ {{\lambda _k}}{\eta ^k}\geqslant 0,\; ({\lambda _k})^2| {{\zeta ^k}} |{\eta ^k} = 0 $

(11)

注意到 $ {\lambda _k} > 0 $ ，由式(11)可得，对任意 $ k $ 有

$ {\eta ^k} \geqslant 0 和 | {{\zeta ^k}} |{\eta ^k} = 0 $

如果存在正整数 $ {k_2} $ 使得对任意 $ k > {k_2} $ 有 $ {\eta ^k} \equiv 0 $ 成立，则有 $ \mathop {\lim }\limits_{k \to \infty } {\eta ^k} = 0 = \eta $ ，从而有

$ (\zeta ,\eta ) \in \mathbb{R} \times \{ 0\} $

(12)

否则，对于序列 $\{ {\eta ^k}\} $ ，一定存在子列 $ K $ ，使得对任意 $ k \in K $ ， $ {\eta ^k} > 0 $ 且 $ \mathop {\lim }\limits_{k \in K,k \to \infty } {\eta ^k} = \eta $ 。结合等式 $| {{\zeta ^k}} |{\eta ^k} = 0 $ ，可得对任意 $ k \in K $ ，有 $ {\zeta ^k} = 0 $ 成立，进而有 $ \mathop {\lim }\limits_{k \in K,k \to \infty } {\zeta ^k} = 0 = \zeta $ 成立。故有

$ (\zeta ,\eta ) \in \{ 0\} \times \mathbb{R} $

(13)

由 $ (\zeta ,\eta ) $ 的任意性，根据式(12)和式(13)，可知式(10)成立。最后根据式(9)和式(10)可知

$ {T_D}(\overline t ,\overline \tau ){\text{ = }}(\mathbb{R} \times \{ 0\} ) \cup (\{ 0\} \times {\mathbb{R}_ + }) $

情况3 　 $ \overline t \ne 0,\overline \tau = 0 $ 。分 $ \overline t > 0 $ 和 $ \overline t < 0 $ 两种情况论证。

(1) $ \overline t > 0,\overline \tau = 0 $ 。证明式(14)成立。

$ {T_D}(\overline t ,\overline \tau ){\text{ = }}\mathbb{R} \times \{ 0\} $

(14)

任意取定 $ d \in \mathbb{R} $ ,令序列 ${\lambda _k} = \dfrac{1}{k}$ 和 $ {d^k} \equiv d $ ,容易验证，对于足够大的 $ k $ 一定有

$ (\overline{t},\overline{\tau })+{\lambda }_{k}({d}^{k}，0)=(\overline{t}+\frac{1}{k}{d}^{k},0)\in D $

成立。根据定义1，可知 $ (d,0) \in {T_D}(\overline t ,\overline \tau ) $ 。结合 $ d $ 的任意性，可知

$ \mathbb{R} \times {\text{\{ }}0{\text{\} }} \subseteq {T_D}(\overline t ,\overline \tau ) $

(15)

反过来，任意从集合 $ {T_D}(\overline t ,\overline \tau ) $ 中取一点 $ (\zeta ,\eta ) $ ，则根据定义1，存在正数序列 $ \left\{ {{\lambda _k}} \right\} $ 满足 $ \mathop {\lim }\limits_{k \to \infty } {\lambda _k} = 0 $ 和序列 $ \left\{ {({\zeta ^k},{\eta ^k})} \right\} $ 满足 $ \mathop {\lim }\limits_{k \to \infty } ({\zeta ^k},{\eta ^k}) = (\zeta ,\eta ) $ 使得对任意的 $ k $ 有 $(\overline t ,\overline \tau ) + {\lambda _k}({\zeta ^k}, {\eta ^k}) \in D$ 成立，则

$ {\lambda _k}{\eta ^k} \geqslant 0$

$ {({\lambda _k})^2}\left| {\overline t + {\lambda _k}{\zeta ^k}} \right|{\eta ^k} = 0 $

(16)

注意到 $ \overline t > 0 $ 和 $ \mathop {\lim }\limits_{k \to \infty } (\overline t + {\lambda _k}{\zeta ^k}) = \overline t $ ，则一定存在正整数 $ {k_3} $ 使得对于任意 $ k > {k_3} $ ，有 $ \overline t + {\lambda _k}{\zeta ^k} > 0 $ 。再根据式(16)可得对任意 $ k > {k_3} $ ，有 $ {\eta ^k} = 0 $ 。进而有 $ \mathop {\lim }\limits_{k \to \infty } {\eta ^k} = 0 = \eta $ 。故有 $ (\zeta ,\eta ) \in \{ 0\} \times \mathbb{R} $ 。由 $ (\zeta ,\eta ) $ 的任意性，可知

$ {T_D}(\overline t ,\overline \tau ) \subseteq \mathbb{R} \times \{ 0\} $

(17)

结合式(15)和式(17)，可以得知式(14)成立。

(2) $ \overline t > 0,\overline \tau = 0 $ 。类似情况3中的(1)，可得

$ {T_D}(\overline t ,\overline \tau ){\text{ = }}\mathbb{R} \times \{ 0\} $

综上所述，当 $ \overline t \ne 0,\overline \tau = 0 $ ，有 $ {T_D}(\overline t ,\overline \tau ){\text{ = }}\mathbb{R} \times \{ 0\} $ 成立。

定理2 　假设 $ (\overline t ,\overline \tau ) \in D $ ，则

$ N_D^f(\overline t ,\overline \tau ) = \left\{ {\begin{array}{*{20}{c}} {\mathbb{R} \times \{ 0\} ,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} }&{\overline t = 0,\overline \tau > 0} \\ {\{ 0\} \times {\mathbb{R}\_ },}&{\overline t = 0,\overline \tau = 0} \\ {\{ 0\} \times \mathbb{R},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} }&{\overline t \ne 0,\overline \tau = 0} \end{array}} \right. $

(18)

证明 　根据文献[1]中的定理6.28可知

$ N_D^f(\overline t ,\overline \tau ) = {({T_D}(\overline t ,\overline \tau ))^ \circ } $

(19)

结合式(3)，容易验证当 $ \overline t = 0,\;\overline \tau > 0 $ 时，

$ N_D^f(\overline t ,\overline \tau ) = \mathbb{R} \times {\text{\{ }} 0{\text{\} }} $

当 $ \overline t \ne 0,\;\overline \tau {\text{ = }}0 $ 时，有

$ N_D^f(\overline t ,\overline \tau ) = {\text{\{ }} 0{\text{\} }} \times \mathbb{R} $

因此，只需要验证当 $ \overline t = 0,\;\overline \tau {\text{ = }}0 $ 时有下面的等式成立

$ N_D^f(\overline t ,\overline \tau ) = {\text{\{ }} 0{\text{\} }} \times {\mathbb{R}\_ } $

(20)

从集合 $ {\text{\{ }}0{\text{\} }} \times {\mathbb{R}\_ } $ 中任意选取一点 $ (u,v) $ ，容易验证有

$ \langle (u,v),(\zeta ,\eta )\rangle \leqslant 0，\forall (\zeta ,\eta )\in (\mathbb{R}\times \{0\})\cup (\{0\}\times {\mathbb{R}}_+) $

成立。根据式(3)和定理1相依切锥的刻画，可知

$ (u,v) \in {({T_D}(\overline t ,\overline \tau ))^ \circ } $

再根据式(19)和 $ (u,v) $ 的任意性，可知

$ {\text{\{ }} 0{\text{\} }} \times {\mathbb{R}\_ } \subseteq N_D^f(\overline t ,\overline \tau ) $

(21)

反过来，从集合 $ N_D^f(\overline t ,\overline \tau ) $ 中任意选取一点 $ (u,v) $ ，根据式(19)可知，对任意的 $ \;\;(\zeta ,\eta ) \in {T_D}(\overline t ,\overline \tau ) $ 有

$ \left\langle {(u,v),(\zeta ,\eta )} \right\rangle \leqslant 0 $

(22)

根据定理1，在式(22)中分别取 $ ({\zeta _1},{\eta _1}) = (1,0) $ 和 $ ({\zeta _2},{\eta _2}) = ( - 1,0) $ ，可得 $ u = 0 $ 。取 $ ({\zeta _3},{\eta _3}) = (0,1) $ ，并结合 $ u = 0 $ ，可得 $ v \leqslant 0 $ 。故有 $(u,v) \in \{ 0\} \times {\mathbb{R}\_ }$ 。再由 $ (u,v) $ 的任意性，可知

$ N_D^f(\overline t ,\overline \tau ) \subseteq \{0\} \times {\mathbb{R}\_ } $

(23)

最后根据式(21)和式(23)，可知式(20)成立。

定理3 　假设 $ (\overline t ,\overline \tau ) \in D $ ，则

$ {N_D}(\overline t ,\overline \tau ) = \left\{ {\begin{array}{*{20}{c}} {\mathbb{R} \times \{ 0\} ,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} }&{\overline t = 0,\overline \tau > 0} \\ {(\mathbb{R} \times \{ 0\} ) \cup (\{ 0\} \times \mathbb{R}),}&{\overline t = 0,\overline \tau = 0} \\ {\{ 0\} \times \mathbb{R},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\kern 1pt} {\kern 1pt} }&{\overline t \ne 0,\overline \tau = 0} \end{array}} \right. $

证明 　由于 $ (\overline t ,\overline \tau ) \in D $ ，下文分3种情况进行讨论。

情况1 　 $ \overline t = 0,\overline \tau > 0 $ 。根据式(4)，只需要论证

$ {N_D}(0,\overline \tau ) \subseteq \mathbb{R} \times \{ 0\} $

(24)

现从 $ {N_D}(0,\overline \tau ) $ 中任意选取一点 $ (u,v) $ ，由定义3可知，存在序列 $ \{({t}^{k},{\tau }^{k})\}和\{({u}^{k},{v}^{k})\} $ 满足 $({t^k},{\tau ^k}) \in D$ ， $\underset{k\to \infty }{\mathrm{lim}}({t}^{k},{\tau }^{k}) = (0,\overline{\tau })，$ $ \mathop {\lim }\limits_{k \to \infty } ({u^k},{v^k}) = (u,v), $ 使得

$ ({u^k},{v^k}) \in N_D^f({t^k},{\tau ^k}) $

(25)

由 $ \overline \tau > 0 $ 和 $ \mathop {\lim }\limits_{k \to \infty } {\tau ^k} = \overline \tau $ 可知，存在正整数 $ {k_1} $ 使得对任意的 $ k > {k_1} $ ，有 $ {\tau ^k} > 0 $ 成立。再结合 $ ({t^k},{\tau ^k}) \in D $ 可知，对任意的 $ k > {k_1} $ ，有 $ {t^k} = 0 $ ，联合式(25)和式(18)可得 ${v^k} = 0$ ，故 $ \mathop {\lim }\limits_{k \to \infty } {v^k} = v = 0 $ ，由 $(u,v) $ 的任意性可知式(25)成立。

情况2 　 $ \overline t = 0,\overline \tau = 0 $ 。先论证式(26)的包含关系。

$ {N_D}(0,0) \subseteq (\mathbb{R} \times \{ 0\} ) \cup (\{ 0\} \times \mathbb{R}) $

(26)

现从集合 $ {N_D}(0,0) $ 中任意选取一点 $ (u,v) $ ，则根据定义3可知，存在序列 $ \{ ({t^k},{\tau ^k})\} ,\{ ({u^k},{v^k})\} $ 满足 $({t^k},{\tau ^k}) \in D$ ， $\mathop {\lim }\limits_{k \to \infty } ({t^k},{\tau ^k}) = 0$ ， $ \mathop {\lim }\limits_{k \to \infty } ({u^k},{v^k}) = (u,v) $ 使得式(27)成立。

$ ({u^k},{v^k}) \in N_D^f({t^k},{\tau ^k}) $

(27)

注意到 $ {\tau ^k} \geqslant 0 $ 和 $ \mathop {\lim }\limits_{k \to \infty } {\tau ^k} = 0 $ ，下面分两种情况讨论。

(1) 假设存在正整数 $ {k_2} $ 使得对任意 $ k > {k_2} $ 有 $ {\tau ^k} \equiv 0 $ 。注意到 $ \mathop {\lim }\limits_{k \to \infty } {t^k} = 0 $ ,如果存在正整数 $ {k_3} $ 满足 $ {k_3} > {k_2} $ ，使得对任意 $ k > {k_3} $ 有 $ {t^k} \equiv 0 $ 成立，则由式(27)和式(18)可知

$ {u^k} = 0,\;\;\forall \;k > {k_3} $

(28)

否则一定存在一个子列 $ {K_1} $ 使得 $ \mathop {\lim }\limits_{k \in {K_1},k \to \infty } {t^k} = 0 $ 且 ${t^k} \ne 0(k \in {K_1})$ ，同样根据式(27)和式(18)可知

$ {u}^{k}=0，\forall k\in {K}_{1} $

(29)

注意到 $ \mathop {\lim }\limits_{k \to \infty } {u^k} = u $ ，可知 $ u = 0 $ 成立。结合 $ (u,v) $ 的任意性，可知式(26)成立。

(2) 如果上述情况2中的(1)不成立，则一定存在一个子列 $ {K_2} $ 使得 $ \mathop {\lim }\limits_{k \in {K_2},k \to \infty } {\tau ^k} = 0 $ 且 $ {\tau ^k} > 0(k \in {K_2}) $ 。类似情况1的后半段证明可知， $ {v^k} = 0(k \in {K_2}) $ ，从而有 $ \mathop {\lim }\limits_{k \in {K_2},k \to \infty } {v^k} = v = 0 $ ，由 $ (u,v) $ 的任意性可知式(26)成立。

下文说明反向包含成立。任取一点 $(a,0) \in \mathbb{R} \times \{ 0\} $ ，令 $({t^k},{\tau ^k},{a^k},{b^k}) = (0,1/k,a,0)$ ，则对任意的整数 $ k $ ，有 $({t^k},{\tau ^k}) \to (t,\tau )$ 并且 $({a^k},{b^k}) \in N_D^f({t^k},{\tau ^k})$ 。那么根据极限法锥的定义，有 $(a,0) \in {N_D}(\overline t ,\overline \tau )$ 。因此 $\mathbb{R} \times \{0\} \in {N_D}(\overline t ,\overline \tau )$ 。同样地，可以任取一点 $(0,b) \in \{0\} \times \mathbb{R}$ ，令 $({t}^{k},{\tau }^{k},{a}^{k},{b}^{k})= (1/k,0,0,b)$ ，则可以说明 $\{ 0\} \times \mathbb{R} \in {N_D}(\overline t ,\overline \tau )$ 。即反向包含成立。因此结论得证。

情况3 　 $ \overline t \ne 0,\overline \tau = 0 $ 根据式(4)只需要证明

$ {N_D}(\overline t ,0) \subseteq \{ 0\} \times \mathbb{R} $

(30)

现从集合 $ {N_D}(\overline t ,0) $ 中任意选取一点 $ (u,v) $ ，则由定义3存在序列 $ \{ ({t^k},{\tau ^k})\} $ 和 $ \{ ({u^k}{v^k})\} $ 满足 $ ({t^k},{\tau ^k}) \in D $ ， $\mathop {\lim }\limits_{k \to \infty } ({t^k},{\tau ^k}) = (\overline t ,0)$ 和 $ \mathop {\lim }\limits_{k \to \infty } ({u^k},{v^k}) = (u,v) $ 使得

$ ({u^k},{v^k}) \in N_D^f({t^k},{\tau ^k}) $

(31)

注意到 $ \overline t \ne 0 $ 和 $ \mathop {\lim }\limits_{k \to \infty } {t^k} = \overline t $ ，则存在正整数 $ {k_4} $ 使得对任意 $ k > {k_4} $ ，有 $ {t^k} \ne 0 $ 。结合 $ ({t^k},{\tau ^k}) \in D $ 可知 $ {\tau ^k} = 0,\;\forall \;k > {k_4} $ 。再联合式(31)和式(18)，可得 $ {u^k} = 0,\;\forall \;k > {k_3} $ ，从而有 $\mathop {\lim }\limits_k {u^k} = u = 0$ ，由 $ (u,v) $ 的任意性可知式(30)成立。结论得证。

3 结论

稀疏约束使得优化问题(1)产生了组合特征，是一个NP难问题。一般来讲，连续优化的理论通常不能用于处理该类问题，但是稀疏约束集合的特殊结构也为研究提供了一个新机遇。切锥、法锥是刻画优化问题的最优性条件的重要工具之一。本文利用了切锥、法锥的工具,刻画了半互补集合D的相依切锥、正则法锥和极限法锥。后续将提出相应的约束规范并建立最优性条件。这些结果在某种程度上丰富了非连续、非凸规划问题的最优性理论。