在1994年, 分裂可行问题最早是由Censor和Elfving^[1]依据医学中调强放射治疗的实践经验和理论提出的.分裂可行问题的具体形式如下:找一个向量$ x $, 满足

$ x\in C, \; \; \; \; Ax\in Q, $

这里$ C $和$ Q $是非空闭凸集, $ C\subseteq R^{N}, Q\subseteq R^{M} $, $ A $是一个$ M\times N $的矩阵.

分裂可行问题不仅仅在信号处理、图像恢复上有重要的应用, 而且在系统识别、经济、军事领域也有重要的应用.因此, 从问题被提出至今, 许多学者对其进行了大量的分析和研究, 如Byrne^{[2, 3]}提出的CQ算法, Yang^[4]接着提出了一种松弛的CQ算法.后来, Qu和Xiu ^[5]利用类Aimijo搜索来获得步长, 对松弛CQ法进行了修正, 改进后的算法不需要求矩阵范数, 克服了往常算法计算矩阵特征值等缺点, 并且在此算法的基础之上进行了进一步的改进, 提出了修正松弛CQ算法.

近几年, 随着压缩传感技术在信号处理、图像恢复等方面的应用, 要求变量具有稀疏性.因此我们考虑稀疏分裂可行问题.

对于稀疏约束优化问题, 已经有了较多的研究.对于线性目标函数, 已经有了一些算法, 如Agarwal^[6]改进严格强凸性(RSC)条件并且引进了严格强光滑性(RSS)条件来保证一种一阶方法的收敛性.后来, 有些学者对RSC和RSS进行改进以保证唯一解的存在^[7-10]. Bahmani等在文献[11]中对于二阶连续可微目标函数提出了稳定严格Hessen (SRH)性质且对于非光滑的函数提出了稳定严格线性性质(SRL). Cands和Tao^[12]在压缩传感=^{[12, 13]}中提出了严格等距性条件(RIP)来保证线性目标函数优化问题具有唯一解.最近几年Beck和Eldar ^[14]提出了目标函数是非线性的优化问题, 并且给出了几种最优性条件以及一些相应的算法.在此基础上, Pan和Xiu^[15]提出了一种新的步长规则, 以加快计算.

稀疏分裂可行问题是分裂可行问题与稀疏限制优化问题的一个结合问题.虽然, 关于上面两个问题有较多的学者在研究, 但是对于稀疏分裂可行问题, 这方面的专门研究还没看到.

问题形式如下:找向量$ x $, 满足

$ \begin{align} x\in C, \; \; \; \; Ax\in Q \; \; \; \; \; {\rm s.t.}\; \; \|x\|_{0}\leq s, \end{align} $

(1.1)

其中$ C $和$ Q $是非空闭凸集, $ C\subseteq R^{N}, Q\subseteq R^{M} $, $ A $是一个$ M\times N $的实矩阵, $ \|x\|_{0} $是$ x $的$ l_{0} $范数, 即向量$ x $中非零元素的向量的全体.

本文将问题(1.1)转化为下述问题

$ \begin{align} \begin{array}{ll} \min \frac{1}{2}(\|Ax-P_{Q}(Ax)\|^{2}+\|x-P_{C}(x)\|^{2})\; \; \; \; \; {\rm s.t.}\; \; \|x\|_{0}\leq s.\end{array} \end{align} $

(1.2)

通过求解此问题得到(1.1)的一个解.

在本文中, $ C_{S} $表示所有最多$ s $个非零元素的向量全体.

定义 2.1 ^[14] 称集合$ C_{S} = \{x\in R^{n}:\|x\|_{0}\leq s\} $为稀疏集合, 这里$ s\in \{1, 2, \cdots, n\} $.

定义 2.2 ^[14] 支撑集:对于向量$ x, $记$ I_{1}(x)\equiv\{i\in\{1, \cdots, n\}:x_{i}\neq 0\} $为向量$ x $的支撑集.记$ I_{0}(x)\equiv\{i\in\{1, \cdots, n\}:x_{i} = 0\} $为向量$ x $的外支撑集.显然$ I_{0}(x) $和$ I_{1}(x) $满足如下关系: $ I_{1}(x)\cap I_{0}(x) = \varnothing, I_{1}(x)\cup I_{0}(x) = \{1, \cdots, n\} $.

