由于社会的发展和生产实践的需求, 最优化问题在金融、医学、药学以及手工农业等领域受到越来越多的重视, 分裂可行问题就是其中之一. 1994年, Censor和Elfving依据医学中有关放射治疗的实践经验和理论提出了分裂可行问题^[1], 问题形式如下

$\begin{eqnarray} \mbox{求} x\in C {\rm s.t.} Ax\in Q,\end{eqnarray}$

(1.1)

其中$C,Q$分别为$R^{N}$和$R^{M}$中的非空闭凸集, A为一个$ M\times N$的实矩阵.

随后, 分裂可行问题的拓展形式被学者们相继提出.本文主要研究的是带1 -范数约束的分裂可行问题的解, 问题形式如下

$\begin{eqnarray} \mbox{求} x\in C,Ax\in Q {\rm s.t.} \|x\|_{1}\leq s,\end{eqnarray}$

(1.2)

其中$\|.\|_{1}$代表 1 -范数, $s>0$为一个给定的常数.

目前, 大多数关于求解分裂可行问题及其拓展问题的算法, 要么牵涉到往闭凸集上的投影, 而这一投影在实际操作中难以实现; 要么在求解合适的步长过程中需要估算相关矩阵的最大特征值、Lipschitz系数或进行线搜索, 而这些操作往往需要大量的计算.关于求解分裂可行问题的1 -范数解问题已有学者在研究^{[14, 15]}.在文献[14]中, 作者将分裂可行问题的1 -范数解问题转化为变分不等式问题进行求解, 但在其给出的算法中需要估算矩阵的最大特征值.

在文献[2]中, 对于多集分裂可行问题

$\begin{eqnarray}\begin{array}{ll} \ \ x\in \bigcap\limits_{i=1}^{t}C_{i} {\rm s.t.} Ax\in\bigcap\limits_{j=1}^{r}Q_{j},\end{array}\end{eqnarray}$

(1.3)

其中$C_{i} (i=1,2,\cdot\cdot\cdot, t)$和$Q_{j} (j=1,2,\cdot\cdot\cdot ,r)$分别为$R^{N}$和$R^{M}$中的非空闭凸集.

作者提出了一种序列投影算法

$ \begin{array}{ll} \ \ x^{k+1}=P_{C_{t}}P_{C_{t-1}}\cdot\cdot\cdot P_{1}(x^{k}+\omega_{k}r_{k}d_{k}),\end{array} $

其中$d^{k}_{j}=P_{Q_{j}}(Ax_{k})-Ax_{k},j=1,2,\cdot\cdot\cdot r,d_{k}=\sum\limits^{r}_{j=1}A^{T}d^{k}_{j},$ $r_{k}=\dfrac{\sum\limits^{r}_{j=1}\|d^{k}_{j}\|^{2}}{\|d_{k}\|^{2}},0<\underline{\omega}\leq\omega_{k}\leq\overline{\omega}<2,k=1,2,\cdot\cdot\cdot.$

显然, 序列投影算法有可以直接计算的步长, 从而避免了在求解步长时进行大量的计算.受到文献[2]的启发, 将问题(1.2) 转化为如下形式

$\begin{eqnarray} \mbox{求} x\in C\cap D {\rm s.t.} Ax\in Q,\end{eqnarray}$

(1.4)

其中$D=\{x|\|x\|_{1}\leq s\}$.

序列投影算法虽有可以直接计算的步长, 但却牵涉到往闭凸集上的投影.首先, 本文在序列投影的基础上, 提出交替投影算法求解了问题(1.4).其次, 考虑到在实际操作中往闭凸集上的投影是难以实现的, 文章后半部分构造包含$C,D,Q$的半空间, 利用到半空间上的投影来代替到闭凸集上的投影, 从而使投影得到了顺利实现.

定义1  ^{[3, 4]}设$\Omega\subset R^{N}$为非空闭凸集, 对任意的$x\in R^{N}$, 定义

$ \begin{array}{ll} \ \ P_{\Omega}(x)=\arg\min\{\|x-y\||y\in \Omega\}.\end{array} $

并称其为$x$到$\Omega$上的投影.显然, 若$x\in \Omega$, 则$x=P_{\Omega}(x)$.

注1  由投影的定义, 可以得出问题(1.2) 等价于如下带约束的最小化问题

$\begin{eqnarray*} &&\min \frac{1}{2}\|Ax-P_{Q}(Ax)\|^{2},\\ &&{\rm s.t.} x\in C\cap D.\end{eqnarray*}$

