分裂可行性问题的超松弛投影算法及其强收敛性

Strong Convergence of Over Relaxation Projection Algorithms for Solving Split Feasibility Problems

摘要: 分裂可行性问题(Split feasibility problem, SFP)是寻找与非空闭凸集距离最近的点，并使得该点在线性变换下的像与另一非空闭凸集的距离最近。作为一类产生于工程实践的重要优化问题，在医学、信号处理和图像重建领域中被广泛应用。本文在Hilbert空间中，提出一种求解分裂可行性问题的超松弛投影算法。首先在CQ算法上引入改造的Halpern迭代序列和多个参数；然后在一定条件下，证明算法的强收敛性；数值实验结果验证了提出算法的有效性。

Abstract: The splitting feasible problem is to find the point closest to a non-empty closed convex set and make the image of the point under linear transformation closest to another non-empty closed convex set. Split feasible problem is an important optimization problem, arising from engineering practice, and is widely used in the fields of medicine, signal processing and image reconstruction. In this paper, an over-relaxed projection algorithm is presented for solving the split feasible problem in Hilbert space. Firstly, the modified Halpern iteration sequence and several parameters are introduced into the CQ algorithm. Then, under certain conditions, the strong convergence of the algorithm is proved. Finally, the numerical results show that the proposed algorithm is effective.

1. 引言

设C、Q分别是Hilbert空间H₁、H₂上的非空闭凸子集， $A:H_1\to H_2$ 是一个有界线性算子。所谓分裂可行性问题(Split Feasibility Problem, SFP)就是要找到一点x，满足

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

该问题是由Censor和Elfving [1] 首次在有限维Hilbert空间中提出的，且在医学、信号处理、图像重建等方面被广泛应用 [2] [3] [4] [5] 。本文中，I表示恒定算子，定义 $f:H_1\to ℝ$ 为

$f\left(x^k\right)=\frac{1}{2}{\Vert \left(I-P_Q\right)A{x}^k\Vert }^2,$

其中 $P_Q$ 表示在闭凸集Q上的投影。凸函数 $f\left(x\right)$ 是可微的其梯度为

$\nabla f\left(x\right)=A^{*}\left(I-P_Q\right)Ax,$

其中 $A^{*}$ 是线性算子A的伴随算子。

为了解决SFP问题，很多学者提出各种各样的算法 [6] - [11] 。其中部分学者使用多重投影的方法得到求解SFP的迭代算法，但这些迭代算法需要计算矩阵的逆，矩阵逆的计算需要花费大量时间并且不容易求解，进而会影响算法的迭代效率。为了克服上述不足，Byrne [7] 首先提出了CQ算法，迭代公式为

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

其中步长 $\lambda \in \left(0,\frac{2}{{\Vert A\Vert }^2}\right)$ 。受CQ算法的影响，Wang和Xu [12] 通过引入系数 ${\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].$ (1.3)

其中， $\left\{{\alpha }_k\right\}\subset \left(0,1\right)$ ，当 $\left\{{\alpha }_k\right\}$ 满足以下条件时：

1) $\underset{k\to \infty }{\lim }{\alpha }_k=0$ ；

2) ${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{\alpha }_k}=\infty$ ；

3) ${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}\left|{\alpha }_{k+1}-{\alpha }_k\right|}<\infty$ ，或者 $\underset{k\to \infty }{\lim }\frac{\left|{\alpha }_{k+1}-{\alpha }_k\right|}{{\alpha }_k}=0$ 。

证明了(1.3)式强收敛于分裂可行性问题的最优解。López等人 [13] 在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)$ ，进而证明了具有此步长的算法(1.2)式弱收敛于SFP的解。

在此基础上又引入Halpern [14] 迭代思想，迭代公式为

$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),$ (1.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}$ ，并证明了(1.4)式强收敛于SFP的最优解。

