稀疏优化问题是借助向量的$ l_{0} $范数来刻画向量的稀疏性, 其数学模型可以大致归结为$ l_{0} $正则优化问题和稀疏约束优化问题两大类, 其中$ l_{0} $范数是指向量中非零元素的个数. 稀疏约束优化问题是一类重要的非凸非连续优化问题, 对该问题的研究被广泛应用于图像处理^[1-3]、机器学习^{[4, 5]}、经济学^[6]、统计学^[7]和主成分分析^{[8, 9]}等众多领域. 经过几十年的发展, 稀疏约束优化问题已经成为当下一个热门的研究方向, 并已获得很多丰硕的研究成果.

稀疏约束优化问题的一般模型可表述如下

(1.1) $ \begin{eqnarray} &{ } \min\limits_{x\in {{\Bbb R}} ^n } {f(x)}\\ &\mbox{s.t.}\ G(x)\in K, \left \| x \right \| _{0} \le s, \end{eqnarray} $

其中$ f:{{\Bbb R}} ^n\rightarrow {{\Bbb R}} $, $ G:{{\Bbb R}} ^n \rightarrow {{\Bbb R}} ^m $为给定的函数, $ K $为$ {{\Bbb R}} ^m $中的非空闭集, 表示的$ l_{0} $范数. 求解问题(1.1)的主要困难在于对稀疏约束的处理. 根据处理方式的不同, 可将求解问题(1.1) 的方法简单分为模型转化法^{[10, 11]}和直接处理法^{[12, 13]}两大类. 其中, 直接处理法借助稀疏集的投影与一些切锥和法锥的表达式得到了问题(1.1)的最优性条件. 具体地, 基于近十年研究者们给出的一些最优性条件, Pan^[12]建立了问题(1.1)的一阶和二阶最优性条件. 这些最优性条件不仅丰富了稀疏优化的理论成果, 还为算法的设计和收敛性分析提供了坚实基础.

若$ G(x)=x, \; K={{\Bbb R}} ^n $, 则问题(1.1)退化为如下单稀疏约束优化问题

(1.2) $ \begin{eqnarray} &\min\limits_{x\in {{\Bbb R}} ^n } {f(x)}\\ &\mbox{s.t.}\left \|x \right \| _{0} \le s. \end{eqnarray} $

Beck等^[13]应用直接处理法建立了问题(1.2)的三类一阶必要最优性条件: 基本可行性条件, CW最优性条件和$ L $ -稳定点, 其中, CW最优性条件是借助于坐标下降法思想而建立的. 基于CW最优性条件, 他们设计了贪婪稀疏单纯形算法与部分贪婪稀疏单纯形算法. 贪婪稀疏单纯形算法是沿坐标方向求单稀疏约束优化问题的极小值, 故算法具有贪婪性; 并且由于算法的基本迭代思路类似于单纯形法, 故称之为贪婪稀疏单纯形算法. 在问题(1.2)的约束条件具有对称性假设(除凸性和闭性外)下, Beck等^[14]基于该问题构建的CW最优性条件, 设计了Zero-CW search算法和Full-CW search算法. 上述CW最优性条件为单稀疏约束优化问题的求解提供了理论基础, 并且它也成为一些一般稀疏优化问题的算法设计基础, 如: 主成分分析问题^[15]和组稀疏优化问题^[16]等.

很多实际应用中往往不需要寻找最稀疏的解, 而只需最优解满足一定的稀疏度. 借助稀疏度上界的先验信息, 从而可以通过求解问题(1.2)来获得最佳决策. 然而, 还有一些实际问题需要将相应的决策变量分成两块, 并要求这两块决策变量都满足一定的稀疏度, 这一类问题的数学模型可表述为如下双重稀疏约束优化问题

(1.3) $ \begin{eqnarray} &\min {f(x, y)}\\ &\mbox{s.t.}\left \| x \right \| _{0} \le s, \left \| y \right \| _{0} \le t, \end{eqnarray} $

其中变量$ x\in {{\Bbb R}} ^n, \; y\in {{\Bbb R}} ^m $, $ f(x, y):{{\Bbb R}} ^{n+m}\to{{\Bbb R}} $是连续实值函数, $ \left \| x \right \| _{0} $和$ \left \|y \right \| _{0} $分别为$ x $和$ y $的$ l_{0} $范数, 且$ s $ ($ s\le n $)和$ t $ ($ t\le m $)均为正整数. 尽管问题(1.3)可以看作问题(1.2)的一种特殊情况, 但其求解方法更为复杂, 因此有必要对该问题进行深入研究. Gao等^[17]构建了问题(1.3)的必要最优性条件: $ L $ -稳定点, 并基于$ L $ -平稳点, 设计了一种交替最小化算法. 由于$ L $ -稳定点要求问题(1.3)的$ \bigtriangledown _{x} f(z) $和$ \bigtriangledown _{y} f(z) $满足Lipschitz条件, 并且算法的迭代中需要计算Lipschitz常数, 因此为了减少计算成本, 本文探讨一种不需要计算Lipschitz常数的算法.

受到Beck等^[13]工作的启发, 本文建立了问题(1.3)的CW最优性条件, 为了说明CW最优解比文献[17]中$ L $ -稳定点更具有优越性, 进一步建立了基本可行性条件. 由于CW最优性条件不需要目标函数梯度满足Lipschitz条件, 从而使得所求解的问题范围更加广泛. 然后, 本文基于CW最优性条件设计了一种贪婪单纯形算法, 并给出了算法的收敛性结果. 本文的研究框架如下: 第二节构建了问题(1.3)的CW最优性条件和基本可行性条件, 并分别研究了它们与问题(1.3)的最优解之间的关系, 然后分析了这两者之间的关系. 在研究了CW最优性条件与基本可行性条件关系的基础上, 研究了CW最优性条件的性质, 并分析了CW最优解与$ L $ -稳定点^[17]之间的关系; 第三节首先建立了问题(1.3)的贪婪单纯形算法, 并分析了算法的可行性, 然后在适当的假设条件下研究了算法的全局收敛性; 最后一节给出总结.

本节最后给出后文中所需要的一些数学符号. 令$ z=(x, y) $, 则问题(1.3)的目标函数$ f(x, y) $可以写为$ f(z) $; 分别令$ \bigtriangledown _{x} f(z) $和$ \bigtriangledown _{y} f(z) $表示$ f(z) $关于向量$ x $和$ y $的梯度; 令$ \bigtriangledown f(z) $表示$ f(z) $的梯度, 即$ \bigtriangledown f(z)=(\bigtriangledown _{x} f(z), \bigtriangledown _{y} f(z))\in {{\Bbb R}} ^n \times {{\Bbb R}} ^m $; 令$ \bigtriangledown _{i} f(z) $表示$ f(z) $关于$ z $的第个$ i $分量的偏导数. 令$ e_{i} \in {{\Bbb R}} ^{n+m} $表示第$ i $个分量为$ 1 $的$ n+m $维单位列向量.

本节首先给出问题(1.3)的最优解的刻画—CW最优解, 然后在此基础上研究它的性质. 令$ C_{s} =\left \{ x: \left \| x \right \| _{0}\le s \right \} $, $ C_{t} =\left \{ y: \left \| y \right \| _{0}\le t \right \} $, 则问题(1.3)可写为如下形式

(2.1) $ \begin{eqnarray} &\min f(x)\\ &\mbox{s.t.} \ x\in C_{s}, \; y\in C_{t}, \end{eqnarray} $

其中$ z\in C_{t} \times C_{t} $.

对$ \forall x\in {{\Bbb R}} ^n , \; y\in {{\Bbb R}} ^m, \; z\in {{\Bbb R}} ^{n+m} $, 定义支撑集如下

$ \begin{eqnarray*} &I_{1}(x)=\left \{ i:x_{i}\ne 0 \right \} , \; I_{1}(y)=\left \{ i:y_{i} \ne 0 \right \}, \; I_{1}(z)=\left \{ i:z_{i} \ne 0 \right \};\\ &I_{0}(x)=\left \{ i:x_{i}= 0 \right \} , \; I_{0}(y)=\left \{ i:y_{i} =0 \right \}, \; I_{0} (z)=\left \{ i:z_{i} = 0 \right \}. \end{eqnarray*} $

基于文献[13, 14]中CW最优性条件的概念, 下面定义问题(2.1)的CW最优性条件.

定义2.1  若问题$ (2.1) $的可行解$ z^{*} $满足如下条件之一

$ (1) $当$ \left \| x^{*} \right \| _{0}< s, \; \left \| y^{*} \right \| _{0}< t $时, 对任意$ i\in \left \{ 1, \cdots , n+m \right \} $, 有$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +ae_{i} ) $;

$ (2) $当$ \left \| x^{*} \right \| _{0}= s, \; \left \| y^{*} \right \| _{0}= t $时, 对任意$ i\in I_{1} (x^{*} ) $且$ j\in \left \{ 1, \cdots , n\right \} $或$ i\in I_{1} (y^{*} ) $且$ j\in \left \{ n+1, \cdots , n+m\right \} $, 有$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{*} -z_{i}^{*} e_{i}+ae_{j} ) $;

$ (3) $当$ \left \| x^{*} \right \| _{0}= s, \; \left \| y^{*} \right \| _{0}< t $时, 对任意$ i\in I_{1} (x^{*} ) $且$ j\in \left \{ 1, \cdots , n\right \} $, 有$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{*} -z_{i}^{*} e_{i}+ae_{j} ) $, 或对任意$ i\in \left \{ n+1, \cdots , n+m \right \} $, 有$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +ae_{i} ) $;

$ (4) $当$ \left \| x^{*} \right \| _{0}< s, \; \left \| y^{*} \right \| _{0}= t $时, 对任意$ i\in I_{1} (y^{*} ) $且$ j\in \left \{ n+1, \cdots , n+m\right \} $, 有$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{*} -z_{i}^{*} e_{i}+ae_{j} ) $, 或对任意$ i\in \left \{ 1, \cdots , n \right \} $, 有$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +ae_{i} ) $; 则称$ z^{*} $具有CW最优性, 或称$ z^{*} $为问题$ (2.1) $的CW最优解. 同时称条件(1)–(4)为问题$ (2.1) $在$ z^{*} $处的CW最优性条件.