定义2  ^[3]给定正常凸函数$f:R^{N}\rightarrow (-\infty,+\infty],$对任意一点$x\in {\rm dom}f$, 若向量$\xi\in R^{N}$满足

$\begin{array}{ll} \ \ f(y)-f(x)\geq \langle\xi,y-x\rangle,y\in R^{N},\end{array} $

(2.1)

则称$\xi$为凸函数$f$在点$x$处的次梯度.将满足式(2.1) 的向量$\xi$的全体构成的集合记为$\partial f(x)$, 并称之为$f$在$x$处的次微分.

注2  ${\rm dom}f$表示$f$的有效域, 即${\rm dom}f=\{x\in R^{N}|f(x)<+\infty\}$.若$f$在$x$处可微, 则满足(2.1) 式的$\xi$存在且唯一, 并且易知该向量即梯度$\nabla f(x)$.

由次梯度的定义, 简单计算可得$f(x)=\|x\|_{1}$在$x\in R^{N}$的次梯度$t$, 其分量为

$t_{j}=\left\{ \begin{array}{ll} 1,& x_{j}>0 ; \\ [-1, 1], & x_{j}=0;\\ -1,& x_{j}<0 . \end{array} \right.$

引理2.1  ^[9]设$\Omega$为$ R^{N}$中的非空闭凸集, 则对于投影算子$P_{\Omega}(.)$, 下述结论成立.

(a) $\langle P_{\Omega}(x)-x,z-P_{\Omega}(x)\rangle\geq 0,\forall x\in R^{N},z\in\Omega;$

(b) $\|P_{\Omega}(x)-P_{\Omega}(y)\|\leq\|x-y\|,\forall x,y\in R^{N};$

(c) $\|P_{\Omega}(x)-z\|^{2}\leq\|x-z\|^{2}-\|P_{\Omega}(x)-x\|^{2},\forall x\in R^{N},z\in\Omega;$

(d) $\|P_{\Omega}(x)-P_{\Omega}(y)\|^{2}\leq\|x-y\|^{2}-\|P_{\Omega}(x)-x+y-P_{\Omega}(y)\|^{2},\forall x,y\in R^{N}.$

引理2.2  ^[3]假设$f:R^{N}\rightarrow R$为凸函数, 则$f$在$R^{N}$上处处次可微且次微分在$R^{N}$的任意有界子集上一致有界.

引理2.3  ^[4]设$a\in R^{N},b\in R,$则$u\in R^{N}$到半空间$\{x\in R^{N}|a^{T}x\geq b\}$上的投影为

$\begin{array}{ll} \ \ P(u)=u+\dfrac{\max\{0,b-a^{T}u\}}{\|a\|^{2}}a.\end{array} $

引理2.4  ^[16]设$f:R^{N}\rightarrow(-\infty,+\infty]$为闭正常凸函数.给定满足$x^{k}\rightarrow x$的点列${\{x^{k}\}}\subseteq R^{N}$, 若$\xi^{k}\in\partial f(x^{k})$且$\xi^{k}\rightarrow\xi$, 则有$\xi\in\partial f(x)$.

此部分给出问题(1.4) 的求解算法.

3.1交替投影算法 

本文采用可以直接计算的步长, 避免了在求合适步长时, 进行大量的计算.在该算法中, 假设到闭凸集上的投影是可以直接计算的, 且问题(1.4) 的解集非空.

算法3.1 

步骤1 任取$x^{0}\in R^{N}$, 选取$0\leq\underline{\omega}\leq\omega_{k}\leq\bar{\omega}<2,k=0,1,2,\cdots;$

步骤2 令$\overline {{d_k}} = {P_Q}\left( {A{x_k}} \right) - A{x_k},{d_k} = {A^T}\overline {{d_k}} ,{r_k} = \dfrac{{{{\left\| {\overline {{d_k}} } \right\|}^2}}}{{{{\left\| {{d_k}} \right\|}^2}}};$

步骤3 计算$x^{k+1}=P_{D}P_{C}(x^{k}+\omega_{k}r_{k}d_{k}).$

引理3.1 设$x^{*}$为问题(1.4) 的任意解, $\{x^{k}\}$为算法3.1产生的点列, 则数列$\{\|x^{k}-x^{*}\|\}$收敛.

定理3.1 设$\{x^{k}\}$为算法3.1产生的点列, 则$\{x^{k}\}$收敛到问题(1.4) 的一个解.

注3  算法3.1可以看成^[2]中序列投影算法的特例, 引理3.1、定理3.1的证明过程可分别参看文献[2]中引理2.2、定理2.1.

3.2松弛交替投影算法 

由于算法3.1牵涉到往闭凸集上的投影, 所以针对这一不足对算法3.1进行改进.这里, 寻找包含集合$C,D,Q$的半空间, 利用到半空间上的投影来代替到闭凸集上的投影, 从而使投影简单可行.

在该部分, 将集合$D=\{{x\in R^{N}|\|x\|_{1}\leq s}\}$记为$D=\{{x\in R^{N}|f(x)\leq 0}\}$, 其中$f(x)=\|x\|_{1}-s$.

假设$C,Q$满足如下条件:

(H1) $C = \{ x \in {R^N}|c(x) \le 0\} $, 其中$c:{R^N} \to R$是凸函数(不需要可微的)且$C$是非空的. $Q = \{ y \in {R^M}|q(y) \le 0\},$其中$q:{R^M} \to R$是凸函数(不需要可微的)且$Q$是非空的.

(H2) 对于任意的$x \in {R^N}$, 至少有一个次梯度$\varsigma \in \partial c\left( x \right)$是可以计算的, 其中$\partial c(x) = \{ \varsigma \in {R^N}|c(z) \ge c(x) + \left\langle {\varsigma ,z - x} \right\rangle ,\forall z \in {R^N}\}.$

对于任意的$y\in {R^M}$, 至少有一个次梯度$\eta \in \partial q\left( y \right)$是可以计算的, 其中$\partial q(y) = \{ \eta \in {R^M}|q(u) \ge q(y) + \left\langle {\eta ,u - y} \right\rangle ,\forall u \in {R^M}\}.$并且构造包含$C,D,Q$的半空间$C_{k},D_{k},Q_{k}$如下

$\begin{eqnarray*} &&{C_k} = \{ x \in {R^N}|c\left( {{x^k}} \right) + \left\langle {{\varsigma ^k}} \right.,x - \left. {{x^k}} \right\rangle \le 0\},\mbox{其中} {\varsigma ^k} \in \partial c\left({{x^k}} \right).\\ &&{D_k} = \{ x \in {R^N}|f\left( {{x^k}} \right) + \left\langle {{\phi ^k}} \right.,x - \left. {{x^k}} \right\rangle \le 0\},\mbox{其中} {\phi ^k} \in \partial f\left( {{x^k}} \right).\\ &&{Q_k} = \{ y \in {R^M}|q\left( {A{x^k}} \right) + \left\langle {{\eta ^k}} \right.,y - A\left. {{x^k}} \right\rangle \le 0\},\mbox{其中} {\eta ^k} \in \partial q\left( {A{x^k}} \right).\end{eqnarray*}$

注4  由次梯度的定义, 容易得出$\forall k\in N$, 有$C\subset C_{k},D\subset D_{k},Q\subset Q_{k}.$

算法3.2 

步骤1 任取${x^0} \in {R^N}$, 选取$0 < \underline w \le {w_k} \le \overline w < 2,k = 0,1,2,\cdots$;

步骤2 令$\overline {{d_k}} = {P_{{Q_k}}}\left( {A{x_k}} \right) - A{x_k},{d_k} = {A^T}\overline {{d_k}} $, ${r_k} = \dfrac{{{{\left\| {\overline {{d_k}} } \right\|}^2}}}{{{{\left\| {{d_k}} \right\|}^2}}}$;

步骤3 计算${x^{k + 1}} = {P_{{D_k}}}{P_{{C_k}}}\left( {{x^k} + {w_k}r{}_k{d_k}} \right)$.

其中$C_{k},D_{k},Q_{k}$如上文所述.

注5 在实际计算中,

$\begin{eqnarray*} &&\overline {{d_k}} = {P_{{Q_k}}}\left( {A{x_k}} \right) - A{x_k}=\dfrac{\max\{0,q(Ax^{k})\}}{\|\eta^{k}\|^{2}}(-\eta^{k}),\\ &&{r_k} = \dfrac{{{{\left\| {\overline {{d_k}} } \right\|}^2}}}{{{{\left\| {{d_k}} \right\|}^2}}} =\dfrac{\|P_{Q_{k}}(Ax_{k})-Ax_{k}\|^{2}}{\|A^{T}(P_{Q_{k}}(Ax_{k})-Ax_{k})\|^{2}}=\dfrac{\|\frac{\max\{0,q(Ax^{k})\}}{\|\eta^{k}\|^{2}}\eta^{k}\|^{2}}{\|A^{T}(\frac{\max\{0,q(Ax^{k})\}}{\|\eta^{k}\|^{2}}\eta^{k})\|^{2}},\\ &&{x^{k + 1}} = {P_{{D_k}}}{P_{{C_k}}}\left( {{x^k} + {w_k}r{}_k{d_k}} \right)=P_{D_{k}}(x^{k}+\omega_{k}r_{k}d_{k}+\\ &&\dfrac{\max\{0,c(x^{k})+(\varsigma^{k})^{T}(\omega_{k}r_{k}d_{k})\}}{\|\varsigma^{k}\|^{2}}(-\varsigma^{k})).\end{eqnarray*}$

令

$y=x^{k}+\omega_{k}r_{k}d_{k}+ \dfrac{\max\{0,c(x^{k})+(\varsigma^{k})^{T}(\omega_{k}r_{k}d_{k})\}}{\|\varsigma^{k}\|^{2}}(-\varsigma^{k}),$

则

${x^{k + 1}} = {P_{{D_k}}}{P_{{C_k}}}\left( {{x^k} + {w_k}r{}_k{d_k}} \right)=P_{D_{k}}(y)=y+\dfrac{\max\{0,f(x^{k})-(\phi^{k})^{T}x^{k}+(\phi^{k})^{T}y\}}{\|\phi^{k}\|^{2}}(-\phi^{k}).$

对任意的$\tilde{x}\in R^{N}$, 记

$\begin{eqnarray}\begin{array}{ll} \ \ C\left( {\tilde x} \right) = \{ x \in {R^N}|c\left( {\tilde x} \right) + \left\langle {\tilde \varsigma } \right.,x - \left. {\tilde x} \right\rangle \le 0\},\end{array}\end{eqnarray}$

(3.1)

其中$\tilde \varsigma \in \partial c\left( {\tilde x} \right)$.

注6 由(3.1) 式及$C_{k}$的定义, 显然$C_{k}=C(x^{k})$.在式(3.1) 中, 可以取满足如下条件的$\tilde{x},\tilde{\varsigma}:$ $\mathop {\lim }\limits_{k \to \infty } {x^k} = \tilde x,\mathop {\lim }\limits_{k \to \infty } {\varsigma ^k} = \tilde \varsigma $.由引理2.4知$\tilde{\varsigma}\in \partial c(\tilde{x})$.

引理3.2 若点列$\left\{ {{x^k}} \right\}$收敛到$\tilde x$, $\left\{ {{y^k}} \right\}$收敛到$\tilde y$, 则$\mathop {\lim }\limits_{k \to \infty } {P_{{C_k}}}\left( {{y^k}} \right) = {P_{C\left( {\tilde x} \right)}}\left( {\tilde y} \right)$, 其中$C\left( {\tilde x} \right)$中$\tilde{\varsigma}$满足$\mathop {\lim }\limits_{k \to \infty } {\varsigma ^k} = \tilde \varsigma $.

证 由引理2.3得

$\begin{eqnarray} &&{P_{{C_k}}}\left( {{y^k}} \right) = {y^k} + \dfrac{{\max \left\{ {0,{{\left( {{\varsigma ^k}} \right)}^T}{x^k} - c\left( {{x^k}} \right) - {{\left( {{\varsigma ^k}} \right)}^T}{y^k}} \right\}}}{{{{\left\| {{\varsigma ^k}} \right\|}^2}}}{\varsigma ^k},\\ \end{eqnarray}$

(3.2)

$\begin{eqnarray} &&{P_{C\left( {\tilde x} \right)}}\left( {\tilde y} \right) = \tilde y + \dfrac{{\max \left\{ {0,{{\left( {\tilde \varsigma } \right)}^T}\tilde x - c\left( {\tilde x} \right) - {{\left( {\tilde \varsigma } \right)}^T}\tilde y} \right\}}}{{{{\left\| {\tilde \varsigma } \right\|}^2}}}\tilde \varsigma. \end{eqnarray}$

(3.3)

因为点列$\left\{ {{x^k}} \right\}$收敛到$\tilde x$, $\left\{ {{y^k}} \right\}$收敛到$\tilde y$及$\mathop {\lim }\limits_{k \to \infty } {\varsigma ^k} = \tilde \varsigma $, 所以

$ \begin{array}{ll} \ \ \begin{array}{l} \mathop {\lim }\limits_{k \to \infty } {P_{{C_k}}}\left( {{y^k}} \right) = \mathop {\lim }\limits_{k \to \infty } {y^k} + \mathop {\lim }\limits_{k \to \infty } \dfrac{{\max \left\{ {0,{{\left( {{\varsigma ^k}} \right)}^T}{x^k} - c\left( {{x^k}} \right) - {{\left( {{\varsigma ^k}} \right)}^T}{y^k}} \right\}}}{{{{\left\| {{\varsigma ^k}} \right\|}^2}}}{\varsigma ^k}\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} = \tilde y + \dfrac{{\max \left\{ {0,{{\left( {\tilde \varsigma } \right)}^T}\tilde x - c\left( {\tilde x} \right) - {{\left( {\tilde\varsigma } \right)}^T}\tilde y} \right\}}}{{{{\left\| {\tilde \varsigma } \right\|}^2}}}\tilde \varsigma \\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} = {P_{C\left( {\tilde x} \right)}}\left( {\tilde y} \right). \end{array}\end{array} $