本文通过在CQ算法上引入改造的Halpern迭代序列和多个参数，提出了一种求解分裂可行性问题的超松弛投影算法，并在一定条件下，证明了该算法的强收敛性。

2. 预备知识

本文中假设SFP有解，设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$ ， $x^{k_j}\in x^k$

是 $\left\{x^k\right\}$ 的子序列，“ $\mapsto$ ”表示弱收敛，“ $\to$ ”表示强收敛。 ${\omega }_{\omega }\left(x^k\right):=\left\{z\in H|\underset{j\to \infty }{\lim }{x}^{k_j}\mapsto z\right\}$ 表示 $x^k$ 的弱收敛簇。

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

F是非扩张算子，如果

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

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

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

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

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

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

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 设 $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 设 $C\subseteq H$ ，是非空闭凸集，则对任意 $x,y\in H$ ，有

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

$\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$ ；

${\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$ ；

${\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$ ；

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

引理2.2 设 $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 [15] 设 $\nabla f\left(x\right)=A^{*}\left(I-P_Q\right)Ax$ 是Lipschitz连续，问题(1.1)的解集是非空的。当且仅当 $z=P_C\left(I-\alpha \nabla f\right)z$ ， $z\in H$ 时，z是问题(1.1)的解。

引理2.4 [16] 设 $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 [16] 假设 $\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 [15] [17] 设 $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. 超松弛投影算法及其强收敛性

以下将提出一种求解分裂可行问题的超松弛投影算法，并证明其强收敛性。该算法过程如下：

算法

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

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

其中 $\nabla f\left(x\right)=A^{*}\left(1-P_Q\right)Ax$ ， $\left\{t_k\right\}\subset \left(0,1\right)$ ， $\left\{{\gamma }_k\right\}\subset \left(-1,1\right)$ ， $\left\{{\lambda }_k\right\}\subset \left(0,2\right)$ ， $t_k+{\gamma }_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 .$ (3.2)

$\left\{e_k\right\}$ 表示误差项，且

${\displaystyle {\sum }_{k=0}^{\infty }\Vert e_k\Vert <\infty }.$ (3.3)

以下引理对于证明算法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.$ (3.4)

证明：从引理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}$

引理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非空，(3.2)，(3.3)成立，且系数 $\left\{{\alpha }_k\right\}$ ， $\left\{t_k\right\}$ ， $\left\{{\lambda }_k\right\}$ 满足以下条件

$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)+{\gamma }_k{v}^k+{\lambda }_k{P}_C\left(I-{\alpha }_k\nabla f\right)v^k,$ (3.5)

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

证明：设 $T_k=P_C\left(I-{\alpha }_k\nabla f\right)$ ， ${\rho }_k=\frac{{\lambda }_k}{1-t_k}$ ， $u_k=\left(1-{\rho }_k\right)v^k+{\rho }_k{T}_k{v}^k$ ， ${\lambda }_k=\left(1-t_k\right){\rho }_k$ ， ${\gamma }_k=\left(1-t_k\right)\left(1-{\rho }_k\right)$ 。由条件3)可得

$0<{\rho }_k\le \underset{k}{\sup }{\rho }_k<\frac{4}{\bar{\alpha }L+2}\le \frac{4}{{\alpha }_{k}L+2},$ (3.6)

(3.5)可改写为

$v^{k+1}=t_{k}h\left(v^k\right)+\left(1-t_k\right)u_k.$ (3.7)

接下来分三个步骤来完成证明。

步骤1：证明序列 $\left\{v^k\right\}$ 有界。

对于 $z\in S$ ，由引理2.3和引理3.1知

$\begin{array}{c}{\Vert T{v}^k-z\Vert }^2={\Vert T{v}^k-Tz\Vert }^2\\ \le {\Vert v^k-z\Vert }^2-\frac{2-\alpha L}{2+\alpha L}{\Vert \left(I-T\right)v^k-\left(I-T\right)z\Vert }^2\\ ={\Vert v^k-z\Vert }^2-\frac{2-\alpha L}{2+\alpha L}{\Vert T{v}^k-v^k\Vert }^2.\end{array}$

