求解分裂可行性问题的松弛投影算法

Relaxation Projection Algorithm for Solving Split Feasibility Problem

摘要: 分裂可行性问题被广泛地应用于放射性治疗、图像重构和信号处理等领域，研究其迭代算法具有较大的理论意义和实际价值。本文在Hilbert空间中，提出一种求解分裂可行问题的松弛投影算法，其算法在CQ算法的基础上引入改造的Halpern迭代序列和线性算子。在文中用数值实验将所提算法与前人算法进行对比验证，数值实验结果表明了提出算法的有效性。

Abstract: Split feasibility problem is widely used in the fields of radiotherapy, image reconstruction and signal processing, thus the iterative algorithm has great theoretical significance and practical value in studying iterative algorithms. In this paper, a relaxation projection algorithm for solving split feasible problems is proposed in Hilbert space, and its algorithm introduces modified Halpern iterative sequences and linear operators on the basis of the CQ algorithm. In this paper, the proposed algorithm is compared with predecessor algorithm by numerical experiments, and the numerical experimental results show the effectiveness of the proposed algorithm.

1. 引言

分裂可行性问题(SFP)在图像重建、信号处理和放射治疗中起着重要作用 [1] [2] [3] [4]。设 $C,Q$ 分别是Hilbert空间 $H_1,H_2$ 上的非空闭凸子集， $A:H_1\to H_2$ 是一个有界线性算子。分裂可行问题(SFP)是指找到一点x，满足

$x\in C$, $Ax\in Q$.(1)

该问题由Censor和Elfving [5] 于1994年首次在有限维Hilbert空间中提出。为了解决SFP问题，很多学者提出各种各样的算法(参见文献 [6] [7] [8] [9])。其中部分学者使用投影的方法得到求解SFP的迭代算法，但这些迭代算法需要计算矩阵的逆，矩阵逆的计算需要花费大量时间并且不容易求解，进而会影响算法的迭代效率。为了克服这点，Byrne [10] 首先提出了CQ算法，迭代公式为

$x^{k+1}=P_C\left(x^k-\lambda A^{*}\left(I-P_Q\right)A{x}^k\right)$, (2)

其中步长 $\lambda \in \left(0,\frac{2}{{\Vert A\Vert }^2}\right)$。受CQ算法的影响，Wang和Xu [11] 通过引入系数 ${\alpha }_k$，提出了修正CQ算法

$x^{k+1}=P_C\left[\left(1-{\alpha }_k\right)\left(x^k-\lambda A^{*}\left(I-P_Q\right)A{x}^k\right)\right]$. (3)

并证明了(3)式强收敛于分裂可行性问题的最优解。Dang [6] 等人提出KM-CQ-Like算法

$x^{k+1}=\left(1-{\beta }_k\right)x^k+{\beta }_k{P}_C\left[\left(1-{\alpha }_k\right)\left(I-\gamma A^{*}\left(I-P_Q\right)A\right)x^k\right]$

其中 $\left\{{\alpha }_k\right\}$ 和 $\left\{{\beta }_k\right\}$ 在(0, 1)之间。并证明了算法的强收敛性。López等人 [12] 首先在CQ算法上引入新的选择步长的方法，步长 ${\lambda }_k=\frac{{\rho }_k{f}_k\left(x^k\right)}{{\Vert \nabla f_k\left(x^k\right)\Vert }^2}$，其中 ${\rho }_k\in \left(0,4\right)$，并证明了具有此步长的算法(2)式弱收敛到SFP的解。在此基础上他们又引入Halpern [13] 迭代思想，迭代公式为

$x^{k+1}={\alpha }_{k}u+\left(1-{\alpha }^k\right)P_C\left(x^k-{\lambda }_k\nabla f_k\left(x^k\right)\right)$,(4)

其中，u是C的不动点， ${\alpha }_k\subset \left[0,1\right)$， $\nabla f\left(x\right)=A^{*}\left(I-P_Q\right)Ax$， ${\lambda }_k=\frac{{\rho }_k{f}_k\left(x^k\right)}{{\Vert \nabla f_k\left(x^k\right)\Vert }^2}$，并证明了(4)式强收敛于

SFP的最优解。本文受前人文献的启发，提出一种求解分裂可行问题的松弛投影算法。此算法在CQ算法上引入改造的Halpern迭代序列和线性算子。

文章结构安排如下：第2节中，回顾一些必要的定义和基础知识；在第3节，提出松弛投影算法和相关引理；在第4节中，将提出的算法与前人算法进行对比，并对结果进行分析。最后，在第5节中，对论文进行简短总结。

