1. 引言
分裂可行性问题(SFP)在图像重建、信号处理和放射治疗中起着重要作用 [1] [2] [3] [4]。设
分别是Hilbert空间
上的非空闭凸子集,
是一个有界线性算子。分裂可行问题(SFP)是指找到一点x,满足
,
.(1)
该问题由Censor和Elfving [5] 于1994年首次在有限维Hilbert空间中提出。为了解决SFP问题,很多学者提出各种各样的算法(参见文献 [6] [7] [8] [9])。其中部分学者使用投影的方法得到求解SFP的迭代算法,但这些迭代算法需要计算矩阵的逆,矩阵逆的计算需要花费大量时间并且不容易求解,进而会影响算法的迭代效率。为了克服这点,Byrne [10] 首先提出了CQ算法,迭代公式为
, (2)
其中步长
。受CQ算法的影响,Wang和Xu [11] 通过引入系数
,提出了修正CQ算法
. (3)
并证明了(3)式强收敛于分裂可行性问题的最优解。Dang [6] 等人提出KM-CQ-Like算法
其中
和
在(0, 1)之间。并证明了算法的强收敛性。López等人 [12] 首先在CQ算法上引入新的选择步长的方法,步长
,其中
,并证明了具有此步长的算法(2)式弱收敛到SFP的解。在此基础上他们又引入Halpern [13] 迭代思想,迭代公式为
,(4)
其中,u是C的不动点,
,
,
,并证明了(4)式强收敛于
SFP的最优解。本文受前人文献的启发,提出一种求解分裂可行问题的松弛投影算法。此算法在CQ算法上引入改造的Halpern迭代序列和线性算子。
文章结构安排如下:第2节中,回顾一些必要的定义和基础知识;在第3节,提出松弛投影算法和相关引理;在第4节中,将提出的算法与前人算法进行对比,并对结果进行分析。最后,在第5节中,对论文进行简短总结。
2. 预备知识
设H是Hilbert空间,
表示内积,
表示对应的范数,I表示Hilbert空间上的单位算子,
表示算子T的不动点集合。
是H中的一个序列,
。
定义2.1 [14] 令
为非线性算子,称
1) F是非扩张算子,如果
,
;
2) F是固定非扩张算子,如果
,
;
3) F是
-平均算子,如果
,
其中
,I是单位算子,
是非扩张算子。
4) F是L-Lipschitz连续,其中
,如果
,
如果,
,F则为L-压缩映像。
定义2.2 [15] 设
是非空闭凸集,对任意
,x到C上的投影定义为:
.
显然,若
,则
。投影
具有下面重要的性质。
引理2.1 [15] 设
,是非空闭凸集,则对任意
,有
1)
,
;
2)
;
3)
,
;
4)
;
5)
.
引理2.2 [16] 设
,
。其中R是实数集。则有
;
;
.
引理2.3 [17] 设
是Lipschitz连续,问题(1)的解集是非空的。当且仅当
,
时,则z是问题(1)的解。
引理2.4 [18] 设
是
的非扩张映射。如果
是H中的一个弱收敛到
的序列,
并且
强烈收敛到0,则
。
引理2.5 [18] 假设
是满足以下条件的非负实数序列
,
,
其中
,
,
满足条件
1)
,
;
2)
;
3)
,
。
则
。
引理2.6 [17] [19] 设
,
,L是
的Lipschitz常数,有
,
,
对于任何
,
是
-平均算子 [14],也是非扩张的。
证明 设
。
其中
是非扩张的。□
3. 松弛投影算法
本节提出一种求解分裂可行性问题的松弛投影算法。以下为算法过程:
算法3.1
设
分别是Hilbert空间
上的非空闭凸子集,
是一个有界线性算子。对于任意选取的初始点
,算法迭代序列为
,
. (5)
其中
,
,
,
。定义
是
-压缩映射,且
。
是线性有界算子满足
. (6)
下面为对证明算法3.1收敛性重要的引理:
引理3.1设
,
,其中
为可微凸函数
的梯度
的Lipschitz常数。设
,有
. (7)
证明 从引理2.6知T属于
-平均算子。因此,存在一个非扩张算子
,使得
,其中
。因此,对于任何
,由引理2.2有
(8)
□
引理3.2令
,
,其中
为可微凸函数
的梯度
的Lipschitz常数。设
和
。则
是非扩张的。
证明 对于任意
。由引理2.2和引理3.1
□
接下来使用引理3.1和引理3.2证明算法3.1的收敛结果。
定理3.3假设SFP的解集S非空,(6)成立,且系数
,
,
满足以下条件
1)
;
2)
和
;
3)
和
。
则序列
, (9)
强烈收敛到点
。
定理3.4 假设问题(1)的解集S不为空,式(6)成立并且
,
,
满足以下条件
1)
;
2)
和
;
3)
和
。
则由算法(3.1)生成的序列
强收敛到点
。
4. 数值实验
本节给出两个数值实验来验证算法的可行性。所有代码程序由MATLAB (R2017a)编写,在Windows 10 Inter(R) Core(TM) i5-8500 CPU@3.00GHz 3.0 GHz和8 GB内存的Dell电脑上运行。
例4.1设
;
;
找一点x,使
,
。令
,
,
,同时取,
,
,
。在数值实验中,采用了
作为停止准则。
例4.1的数值结果见表1。在表1中,“算式(5)”,“算式(3)”和“CQ”和分别表示松弛投影算法,修改CQ算法和CQ算法。“Iter”,“Cpu”和“
”分别表示迭代次数,以秒为单位的运行时间和最优解。
是初始值(在区间(−10, 10)中随机产生)。
Table 1. Comparison of Equation (5) with Equation (3) and CQ algorithms at different initial values
表1. 算式(5)与算式(3)和CQ算法在不同初始值下的对比
例4.2设
;
;
求
,
。取
,
,
,同时取,
,
,
。在数值实验中,采用了
作为停止准则。
例4.2的数值结果可见于图1。在图1中,“算式(5)”,“算式(3)”和“CQ”和分别表示松弛投影算法,修改CQ算法和CQ算法。
图1中的数值结果为当初始值
时算式(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迭代和线性算子,构建了求解分裂可行问题的新算法。数值实验结果表明了所提算法的有效性。本文算法的步长为固定步长,其取值范围的算子范数难以估计,因此结合其它方法,优化迭代步长,是下一步研究方向。