从而

$\begin{array}{l}{\Vert u_k-z\Vert }^2\\ ={\Vert \left(1-{\rho }_k\right)v^k+{\rho }_k{T}_k{v}^k-z\Vert }^2\\ ={\Vert v^k-z\Vert }^2+{\left({\rho }_k\right)}^2{\Vert T_k{v}^k-v^k\Vert }^2-2{\rho }_k\langle v^k-z,v^k-T_k{v}^k\rangle \\ ={\Vert v^k-z\Vert }^2+{\left({\rho }_k\right)}^2{\Vert T_k{v}^k-v^k\Vert }^2-{\rho }_k\left[{\Vert v^k-z\Vert }^2+{\Vert T_k{v}^k-v^k\Vert }^2-{\Vert T_k{v}^k-z\Vert }^2\right]\end{array}$

$\begin{array}{l}=\left(1-{\rho }_k\right){\Vert v^k-z\Vert }^2-{\rho }_k\left(1-{\rho }_k\right){\Vert T_k{v}^k-v^k\Vert }^2+{\rho }_k{\Vert T_k{v}^k-z\Vert }^2\\ \le \left(1-{\rho }_k\right){\Vert v^k-z\Vert }^2-{\rho }_k\left(1-{\rho }_k\right){\Vert T_k{v}^k-v^k\Vert }^2+{\rho }_k\left[{\Vert v^k-z\Vert }^2-\frac{2-\alpha L}{2+\alpha L}{\Vert T_k{v}^k-v^k\Vert }^2\right]\\ ={\Vert v^k-z\Vert }^2-{\rho }_k\left(1-{\rho }_k+\frac{2-\alpha L}{2+\alpha L}\right){\Vert T_k{v}^k-v^k\Vert }^2\\ ={\Vert v^k-z\Vert }^2-{\rho }_k\left(\frac{4}{2+\alpha L}-{\rho }_k\right){\Vert T_k{v}^k-v^k\Vert }^2.\end{array}$ (3.8)

因此可得，

$\begin{array}{c}\Vert v^{k+1}-z\Vert =\Vert t_{k}h\left(v^k\right)+\left(1-t_k\right)u_k-z\Vert \\ =\Vert t_k\left(h\left(v^k\right)-z\right)+\left(1-t_k\right)\left(u_k-z\right)\Vert \\ \le t_k\Vert h\left(v^k\right)-h\left(z\right)+h\left(z\right)-z\Vert +\left(1-t_k\right)\Vert u_k-z\Vert \\ \le t_k\Vert h\left(v^k\right)-h\left(z\right)\Vert +t_k\Vert h\left(z\right)-z\Vert +\left(1-t_k\right)\Vert u_k-z\Vert \\ \le t_k\phi \Vert v^k-z\Vert +t_k\Vert h\left(z\right)-z\Vert +\left(1-t_k\right)\Vert v^k-z\Vert \\ =\left(1-t_k\left(1-\phi \right)\right)\Vert v^k-z\Vert +t_k\left(1-\phi \right)\frac{\Vert h\left(z\right)-z\Vert }{1-\phi }\\ \le \max \left\{\Vert v^k-z\Vert ,\frac{\Vert h\left(z\right)-z\Vert }{1-\phi }\right\}.\end{array}$ (3.9)

由上式得

$\Vert v^{k+1}-z\Vert \le \max \left\{\Vert v^k-z\Vert ,\frac{\Vert h\left(z\right)-z\Vert }{1-\phi }\right\},$

所以序列 $\left\{v^k\right\}$ 是有界的。

步骤2：证明存在子序列 $\left\{v^{k_j}\right\}\subset \left\{v^k\right\}$ ，使得 $\left\{v^{k_j}\right\}$ 的任何弱收敛簇 ${\omega }_{\omega }\left(v^{k_j}\right)$ 点都属于S。