2. 预备知识

设H是Hilbert空间， $\langle \cdot ,\cdot \rangle$ 表示内积， $\Vert \cdot \Vert$ 表示对应的范数，I表示Hilbert空间上的单位算子， $Fix\left(T\right):=\left\{x|x=Tx\right\}$ 表示算子T的不动点集合。 $\left\{x^k\right\}$ 是H中的一个序列， $x\in H$。

定义2.1 [14] 令 $F:H\to H$ 为非线性算子，称

1) F是非扩张算子，如果

$\Vert Fx-Fy\Vert \le \Vert x-y\Vert$, $\forall x,y\in H$ ;

2) F是固定非扩张算子，如果

${\Vert Fx-Fy\Vert }^2\le \langle x-y,Fx-Fy\rangle$, $\forall x,y\in H$ ;

3) F是 $\alpha$ -平均算子，如果

$T=\left(1-\alpha \right)I+\alpha R$,

其中 $\alpha \in \left(0,1\right)$，I是单位算子， $R:H\to H$ 是非扩张算子。

4) F是L-Lipschitz连续，其中 $L\ge 0$，如果 $\forall x,y\in H$

$\Vert Fx-Fy\Vert \le L\Vert x-y\Vert$,

如果， $0\le L<1$，F则为L-压缩映像。

定义2.2 [15] 设 $C\subseteq H$ 是非空闭凸集，对任意 $x\in H$，x到C上的投影定义为：

$P_C\left(x\right)=\arg \min \left\{\Vert y-x\Vert |y\in C\right\}$.

显然，若 $x\in C$，则 $x=P_C\left(x\right)$。投影 $P_C$ 具有下面重要的性质。

引理2.1 [15] 设 $C\subseteq H$，是非空闭凸集，则对任意 $x,y\in H$，有

1) $\langle x-P_C\left(x\right),z-P_C\left(x\right)\rangle \le 0$, $\forall z\in C$ ;

2) $\langle P_C\left(y\right)-P_C\left(x\right),y-x\rangle \ge {\Vert P_C\left(y\right)-P_C\left(x\right)\Vert }^2$ ;

3) ${\Vert P_C\left(x\right)-z\Vert }^2\le {\Vert x-z\Vert }^2-{\Vert P_C\left(x\right)-x\Vert }^2$, $\forall z\in C$ ;

4) ${\Vert P_C\left(x\right)-P_C\left(y\right)\Vert }^2\le {\Vert x-y\Vert }^2-{\Vert \left(1-P_C\right)x-\left(1-P_C\right)y\Vert }^2$ ;

5) ${\Vert P_C\left(x\right)-P_C\left(y\right)\Vert }^2\le \Vert x-y\Vert$.

引理2.2 [16] 设 $x,y\in H$， $t,s\in R$。其中R是实数集。则有

${\Vert x+y\Vert }^2\le {\Vert x\Vert }^2+2\langle y,x+y\rangle$ ;

${\Vert tx+sy\Vert }^2=t\left(t+s\right){\Vert x\Vert }^2+s\left(t+s\right){\Vert y\Vert }^2-st{\Vert x-y\Vert }^2$ ;

${\Vert tx+\left(1-t\right)y\Vert }^2=t{\Vert x\Vert }^2+\left(1-t\right){\Vert y\Vert }^2-t\left(1-t\right){\Vert x-y\Vert }^2$.

引理2.3 [17] 设 $\nabla f\left(x\right)=A^{*}\left(I-P_Q\right)Ax$ 是Lipschitz连续，问题(1)的解集是非空的。当且仅当 $z=P_C\left(I-\alpha \nabla f\right)z$， $z\in H$ 时，则z是问题(1)的解。

引理2.4 [18] 设 $T:H\to H$ 是 $Fix\left(T\right)\ne \cancel{0}$ 的非扩张映射。如果 $\left\{x^k\right\}$ 是H中的一个弱收敛到 $x^{*}$ 的序列，

并且 $\left\{\left(1-T\right)x^k\right\}$ 强烈收敛到0，则 $\underset{k\to \infty }{\lim }\left(1-T\right)x^k=0$。

引理2.5 [18] 假设 $\left\{s^k\right\}$ 是满足以下条件的非负实数序列

$s^{k+1}\le \left(1-{\gamma }_k\right)s^k+{\gamma }_k{\delta }_k+{\beta }_k$, $k\ge 0$,