证毕.

引理3.3 设${x^*}$为问题(1.4) 的任意解, $\left\{ {{x^k}} \right\}$为算法3.2产生的点列, 则数列$\{ \left\| {{x^k} - {x^*}} \right\|\} $收敛.

证 因为${x^*}$为问题(1.4) 的任意解, 所以${x^*} \in C \cap D$, $A{x^*} \in Q$, 由引理2.1(a)得

$ \begin{array}{ll} \ \ \begin{array}{l} \left\langle {{x^*}} \right. - {x^k},\left. {{d_k}} \right\rangle = \left\langle {{x^*} - {x^k},\left. {{A^T}\overline {{d_k}} } \right\rangle } \right.\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} = \left\langle {A{x^*} - A{x^k},\left. {\overline {{d_k}} } \right\rangle } \right.\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} = \left\langle A \right.{x^*} + {P_Q}\left( {A{x^k}} \right) - {P_Q}\left( {A{x^k}} \right) - A{x^k},\left. {\overline {{d_k}} } \right\rangle \\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} = {\left\| {\overline {{d_k}} } \right\|^2} + \left\langle {A{x^*}} \right. - {P_Q}\left( {A{x^k}} \right),{P_Q}\left( {A{x^k}} \right)\left. { - A{x^k}} \right\rangle \\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} \ge {\left\| {\overline {{d_k}} } \right\|^2.} \end{array}\end{array} $