由(3.8)和引理2.2，可得

$\begin{array}{l}{\Vert v^{k+1}-z\Vert }^2\\ ={\Vert t_k\left(h\left(v^k\right)-z\right)+\left(1-t_k\right)\left(u_k-z\right)\Vert }^2\\ ={\Vert t_k\left(h\left(v^k\right)-h\left(z\right)+h\left(z\right)-z\right)+\left(1-t_k\right)\left(u_k-z\right)\Vert }^2\\ ={\Vert \left[t_k\left(h\left(v^k\right)-h\left(z\right)\right)+\left(1-t_k\right)\left(u_k-z\right)\right]+t_k\left(h\left(z\right)-z\right)\Vert }^2\\ \le {\Vert t_k\left(h\left(v^k\right)-h\left(z\right)\right)+\left(1-t_k\right)\left(u_k-z\right)\Vert }^2+2\langle t_k\left(h\left(z\right)-z\right),v^{k+1}-z\rangle \end{array}$

$\begin{array}{l}\le t_k{\Vert h\left(v^k\right)-h\left(z\right)\Vert }^2+\left(1-t_k\right){\Vert u_k-z\Vert }^2+2t_k\langle h\left(z\right)-z,v^{k+1}-z\rangle \\ \le t_k\phi {\Vert v^k-z\Vert }^2+\left(1-t_k\right)\left[{\Vert v^k-z\Vert }^2-{\rho }_k\left(\frac{4}{2+{\alpha }_{k}L}-{\rho }_k\right){\Vert T_k{v}^k-v^k\Vert }^2\right]+2t_k\langle h\left(z\right)-z,v^{k+1}-z\rangle \\ =\left(1-t_k\left(1-\phi \right)\right){\Vert v^k-z\Vert }^2-\left(1-t_k\right){\rho }_k\left(\frac{4}{2+{\alpha }_{k}L}-{\rho }_k\right){\Vert T_k{v}^k-v^k\Vert }^2+2t_k\langle h\left(z\right)-z,v^{k+1}-z\rangle \\ =\left(1-t_k\left(1-\phi \right)\right){\Vert v^k-z\Vert }^2-{\lambda }_k\left(\frac{4}{2+{\alpha }_{k}L}-{\rho }_k\right){\Vert T_k{v}^k-v^k\Vert }^2+2t_k\langle h\left(z\right)-z,v^{k+1}-z\rangle \\ =:\left(1-t_k\left(1-\phi \right)\right){\Vert v^k-z\Vert }^2+t_k\left(1-\phi \right)g_k.\end{array}$ (3.10)

其中 $g_k=\frac{1}{1-\phi }\left[2\langle h\left(z\right)-z,v^{k+1}-z\rangle -\frac{{\lambda }_k}{t_k}\left(\frac{4}{2+{\alpha }_{k}L}-{\rho }_k\right){\Vert T_k{v}_k-v_k\Vert }^2\right]$ 。由于 $0<{\rho }_k<\frac{4}{2+{\alpha }_{k}L}$ (请参看(3.6))，显然

$g_k\le \frac{2}{1-\phi }\langle h\left(z\right)-z,v^{k+1}-z\rangle \le \frac{2}{1-\phi }\Vert h\left(z\right)-z\Vert \Vert v^{k+1}-z\Vert <\infty .$

又通过步骤1知 $\left\{\Vert v^{k+1}-z\Vert \right\}$ 是有界的。因此 ${\sup }_k{g}_k$ 是有界的。令 $\left\{g_{k_j}\right\}\subset \left\{g_k\right\}$ 使得 ${\sup }_k{g}_k=\underset{j\to \infty }{\lim }{g}_{k_j}$ 。在不失一般性的前提下，假设 $\underset{j\to \infty }{\lim }\langle h\left(z\right)-z,v^{k_j+1}-z\rangle$ 和 $\underset{j\to \infty }{\lim }{\rho }_{k_j}$ 存在，由于 $\left\{\langle h\left(z\right)-z,v^{k+1}-z\rangle \right\}$ 和 $\left\{{\rho }_k\right\}$ 都是有界序列的。因此有