注2.1  由定义$ 2.1 $可知: 求解问题$ (2.1) $的CW最优解不需要考虑$ \bigtriangledown _{x} f(z) $和$ \bigtriangledown _{y} f(z) $的存在性.

根据定义2.1, 下面将分析问题(2.1)的最优解与CW最优解的关系.

定理2.1  若为$ z^{*} $问题$ (2.1) $的最优解, 则$ z^{*} $满足CW最优性条件.

证  根据定义2.1对CW最优性条件的表述, 这里分四种情形进行证明.

(ⅰ) 若$ \left \| x^{*} \right \| _{0}< s, \; \left \| y^{*} \right \| _{0}< t $, 则令$ g(a)=f(z^{*} +ae_{i} ) $, 其中$ i\in \left \{ 1, \cdots , \; n+m \right \} $, $ a\in{{\Bbb R}} $. 由$ z^{*} $为问题(2.1)的最优解可得

$ \begin{eqnarray*} f(z^{*} )=g(0)\le g(a)=f(z^{*} +ae_{i} ). \end{eqnarray*} $

反之, 则存在一个非零的数$ a_{0}\in{{\Bbb R}} $, 使得

(2.2) $ \begin{equation} f(z^{*} )=g(0)\ge g(a_{0})=f(z^{*} +a_{0} e_{i} ), \end{equation} $

这与$ z^{*} $为问题(2.1)最优解相矛盾. 故$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +ae_{i} ) $.

(ⅱ) 若$ \left \| x^{*} \right \| _{0}= s, \left \| y^{*} \right \| _{0}= t $, 则进行如下分析.

当$ i\in I_{i} (x^{*} ) $且$ j\in \left \{ 1, \cdots , n\right \} $时, 根据$ j $的不同取值可分为如下三种情形进行证明.

(a) 当$ j\in I_{1}(x^{*} ) $且$ j=i $时, 由于$ z^{*} $为问题(2.1)的最优解, 故有$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +(a-z_{i}^{*} )e_{i} ) $.

(b) 当$ j\in I_{1}(x^{*} ) $且$ j\ne i $时, 由于$ \left \| x^{*}-x_{i}^{*}e_{i}+ae_{j} \right \| _{0} =s-1 $, 故有$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(x^{*}-x_{i}^{*}e_{i} +ae_{j} , y^{*} ) $.

(c) 当$ j\notin I_{1}(x^{*} ) $时, 由于$ \left \| x^{*}-x_{i}^{*}e_{i}+ae_{j} \right \| _{0} =s $, 故有$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(x^{*}-x_{i}^{*}e_{i} +ae_{j} , y^{*} ) $.

当$ i\in I_{1} (y^{*} ) $且$ j\in \left \{ n+1, \cdots , n+m\right \} $时, 根据$ j $的不同取值可分为如下三种情形进行证明.

(a) 当$ j\in I_{1}(y^{*} ) $且$ j=i $时, 由于$ z^{*} $为问题(2.1)的最优解, 故有$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +(a-z_{i}^{*} )e_{i} ) $.

(b) 当$ j\in I_{1}(y^{*} ) $且$ j\ne i $时, 由于$ \left \| y^{*}-y_{i}^{*}e_{i}+ae_{j} \right \| _{0} =t-1 $, 故有$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(x^{*}, y^{*}-y_{i}^{*}e_{i} +ae_{j} ) $.

(c) 当$ j\notin I_{1}(y^{*} ) $时, 由于$ \left \| y^{*}-y_{i}^{*} e_{i}+ae_{j} \right \| _{0} =t $, 故有$ f(z^{*} )= \min\limits_{a\in{{\Bbb R}} } f(x^{*}, y^{*}-y_{i}^{*}e_{i} +ae_{j} ) $.

(ⅲ)若$ \left \| x^{*} \right \| _{0}= s, \left \| y^{*} \right \| _{0}< t $, 则进行如下分析.

当$ i\in I_{1} (x^{*} ) $且$ j\in \left \{ 1, \cdots , n\right \} $时, 根据$ j $的不同取值可分为如下三种情形进行证明.

(a) 当$ j\in I_{1}(x^{*} ) $且$ j=i $时, 由于$ z^{*} $为问题(2.1)的最优解, 故有$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +(a-z_{i}^{*} )e_{i} ) $.

(b) 当$ j\in I_{1}(x^{*} ) $且$ j\ne i $时, 由于$ \left \| x^{*}-x_{i}^{*}e_{i}+ae_{j} \right \| _{0} =s-1 $, 故有$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(x^{*}-e_{i} x_{i}^{*} +ae_{j} , y^{*} ) $.

(c) 当$ j\notin I_{1}(x^{*} ) $时, 由于$ \left \| x^{*}-e_{i}x_{i}^{*}+ae_{j} \right \| _{0} =s $, 故有$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(x^{*}-z_{i}^{*}e_{i} +ae_{j} , y^{*}) $.

当$ i\in \left \{ n+1, \cdots , n+m\right \} $时, 则令$ g(a)=f(z^{*} +ae_{i} ) $, 其中$ a\in{{\Bbb R}} $. 由于$ z^{*} $为问题(2.1)的最优解, 故有$ f(z^{*} )=g(0)\le g(a)=f(z^{*} +ae_{i} ) $, 反之, 则存在一个非零的常数$ a_{0} \in{{\Bbb R}} $, 使得$ f(z^{*} )=g(0)> g(a_{0} )=f(z^{*} +a_{0} e_{i} ) $, 这与$ z^{*} $为问题(2.1)的最优解相矛盾. 故$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +ae_{i} ) $.

(ⅳ) 若$ \left \| x^{*} \right \| _{0}< s, \left \| y^{*} \right \| _{0}= t $, 则进行如下分析.

当$ i\in I_{1} (y^{*} ) $且$ j\in \left \{ n+1, \cdots , n+m\right \} $时, 根据$ j $的不同取值可分为如下三种情形进行证明.

(a) 当$ j\in I_{1}(y^{*} ) $且$ j=i $时, 由于$ z^{*} $为问题(2.1)的最优解, 故有$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +(a-z_{i}^{*} )e_{i} ) $.

(b) 当$ j\in I_{1}(y^{*} ) $且$ j\ne i $时, 由于$ \left \| y^{*}-y_{i}^{*}e_{i}+ae_{j} \right \| _{0} =t-1 $, 故有$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(x^{*}, y^{*}-y_{i}^{*}e_{i} +ae_{j} ) $.

(c) 当$ j\notin I_{1}(y^{*} ) $时, 由于$ \left \| y^{*}-y_{i}^{*}e_{i}+ae_{j} \right \| _{0} =t $, 故有$ f(z^{*} )= \min\limits_{a\in{{\Bbb R}} } f(x^{*}, y^{*}-y_{i}^{*}e_{i} +ae_{j} ) $.

当$ i\in \left \{ 1, \cdots , n\right \} $时, 则令$ g(a)=f(z^{*} +ae_{i} ) $, 其中$ a\in{{\Bbb R}} $. 由于$ z^{*} $为问题(2.1)的最优解, 故有$ f(z^{*} )=g(0)\le g(a)=f(z^{*} +ae_{i} ) $, 反之, 则存在一个非零的常数$ a_{0} \in{{\Bbb R}} $, 使得$ f(z^{*} )=g(0)> g(a_{0})=f(z^{*} +a_{0}e_{i} ) $, 这与$ z^{*} $为问题(2.1)的最优解相矛盾. 故$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +ae_{i} ) $.

注2.2  由定理$ 2.1 $可知: CW最优性条件可作为问题$ (2.1) $最优解的一种刻画形式.

由于后文需要借助基本可行性条件研究CW最优解与文献[17]中$ L $ -稳定点之间的关系, 下面给出问题(2.1)的基本可行性条件的定义.

定义2.2  若$ f(z) $在$ z $处可微且问题$ (2.1) $的可行解$ z^{*} $满足如下条件之一$ : $

$ (1) $当$ \left \| x^{*} \right \| _{0}=s, \; \left \| y^{*} \right \| _{0}= t $时, 对任意$ i\in I_{1}(z^{*} ) $, 有$ \bigtriangledown _{i} f(z)=0 $;

$ (2) $当$ \left \| x^{*} \right \| _{0}< s, \; \left \| y^{*} \right \| _{0}< t $时, 有$ \bigtriangledown f(z)=0 $;

$ (3) $当$ \left \| x^{*} \right \| _{0}< s, \; \left \| y^{*} \right \| _{0}= t $时, 对任意$ i\in I_{1}(y^{*} ) \cup \left \{ 1, \cdots , n \right \} $, 有$ \bigtriangledown _{i} f(z)=0 $;

$ (4) $当$ \left \| x^{*} \right \| _{0}= s, \; \left \| y^{*} \right \| _{0}< t $时, 对任意$ i\in I_{1}(x^{*} ) \cup \left \{n+ 1, \cdots , n +m\right \} $, 有$ \bigtriangledown _{i} f(z)=0 $; 则称$ z^{*} $具有基本可行性, 或称$ z^{*} $为问题$ (2.1) $的基本可行性向量. 同时称条件(1)–(4)为问题$ (2.1) $在$ z^{*} $处的基本可行性条件.

下面研究基本可行性向量与最优解的关系.

定理2.2  若$ z^{*} $为问题$ (2.1) $的最优解且$ f(z^{*}) $在$ z^{*} $处可微, 则$ z^{*} $满足基本可行性条件.

证  若$ z^{*} $为问题(2.1)的最优解, 则令$ g(a)=f(z^{*} +ae_{i} ) $, 其中$ i\in \left \{ 1, \cdots , n+m\right \} $, $ a\in{{\Bbb R}} $. 显然$ 0\in \arg\min g(a) $, 否则一定存在一个非零常数$ a_{0} $, 使得