定义 2.3 ^[14] 称由$ R^{N} $往稀疏集$ C_{S} $上的投影为支撑映射, 即

$ P_{C_{S}}(x): = {\rm arg}\min\limits_{y\in C_{S}}\|x-y\|. $

向量$ x $往稀疏集$ C_{S} $上的投影$ P_{C_{S}} $, 其分量包括向量$ x $的$ s $个绝对值最大的分量和$ N-s $个零.

对于一个向量$ x\in R^{n} $和$ i\in\{1, 2, \cdots, n\} $, $ M_{i}(x) $代表向量$ x $中第$ \; i $个绝对值最大的元素, 所以

$ M_{1}(x)\geq M_{2}(x)\geq\cdot\cdot\cdot\geq M_{n}(x), $

并且$ M_{1}(x) = \max\limits_{i = 1, \cdots, n}|x_{i}| $, $ M_{n}(x) = \min\limits_{i = 1, \cdots, n}|x_{i}|. $取$ x $的指标集$ I_{s} = \{j_{1}, j_{2}, \cdots, j_{s}\}\subseteq\{1, 2, \cdots, n\} $使得$ \min\limits_{i\in I_{s}(x)}|x_{i}|\geq \max\limits_{i\not\in I_{s}(x)}|x_{i}|, $有

$ P_{C_{s}}(x) = \{y\in R^{n}\mid y_{i} = x_{i}, i\in I_{s}(x);y_{i} = 0, i\not\in I_{s}(x)\}. $

因为$ C_{s} $是非凸的, 所以投影$ P_{C_{s}}(x) $可能不是唯一的.如果$ M_{s}(x) = 0 $或者$ M_{s}(x)>M_{s+1}(x) $, 那么$ P_{C_{s}}(x) $是唯一的.即下面这种情况

$ (P_{C_{s}}(x))_{i} = \begin{cases} x_{i}, \; \; |x_{i}|\geq M_{s}(x), \\ 0, \; \; |x_{i}|<M_{s}(x). \end{cases} $

如果多于一个$ x_{i} $使得$ |x_{i}| = M_{s}(x) $, 即下面这种情况

$ (P_{C_{s}}(x))_{i} = \begin{cases} x_{i}, \; \; &|x_{i}|>M_{s}(x), \\ x_{i} \; \; \mbox{或者}\; \; 0, &|x_{i}| = M_{s}(x), \\ 0, \; \; &|x_{i}|<M_{s}(x). \end{cases} $

如果多于一个$ x_{i} $使得$ |x_{i}| = M_{s}(x), $那么在取投影点时, 可以随意的选取其中一个$ |x_{i}| = M_{s}(x) $, 或者根据已经定好的规则去选取, 其他取零.

举个例子, 如$ x = \{5, 4, 3, 1, -3\} $, $ C_{S} = \{x\in R^{5}:\|x\|_{0}\leq 3\} $, 则$ P_{C_{s}}(x) = \{5, 4, 3, 0, 0\} $或者$ P_{C_{s}}(x) = \{5, 4, 0, 0, -3\}. $对于问题(1.2), 令

$ f(x) = \frac{1}{2}(\|Ax-P_{Q}(Ax)\|^{2}+\|x-P_{C}(x)\|^{2}). $

很显然$ f(x) $是连续可微函数, 且它的梯度为

$ \nabla f(x) = A^{T}(I-P_{Q})Ax+(I-P_{C})x. $

引理 2.1  目标函数$ f(x) $的梯度$ \nabla f(x) $是Lipschitz连续的.

证  对于任意的$ x, y\in R^{N} $, 有