$\begin{array}{l}\left(1-\phi \right){\sup }_k{g}_k=\left(1-\phi \right)\underset{j\to \infty }{\lim }{g}_{k_j}\\ =\underset{j\to \infty }{\lim }\left(2\langle h\left(z\right)-z,v^{k_j+1}-z\rangle -\frac{{\lambda }_{k_j}}{t_{k_j}}\left(\frac{4}{2+{\alpha }_{k_j}L}-{\rho }_{k_j}\right){\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert }^2\right)\\ =2\underset{j\to \infty }{\lim }\langle h\left(z\right)-z,v^{k_j+1}-z\rangle -\underset{j\to \infty }{\lim }\frac{{\lambda }_{k_j}}{t_{k_j}}\left(\frac{4}{2+{\alpha }_{k_j}L}-{\rho }_{k_j}\right){\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert }^2.\end{array}$ (3.11)

由于， $0<\frac{4}{2+\bar{\alpha }L}-{\sup }_k{\rho }_k\le \frac{4}{2+\bar{\alpha }L}-{\rho }_k\le 2$ 表明 $\left\{\frac{{\lambda }_{k_j}}{t_{k_j}}{\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert }^2\right\}$ 具有收敛的子序列，也可用序列本身来表示。利用条件3)，得出结论

$\underset{j\to \infty }{\lim }\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert =0$ . (3.12)

接下来，证明当 $j\to \infty$ 时 $\Vert P_C\left(I-\bar{\alpha }\nabla f\right)v^{k_j}-v^{k_j}\Vert \to 0$ 。假设当 $j\to \infty$ 时 ${\alpha }_{k_j}\to \bar{\alpha }$ 且 $0<\alpha <\frac{2}{L}$ ，已知 $\left\{v^{k_j}\right\}$ 有界，所以有 $\Vert \nabla f\left(v^{k_j}\right)\Vert \le M$ ，M为常数，通过引理2.6和(3.12)，得

$\begin{array}{l}\Vert P_C\left(I-\bar{\alpha }\nabla f\right)v^{k_j}-v^{k_j}\Vert \\ =\Vert P_C\left(I-\bar{\alpha }\nabla f\right)v^{k_j}-T_{k_j}{v}^{k_j}+T_{k_j}{v}^{k_j}-v^{k_j}\Vert \\ \le \Vert P_C\left(I-\bar{\alpha }\nabla f\right)v^{k_j}-T_{k_j}{v}^{k_j}\Vert +\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert \\ =\Vert P_C\left(I-\bar{\alpha }\nabla f\right)v^{k_j}-P_C\left(I-{\alpha }_{k_j}\nabla f\right)v^{k_j}\Vert +\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert \\ \le \left(\bar{\alpha }-{\alpha }_{k_j}\right)\Vert \nabla f\left(v^{k_j}\right)\Vert +\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert \\ \le \left(\bar{\alpha }-{\alpha }_{k_j}\right)M+\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert \\ \to 0\left(当j\to \infty 时\right)\end{array}$ (3.13)

由引理2.4知 ${\omega }_{\omega }\left(v^{k_j}\right)\in S$ 。

步骤3：证明对于 $z\in S$ ， $\underset{k\to \infty }{\lim }\Vert v^k-z\Vert \to 0$ 。