$ f(z^{*} )=g(0)> g(a_{0} )=f(z^{*} +a_{0} e_{i} ), $

这与$ z^{*} $为$ f(z) $的最优解相矛盾. 因此, 对任意$ i\in \left \{ 1, \cdots , n+m\right \} $, 有$ \bigtriangledown _{i} f(z^{*} )=g{}'(0) =0 $. 因此, 完成了定理2.2的证明.

下面研究CW最优性条件与基本可行性条件之间的关系.

定理2.3  若$ z^{*} $为问题$ (2.1) $的CW最优解且$ f(z) $在$ z^{*} $处可微, 则$ z^{*} $满足基本可行性条件.

证  根据定义$ 2.1 $和定义$ 2.2 $对CW最优性条件和基本可行性条件的表述, 这里对$ z^{*} $分为四种情形进行证明.

(ⅰ)若$ \left \| x^{*} \right \| _{0}= s, \left \| y^{*} \right \| _{0}= t $, 则当$ i\in I_{1}(z^{*} ) $且$ j=i $时, 可得$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{*} -z_{i}^{*} e_{i}+ae_{j} ) $. 由于$ f(z^{*} )= f(z^{*} -z_{i}^{*} e_{i}+z_{i}^{*}e_{i} ) $, 上述不等式等价为

(2.3) $ \begin{equation} f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} -z_{i}^{*} e_{i}+ae_{i} ). \end{equation} $

令$ u=a-z_{i}^{*} $, 则(2.3)式可写为$ f(z^{*} )=\min\limits_{u\in{{\Bbb R}} } f(z^{*} +ue_{i} ) $, 故有$ \bigtriangledown _{i} f(z^{*} )=0. $

(ⅱ)若$ \left \| x^{*} \right \| _{0}< s, \left \| y^{*} \right \| _{0}< t $, 则对任意$ i\in \left \{ 1, \cdots , n+m\right \} $有$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{*} +ae_{i} ) $, 故有$ \bigtriangledown _{i} f(z^{*} )=0 $.

(ⅲ)若$ \left \| x^{*} \right \| _{0}< s, \left \| y^{*} \right \| _{0}= t $, 则进行如下分析.

当$ i\in I_{1}(y^{*} ) $且$ j=i $时, 由情形(ⅰ)可得$ \bigtriangledown _{i} f(z^{*} )=0 $.

当$ i\in \left \{ 1, \cdots , n \right \} $时, 由情形(ⅱ)可得$ \bigtriangledown _{i} f(z^{*} )=0 $. 因此, 当$ i\in I_{1}(y^{*} ) \cup \left \{ 1, \cdots , n \right \} $时, 有$ \bigtriangledown _{i} f(z^{*} ) $=0.

(ⅳ)若$ \left \| x^{*} \right \| _{0}= s, \left \| y^{*} \right \| _{0}< t $, 则进行如下分析.

当$ i\in I_{1}(x^{*} ) $且$ j=i $时, 由情形(ⅰ)可得$ \bigtriangledown _{i} f(z^{*} )=0 $.

当$ i\in \left \{n+ 1, \cdots , n +m\right \} $时, 由情形(ⅱ)可得$ \bigtriangledown _{i} f(z^{*} )=0 $. 因此, 当$ i\in I_{1}(x^{*} ) \cup \left \{n+ 1, \cdots , n +m\right \} $时, 有$ \bigtriangledown _{i} f(z^{*} )=0 $.

综上所述, 情形(ⅰ)–(ⅳ)中的分别满足基本可行性条件(1)–(4).

为了研究问题(2.1)的CW最优解与文献[17]中$ L $ -稳定点之间的关系, 引入$ \bigtriangledown _{x} f(z) $和$ \bigtriangledown _{y} f(z) $的Lipschitz条件、正交投影算子以及$ L $ -稳定点的定义^[17].

定义2.3^[17] (Lipschitz条件)  若问题$ (2.1) $中$ f(z) $在可行解$ z $处可微且存在常数$ L^{1}(f) $和$ L^{2}(f) $, 使得使得如下条件成立

(2.4) $ \begin{equation} \left \| \bigtriangledown _{x}f(x+d_{1}, y ) -\bigtriangledown _{x}f(z) \right \| \le L^{1}(f)\left \| d_{1} \right \|, \end{equation} $

(2.5) $ \begin{equation} \left \| \bigtriangledown _{y}f(x, y +d_{2} ) -\bigtriangledown _{y}f(z) \right \| \le L^{2}(f)\left \| d_{2} \right \| , \end{equation} $

其中$ d_{1} \in {{\Bbb R}} ^n $和$ d_{2} \in {{\Bbb R}} ^m $, 则称$ \bigtriangledown _{x} f(z) $和$ \bigtriangledown _{y} f(z) $满足Lipschitz条件.

定义2.4^[13]  令D为上$ {{\Bbb R}} ^n $的闭集, 对于$ y\in {{\Bbb R}} ^n $, 定义$ y $到$ D $上的正交投影算子为

$ P_{D}(y)=\arg\min\limits_{x\in D} \left \| x-y \right \| ^{2} , $

其中$ \left \| \cdot \right \| $表示$ l_{2} $范数.

定义2.5^[17]  对于问题$ (2.1) $的可行解$ z^{*} $, 若$ \bigtriangledown _{x} f(z^{*} ) $和$ \bigtriangledown _{y} f(z^{*}) $满足Lipschitz条件且存在正常数$ L(L\ge \max \left \{ L^{1}(f) , L^{2}(f) \right \} ) $, 使得如下条件成立

(2.6) $ \begin{equation} 0\in (x^{*}-P_{C_{s} }(x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) , y^{*}-P_{C_{t} }(y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) ) ), \end{equation} $

则称$ z^{*} $为问题(2.1)的$ L $ -稳定点.

在$ \bigtriangledown _{x} f(z ) $和$ \bigtriangledown _{y} f(z) $满足Lipschitz条件的基础上, 可以得到如下引理2.1.

引理2.1^[17] (局部下降引理)  对于问题$ (2.1) $的可行解$ z^{*} $, 若$ \bigtriangledown _{x} f(z^{*} ) $和$ \bigtriangledown _{y} f(z^{*}) $满足$ {\rm{Lipschitz}} $条件且存在正常数$ L^{1} (L^{1}\ge L^{1}(f)) $和$ L^{2} (L^{2}\ge L^{2}(f)) $, 使得如下不等式成立

(2.7) $ \begin{equation} f(x^{*}+d_{1} , y^{*} )\le f(z^{*} )+\left \langle \bigtriangledown _{x}f(z^{*} ) , d_{1} \right \rangle +\frac{L^{1} }{2}\left \| d_{1} \right \| , \; d_{1}\in {{\Bbb R}} ^n, \end{equation} $

(2.8) $ \begin{equation} f(x^{*} , y^{*}+d_{2} )\le f(z^{*} )+\left \langle \bigtriangledown _{y}f(z^{*} ) , d_{2} \right \rangle +\frac{L^{2} }{2}\left \| d_{2} \right \| , \; d_{2}\in {{\Bbb R}} ^m. \end{equation} $

为便于叙述, 对$ \forall z=(x, y) \in {{\Bbb R}} ^n\times {{\Bbb R}} ^m $, 令$ M_{i}(x) $表示$ x $的第$ i $个最大绝对值分量, 其中$ i=\left \{ 1, \cdots , n \right \} $; 令$ M_{i}(y) $表示$ y $的第个$ i $最大绝对值分量, 其中$ i=\left \{ n+1, \cdots , n +m\right \} $; 令$ M_{i}(z) $表示$ z $的第$ i $个最大绝对值分量, 其中$ i=\left \{ 1, \cdots , n +m\right \} $.

借助局部下降引理, 下面将研究CW最优性条件的性质.

定理2.4  若$ z^{*} $为问题$ (2.1) $的CW最优解且$ \bigtriangledown _{x} f(z^{*} ) $和$ \bigtriangledown _{y} f(z^{*}) $满足Lipschitz条件, 则对任意$ i\in I_{0}(x^{*} ) $有

(2.9) $ \begin{equation} \left | \bigtriangledown _{i}f(z^{*} ) \right | \le L^{1}M_{s} (x^{*} ); \end{equation} $

对任意$ i\in I_{0}(y^{*} ) $有

(2.10) $ \begin{equation} \left | \bigtriangledown _{i}f(z^{*} ) \right | \le L^{2}M_{t} (y^{*} ); \end{equation} $

对任意$ i\in I_{1}(z^{*} ) $有

(2.11) $ \begin{equation} \left | \bigtriangledown _{i}f(z^{*} ) \right | =0. \end{equation} $

证  根据定义$ 2.1 $对CW最优性条件的表述, 下面分四种情形进行证明.

(ⅰ)若$ \left \| x^{*} \right \| _{0}< s, \; \left \| y^{*} \right \| _{0}< t $, 则由定理2.3可得$ z^{*} $为基本可行性向量, 故$ \left | \bigtriangledown f(z^{*} ) \right | =0 $.

(ⅱ)若$ \left \| x^{*} \right \| _{0}= s, \; \left \| y^{*} \right \| _{0}= t $, 则根据$ i $的不同取值可分为如下三种情形进行证明.

(ⅱ-1)当$ i\in I_{1} (z^{*} ) $时, 由定理2.3可知, $ z^{*} $为基本可行性向量, 故$ \bigtriangledown _{i}f(z^{*} ) $.

(ⅱ-2)当$ i\in I_{0} (x^{*} ) $时, 令$ \left | x_{k}^{*} \right | =M_{s} (x^{*} ) $, 且可得$ z_{k}^{*} =x_{k}^{*} $. 又由于$ M_{s} (x^{*} )\ne 0 $, 故有$ k\in I_{1} (x^{*} ) $. 由$ CW $最优性条件可知, 当$ k\in I_{1} (x^{*} ) $时, 可得