其中 $\left\{{\gamma }_k\right\}$， $\left\{{\beta }_k\right\}$， $\left\{{\delta }_k\right\}$ 满足条件

1) $\left\{{\gamma }_k\right\}\subset \left[0,1\right]$, ${\displaystyle {\sum }_{k=0}^{\infty }{\gamma }_k=\infty }$ ；

2) $\lim {\sup }_{k\to \infty }{\delta }_k\le 0$ ；

3) ${\beta }_k\ge 0$, ${\displaystyle {\sum }_{k=0}^{\infty }{\beta }_k<\infty }$。

则 $\underset{k\to \infty }{\lim }{s}^k=0$。

引理2.6 [17] [19] 设 $f\left(x\right):=\frac{1}{2}{\Vert Ax-P_{Q}Ax\Vert }^2$， $\nabla f\left(x\right)=A^{*}\left(I-P_Q\right)Ax$，L是 $\nabla f\left(x\right)$ 的Lipschitz常数，有

$\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert \le L\Vert x-y\Vert$, $\forall x,y\in H$,

对于任何 $\alpha \in \left(0,\frac{2}{L}\right)$， $P_C\left(I-\alpha \nabla f\right)$ 是 $\frac{2+\alpha L}{4}$ -平均算子 [14]，也是非扩张的。

证明 设 $P_C\left(I-\alpha \nabla f\right)=\left(1-\frac{2+\alpha L}{4}\right)I+\frac{2+\alpha L}{4}$。

$\begin{array}{l}\Vert P_C\left(I-\alpha \nabla f\right)\left(x\right)-P_C\left(I-\alpha \nabla f\right)\left(y\right)\Vert \\ =\Vert \left(1-\frac{2+\alpha L}{4}\right)\left(x\right)+\frac{2+\alpha L}{4}R\left(x\right)-\left(1-\frac{2+\alpha L}{4}\right)\left(y\right)-\frac{2+\alpha L}{4}R\left(y\right)\Vert \\ \le \left(1-\frac{2+\alpha L}{4}\right)\Vert x-y\Vert +\frac{2+\alpha L}{4}\Vert R\left(x\right)-R\left(y\right)\Vert \\ \le \Vert x-y\Vert \end{array}$

其中 $R:H\to H$ 是非扩张的。□

3. 松弛投影算法

本节提出一种求解分裂可行性问题的松弛投影算法。以下为算法过程：

算法3.1

设 $C,Q$ 分别是Hilbert空间 $H_1,H_2$ 上的非空闭凸子集， $A:H_1\to H_2$ 是一个有界线性算子。对于任意选取的初始点 $x^0\in H_1$，算法迭代序列为

$x^{k+1}:=t_{k}h\left(x^k\right)+{\lambda }_k{P}_C\left(x^k-{\alpha }_{k}D\left(x^k\right)\nabla f\left(x^k\right)\right)$, $k\ge 0$. (5)

其中 $\nabla f\left(x\right)=A^{*}\left(1-P_Q\right)Ax$， $\left\{t_k\right\}\subset \left(0,1\right)$， $\left\{{\lambda }_k\right\}\subset \left(0,2\right)$， $t_k+{\lambda }_k=1$。定义 $h:H_1\to ℝ$ 是 $\phi$ -压缩映射，且 $\phi \in \left[0,1\right)$。 $D\left(x\right):H_1\to ℝ$ 是线性有界算子满足

${\displaystyle {\sum }_{k=0}^{\infty }\Vert \nabla f\left(x\right)-D\nabla f\left(x\right)\Vert }:={\displaystyle {\sum }_{k=0}^{\infty }\Vert \nabla f\left(x\right)-D\left(x\right)\nabla f\left(x\right)\Vert }=:{\displaystyle {\sum }_{k=0}^{\infty }\Vert \theta \left(x\right)\Vert }<\infty$. (6)

下面为对证明算法3.1收敛性重要的引理：

引理3.1设 $f:H_1\to ℝ$， $0<\alpha <\frac{2}{L}$，其中 $L\ge 0$ 为可微凸函数 $f\left(x\right)$ 的梯度 $\nabla f$ 的Lipschitz常数。设 $T:=P_C\left(I-\alpha \nabla f\right)$，有

${\Vert Tx-Ty\Vert }^2\le {\Vert x-y\Vert }^2-\frac{2-\alpha L}{2+\alpha L}{\Vert \left(I-T\right)x-\left(I-T\right)y\Vert }^2$. (7)