通过设 ${\bar{\gamma }}_k=t_k\left(1-\phi \right)$ ， ${\beta }_k=0$ 来证明(3.10)满足引理2.5中的条件。显然， $t_k\left(1-\phi \right)\in \left[0,1\right]$ 和 ${\displaystyle {\sum }_{k=0}^{\infty }{t}_k\left(1-\phi \right)=\infty }$ 满足条件2)。接下来证明 $\underset{k\to \infty }{\lim \sup }{g}_k\le 0$ 。

由式(3.13)，有

$\begin{array}{l}\Vert v^{k_j+1}-v^{k_j}\Vert \\ =\Vert t_{k_j}h\left(v^{k_j}\right)+\left(1-t_{k_j}\right)\left(u_{k_j}-v^{k_j}\right)\Vert \\ =\Vert t_{k_j}h\left(v^{k_j}\right)-t_{k_j}{v}^{k_j}-\left(1-t_{k_j}\right)v^{k_j}+\left(1-t_{k_j}\right)u_{k_j}\Vert \\ =\Vert t_{k_j}\left(h\left(v^{k_j}\right)-v^{k_j}\right)+\left(1-t_{k_j}\right)\left(u_{k_j}-v^{k_j}\right)\Vert \\ =\Vert t_{k_j}\left(h\left(v^{k_j}\right)-v^{k_j}\right)+\left(1-t_{k_j}\right)\left(\left(1-{\rho }_{k_j}\right)v^{k_j}+{\rho }_{k_j}{T}_{k_j}{v}^{k_j}-v^{k_j}\right)\Vert \end{array}$

$\begin{array}{l}=\Vert t_{k_j}\left(h\left(v^{k_j}\right)-v^{k_j}\right)+\left(1-t_{k_j}\right){\rho }_{k_j}\left(T_{k_j}{v}^{k_j}-v^{k_j}\right)\Vert \\ \le t_{k_j}\Vert h\left(v^{k_j}\right)-v^{k_j}\Vert +\frac{4}{2+\bar{\alpha }L}\left(1-t_{k_j}\right)\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert \\ \le t_{k_j}\Vert h\left(v^{k_j}\right)-v^{k_j}\Vert +\frac{4}{2+\bar{\alpha }L}\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert \\ \le t_{k_j}\left[\Vert h\left(v^{k_j}\right)\Vert +\Vert v^{k_j}\Vert \right]+\frac{4}{2+\bar{\alpha }L}\Vert T_{k_j}{v}^{k_j}-v^{k_j}\Vert \\ \to 0\left(当j\to \infty 时\right)\end{array}$ (3.14)

由(3.14)和 ${\omega }_{\omega }\left(v^{k_j}\right)\in S$ 可得 ${\omega }_{\omega }\left(v^{k_j+1}\right)\in S$ 。随着 $j\to \infty$ 令 $v^{k_j}\to v^{*}$ (则 $v^{*}\in S$ )，因此

$\underset{k\to \infty }{lim\sup }\langle h\left(z\right)-z,v^{k+1}-z\rangle =\underset{j\to \infty }{lim}\langle h\left(z\right)-z,v^{k_j+1}-z\rangle .$

从而，

$\begin{array}{c}\underset{k\to \infty }{lim\sup }{g}_k\le \frac{2}{1-\phi }\underset{k\to \infty }{lim\sup }\langle h\left(z\right)-z,v^{k+1}-z\rangle \\ =\frac{2}{1-\phi }\underset{j\to \infty }{lim\sup }\langle h\left(z\right)-z,v^{k_j+1}-z\rangle \\ =\frac{2}{1-\phi }\langle h\left(z\right)-z,v^{*}-z\rangle =0.\end{array}$ (3.15)

通过将引理2.5带入(3.10)，得到 $\underset{k\to \infty }{\lim }\Vert v^k-z\Vert \to 0$ ，证毕。

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

$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\}$ 强收敛于点 $z\in S$ 。

证明：令序列 $\left\{x^k\right\}$ ， $\left\{v^k\right\}$ 分别由(3.1)和(3.5)产生。然后，根据定理3.3知 $\left\{v^k\right\}$ 强收敛于问题(1.1)的解。只需证明当 $k\to \infty$ 时， $\Vert x^k-v^k\Vert \to 0$ 。