(2.12) $ \begin{equation} f(z^{*} )\le \min f(z^{*} -z_{k}^{*} e_{k} -\sigma z_{k}^{*}e_{i} ), \end{equation} $

其中, $ \sigma =sgn(x_{k}^{*}\bigtriangledown _{i}f(z^{*} ) ) $. 假设$ \bigtriangledown _{i}f(z^{*} )\ne 0 $, 反之, $ \bigtriangledown _{i}f(z^{*} ) $一定会满足(2.9)式.由引理2.1可将(2.12)式写为如下不等式

(2.13) $ \begin{eqnarray} f(z^{*}-z_{k}^{*} e_{k}-\sigma z_{k}^{*} e_{i} ) &\le& f(z^{*})+(\bigtriangledown _{x}f(z^{*}) )^{\tau } (-z_{k}^{*} e_{k}-\sigma z_{k}^{*} e_{i})+\frac{L^{1} }{2}\left \| z_{k}^{*} e_{k}+\sigma z_{k}^{*} e_{i} \right \| ^{2} \\ &=&f(z^{*})-z_{k}^{*}(\bigtriangledown _{x}f(z^{*} ) )^{\tau } e_{k}-\sigma z_{k}^{*}(\bigtriangledown _{x}f(z^{*} ) )^{\tau } e_{i}+L^{1}( z_{k}^{*})^{2} \\ &=&f(z^{*})-\sigma z_{k}^{*}(\bigtriangledown _{i}f(z^{*} ) )^{\tau } e_{i}+L^{1}( z_{k}^{*})^{2}. \end{eqnarray} $

由$ k\in I_{1} (x^{*} ) $与定理2.3可得$ \bigtriangledown _{k}f(z^{*} ) =0 $. 由(2.12)式和(2.13)式可得

$ \begin{eqnarray*} \sigma z_{k}^{*} \bigtriangledown _{i}f(z^{*} ) \le L^{1}(z_{k}^{*} ) ^{2} , \end{eqnarray*} $

其中由$ \sigma $的定义可得$ \left | z_{k}^{*}\bigtriangledown _{i}f(z^{*} ) \right | \le L^{1}(z_{k}^{*}) ^{2} $, 故$ \left |\bigtriangledown _{i} f(z^{*} ) \right | \le L^{1} \left | z_{k}^{*} \right | = L^{1} M_{s}(z^{*} ) $.

(ⅱ-3)当$ i\in I_{0} (y^{*} ) $时, 令$ \left | y_{k}^{*} \right | =M_{t} (y^{*} ) $, 且可得$ z_{k}^{*} =y_{k}^{*} $. 又由于$ M_{t} (y^{*} )\ne 0 $, 故有$ k\in I_{1} (y^{*} ) $. 当$ k\in I_{1} (y^{*} ) $时, 由CW最优性条件可得

(2.14) $ \begin{equation} f(z^{*} )\le \min f(z^{*} -z_{k}^{*} e_{k} -\sigma z_{k}^{*}e_{i} ), \end{equation} $

其中, $ \sigma =sgn(y_{k}^{*}\bigtriangledown _{i}f(z^{*} ) ) $. 假设$ \bigtriangledown _{i}f(z^{*} )\ne 0 $, 反之, $ \bigtriangledown _{i}f(z^{*} ) $一定会满足(2.10)式. 由引理2.1可以得到

(2.15) $ \begin{eqnarray} f(z^{*}-z_{k}^{*} e_{k}-\sigma z_{k}^{*} e_{i} ) &\le& f(z^{*})+(\bigtriangledown _{y}f(z^{*}) )^{\tau } (-z_{k}^{*} e_{k}-\sigma z_{k}^{*} e_{i})+\frac{L^{2} }{2}\left \| z_{k}^{*} e_{k}+\sigma z_{k}^{*} e_{i} \right \| ^{2} \\ &=&f(z^{*})-z_{k}^{*}(\bigtriangledown _{y}f(z^{*} ) )^{\tau } e_{k}-\sigma z_{k}^{*}(\bigtriangledown _{y}f(z^{*} ) )^{\tau } e_{i}+L^{2}( z_{k}^{*})^{2} \\ &=&f(z^{*})-\sigma z_{k}^{*}(\bigtriangledown _{i}f(z^{*} ) )^{\tau } e_{i}+L^{2}( z_{k}^{*})^{2}. \end{eqnarray} $

由$ k\in I_{1} (y^{*} ) $与定理2.3可得$ \bigtriangledown _{k}f(z^{*} ) =0 $. 由(2.14)式和(2.15)式可得

$ \begin{eqnarray*} \sigma z_{k}^{*} \bigtriangledown _{i}f(z^{*} ) \le L^{2}(z_{k}^{*} ) ^{2} , \end{eqnarray*} $

其中由$ \sigma $的定义可得$ \left | z_{k}^{*}\bigtriangledown _{i}f(z^{*} ) \right | \le L^{2}(z_{k}^{*}) ^{2} $, 故$ \left |\bigtriangledown _{i} f(z^{*} ) \right | \le L^{2} \left | z_{k}^{*} \right | = L^{2} M_{t}(z^{*} ) $.

(ⅲ)若$ \left \| x^{*} \right \| _{0}= s, \; \left \| y^{*} \right \| _{0}< t $, 则当$ i\in I_{1}(x^{*} ) \cup \left \{n+ 1, \cdots , n +m\right \} $时, 由定理2.3可得$ \bigtriangledown _{i} f(z^{*} )=0 $. 因此, 当$ i\in I_{1} (z^{*} )\cup I_{0} (y^{*} ) $时, 有$ \left |\bigtriangledown _{i} f(z^{*} ) \right | =0 $. 当$ i\in I_{0} (x^{*} ) $时, 由(2.12)式和(2.13)式可得$ \left | \bigtriangledown _{i}f(z^{*} ) \right | \le L^{1}M_{s} (x^{*} ) $.

(ⅳ)若$ \left \| x^{*} \right \| _{0}< s, \; \left \| y^{*} \right \| _{0}= t $, 则当$ i\in I_{1}(y^{*} ) \cup \left \{1, \cdots , n \right \} $时, 由定理2.3可得$ \bigtriangledown _{i} f(z^{*} )=0 $. 因此, 当$ i\in I_{1} (z^{*} )\cup I_{0} (x^{*} ) $时, 有$ \left |\bigtriangledown _{i} f(z^{*} ) \right |=0 $. 当$ i\in I_{0} (y^{*} ) $时, 由(2.14)式和(2.15)式可得$ \left | \bigtriangledown _{i}f(z^{*} ) \right | \le L^{2}M_{t} (y^{*} ) $.

证毕.

根据定理2.4, 下面研究CW最优解与$ L $ -稳定点之间的关系.

定理2.5  若为问题$ (2.1) $的CW最优解且$ \bigtriangledown _{x} f(z^{*} ) $和$ \bigtriangledown _{y} f(z^{*}) $满足Lipschitz条件, 则$ z^{*} $为$ L $ -稳定点.

证  由定理2.4可知: 存在正常数$ L $且$ L\ge \max \left \{ L^{1}, L^{2} \right \} $, 使得对任意$ i\in I_{0}(x^{*} ) $有

(2.16) $ \begin{equation} \left | \bigtriangledown _{i}f(z^{*} ) \right | \le LM_{s} (x^{*} ); \end{equation} $

对任意$ i\in I_{0}(y^{*} ) $有

(2.17) $ \begin{equation} \left | \bigtriangledown _{i}f(z^{*} ) \right | \le LM_{t} (y^{*} ); \end{equation} $

对任意$ i\in I_{1}(z^{*} ) $有

(2.18) $ \begin{equation} \left | \bigtriangledown _{i}f(z^{*} ) \right | =0. \end{equation} $

根据定义2.1对CW最优性条件的表述, 这里分四种情形进行证明.

(ⅰ) 若$ \left \| x^{*} \right \| _{0}< s, \left \| y^{*} \right \| _{0}< t $, 则由$ M_{s} (x^{*} )=M_{t} (y^{*} )=0 $与(2.16)式、(2.17)式和(2.18)式可得$ \bigtriangledown f(z^{*} )=0 $, 进一步可得$ \left | x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) \right | =x^{*} $与$ \left | y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) \right | =y^{*} $, 从而可得$ P_{C_{s} } (x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) )=P_{C_{s} }(x^{*})=\left \{ x^{*} \right \} $与$ P_{C_{t} } (y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) )=P_{C_{t} }(y^{*})=\left \{ y^{*} \right \} $. 因此, 可得

$ 0\in (x^{*}-P_{C_{s} }(x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) , y^{*}-P_{C_{t} }(y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) )). $

(ⅱ) 若$ \left \| x^{*} \right \| _{0}= s, \left \| y^{*} \right \| _{0}= t $, 则由$ M_{s} (x^{*} )\ne 0 $、$ I_{1} (x^{*} )=s $、(2.16)式和(2.18)式可得对任意$ i\in I_{0} (x^{*} ) $有$ \left | x^{*}-\frac{1}{L} \bigtriangledown _{i}f(z^{*} ) \right | \le M_{s} (x^{*}) $, 或对任意$ i\in I_{1} (x^{*} ) $有$ \left | x^{*}-\frac{1}{L} \bigtriangledown _{i}f(z^{*} ) \right | =\left |x_{i}^{*} \right | $. 由$ M_{t}(y^{*} ) \ne 0 $、$ I_{1} (y^{*} )=t $、(2.17)式和(2.18) 式可得对任意$ i\in I_{0} (y^{*} ) $有$ \left | y^{*}-\frac{1}{L} \bigtriangledown _{i}f(z^{*} ) \right | \le M_{t} (y^{*}) $, 或对任意$ i\in I_{1} (y^{*} ) $有$ \left | y^{*}-\frac{1}{L} \bigtriangledown _{i}f(z^{*} ) \right | =\left |y_{i}^{*} \right | $. 由于$ P_{C_{s} } (x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) $中的向量由$ x^{*} $中最大绝对值分量与其它都小于或等于的$ M_{s}(x^{*} ) $分量组成, 因此, $ x^{*} \in P_{C_{s} } (x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) $进而$ 0\in \left \{ x^{*} - P_{C_{s} } (x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) \right \} $. 同理可得$ 0\in \left \{ y^{*} - P_{C_{t} } (y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) ) \right \} $. 因此, 可得