$ \begin{eqnarray*} &&\|\nabla f(x)-\nabla f(y)\|\\ & = &\|A^{T}(I-P_{Q})Ax+(I-P_{C})x-A^{T}(I-P_{Q})Ay-(I-P_{C})y\|\\ &\leq&\|A^{T}(I-P_{Q})Ax-A^{T}(I-P_{Q})Ay\|+\|(I-P_{C})x-(I-P_{C})y\|\\ &\leq& \|A\|\|(I-P_{Q})Ax-(I-P_{Q})Ay\|+\|(I-P_{C})x-(I-P_{C})y\|\\ &\leq& \|A\|\|Ax-Ay\|+\|x-y\|\\ &\leq&\|A\|^{2}\|x-y\|+\|x-y\|\\ & = &(\|A\|^{2}+1)\|x-y\|. \end{eqnarray*} $

取$ L = (\|A\|^{2}+1) $, 则$ \|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|. $

在下文中, 所有的$ L $取$ \|A\|^{2}+1 $为Lipschitz常数.

定义 2.4 ^[14] 向量$ x^{\ast}\in C_{s} $是问题(1.2)一个$ BF $点.如果

1.当$ \|x^{\ast}\|_{0}<s, \bigtriangledown f(x^{\ast}) = 0 $;

2.当$ \|x^{\ast}\|_{0} = s, \bigtriangledown_{i}f(x^{\ast}) = 0 $, 对于所有的$ i\in I_{1}(x^{\ast}) $.

定理 2.1 ^[14] 假设$ x^{\ast} $是问题(1.2)的最优解, 那么$ x^{\ast} $是一个$ BF $点.

定义 2.5 ^[14] 一个向量$ x^{\ast}\in C_{s} $称为问题(1.2)的$ \alpha $ -稳定点, 如果它满足

$ \begin{align} x^{\ast}\in P_{C_{s}}(x^{\ast}-\alpha \nabla f(x^{\ast})). \end{align} $

(2.1)

引理 2.2 ^[14] 对于$ \frac{1}{\alpha}>0, $ $ x^{\ast} $是一个$ \alpha $ -稳定点当且仅当$ \|x^{\ast}\|_{0}\leq s, $且

$ \begin{align} |\nabla_{i}f(x^{\ast})| \begin{cases} \leq \frac{1}{\alpha}M_{s}(x^{\ast}), \; \; \; \; &\mbox{如果} \; \; i\in I_{0}(x^{\ast}), \\ = 0, \; \; \; \; \; \; \; \; &\mbox{如果}\; \; i\in I_{1}(x^{\ast}). \end{cases} \end{align} $

(2.2)

推论 2.1 ^[14] 假设$ x^{\ast} $是一个$ \alpha $ -稳定点对于一些$ \alpha>0. $那么$ x^{\ast} $是一个$ BF $点.

定理 2.2 ^[14] 假设$ x^{\ast} $是问题(1.2)的最优解, 那么

1. $ x^{\ast} \; $是一个$ \; \alpha $ -稳定点;

2.集合$ \; P_{C_{s}}(x^{\ast}-\alpha \nabla f(x^{\ast})) \; $是单点集.

引理 2.3 ^[16] 设$ f $是一个连续可微的函数, 并且其梯度函数是Lipschtz连续的, Lipschtz常数为$ L $, 则对$ L^{'}\geq L $, 有$ f(x)\leq h_{L{'}}(x, y) $, 其中

$ h_{L^{'}}(x, y)\equiv f(y)+\langle \nabla f(y), x-y\rangle +\frac{L^{'}}{2}\|x-y\|^{2}. $