令 $V_k=P_C\left(I-{\alpha }_{k}D\nabla f\right)$ ， $T_k=P_C\left(I-{\alpha }_k\nabla f\right)$ 和 $R_k=g_k{T}_k+\left(1-g_k\right)I$ ，其中 $g_k=\frac{4}{2+{\alpha }_{k}L}$ ， $\theta \left(x^k\right)=V_k{x}^k-T_k{x}^k$ (参见(3.2))。由引理3.2可知 $R_k$ 是非扩张的。此外， ${\rho }_k=\frac{{\lambda }_k}{1-t_k}$ 满足 $\frac{{\rho }_k}{g_k}<1$ (参见(3.6))。可得

$\begin{array}{l}\Vert x^{k+1}-v^{k+1}\Vert \\ =\Vert \left[t_{k}h\left(x^k\right)+{\gamma }_k{x}^k+{\lambda }_k{P}_C\left(I-{\alpha }_{k}D\nabla f\right)x^k\right]-\left[t_{k}h\left(v^k\right)+{\gamma }_k{v}^k+{\lambda }_k{P}_C\left(I-{\alpha }_k\nabla f\right)v^k\right]+e_k\Vert \\ =\Vert t_k\left(h\left(x^k\right)-h\left(v^k\right)\right)+{\gamma }_k\left(x^k-v^k\right)+{\lambda }_k\left[P_C\left(I-{\alpha }_{k}D\nabla f\right)x^k-P_C\left(I-{\alpha }_k\nabla f\right)v^k\right]+e_k\Vert \\ =\Vert t_k\left(h\left(x^k\right)-h\left(v^k\right)\right)+{\gamma }_k\left(x^k-v^k\right)+{\lambda }_k\left(V_k{x}^k-T_k{x}^k+T_k{x}^k-T_k{v}^k\right)+e_k\Vert \\ \le \Vert t_k\left(h\left(x^k\right)-h\left(v^k\right)\right)+{\gamma }_k\left(x^k-v^k\right)+{\lambda }_k\left(T_k{x}^k-T_k{v}^k\right)\Vert +{\lambda }_k\Vert V_k{x}^k-T_k{x}^k\Vert +\Vert e_k\Vert \end{array}$

$\begin{array}{l}\le \Vert t_k\left(h\left(x^k\right)-h\left(v^k\right)\right)+\left(1-t_k\right)\left[\left(1-{\rho }_k\right)\left(x^k-v^k\right)+{\rho }_k\left(T_k{x}^k-T_k{v}^k\right)\right]\Vert +{\lambda }_k{\alpha }_k\Vert \theta \left(x^k\right)\Vert +\Vert e_k\Vert \\ \le t_k\phi \Vert x^k-v^k\Vert +\left(1-t_k\right)\Vert \left(1-\frac{{\rho }_k}{g_k}\right)\left(x^k-v^k\right)+\frac{{\rho }_k}{g_k}\left(R_k{x}^k-R_k{v}^k\right)\Vert +{\lambda }_k{\alpha }_k\Vert \theta \left(x^k\right)\Vert +\Vert e_k\Vert \\ \le t_k\phi \Vert x^k-v^k\Vert +\left(1-t_k\right)\Vert x^k-v^k\Vert +{\lambda }_k{\alpha }_k\Vert \theta \left(x^k\right)\Vert +\Vert e_k\Vert \\ =\left(1-t_k\left(1-\phi \right)\right)\Vert x^k-v^k\Vert +t_k\left(1-\phi \right){\alpha }_k\Vert \theta \left(x^k\right)\Vert +\Vert e_k\Vert .\end{array}$ (3.16)