$ 0\in (x^{*}-P_{C_{s} }(x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) , y^{*}-P_{C_{t} }(y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) )). $

(ⅲ) 若$ \left \| x^{*} \right \| _{0}< s, \left \| y^{*} \right \| _{0}= t $, 则进行如下分析.

当$ i\in \left \{ 1, \cdots , n \right \} $时, 由$ M_{s} (x^{*} )=0 $, (2.16) 式和(2.18)式可得$ \bigtriangledown _{i} f(z^{*} )=0 $, 进一步可得$ \left | x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) \right |=x^{*} $, 从而可得$ P_{C_{s} } (x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) )=P_{C_{s} }(x^{*})=\left \{ x^{*} \right \} $, 故$ 0\in \left \{ x^{*} - P_{C_{s} } (x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) \right \} $.

由$ \left \| y^{*} \right \| _{0} =t $, 从而可得$ M_{t}(y^{*} ) \ne 0 $与$ I_{1} (y^{*} )=t $. 由(2.17)式和(2.18)式可得对任意$ i\in I_{0} (y^{*} ) $有$ \left | y^{*}-\frac{1}{L} \bigtriangledown _{i}f(z^{*} ) \right | \le M_{t} (y^{*}) $, 或对任意$ i\in I_{1} (y^{*} ) $有$ \left | y^{*}-\frac{1}{L} \bigtriangledown _{i}f(z^{*} ) \right | =\left |y_{i}^{*} \right | $. 由于$ P_{C_{t} } (y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) ) $中的向量由$ y^{*} $中最大绝对值分量与其它都小于或等于$ M_{t}(y^{*} ) $的分量组成, 所以$ 0\in \left \{ y^{*} - P_{C_{t} } (y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) ) \right \} $. 因此

$ 0\in (x^{*}-P_{C_{s} }(x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) , y^{*}-P_{C_{t} }(y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) )). $

(ⅳ) 若$ \left \| x^{*} \right \| _{0}= s, \left \| y^{*} \right \| _{0}< t $, 则进行如下分析.

当$ i\in \left \{ n+1, \cdots , n+m \right \} $时, 由$ M_{s} (y^{*} ) $, (2.17)式及(2.18)式可得$ \bigtriangledown _{i} f(z^{*} ) $, 进一步可得$ \left | y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) \right | =y^{*} $, 从而可得$ P_{C_{t} } (y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) )=P_{C_{t} }(y^{*})=\left \{ y^{*} \right \} $. 故$ 0\in \left \{ y^{*} - P_{C_{t} } (y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) ) \right \} $.

由$ \left \| x^{*} \right \| _{0} =s $, 可得$ M_{s}(x^{*} ) \ne 0 $与$ I_{1} (x^{*} )=s $. 由(2.16)式和(2.18)式可得对任意$ i\in I_{0} (x^{*} ) $有$ \left | x^{*}-\frac{1}{L} \bigtriangledown _{i}f(z^{*} ) \right | \le M_{s} (x^{*}) $, 或对任意$ i\in I_{1} (x^{*} ) $有$ \left | x^{*}-\frac{1}{L} \bigtriangledown _{i}f(z^{*} ) \right | =\left |x_{i}^{*} \right | $. 由于$ P_{C_{s} } (x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) $中向量由$ x^{*} $中最大绝对值分量与其它都小于或等于$ M_{s}(x^{*} ) $的分量组成, 所以$ 0\in \left \{ x^{*} - P_{C_{s} } (x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) \right \} $. 因此, 可得

$ 0\in (x^{*}-P_{C_{s} }(x^{*}-\frac{1}{L} \bigtriangledown _{x}f(z^{*} ) ) , y^{*}-P_{C_{t} }(y^{*}-\frac{1}{L} \bigtriangledown _{y}f(z^{*} ) )). $

综上所述, 情形(ⅰ)–(ⅳ)中的都为$ L $ -稳定点.

注2.3  定理$ 2.5 $分析了CW最优解与Gao等^[17]中$ L $ -稳定点之间的关系, 阐明了CW最优性条件对目标函数要求的条件更弱, 适用的范围更广泛, 且CW最优性条件的定义更简洁.

根据第2节建立的CW最优性条件, 本节首先给出求解问题(2.1)的一种贪婪单纯形算法, 然后分析算法的全局收敛性.

在下面的算法描述中, 记算法的第$ k $次迭代点为$ z^{k}=(x^{k}, y^{k} ) $, 且令$ z^{k+\frac{1}{2} }=(x^{k+1}, y^{k} ) $.

算法3.1  步1: 令$ k=0 $, 给定$ z^{0}\in C_{s} \times C _{t} $, 即$ x^{0}\in C_{s} , \; y^{0} \in C _{t} $.

步2: 若$ x^{k}<s , \; y^{k} <t $不成立, 则转步3; 否则对每一个$ i\in \left \{ 1, \cdots , n+m \right \} $,

计算

$ a_{i} \in \arg\min\limits_{a\in{{\Bbb R}} } f(z^{k} +ae_{i} ), f_{i} =f(z^{k} +a_{i} e_{i} ), i_{k} \in \arg\min\limits_{i\in \left \{ 1, \cdots , n+m \right \} } f_{i} . $

如果$ f_{i_{k} } <f(z^{k} ) $, 令$ z^{k+1}=z^{k} +a_{i_{k} } e_{i_{k} } $且$ k:=k+1 $, 转步3; 否则, 停止迭代.

步3: 若$ x^{k}=s , \; y^{k} =t $不成立, 则转步5; 否则对每一个$ i\in I_{1} (x^{k} ) $且$ j\in\left \{ 1, \cdots , n \right \} $,

计算

$ a_{i, j} \in\arg\min\limits_{a\in{{\Bbb R}} } f(z^{k} -z_{i}^{k} e_{i} +ae_{j} ) , f_{i, j} =f(z^{k}-z_{i}^{k} e_{i} +a_{i, j} e_{j} ) ; $

$ (i_{k} , j_{k} )\in \arg\min\limits_{i\in I_{1}(x^{k} ), j\in \left \{ 1, \cdots , n \right \} } f_{i, j}; $

如果$ f_{i_{k} , j_{k} } <f(z^{k} ) $, 令$ z^{k+\frac{1}{2} } =z^{k} -z_{i_{k} }^{k} e_{i_{k} } +a_{i_{k} , j_{k} } e_{j_{k} } $, 转步4; 否则令$ z^{k+\frac{1}{2} } =z^{k} $, 转步4.

步4: 对每一个$ i\in I_{1} (y^{k} ) $且$ j\in \left \{ n+1, \cdots , n+m \right \} $, 计算

$ a_{i, j} \in \arg\min\limits_{a\in{{\Bbb R}} } f(z^{k} -z_{i}^{k} e_{i} +ae_{j} ), f_{i, j} =f(z^{k}-z_{i}^{k} e_{i} +a_{i, j} e_{j} ); $

$ (i_{k} , j_{k} )\in \arg\min\limits_{i\in I_{1}(y^{k} ) , j\in \left \{ n+1, \cdots , n+m \right \} } f_{i, j}; $

如果$ f_{i_{k} , j_{k} } <f(z^{k+\frac{1}{2} } ) $, 令$ z^{k+1 } =z^{k} -z_{i_{k} }^{k} e_{i_{k} } +a_{i_{k} , j_{k} } e_{j_{k} } $且$ k:=k+1 $, 转步5; 否则如果$ f(z^{k+\frac{1}{2} } )<f(z^{k} ) $, 令$ z^{k+1}=z^{k+\frac{1}{2} } $且$ k:=k+1 $, 转步5, 否则停止迭代.

步5: 若$ x^{k}<s , \; y^{k} =t $不成立, 则转步7; 否则对每一个$ i\in\left \{ 1, \cdots , n \right \} $, 计算

$ a_{i} \in \arg\min\limits_{a\in{{\Bbb R}} } f(z^{k} +ae_{i} ), f_{i} =f(z^{k} +a_{i} e_{i} ), i_{k} \in \arg\min\limits_{i\in \left \{ 1, \cdots , n \right \} } f_{i} ; $

如果$ f_{i_{k} } <f(z^{k} ) $, 令$ z^{k+\frac{1}{2} }=z^{k} +a_{i_{k} } e_{i_{k} } $, 转步6; 否则令$ z^{k+\frac{1}{2} }=z^{k} $, 转步6.

步6: 对每一个$ i\in I_{1} (y^{k} ) $且$ j\in \left \{ n+1, \cdots , n+m \right \} $, 计算

$ a_{i, j} \in \arg\min\limits_{a\in{{\Bbb R}} } f(z^{k} -z_{i}^{k} e_{i} +ae_{j} ), f_{i, j} =f(z^{k}-z_{i}^{k} e_{i} +a_{i, j} e_{j} ); $

$ (i_{k} , j_{k} )\in \arg\min\limits_{i\in I_{1}(y^{k} ) , j\in \left \{ n+1, \cdots , n+m \right \} } f_{i, j}; $

如果$ f_{i_{k} , j_{k} } <f(z^{k+\frac{1}{2} } ) $, 令$ z^{k+1 } =z^{k} -z_{i_{k} }^{k} e_{i_{k} } +a_{i_{k} , j_{k} } e_{j_{k} } $且$ k:=k+1 $, 转步7; 否则如果$ f(z^{k+\frac{1}{2} } )<f(z^{k} ) $, 令$ z^{k+1}=z^{k+\frac{1}{2} } $且$ k:=k+1 $, 转步7, 否则停止迭代.