证明 从引理2.6知T属于 $\frac{\alpha L+2}{4}$ -平均算子。因此，存在一个非扩张算子 $R:H_1\to ℝ$，使得

$T=\left(1-\beta \right)I+\beta R$，其中 $\beta =\left(\alpha L+2\right)/4\in \left(0,1\right)$。因此，对于任何 $x,y\in H_1$，由引理2.2有

$\begin{array}{c}{\Vert Tx-Ty\Vert }^2={\Vert \left(1-\beta \right)x+\beta R\left(x\right)-\left[\left(\left(1-\beta \right)y+\beta R\left(y\right)\right)\right]\Vert }^2\\ ={\Vert \left(1-\beta \right)\left(x-y\right)+\beta \left(R\left(x\right)-R\left(y\right)\right)\Vert }^2\\ =\left(1-\beta \right){\Vert x-y\Vert }^2+\beta {\Vert R\left(x\right)-R\left(y\right)\Vert }^2-\beta \left(1-\beta \right){\Vert x-y-\left(R\left(x\right)-R\left(y\right)\right)\Vert }^2\\ =\left(1-\beta \right){\Vert x-y\Vert }^2+\beta {\Vert R\left(x\right)-R\left(y\right)\Vert }^2-\frac{1-\beta }{\beta }{\Vert \beta \left(x-y\right)-\beta \left(R\left(x\right)-R\left(y\right)\right)\Vert }^2\\ \le {\Vert x-y\Vert }^2-\frac{2-\alpha L}{2+\alpha L}{\Vert \left(I-T\right)x-\left(I-T\right)x\Vert }^2.\end{array}$ (8)

□

引理3.2令 $f:H_1\to ℝ$， $0<\alpha <\frac{2}{L}$，其中 $L\ge 0$ 为可微凸函数 $f\left(x\right)$ 的梯度 $\nabla f$ 的Lipschitz常数。设 $T:=P_C\left(I-\alpha \nabla f\right)$ 和 $b=\frac{4}{2+\alpha L}$。则 $bT+\left(1-b\right)I$ 是非扩张的。

证明 对于任意 $x,y\in H_1$。由引理2.2和引理3.1

$\begin{array}{l}{\Vert \left(bT+\left(1-b\right)I\right)x-\left(bT+\left(1-b\right)I\right)y\Vert }^2\\ ={\Vert b\left(Tx-Ty\right)+\left(1-b\right)\left(x-y\right)\Vert }^2\\ =b{\Vert Tx-Ty\Vert }^2+\left(1-b\right){\Vert x-y\Vert }^2-b\left(1-b\right){\Vert \left(I-T\right)x-\left(I-T\right)y\Vert }^2\\ \le b\left[{\Vert x-y\Vert }^2+\left(1-b\right){\Vert \left(I-T\right)x-\left(I-T\right)y\Vert }^2\right]+\left(1-b\right){\Vert x-y\Vert }^2-b\left(1-b\right){\Vert \left(I-T\right)x-\left(I-T\right)y\Vert }^2\\ ={\Vert x-y\Vert }^2.\end{array}$

□

接下来使用引理3.1和引理3.2证明算法3.1的收敛结果。

定理3.3假设SFP的解集S非空，(6)成立，且系数 $\left\{{\alpha }_k\right\}$， $\left\{t_k\right\}$， $\left\{{\lambda }_k\right\}$ 满足以下条件

1) $0<{\alpha }_k\le {\sup }_k{\alpha }_k=:\bar{\alpha }<\frac{2}{L}$ ；

2) $\underset{k\to \infty }{\lim }{t}_k=0$ 和 ${\displaystyle {\sum }_{k=0}^{\infty }{t}_k=\infty }$ ；

3) $\sup \frac{{\lambda }_k}{1-t_k}<\frac{4}{\bar{\alpha }L+2}$ 和 $\underset{k\to \infty }{\lim }\frac{t_k}{{\lambda }_k}=0$。

则序列 $\left\{v^k\right\}$

$v^{k+1}=t_{k}h\left(v^k\right)+{\lambda }_k{P}_C\left(I-{\alpha }_k\nabla f\right)v^k$, (9)

强烈收敛到点 $z\in S$。

定理3.4 假设问题(1)的解集S不为空，式(6)成立并且 $\left\{{\alpha }_k\right\}$， $\left\{t_k\right\}$， $\left\{{\lambda }_k\right\}$ 满足以下条件