将条件2)，(3.2)，(3.3)和引理2.5应用于最后一个不等式，得到当 $k\to \infty$ 时 $\Vert x^k-v^k\Vert \to 0$ 。从而由定理3.3推出结论。

4. 数值实验

以下将通过两个数值实验来验证所提出的超松弛投影算法的可行性。所有代码程序由MATLAB(R2017a)编写，在Windows 10 Inter(R) Core(TM) i5-8500 CPU @3.00GHz 3.0GHz和8GB内存的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}8& 4& 2\\ 9& 6& 5\\ 1& 2& 9\end{array}\right]$

找一点x，使 $x\in C$ ， $Ax\in Q$ 。令 $\epsilon ={10}^{-4}$ ， $t_k=\frac{1}{4k}$ ， ${\gamma }_k=0.01+\frac{1}{10k}$ ， ${\lambda }_k=1-t_k-{\gamma }_k=0.99-\frac{7}{20k}$ ，同时取， $h\left(x^k\right)=0.1x^k$ ， ${\alpha }_k=\frac{k}{L\left(k+1\right)}$ ， $D\left(x\right)=diag\left(9x\right)$ 。在数值实验中，采用了 $\Vert x^{k+1}-x^k\Vert <\epsilon$ 作为停止准则。

例4.1的数值实验结果如表1所示。在表1中，“CQ”和“OP”分别表示CQ算法和超松弛投影算法。“Iter”，“Cpu”和“ $x^{*}$ ”分别表示迭代次数，以秒为单位的运行时间和最优解。 $x^0$ 是初始值。

Table 1. Comparison between Algorithm and CQ Algorithm at Different Initial Values

表1. OP算法与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}8& 4& 2\\ 9& 6& 5\\ 1& 2& 9\end{array}\right]$

求 $x\in C$ ， $Ax\in Q$ 。取 $\epsilon ={10}^{-4}$ ， $t_k=\frac{1}{3k}$ ， ${\gamma }_k=0.01+\frac{1}{10k}$ ， ${\lambda }_k=1-t_k-{\gamma }_k=0.99-\frac{13}{30k}$ ，同时取， $h\left(x^k\right)=0.3x^k$ ， ${\alpha }_k=\frac{k}{L\left(k+1\right)}$ ， $D\left(x\right)=diag\left(0.6x\right)$ 。在数值实验中，采用了 $\Vert x^{k+1}-x^k\Vert <\epsilon$ 作为停止准则。

例4.2的数值实验结果如图1所示。在图1中，“CQ”和“OP”分别表示CQ算法和超松弛投影算法。

Figure 1. Comparison of numerical experimental results between OP algorithm and CQ algorithm

图1. OP算法与CQ算法数值实验结果对比图

图1中的数值实验结果为当初始值 $x^1=10\ast rand\left(3,1\right)$ 时的OP算法和CQ算法的迭代次数对比图。其中OP算法和CQ算法的迭代次数分别为22和283。

由以上数值实验结果可知，超松弛投影算法(OP)在处理分裂可行性问题时具有有效性，而且由对比结果可知，OP算法因其需要较少的迭代次数而优于CQ算法。

5. 结束语

本文主要研究了求解分裂可行性问题的超松弛投影算法。为了证明其强收敛性，引入了 $t_k,{\gamma }_k,{\lambda }_k$ 和 $e_k$ 这4个参数，并利用改进的Halpern迭代，构建了求解分裂可行性问题的新算法，在一定假设条件下证明了该算法的强收敛性。同时数值实验的结果也表明了所提出的OP算法的有效性。但本文算法的步长为固定步长，其取值范围的算子范数难以估计，因此结合其它方法，优化迭代步长，将是我们下一步的研究内容或方向。

基金项目

国家社科基金重大项目(20&ZD199、21&ZD200)；教育部人文社科青年基金项目(20YJC820030)；国家新闻出版署“智能与绿色柔板印刷”重点实验室招标课题(KLIGFP-02)。

NOTES

^*通讯作者。