步7: 若$ x^{k}=s , \; y^{k} <t $不成立, 则转步2; 否则对每一个$ i\in\left \{ n+1, \cdots , n+m \right \} $, 计算

$ a_{i} \in \arg\min\limits_{a\in{{\Bbb R}} } f(z^{k} +ae_{i} ), f_{i} =f(z^{k} +a_{i} e_{i} ), i_{k} \in \arg\min\limits_{i\in \left \{ n+1, \cdots , n+m \right \} } f_{i} ; $

如果$ f_{i_{k} } <f(z^{k} ) $, 令$ z^{k+\frac{1}{2} }=z^{k} +a_{i_{k} } e_{i_{k} } $, 转步8; 否则令$ z^{k+\frac{1}{2} }=z^{k} $, 转步8.

步8: 对每一个$ i\in I_{1} (x^{k} ) $且$ j\in \left \{ 1, \cdots , n \right \} $, 计算

$ a_{i, j} \in \arg\min\limits_{a\in{{\Bbb R}} } f(z^{k} -z_{i}^{k} e_{i} +ae_{j} ) , f_{i, j} =f(z^{k}-z_{i}^{k} e_{i} +a_{i, j} e_{j} ); $

$ (i_{k} , j_{k} )\in \arg\min\limits_{i\in I_{1}(x^{k} ) , j\in \left \{ 1, \cdots , n \right \} } f_{i, j}; $

如果$ f_{i_{k} , j_{k} } <f(z^{k+\frac{1}{2} } ) $, 令$ z^{k+1 } =z^{k} -z_{i_{k} }^{k} e_{i_{k} } +a_{i_{k} , j_{k} } e_{j_{k} } $且$ k:=k+1 $, 转步2; 否则如果$ f(z^{k+\frac{1}{2} } )<f(z^{k} ) $, 令$ z^{k+1}=z^{k+\frac{1}{2} } $且$ k:=k+1 $, 转步2, 否则停止迭代.

下面将分析由算法3.1生成的迭代点列的可行性.

定理3.1  若$ \left \{ z^{k} \right \} $为算法$ 3.1 $生成的迭代点列, 则$ z^{k}\in C_{s}\times C_{t} $.

证  用数学归纳法证明如下:

(1) 当$ k=0 $时, 由算法的初始步可知: 命题成立.

(2) 假设当$ k=l $时($ l $为正整数), $ z^{l}\in C_{s}\times C_{t} $. 下面证明$ z^{l+1}\in C_{s}\times C_{t} $, 接下来根据$ z^{l} $取值的不同情况, 下面分为四种情形给出证明.

(ⅰ) 若$ \left \| x ^{l}\right \| _{0}< s, \; \left \| y ^{l}\right \| _{0}< t $, 则进行如下分析.

当$ i_{l}\in \left \{ 1, \cdots , n \right \} $时, 若$ f_{i_{l} } <f(z^{l} ) $, 则$ z^{l+1} =z^{l}+a_{i_{l} } e_{i_{l} } $. 若$ a_{i_{l} } =0 $, 则$ f_{i_{l} } =f(z^{l} ) $, 这与$ f_{i_{l} } <f(z^{l} ) $相矛盾, 故$ a_{i_{l} }\ne 0 $. 由于$ a_{i_{l} }\ne 0 $, 所以$ \left \| x ^{l+1}\right \| _{0}\le s, \; \left \| y ^{l+1}\right \| _{0}< t $, 即$ z^{l+1}\in C_{s}\times C_{t} $. 若$ f_{i_{l} } \ge f(z^{l} ) $, 则停止迭代, 且$ z^{l}=z^{l+1} $.

当$ i_{l}\in \left \{ n+1, \cdots , n+m \right \} $时, 若$ f_{i_{l} } <f(z^{l} ) $, 则$ z^{l+1} =z^{l}+a_{i_{l} } e_{i_{l} } $. 若$ a_{i_{l} } =0 $, 则$ f_{i_{l} } =f(z^{l} ) $, 这与$ f_{i_{l} } <f(z^{l} ) $相矛盾, 故$ a_{i_{l} }\ne 0 $. 由于$ a_{i_{l} }\ne 0 $, 所以$ \left \| x ^{l+1}\right \| _{0}< s, \; \left \| y ^{l+1}\right \| _{0}\le t $, 即$ z^{l+1}\in C_{s}\times C_{t} $. 若$ f_{i_{l} } \ge f(z^{l} ) $, 则停止迭代, 且$ z^{l}=z^{l+1} $.

(ⅱ) 若$ \left \| x ^{l} \right \| _{0}= s, \; \left \| y ^{l} \right \| _{0}= t $, 则进行如下分析.

当$ i_{l}\in I_{1} (y^{l} ) $且$ j_{l}\in \left \{ n+1, \cdot \cdot \cdot , n+m \right \} $时, 若$ f_{i_{l} , j_{l} } <f(z^{l+\frac{1}{2} } ) $, 则$ z^{l+1}=z^{l}-z_{i_{l} }^{l} e _{i_{l} } +a_{i_{l} , j_{l} } e_{j_{l} } $. 若$ a_{i_{l} , j_{l} }=0 $, 则$ \left \| x^{l+1} \right \|=s, \; \left \| y^{l+1} \right \|<t $, 反之, 则$ \left \| x^{l+1} \right \|=s, \left \| y^{l+1} \right \|\le t $, 即$ z^{l+1}\in C_{s}\times C_{t} $. 若$ f_{i_{l} , j_{l} }\ge f(z^{l+\frac{1}{2} } ) $, 则根据$ f(z^{l+\frac{1}{2} } )<f(z^{l} ) $能否成立, 可分为如下两种情形进行证明.

(a) 若$ f(z^{l+\frac{1}{2} } )<f(z^{l} ) $, 则$ z^{l+1}=z^{l+\frac{1}{2} } =z^{l}-z_{i_{l} }^{l} e _{i_{l} } +a_{i_{l} , j_{l} } e_{j_{l} } $, 其中$ i_{l}\in I_{1} (x^{l} ) $, $ j_{l}\in \left \{ 1, \cdots , n \right \} $. 若$ a_{i_{l} , j_{l} }=0 $, 则$ \left \| x^{l+1} \right \| _{0} <s, \; \left \| y^{l+1} \right \| =t $, 反之, 则$ \left \| x^{l+1} \right \| _{0} \le s, \; \left \| y^{l+1} \right \| =t $, 即$ z^{l+1}\in C_{s}\times C_{t} $.

(b) 若$ f(z^{l+\frac{1}{2} } )\ge f(z^{l} ) $, 则停止迭代, 且$ z^{l}=z^{l+1} $.

(ⅲ) 若$ \left \| x ^{l}\right \| _{0}= s, \; \left \| y ^{l}\right \| _{0}< t $, 则进行如下分析.

当$ i_{l}\in I_{1} (x^{l} ) $且$ j_{l}\in \left \{ 1, \cdots , n \right \} $时, 若$ f_{i_{l} , j_{l} } <f(z^{l+\frac{1}{2} } ) $, 则$ z^{l+1}=z^{l}-z_{i_{l} }^{l} e _{i_{l} } +a_{i_{l} , j_{l} } e_{j_{l} } $. 若$ a_{i_{l} , j_{l} }=0 $, 则$ \left \| x^{l+1} \right \|<s, \; \left \| y^{l+1} \right \|<t $, 即$ z^{l+1}\in C_{s}\times C_{t} $. 若$ a_{i_{l} , j_{l} }\ne 0 $, 则$ \left \| x^{l+1} \right \|\le s, $$ \left \| y^{l+1} \right \|<t $, 即$ z^{l+1}\in C_{s}\times C_{t} $. 若$ f_{i_{l} , j_{l} }\ge f(z^{l+\frac{1}{2} } ) $, 则根据$ f(z^{l+\frac{1}{2} } )<f(z^{l} ) $能否成立, 可分为如下两种情形进行证明.

(a) 若$ f(z^{l+\frac{1}{2} } )<f(z^{l} ) $, 则$ z^{l+1}=z^{l+\frac{1}{2} } =z^{l} +a_{i_{l} } e_{i_{l} } $, 其中$ i_{l}\in \left \{ n+1, \cdots , n+m \right \} $. 若$ a_{i_{l} } =0 $, 则$ f(z^{l+\frac{1}{2} } )=f(z^{l} ) $, 这与$ f(z^{l+\frac{1}{2} } )<f(z^{l} ) $相矛盾, 因此, $ a_{i_{l} } \ne 0 $, 则$ \left \| x^{l+1} \right \|=s, $$ \left \| y^{l+1} \right \|\le t $, 即$ z^{l+1}\in C_{s}\times C_{t} $.

(b) 若$ f(z^{l+\frac{1}{2} } )\ge f(z^{l} ) $, 则停止迭代, 且$ z^{l}=z^{l+1} $.

(ⅳ) 若$ \left \| x ^{l}\right \| _{0}< s, \; \left \| y ^{l}\right \| _{0}= t $, 则进行如下分析.

当$ i_{l}\in I_{1} (y^{l} ) $且$ j_{l}\in \left \{ n+1, \cdots , n+m \right \} $时, 若$ f_{i_{l} , j_{l} } <f(z^{l+\frac{1}{2} } ) $, 则$ z^{l+1}=z^{l}-z_{i_{l} }^{l} e _{i_{l} } +a_{i_{l} , j_{l} } e_{j_{l} } $. 若$ a_{i_{l} , j_{l} }=0 $, 则$ \left \| x^{l+1} \right \|<s, \left \| y^{l+1} \right \|<t $, 即$ z^{l+1}\in C_{s}\times C_{t} $. 若$ a_{i_{l} , j_{l} }\ne 0 $, 则$ \left \| x^{l+1} \right \|<s, $$ \left \| y^{l+1} \right \|\le t $, 即$ z^{l+1}\in C_{s}\times C_{t} $. 若$ f_{i_{l} , j_{l} }\ge f(z^{l+\frac{1}{2} } ) $, 则根据$ f(z^{l+\frac{1}{2} } )<f(z^{l} ) $能否成立, 可分为如下两种情形进行证明.