又因为${x^*} \in C \subset {C_k},{x^*} \in D \subset {D_k},$所以

$ \begin{array}{ll} \ \ \begin{array}{l} {\left\| {{x^{k + 1}} - {x^*}} \right\|^2} = {\left\| {{P_{{D_k}}}{P_{{C_k}}}\left( {{x^k} + {w_k}{r_k}{d_k}} \right) - {x^*}} \right\|^2}\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} \le {\left\| {{P_{{C_k}}}\left( {{x^k} + {w_k}{r_k}{d_k}} \right) - {x^*}} \right\|^2}\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} \le {\left\| {{x^k} + {w_k}{r_k}{d_k} - {x^*}} \right\|^2}\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} = {\left\| {{x^k} - {x^*}} \right\|^2} - 2{w_k}{r_k}\left\langle {{x^*}} \right. - {x^k},\left. {{d_k}} \right\rangle + {w_k}^2{r_k}^2{\left\| {{d_k}} \right\|^2}\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} \le {\left\| {{x^k} - {x^*}} \right\|^2} - 2{w_k}{r_k}{\left\| {\overline {{d_k}} } \right\|^2} + {w_k}^2{r_k}^2{\left\| {{d_k}} \right\|^2.} \end{array}\end{array} $

(3.4)

由于$0 < \underline w \le {w_k} \le \overline w < 2,k = 0,1,2,\cdots,$故