引理 2.4 ^[14] 对于任意的$ L^{'}\geq L $, 则对任意的$ y\in C_{S}, x\in R^{N} $, 满足

$ y\in P_{C_{s}}\Big(x-\frac{1}{L^{'}}\nabla f(x)\Big), $

有$ f(x)-f(y)\geq \frac{L^{'}-L}{2} \|x-y\|^{2} $.

下面给出算法.

步骤 0 选取$ \; x^{0}\in R^{n} $, $ \epsilon>0, $ $ 0<\alpha_{0}<\frac{1}{L}, $ $ 0<\alpha_{\min}<\alpha_{0} $, $ 0<\lambda<\frac{1}{4L}, $令$ k\Leftarrow0 $.

步骤 1 计算$ x^{k+1}\in P_{C_{S}}(x^{k}-\alpha_{k}\nabla f(x^{k})) $, 这里$ \alpha_{k} $满足下面不等式

$ \|x^{k}(\alpha_{k})-x^{k}\|\leq\|x^{k}-x^{k-1}\|; \alpha_{\min}\leq \alpha_{k}\leq \alpha_{0}, $

其中$ x^{k}(\alpha)\in P_{C_{S}}(x^{k}-\alpha\nabla f(x^{k})) $.否则, 转步骤2.

步骤 2 计算$ x^{k+1}\in P_{C_{S}}(x^{k}-\alpha_{k}\nabla f(x^{k})), $其中$ \alpha_{k}\in[\frac{1-\sqrt{1-4\lambda L}}{2L}, \frac{1+\sqrt{1-4\lambda L}}{2L}] $.

步骤 3 若$ \|x^{k+1}-x^{k}\|\leq \epsilon, $则停止, 否则令$ k\Leftarrow k+1, $转步骤1.

引理 3.1  设$ \{x^{k}\}_{k\geq0} $为由算法产生的点列, 则

$ f(x^{k+1})\leq \begin{cases} f(x^{k+1})-\frac{1}{2}(\frac{1}{\alpha_{k}}-L)\|x^{k+1}-x^{k}\|^{2};\; \alpha_{k}\in(\alpha_{\min}, \alpha_{0}), \\ f(x^{k+1})-\frac{\lambda}{2}\frac{\|x^{k+1}-x^{k}\|^{2}}{\alpha^{2}_{k}};\; \alpha_{k}\in[\frac{1-\sqrt{1-4\lambda L}}{2L}, \frac{1+\sqrt{1+4\lambda L}}{2L}]. \end{cases} $

证  根据引理2.4下降性定理和算法可得到.

引理 3.2  设$ \{x^{k}\}_{k\geq0} $为由算法产生的点列, 则

1.当$ k\rightarrow\infty $时, $ \{f(x^{k})\} $收敛;

2. $ \|x^{k}-x^{k+1}\|\rightarrow 0 $;

3.对于每个$ k = 0, 1, 2, \cdots $, 如果$ x^{k}\neq x^{k+1} $, 则$ f(x^{k+1})<f(x^{k}) $.

证  1.若$ x^{k+1} $是由步骤1产生的, 根据引理2.4可以得出

$ \begin{align} f(x^{k+1})\leq f(x^{k})-\frac{1}{2}(\frac{1}{\alpha_{k}}-L)\|x^{k+1}-x^{k}\|^{2};\alpha_{k}\in[\alpha_{\min}, \alpha_{0}]. \end{align} $

(3.1)

若$ x^{k+1} $是由步骤2产生的, 根据算法, 可以得出

$ \begin{align} f(x^{k+1})\leq f(x^{k})-\frac{\lambda}{2}\frac{\|x^{k+1}-x^{k}\|^{2}}{(\alpha_{k})^{2}}. \end{align} $

(3.2)

所以$ f(x^{k}) $是单调非增的.又因为函数$ f(x) $是有下界的, 所以$ \{f(x^{k})\} $收敛.

2.若$ x^{k+1} $是由步骤1产生的, 则

$ f(x^{k})-f(x^{k+1})\geq \frac{1}{2}(\frac{1}{\alpha_{0}}-L)\|x^{k+1}-x^{k}\|^{2}. $

若$ x^{k+1} $是由步骤2产生的,

$ f(x^{k})-f(x^{k+1})\geq\frac{\lambda}{2}\frac{\|x^{k+1}-x^{k}\|^{2}}{(\alpha_{k})^{2}}. $

取$ c = \max\{\frac{1}{2}(\frac{1}{\alpha_{0}}-L), \frac{\lambda}{2}\frac{(2L)^{2}}{(1+\sqrt{1+4\lambda L})^{2}}\} $, 则有$ f(x^{k})-f(x^{k+1})\geq c\|x^{k+1}-x^{k}\|^{2}. $对不等式两边取极限有$ \lim\limits_{k\rightarrow\infty}c\|x^{k+1}-x^{k}\|^{2}\leq 0, $又因为$ \|x^{k+1}-x^{k}\|\geq0 $, 所以$ \lim\limits_{k\rightarrow\infty}\|x^{k+1}-x^{k}\| = 0. $综上所述, 可得当$ k\rightarrow\infty $时, $ \|x^{k+1}-x^{k}\|\rightarrow0. $

3.根据结论1可以直接得到.

定理 3.1  设$ \{x^{k}\}_{k\geq0} $为由算法产生的点列, 则$ \{x^{k}\}_{k\geq0} $的任一聚点都为$ \alpha $ -稳定点.

证  设$ x^{\ast} $为$ \{x^{k}\}_{k\geq0} $的任意聚点, 则存在子列$ \{x^{k_{n}}\}_{k_{n}\geq0} $收敛到$ x^{\ast} $.由引理3.1可以得出$ \{f(x^{k_{n}})\} $和$ \{f(x^{k_{n}+1})\} $收敛到同一极限$ \widehat{f} $.当$ n\rightarrow\infty $时, 有$ f(x^{k_{n}})-f(x^{k_{n}+1})\rightarrow0 $, 当$ n\rightarrow\infty $, 有$ x^{k_{n}+1}\rightarrow x^{\ast} $.又因为

$ x^{k_{n}+1} = P_{C_{S}}(x^{k_{n}}-\alpha_{k_{n}}\nabla f(x^{k_{n}})). $

取$ i\in I_{1}(x^{\ast}) $.因为$ x^{k_{n}} $和$ x^{k_{n}+1} $都收敛到$ x^{\ast} $, 所以存在$ N $, 对所有的$ n>N $, 有$ x_{i}^{k_{n}} , x_{i}^{k_{n}+1}\neq0. $从而对所有的$ n>N $, 有$ x_{i}^{k_{n}+1} = x_{i}^{k_{n}}-\alpha_{k_{n}}\nabla_{i}f(x^{k_{n}}). $因为$ \{\alpha_{k}\} $有界的, 不妨假设当$ n\rightarrow\infty $时, 有$ \alpha_{k_{n}}\rightarrow\alpha $.因此可得$ \nabla_{i}f(x^{\ast}) = 0 $.再取$ i\in I_{0}(x^{\ast}) $.如果存在无限个$ k_{n} $且$ x_{i}^{k_{n}+1}\neq0 $, 则有$ x_{i}^{k_{n}+1} = x_{i}^{k_{n}}-\alpha_{k_{n}}\nabla_{i}f(x^{k_{n}}). $取极限可得$ \nabla_{i}f(x^{\ast}) = 0 $.

另一方面, 如果存在$ M>0 $使得对所有的$ n>M $都有$ x_{i}^{k_{n}+1} = 0 $, 则

$ |x_{i}^{k_{n}}-\alpha_{k_{n}}\nabla_{i}f(x^{k_{n}})|\leq M_{s}(x^{k_{n}}-\alpha_{k_{n}}\nabla f(x^{k_{n}})) = M_{s}(x^{k_{n}+1}). $

再取$ n\rightarrow\infty $, 利用函数$ M_{s} $的连续性可得

$ |\nabla_{i}f(x^{\ast})|\leq\frac{1}{\alpha}M_{s}(x^{\ast}). $

所以$ x^{\ast} $是问题(1.2)的一个$ \alpha $ -稳定点.

定理 3.2  设$ \{x^{k}\}_{k\geq0} $为由算法产生的点列$ x^{\ast} $是它的一个聚点, 那么

1.如果$ \|x^{\ast}\|_{0}<s, $那么$ x^{\ast} $是问题(1.2)的全局最优解;

2.如果$ \|x^{\ast}\|_{0} = s, $那么$ x^{\ast} $是问题(1.2)的局部最优解.

证  1.如果$ \|x^{\ast}\|_{0}<s $并且$ x^{\ast} $是一个$ \alpha $ -稳定点, 通过定义$ 2.3 $和推论$ 2.1 $, 知$ \nabla f(x^{\ast}) = 0 $.又因为$ f(x) $是凸函数, 所以$ x^{\ast} $是问题(1.2)的最优解.

2.若$ \|x^{\ast}\|_{0} = s $, 取$ J = I_{0}(x^{\ast}) $且$ \widetilde{R} = \{x\in R^{n}, x_J = 0\} $.因为$ x^{\ast} $是一个$ \alpha $ -稳定点, 所以有

$ x^{\ast}\in {\rm arg}\min\limits_{x\in C_{s}}\|x-(x^{\ast}-\alpha \nabla f(x^{\ast}))\|^{2}, $

所以

$ x^{\ast} = {\rm arg}\min\limits_{x\in \widetilde{R}}\|x-(x^{\ast}-\alpha \nabla f(x^{\ast}))\|^{2}, $

根据凸规划的一阶最优性条件得$ \langle\nabla f(x^{\ast}), y-x^{\ast}\rangle\geq0, \forall y\in \widetilde{R} $.并且因为$ \widetilde{R} $是凸集, $ f $是凸函数, 所以有$ x^{\ast}\in {\rm arg}\min\{f(x):x\in \widetilde{R}\} $.对于所有的$ x\in \widetilde{\Theta}(x^{\ast};\varepsilon), $有$ f(x)\geq f(x^{\ast}), $这里$ \widetilde{\Theta}(x^{\ast};\varepsilon) = \{x\in \widetilde{R}:\|x-x^{\ast}\|<\varepsilon\} $, $ \varepsilon = \min\{|x_i^{\ast}|:i\in I_{1}(x^{\ast})\}. $根据$ \varepsilon $的定义和$ \|x^{\ast}\|_{0} = s $, 可以得到$ \widetilde{\Theta}(x^{\ast};\varepsilon) = \Theta(x^{\ast};\varepsilon), $这里$ \Theta(x^{\ast};\varepsilon) = \{x\in C_{s}:\|x-x^{\ast}\|<\varepsilon\}. $对于所有的$ x\in \Theta(x^{\ast};\varepsilon), $能得到$ f(x)\geq f(x^{\ast}) $.所以$ x^{\ast} $是问题(1.2)的局部最优解.

本章节给出一个数值例子来证明算法的可行性.所有的程序是在LENONVE ideapad, Windows 10 Inter(R) Core(TM)i5-6200U CPU @2.30GHz 2.40GHz and 4GB内存的电脑上运行.

例 设$ C = \{x\in R^{N}|\|x\|_{2}\leq0.25\}, Q = \{y\in R^{M}|-1\leq y_{i}\leq1\}, \; A = (a_{ij})_{M\times N} $.求$ x\in C, \; Ax\in Q\; \; {\rm s.t.}\; \|x\|_{0}\leq s\; . $

在表 1中, 取$ M = 1, N = 5, A = {\rm rand}(M, N), s = 3 $. $ x^{0} $表示初始点, iter表示迭代步数, CPU time表示运行时间, $ x^{\ast} $表示收敛点.

在表 2中, 取$ M = 150, N = 150, A = I, s = 50 $. $ x^{0} $表示初始点, iter表示迭代步数, CPU time表示运行时间.由于收敛点维数过高, 我们就不在表中给出收敛点.

从数值实验中可以看到所有的计算时间都在0.1秒内完成, 并且可以收敛到一个问题(1.2)的近似解.因此可以看出算法是可行的.

本文主要求解了带有稀疏约束的分裂可行问题.我们通过将稀疏分裂可行问题近似的转化为目标函数为凸函数的稀疏约束优化问题, 再设计了一种梯度投影算法来求解此问题, 并且证明了此算法的收敛性.最后给出了一些数值例子, 数值实验的结果表明本文的算法具有较强的可行性.