(a) 若$ f(z^{l+\frac{1}{2} } )<f(z^{l} ) $, 则$ z^{l+1}=z^{l+\frac{1}{2} } =z^{l} +a_{i_{l} } e_{i_{l} } $, 其中$ i_{l}\in \left \{ 1, \cdots , n\right \} $. 若$ a_{i_{l} } =0 $, 则$ f(z^{l+\frac{1}{2} } )=f(z^{l} ) $, 这与$ f(z^{l+\frac{1}{2} } )<f(z^{l} ) $相矛盾, 因此, $ a_{i_{l} } \ne 0, $则$ \left \| x^{l+1} \right \|\le s, $$ \left \| y^{l+1} \right \|\ =t $, 即$ z^{l+1}\in C_{s}\times C_{t} $.

(b) 若$ f(z^{l+\frac{1}{2} } )\ge f(z^{l} ) $, 则停止迭代, 且$ z^{l}=z^{l+1} $.

注3.1  定理$ 3.1 $说明了由算法$ 3.1 $迭代产生的点列是可行的, 这是收敛性分析中所必需的前提条件.

下面根据算法3.1的设计思路分为有限步迭代终止与无限步迭代终止两种情况探讨其收敛性.

定理3.2  若$ \left \{ z^{k} \right \} $是由算法$ 3.1 $生成的迭代点列, 则$ f(z^{k+1} )\le f(z^{k} ) $. 其中$ f(z^{k+1} )= f(z^{k} ) $当且仅当$ z^{k+1}= z^{k} $, 并且$ z^{k} $满足CW最优性条件.

证  由定理$ 3.1 $可知: 由算法$ 3.1 $生成的迭代点$ z^{k}\in C_{s}\times C_{t} $. 由算法$ 3.1 $的迭代定义可得函数列是单调非增的, 即$ f(z^{k+1} )\le f(z^{k} ) $. 充分性显然, 下面证明必要性. 若$ f(z^{k+1} )= f(z^{k} ) $, 则算法迭代停止且$ z^{k+1}= z^{k} $. 根据定义2.1对CW最优性条件的表述, 这里分如下四种情形进行证明.

(ⅰ) 若$ \left \| x ^{k} \right \| _{0}< s, \; \left \| y^{k} \right \| _{0}< t $, 则对任意$ i\in \left \{ 1, \cdots , n+m \right \} $, 由算法迭代定义可得$ f(z^{k+1} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{k} +ae_{i} )\le f(z^{k} ) $. 又由于$ f(z^{k+1} )= f(z^{k} ) $, 故有$ \min\limits_{a\in{{\Bbb R}} } f(z^{k} +ae_{i} )=f(z^{k} ) $.

(ⅱ) 若$ \left \| x ^{k} \right \| _{0}= s, \; \left \| y^{k} \right \| _{0}= t $, 则对任意, 或对任意$ i\in I(x^{k} ), j\in \left \{ 1, \cdot \cdot \cdot , n \right \} $, 由算法迭代定义可得$ f(z^{k+1} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{k}-z_{i}^{k} e_{i} +ae_{j} )\le f(z^{k} ) $. 又由$ f(z^{k+1} )= f(z^{k} ) $可得$ \min\limits_{a\in{{\Bbb R}} } f(z^{k} -z_{i}^{k} e_{j} +ae_{i} )=f(z^{k} ) $.

(ⅲ) 若$ \left \| x ^{k} \right \| _{0}= s, \; \left \| y^{k} \right \| _{0}< t $, 则进行如下分析.

对任意$ i\in I_{1} (x^{k} ), j\in \left \{ 1, \cdots , n \right \} $, 由算法迭代定义可得$ f(z^{k+1} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{k}-z_{i}^{k} e_{i} +ae_{j} )\le f(z^{k} ) $.

对任意$ i\in \left \{ n+1, \cdots , n+m \right \} $, 由算法迭代定义可得$ f(z^{k+1} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{k} +ae_{i} )\le f(z^{k} ) $.

又由于$ f(z^{k+1} )= f(z^{k} ) $, 故有$ \min\limits_{a\in{{\Bbb R}} } f(z^{k} -z_{i}^{k} e_{j} +ae_{i} )=f(z^{k} ) $($ i\in I(x^{k} ), j\in \left \{ 1, \cdots , n \right \} $)和$ \min\limits_{a\in{{\Bbb R}} } f(z^{k} +ae_{i} )=f(z^{k} ) $($ i\in \left \{ n+1, \cdots , n+m \right \} $).

(ⅳ)若$ \left \| x ^{k} \right \| _{0}< s, \; \left \| y^{k} \right \| _{0}=t $, 则进行如下分析.

对任意$ i\in I(y^{k} ), j\in \left \{ n+1, \cdots , n+m \right \} $, 由算法迭代定义可得$ f(z^{k+1} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{k}-z_{i}^{k} e_{i} +ae_{j} )\le f(z^{k} ) $.

对任意$ i\in \left \{ 1, \cdots , n \right \} $时, 由算法迭代定义可得$ f(z^{k+1} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{k} +ae_{i} )\le f(z^{k} ) $.

又由于$ f(z^{k+1} )= f(z^{k} ) $, 故有$ \min\limits_{a\in{{\Bbb R}} } f(z^{k} -z_{i}^{k} e_{j} +ae_{i} )=f(z^{k} ) $ ($ i\in I(y^{k} ), j\in \{ n+1, \cdots , $$ n+m \} $)和$ \min\limits_{a\in{{\Bbb R}} } f(z^{k} +ae_{i} )=f(z^{k} ) $ ($ i\in \left \{ 1, \cdots , n \right \} $).

综上所述, 情形(ⅰ)–(ⅳ)中的分别满足CW最优性条件(1)–(4).

注3.2  定理$ 3.2 $说明了算法$ 3.1 $经过有限步迭代产生的迭代点列满足CW最优性条件. 自然考虑到, 经过无限步产生迭代点列的聚点是否可以满足CW最优性条件.

下面研究算法3.1在无限步迭代终止下的全局收敛性. 下面的收敛性分析需要$ f(z) $满足有下界的条件, 即: 对$ \forall z\in C_{s} \times C_{t} $, 存在$ \upsilon \in{{\Bbb R}} $, 使得$ f(z)>\upsilon $.

定理3.3  若是$ \left \{ z^{k} \right \} $由算法$ 3.1 $生成的迭代点列, 则$ \left \{ z^{k} \right \} $的收敛点为CW最优解.

证  由定理$ 3.1 $可知: 由算法3.1生成的迭代点$ z^{k} \in C_{s} \times C_{t} $. 由定理$ 3.2 $可知: $ \left \{ f(z^{k}) \right \} $为非增的函数列, 且$ f(z) $有下界, 因此$ \left \{ f(z^{k}) \right \} $收敛. 令$ z^{*} $为$ \left \{ z^{k} \right \} $中的一个聚点, 则存在$ \left \{ z^{k} \right \} $的子列$ \left \{ z^{p_{n} } \right \} $收敛到$ z^{*} $. 根据定义$ 2.1 $对CW最优性条件的表述, 这里对$ z^{*} $分四种情形进行证明. 然而, 由于$ \left \| x^{*} \right \| _{0}< s, \left \| y ^{*} \right \| _{0}= t $和$ \left \| x^{*} \right \| _{0}= s, \left \| y ^{*} \right \| _{0}< t $证明过程相似, 所以下面只需分三种情况证明聚点$ z^{*} $满足CW最优性条件.

(ⅰ)若$ \left \| x^{*} \right \| _{0}= s, \; \left \| y ^{*} \right \| _{0}= t $, 则进行如下分析. 由于$ \left \{ z^{p_{n} } \right \} $收敛到$ z^{*} $, 故存在$ \left \{ z^{p_{n} } \right \} $的子序列$ \left \{ z^{k_{n} } \right \} $, $ z^{k_{n}} \rightarrow z^{*} $且$ I_{1} (z^{k_{n} } )=I_{1} (z^{*} ) $. 当$ i\in I_{1} (x^{*} ) $且$ j\in \left \{ 1, \cdots , n \right \} $或$ i\in I_{1} (y^{*} ) $且$ j\in \left \{ n+1, \cdots , n+m \right \} $时, 由算法3.1迭代可得

(3.1) $ \begin{equation} f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} }-z_{i}^{*} e_{i} +ae _{j} ), \end{equation} $

其中$ a\in{{\Bbb R}} $.

当时$ n\rightarrow \infty $, 由(3.1)式可得$ f(z^{*} )\le f(z^{* }-z_{i}^{*} e_{i} +ae _{j} ) $, 即$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{* }-z_{i}^{*} e_{i} +ae _{j} ) $. 因此, 情形(ⅰ)中的$ z^{*} $满足CW最优性条件中的条件(2).

(ⅱ)若$ \left \| x^{*} \right \| _{0}< s, \; \left \| y ^{*} \right \| _{0}< t $, 则进行如下分析.

由于$ \left \{ z^{p_{n} } \right \} $收敛到$ z^{*} $, 故存在的子序列$ \left \{ z^{k_{n} } \right \} $且$ \left \{ z^{k_{n} } \right \} $, $ z^{k} \rightarrow z^{*} $. 存在正整数$ N $, 当$ n>N $时, 对$ \left \{ z^{k_{n} } \right \} $有$ I_{1} (z^{*} )\subseteq I_{1} (z^{k_{n} } ) $. 若$ i\in I_{1} (z^{*} ) $, 则$ i\in I_{1} (z^{k_{n} } ) $, 且由算法3.1迭代可得

(3.2) $ \begin{equation} f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} } +ae _{i} ), \end{equation} $

其中$ a\in{{\Bbb R}} $. 当$ n\rightarrow \infty $时, 由(3.2)式可得$ f(z^{*} )\le f(z^{* } +ae _{i} ) $, 即$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{* } +ae _{i} ) $.