$ \begin{array}{ll} \ \ {\left\| {{x^{k + 1}} - {x^*}} \right\|^2} \le {\left\| {{x^k} - {x^*}} \right\|^2} - \underline w {r_k}^2{\left\| {{d_k}} \right\|^2}(2 - \overline w ).\end{array}$

(3.5)

从而数列$\{ \left\| {{x^k} - {x^*}} \right\|\} $收敛.证毕.

注7 由(3.4) 式的最后一步可以得出, 当$r_{k}=\dfrac{\|\overline{d_{k}}\|^{2}}{\|d_{k}\|^{2}}$时, $\|x^{k}-x^{*}\|$取得最小值, 也即${x^{k}}$最接近$x^{*}.$

定理3.2 设$\left\{ {{x^k}} \right\}$为算法3.2产生的点列, 若问题(1.4) 的解集非空, 则$\left\{ {{x^k}} \right\}$收敛到问题(1.4) 的一个解.

证 设${x^*}$为问题(1.4) 的任意解, 由引理3.2知数列$\{ \left\| {{x^k} - {x^*}} \right\|\} $收敛, 同时序列$\{ {x^k}\} ,\{ {d_k}\} $有界.更进一步, 由(3.5) 式得$\mathop {\lim }\limits_{k \to \infty } {r_k}^2{\left\| {{d_k}} \right\|^2} = 0$.又因为$\{ {d_k}\} $有界, 所以$\mathop {\lim }\limits_{k \to \infty } {r_k}^2{\left\| {{d_k}} \right\|^4} = 0$, 即