1) $0<{\alpha }_k\le {\sup }_k{\alpha }_k=:\bar{\alpha }<\frac{2}{L}$ ；

2) $\underset{k\to \infty }{\lim }{t}_k=0$ 和 ${\displaystyle {\sum }_{k=0}^{\infty }{t}_k=\infty }$ ；

3) $\sup \frac{{\lambda }_k}{1-t_k}<\frac{4}{\bar{\alpha }L+2}$ 和 $\underset{k\to \infty }{\lim }\frac{t_k}{{\lambda }_k}=0$。

则由算法(3.1)生成的序列 $\left\{x^k\right\}$

$x^{k+1}:=t_{k}h\left(x^k\right)+{\lambda }_k{P}_C\left(x^k-{\alpha }_{k}D\left(x^k\right)\nabla f\left(x^k\right)\right)$

强收敛到点 $z\in S$。

4. 数值实验

本节给出两个数值实验来验证算法的可行性。所有代码程序由MATLAB (R2017a)编写，在Windows 10 Inter(R) Core(TM) i5-8500 CPU@3.00GHz 3.0 GHz和8 GB内存的Dell电脑上运行。

例4.1设 $C=\left\{x\in R^3|x_1+x_2^2+2x_3\le 0\right\}$ ； $Q=\left\{x\in R^3|x_1^2+x_2-x_3\le 0\right\}$ ；

$A=\left[\begin{array}{ccc}2& -1& 3\\ 4& 2& 5\\ 2& 0& 2\end{array}\right]$

找一点x，使 $x\in C$， $Ax\in Q$。令 $\epsilon ={10}^{-4}$， $t_k=\frac{1}{15k}$， ${\lambda }_k=1-t_k$，同时取， $h\left(x^k\right)=0.1x^k$， ${\alpha }_k=\frac{k}{L\left(k+1\right)}$，

$D\left(x\right)=diag\left(5x\right)$。在数值实验中，采用了 $\Vert x^{k+1}-x^k\Vert <\epsilon$ 作为停止准则。

例4.1的数值结果见表1。在表1中，“算式(5)”，“算式(3)”和“CQ”和分别表示松弛投影算法，修改CQ算法和CQ算法。“Iter”，“Cpu”和“ $x^{*}$ ”分别表示迭代次数，以秒为单位的运行时间和最优解。 $x^0$ 是初始值(在区间(−10, 10)中随机产生)。

Table 1. Comparison of Equation (5) with Equation (3) and CQ algorithms at different initial values

表1. 算式(5)与算式(3)和CQ算法在不同初始值下的对比

例4.2设 $C=\left\{x\in R^3|x_1^2+x_2-x_3\le 0\right\}$ ； $Q=\left\{x\in R^3|x_1+x_2^2-3\le 0\right\}$ ；

$A=\left[\begin{array}{ccc}4& 2& 0\\ 5& 2& 0\\ 1& 3& 2\end{array}\right]$

求 $x\in C$， $Ax\in Q$。取 $\epsilon ={10}^{-3}$， $t_k=\frac{1}{3k}$， ${\lambda }_k=1-t_k$，同时取， $h\left(x^k\right)=0.3x^k$， ${\alpha }_k=\frac{k}{L\left(k+1\right)}$，

$D\left(x\right)=diag\left(2x\right)$。在数值实验中，采用了 $\Vert x^{k+1}-x^k\Vert <\epsilon$ 作为停止准则。

例4.2的数值结果可见于图1。在图1中，“算式(5)”，“算式(3)”和“CQ”和分别表示松弛投影算法，修改CQ算法和CQ算法。

图1中的数值结果为当初始值 $x^1=rand\left(3,1\right)$ 时算式(5)，算式(3)和CQ算法的迭代次数对比图。其中算式(5)，算式(3)和CQ的迭代次数分别为31，68和103。

由以上实验结果可知，松弛投影算法(5)在处理分裂可行问题时具有有效性，而且由对比结果可知，本文所提算法因其较少的迭代次数而优于CQ算法和修改CQ算法。

Figure 1. Equation (5) versus Equation (3) and CQ result comparison diagram

图1. 算式(5)与算式(3)和CQ结果对比图

5. 结论

本文主要研究了求解分裂可行性问题的松弛投影算法，在前人研究的基础上引入改进的Halpern迭代和线性算子，构建了求解分裂可行问题的新算法。数值实验结果表明了所提算法的有效性。本文算法的步长为固定步长，其取值范围的算子范数难以估计，因此结合其它方法，优化迭代步长，是下一步研究方向。