若$ i\in I_{0} (z^{*} ) $, 则根据$ z^{k_{n} } $的四种取值情形进行证明, 但是由于$ \left \| x^{k_{n} } \right \| _{0}< s, \; \left \| y ^{k_{n} } \right \| _{0}= t $与$ \left \| x^{k_{n} } \right \| _{0}= s, \; \left \| y ^{k_{n} } \right \| _{0}< t $证明方式相似, 因此只对$ \left \| x^{k_{n} } \right \| _{0}= s, \; \left \| y ^{k_{n} } \right \| _{0}< t $进行证明, 即对如下三种情形证明.

(ⅱ-1)若$ \left \| x^{k_{n} } \right \| _{0}< s, \; \left \| y ^{k_{n} } \right \| _{0}< t $, 则当$ i\in I_{0} (z^{*} ) $时, 由算法3.1的迭代可得

(3.3) $ \begin{equation} f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} } +ae _{i} ), \end{equation} $

其中$ a\in{{\Bbb R}} $. 当$ n\rightarrow \infty $时, 由(3.3)式可得$ f(z^{*} )\le f(z^{* } +ae _{i} ) $, 即$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{* } +ae _{i} ) $.

(ⅱ-2)若$ \left \| x^{k_{n} } \right \| _{0}= s, \; \left \| y ^{k_{n} } \right \| _{0}< t $, 则根据的不同取值又分为如下两种情形进行证明.

(a) 当$ i\in I_{0} (x^{*} ) $时, 由于$ I_{1} (x^{k_{n} } )\setminus I_{1} (x^{*} ) $非空, 故令$ j_{n} \in I_{1} (x^{k_{n} } )\setminus I_{1} (x^{*} ) $, 且由算法3.1迭代定义可得

(3.4) $ \begin{equation} f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} }-z_{j_{n} }^{*} e_{j_{n} } +ae _{i} ), \end{equation} $

其中$ a\in{{\Bbb R}} $. 当$ n\rightarrow \infty $时, 有$ z_{j_{n} }^{*} \rightarrow 0 $, 且由(3.4)式可得$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{* } +ae _{i} ) $. 由于对任意的$ a\in{{\Bbb R}} $不等式恒成立, 所以$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{* } +ae _{i} ) $.

(b) 当$ i\in I_{0} (y^{*} ) $时, 由算法3.1迭代定义可以得到$ f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} } +ae _{i} ) $, 其中$ a\in{{\Bbb R}} $. 当$ n\rightarrow \infty $时, 有$ f(z^{*} )\le f(z^{* } +ae _{i} ) $, 由于对任意$ a\in{{\Bbb R}} $不等式恒成立, 所以$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{* } +ae _{i} ) $.

(ⅱ-3)若$ \left \| x^{k_{n} } \right \| _{0}= s, \; \left \| y ^{k_{n} } \right \| _{0}= t $, 则进行如下证明.

当$ i\in I_{0} (x^{*} ) $时, 由于$ I_{1} (x^{k_{n} } )\setminus I_{1} (x^{*} ) $非空, 故令$ j_{n} \in I_{1} (x^{k_{n} } )\setminus I_{1} (x^{*} ) $, 且由算法3.1迭代定义可得$ f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} }-z_{j_{n} }^{*} e_{j_{n} } +ae _{i} ) $, 其中$ a\in{{\Bbb R}} $. 当$ n\rightarrow \infty $时, 有$ z_{j_{n} }^{*} \rightarrow 0 $, 故$ f(z^{*} )\le f(z^{* } +ae _{i} ) $, 由于对任意$ a\in{{\Bbb R}} $不等式一直成立, 所以$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{* } +ae _{i} ) $.

当$ i\in I_{0} (y^{*} ) $时, 由于$ I_{1} (y^{k_{n} } )\setminus I_{1} (y^{*} ) $非空, 故令$ j_{n} \in I_{1} (y^{k_{n} } )\setminus I_{1} (y^{*} ) $, 且由算法3.1迭代定义可得$ f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} }-z_{j_{n} }^{*} e_{j_{n} } +ae _{i} ) $, 其中$ a\in{{\Bbb R}} $. 当$ n\rightarrow \infty $时, 有$ z_{j_{n} }^{*} \rightarrow 0 $, 故$ f(z^{*} )\le f(z^{* } +ae _{i} ) $, 由于对任意$ a\in{{\Bbb R}} $不等式一直成立, 所以$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{* } +ae _{i} ) $.

综上所述, 情形(ⅱ)中的$ z^{* } $满足CW最优性条件中的条件(1).

(ⅲ)若$ \left \| x^{*} \right \| _{0}= s, \; \left \| y ^{*} \right \| _{0}< t $, 则根据$ i $的不同取值分为如下三种情形进行证明.

(ⅲ-1)当$ i\in I_{1} (x^{*} ) $且$ j=\left \{ 1, \cdots , n \right \} $时, 由于$ \left \{ z^{p_{n} } \right \} $收敛到$ z^{*} $, 故存在$ \left \{ z^{p_{n} } \right \} $的子序列$ \left \{ z^{k_{n} } \right \} $, $ z^{k} \rightarrow z^{*} $且$ I_{1} (z^{k_{n} } )=I_{1} (z^{*} ) $. 由算法3.1迭代定义可得$ f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} }-z_{i}^{*} e_{i} +ae _{j} ) $, 其中$ a\in{{\Bbb R}} $. 当$ n\rightarrow \infty $时, 有$ f(z^{*} )\le f(z^{* }-z_{i}^{*} e_{i} +ae _{j} ) $, 即$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{* }-z_{i}^{*} e_{i} +ae _{j} ) $.

(ⅲ-2)当$ i\in I_{1} (y^{*} ) $时, 由于$ \left \{ z^{p_{n} } \right \} $收敛到$ z^{*} $, 故存在子序列$ \left \{ z^{k_{n} } \right \} $且$ \left \{ z^{k_{n} } \right \} $, $ z^{k} \rightarrow z^{*} $. 存在正整数$ N $, 当$ n>N $时, 可得$ I_{1} (y^{*} )\subseteq I_{1} (y^{k_{n} } ) $. 当$ i\in I_{1} (y^{k_{n} } ) $时, 由算法3.1迭代定义可得$ f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} } +ae _{i} ) $, 其中$ a\in{{\Bbb R}} $.

当$ n\rightarrow \infty $时, 则有$ f(z^{*} )\le f(z^{* } +ae _{i} ) $, 由于对任意的$ a\in{{\Bbb R}} $不等式恒成立, 所以$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{* } +ae _{i} ) $.

(ⅲ-3)当$ i\in I_{0} (y^{*} ) $时, 根据$ y^{k_{n} } $的取值分为如下两种情形进行证明.

(a) 当$ \left \| y^{k_{n} } \right \| _{0} <t $时, 由算法3.1的迭代定义可得$ f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} } +ae _{i} ) $, 其中$ a\in{{\Bbb R}} $.

当$ n\rightarrow \infty $时, $ f(z^{*} )\le f(z^{* } +ae _{i} ) $, 即$ f(z^{*} )\le \min\limits_{a\in{{\Bbb R}} } f(z^{* }-z_{i}^{*} e_{i} +ae _{j} ) $.

(b) 当$ \left \| y^{k_{n} } \right \| _{0} =t $时, 由于$ I_{1} (y^{k_{n} } )\setminus I_{1} (y^{*} ) $非空, 故令$ j_{n} \in I_{1} (y^{k_{n} } )\setminus I_{1} (y^{*} ) $, 且由算法3.1迭代定义可得$ f(z^{k_{n} } )-f(z^{k_{n+1} } )\ge f(z^{k_{n} } )-f(z^{k_{n} }-z_{j_{n} }^{*} e_{j_{n} } +ae _{i} ) $, 其中$ a\in{{\Bbb R}} $.

当$ n\rightarrow \infty $时, $ z_{j_{n} }^{*} \rightarrow 0 $, 故$ f(z^{*} )\le f(z^{* } +ae _{i} ) $, 由于对任意$ a\in{{\Bbb R}} $不等式一直成立, 所以$ f(z^{*} )=\min\limits_{a\in{{\Bbb R}} } f(z^{* } +ae _{i} ) $.

综上所述, 情形(ⅲ)中的满足CW最优性条件中的条件(3).

注3.3  由定理$ 3.3 $可知: 由算法$ 3.1 $生成的无限点列全局收敛到CW最优解.

结合定理2.3与定理2.5可得到如下两个推论.

推论3.1  若问题$ (2.1) $的$ f(z) $可微且$ \left \{ z^{k} \right \} $为算法$ 3.1 $生成的迭代点列, 则$ \left \{ z^{k} \right \} $的聚点为基本可行性向量.

推论3.2  若问题$ (2.1) $的$ \bigtriangledown _{x} f(z ) $和$ \bigtriangledown _{y} f(z) $满足Lipschitz条件且$ \left \{ z^{k} \right \} $为算法$ 3.1 $生成的迭代点列, 则$ \left \{ z^{k} \right \} $的聚点为$ L $ -稳定点.

本文提出了双重稀疏约束优化问题的CW最优性条件, 探讨了CW最优性条件的性质, 并且基于所建立的基本可行性条件分析了CW最优解与$ L $ -稳定点之间的联系, 从而阐明了CW最优解比文献[17] 中$ L $ -稳定点更具广泛性. 基于CW最优性条件, 设计了求解双重稀疏约束优化问题的一种算法—贪婪单纯形算法, 并且探讨了算法的可行性与收敛性. 然而, 仍有大量工作值得今后继续研究: 能否在算法中找到一种索引选择策略, 使得不用对所有的结果都进行计算; 通过理论分析可以得到算法的收敛性与可行性, 但是实际运算还需要数值实验做支撑; 在目标函数满足梯度的前提下, 是否可以利用基本可行性条件设计算法, 并证明算法的收敛性; 利用其他投影和梯度的知识定义最优性条件, 根据最优性条件设计算法, 这些均有待进一步研究.