$\mathop {\lim }\limits_{k \to \infty } {\left\| {\overline {{d_k}} } \right\|^2} = 0.$

也就是

$ \begin{array}{ll} \ \ \mathop {\lim }\limits_{k \to \infty } \|{P_{{Q_k}}}\left( {A{x^k}} \right) - A{x^k}\|^{2} = 0.\end{array}$

(3.6)

设$\overline x $是$\left\{ {{x^k}} \right\}$的任意聚点, 则一定存在$\left\{ {{x^k}} \right\}$的子列$\{ {x^{{k_l}}}\},$使得$\mathop {\lim }\limits_{{k_l} \to \infty } {x^{{k_l}}} = \overline x $.下证$\overline x $为问题(1.4) 的一个解.

首先证明$A\overline x \in Q$.由(3.6) 式得$\mathop {\lim }\limits_{{k_l} \to \infty }\|{P_{{Q_{{k_l}}}}}\left( {A{x^{{k_l}}}} \right) - A{x^{{k_l}}}\|^{2} = 0.$显然$P_{Q_{k_{l}}}(Ax^{k_{l}})\in Q_{k_{l}}.$由$Q_{k_{l}}$的定义得

$ \begin{array}{ll} \ \ q(Ax^{k_{l}})+\langle\eta^{k_{l}},P_{Q_{k_{l}}}(Ax^{k_{l}})-Ax^{k_{l}}\rangle\leq 0.\end{array}$

(3.7)

由引理2.2可知$\{\eta^{k_{l}}\}$有界.对(3.7) 式取极限得$q(A\overline{x})\leq 0.$即$A\overline x \in Q$.

接下来证明$\overline x \in C \cap D$.

由引理2.1(b), (c)可得

$ \begin{array}{ll} \ \ \begin{array}{l} {\left\| {{x^{k + 1}} - {x^*}} \right\|^2} = {\left\| {{P_{{D_k}}}{P_{{C_k}}}({x^k} + {w_k}{r_k}{d_k}) - {x^*}} \right\|^2}\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} \le {\left\| {{P_{{C_k}}}\left( {{x^k} + {w_k}{r_k}{d_k}} \right) - {x^*}} \right\|^2} - {\left\| {{x^{k + 1}} - {P_{{C_k}}}\left( {{x^k} + {w_k}{r_k}{d_k}} \right)} \right\|^2}\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} \le {\left\| {{x^k} + {w_k}{r_k}{d_k} - {x^*}} \right\|^2} - {\left\| {{x^{k + 1}} - {P_{{C_k}}}\left( {{x^k} + {w_k}{r_k}{d_k}} \right)} \right\|^2}. \end{array}\end{array}$

(3.8)

令$\mathop {\lim }\limits_{k \to \infty } {\left\| {{x^k} - {x^*}} \right\|^2} = a\left( {a \ge 0} \right)$, 结合$\mathop {\lim }\limits_{k \to \infty } {r_k}^2{\left\| {{d_k}} \right\|^2} = 0$, 对(3.8) 式取极限得

$ \begin{array}{ll} \ \ \mathop {\lim }\limits_{k \to \infty } {\left\| {{x^{k + 1}} - {P_{{C_k}}}\left( {{x^k} + {w_k}{r_k}{d_k}} \right)} \right\|^2} = 0,\end{array} $

从而

$ \begin{array}{ll} \ \ \mathop {\lim }\limits_{{k_l} \to \infty } {\left\| {{x^{{k_l} + 1}} - {P_{{C_{{k_l}}}}}({x^{{k_l}}} + {w_{{k_l}}}{r_{{k_l}}}{d_{{k_l}}})} \right\|^2} = 0.\end{array}$

(3.9)

下证${x^{{k_l} + 1}} \to \overline x \left( {{k_l} \to \infty } \right)$.

由于${\{x^k\}}$有界, 故$\left\{ {{x^{{k_l} + 1}}} \right\}$有界.设$\overline {\overline x } $为$\left\{ {{x^{{k_l} + 1}}} \right\}$的任意聚点, 易知$\overline {\overline x } $也为$\left\{ {{x^k}} \right\}$的任意聚点, 则存在$\left\{ {{x^{{k_l} + 1}}} \right\}$的子列$\left\{ {{x^{{k_{{l_i}}} + 1}}} \right\}$, 使得$\mathop {\lim }\limits_{{k_{{l_i}}} \to \infty } {x^{{k_{l{}_i}} + 1}} = \overline {\overline x } $, 且$\mathop {\lim }\limits_{{k_{{l_i}}} \to \infty } {x^{{k_{{l_i}}}}} = \overline x $.

由(3.9) 式得

$ \begin{array}{ll} \ \ \mathop {\lim }\limits_{{k_{{l_i}}} \to \infty } {\left\| {{x^{{k_{{l_i}}} + 1}} - {P_{{C_{{k_{{l_i}}}}}}}({x^{{k_{{l_i}}}}} + {w_{{k_{{l_i}}}}}{r_{{k_{{l_i}}}}}{d_{{k_{{l_i}}}}})} \right\|^2} = 0.\end{array}$

(3.10)

由引理3.2, 对(3.10) 式取极限得

$ \begin{array}{ll} \bar{\bar{x}}=P_{C(\bar{x})}(\bar{x}),\end{array} $

其中$C\left( {\bar x} \right) = \{ x \in {R^N}|c\left( {\bar x} \right) + \left\langle {\bar \varsigma } \right.,x - \left. {\bar x} \right\rangle \le 0\} ,\bar \varsigma \in \partial c\left( {\bar x} \right)$, 且$\overline{\varsigma}$满足$\mathop {\lim }\limits_{{k_{{l_i}}} \to \infty }\varsigma^{k_{l_{i}}} = \bar \varsigma. $

因为${x^*} \in {C_{{k_l}_{i}}} = \{ x \in {R^N}|c\left( {{x^{{k_l}_{i}}}} \right) + \left\langle {{\varsigma ^{{k_l}_{i}}}} \right.,x - \left. {{x^{{k_l}_{i}}}} \right\rangle \le 0\} ,{\varsigma ^{{k_l}_{i}}} \in \partial c\left( {{x^{{k_l}_{i}}}} \right)$, 所以

$ \begin{array}{ll} \ \ c\left( {{x^{{k_l}_{i}}}} \right) + \left\langle {{\varsigma ^{{k_l}_{i}}}} \right.,{x^*} - \left. {{x^{{k_l}_{i}}}} \right\rangle \le 0.\end{array}$

(3.12)

对(3.12) 式取极限得$c\left( {\bar x} \right) + \left\langle {\bar \varsigma } \right.,{x^*} - \left. {\bar x} \right\rangle \le 0$, 从而${x^*} \in C\left( {\bar x} \right).$由引理2.1(c), 结合(3.11) 式, 得

$ \begin{array}{ll} \ \ {\left\| {\overline{\overline x} - {x^*}} \right\|^2} \le {\left\| {\overline x - {x^*}} \right\|^2} - {\left\| {\overline{\overline x} - \overline x } \right\|^2}.\end{array}$

(3.13)

又因为${\left\| {\overline{\overline x} - {x^*}} \right\|^2} = {\left\| {\overline x - {x^*}} \right\|^2},$所以$\overline{\overline x} = \overline x $.从而有界子列$\left\{ {{x^{{k_l} + 1}}} \right\}$有唯一聚点$\overline x $.

由(3.11) 式知$\overline x = \overline{\overline x} = {P_{C\left( {\bar x} \right)}}\left( {\overline x } \right)$, 从而$\overline x \in C\left( {\bar x} \right)$.由$C\left( {\bar x} \right)$的定义得

$ \begin{array}{ll} \ \ c\left( {\bar x} \right) + \left\langle {\bar \varsigma } \right.,\bar x - \left. {\bar x} \right\rangle \le 0.\end{array} $

从而$c\left( {\overline x } \right) \le 0$, 即$\overline x \in C$.由于${D_k}$为非空闭凸集, 且$\{ {x^k}\} \subset {D^k}$, 故$\overline x \in {D_k}$, 再由${D_k}$的构造得

$ \begin{array}{ll} \ \ f\left( {{x^{{k_l}}}} \right) + \left\langle {{\phi ^{{k_l}}}} \right.,\bar x - \left. {{x^{{k_l}}}} \right\rangle \le 0.\end{array}$

(3.14)

由引理2.2知$\{ {\phi ^{{k_l}}}\} $有界, 对(3.14) 式取极限得$f\left( {\overline x } \right) \le 0$, 即$\overline x \in D$.

综上所述, 可以得到$\overline x $是问题(1.4) 的一个解.所以, 可以用$\overline x $来代替上述证明过程中的${x^*}$.又$\{ \left\| {{x^k} - \overline x } \right\|\} $收敛, 而其子列$\{ \left\| {{x^{{k_l}}} - \overline x } \right\|\} $收敛到零, 故$\left\{ {{x^k}} \right\}$收敛到$\overline x $.

证毕.

为了验证本文所给算法3.2的可行性, 给出如下几个例子.下面的例1-6取$s=1.2,s=3$两种情况来验证.首先给出的例1-4, 集合$C$与$Q$都是由可微凸函数的水平集来定义的; 其次给出的例5-6, 集合$C$与$Q$为不可微凸函数的水平集来定义的.最后给出的例7选取高维的水平集和随机的矩阵.在实际计算中选取参数$\omega_{k}=1$.

例1 设$C = \left\{ {x \in {R^3}|x_1^2 - {x_2} \le 0} \right\}$, $Q = \left\{ {x \in {R^3}|x_1^2 + x_2^2 + x_3^2 \le 0} \right\}$, $A = I$.

求$x\in C,Ax\in Q {\rm s.t.} {\left\| x \right\|_1} \le s$.

例2 设$C = \left\{ {x \in {R^3}|x_1^2 + x_2^2 - 1 \le 0} \right\},Q = \left\{ {x \in {R^3}|x_2^2 + x_3^2 - 1 \le 0} \right\},$ $A = \left[{\begin{array}{*{20}{c}} 2&1&0\\ 0&1&0\\ 0&0&2 \end{array}} \right].$

求$x\in C,Ax\in Q {\rm s.t.} {\left\| x \right\|_1} \le s$.

例3 设$C = \left\{ {x \in {R^3}|x_2^2 + x_3^2 - 4 \le 0} \right\},Q = \left\{ {x \in {R^3}|{x_3} - x_1^2 - 1 \le 0} \right\},A = I.$

求$x\in C,Ax\in Q {\rm s.t.} {\left\| x \right\|_1} \le s$.

例4 设$C = \left\{ {x \in {R^3}|{x_1} + x_2^2 + 2{x_3} \le 0} \right\},Q = \left\{ {x \in {R^3}|x_1^3 + {x_2} - {x_3} \le 0} \right\},$ $A = \left[{\begin{array}{*{20}{c}} 1&1&0\\ 0&1&1\\ 2&0&1 \end{array}} \right].$

求$x\in C,Ax\in Q {\rm s.t.} {\left\| x \right\|_1} \le s$.

例5 设$C = \left\{ {x \in {R^3}|x_1^2 - {|x_2|} \le 0} \right\}$, $Q = \left\{ {x \in {R^3}|x_1^2 + x_2^2 + x_3^2 \le 0} \right\}$, $A = I$.

求$x\in C,Ax\in Q {\rm s.t.} {\left\| x \right\|_1} \le s.$

例6 设$C = \left\{ {x \in {R^3}|{x_1} + x_2^2 + 2{|x_3|} \le 0} \right\},Q = \left\{ {x \in {R^3}|x_1^3 + {|x_2|} - {x_3} \le 0} \right\},$ $A = \left[{\begin{array}{*{20}{c}} 1&1&0\\ 0&1&1\\ 2&0&1 \end{array}} \right].$

求$x\in C,Ax\in Q {\rm s.t.} {\left\| x \right\|_1} \le s$.

例7 设$C = \{x \in R^{N}|\|x\|_{2}\leq0.25\},Q=\{y\in R^{M}|0.6\leq y_{j}\leq1,j=1,2\cdots,M\},A=(a_{ij})_{M\times N}$且$a_{ij}\in (0,50)$为随机选取的.

求$x\in C,Ax\in Q {\rm s.t.} {\left\| x \right\|_1} \le s$.

例1-6的数值结果如下表 1.1-6.2.在表 1.1-7.1中, $ x^{0}$代表初始点, Iter代表迭代步数, cpu代表计算时间(单位为秒), ${x^*}$代表近似解(以下这些结果都是运用MATLAB计算得到的).

例7的数值结果如下表, 由于选取的水平集为高维的、矩阵是随机的, 所以给出的计算结果中不显示近似解.

从例1-7的数值实验结果可以看出, 所有的计算时间都在0.1秒左右完成, 甚至大多数的计算时间都在0.1秒以内.由此可见松弛交替投影算法具有较强的可行性和实用性.

本文主要对带1 -范数约束的分裂可行问题进行了求解.首先, 在算法上取了可以直接计算的步长, 避免了在求合适的步长时进行大量的计算.其次, 又寻找包含闭凸集的半空间, 用往半空间上的投影来代替往闭凸集上的投影, 从而提出松弛交替投影算法, 使得投影容易计算.并给出几个实例来验证松弛交替投影算法的可行性.数值实验表明本文的算法具有较强的可行性和实用性.