ⓒ 应用数学和力学编委会,ISSN 1000-0887

Hilbert空间中求解分裂可行问题CQ算法的强收敛性

赵世莲

(西华师范大学 数学与信息学院, 四川 南充637002)

摘要 在Hilbert空间中,为了研究分裂可行问题迭代算法的强收敛性,提出了一种新的CQ算法首先利用CQ算法构造了一个改进的Halpern迭代序列; 然后通过把分裂可行问题转化为算子不动点, 在较弱的条件下, 证明了该序列强收敛到分裂可行问题的一个解 推广了Wang和Xu的有关结果

分裂可行问题; 强收敛; CQ算法; 改进的Halpern迭代

引 言

最优化问题是应用数学的一个重要研究领域,它在金融决策、工程设计、经济管理、交通规划、国防科学等重要领域都有广泛的应用,人们对它的研究已经取得了许多重要的成果其中分裂可行问题(SFP)是一类非常重要的最优化问题,它在医学、信号处理、图像重建都有着广泛的应用[1-4]1994年,Censor和Elfving[5] 根据医学中有关强放射治疗的实践经验和理论最早提出了SFP 它是这样一个问题:设C,Q分别是Hilbert空间H1,H2上的非空闭凸子集,A:H1H2是一个有界线性算子SFP(见文献[5])就是要找一点x,满足

xC,AxQ

(1)

近年来,很多学者关注SFP,并提出了许多算法(详见文献[6-9])其中部分学者用多重投影的方法得到了求解该问题的迭代算法,但这些算法在迭代中需要计算矩阵的逆,而矩阵逆的计算需要花费大量的时间且不容易求解,从而影响算法的迭代效率为了克服这一点,Byrne[10]提出了解决分裂可行问题的CQ算法,其迭代公式为

xk+1=PC(I-λA*(I-PQ)A)xk,k≥0,

其中λ∈(0,2/ρ(A*A)),ρ(A*A)是自伴算子A*A的谱半径,PC表示到集合C的投影

在Hilbert空间中,CQ算法一般不具备强收敛性 2010年,Xu[11]利用CQ算法构造了平均算子的Mann迭代序列,但仅得到弱收敛性 此前,Xu[12]应用Halpern迭代得到了强收敛性 之后,Wang和Xu[13]利用一族压缩算子去逼近一个非扩张算子,构造了如下序列:

xk+1=PC[(1-αk)PC(I-λA*(I-PQ)A)xk],

且得到算法的强收敛 本文受文献[13]的启发,主要研究改进的Halpern迭代,提出了下列算法: 对于任意的初始值uH1,定义迭代序列为

xk+1=PC[αku+βkxk+γkPC(I-λA*(I-PQ)A)xk],

其中系数αkβkγk⊂(0,1),并证明了该算法的强收敛性,推广了Wang和Xu的结果

1 预 备 知 识

本文中假设SFP是有解的,用Γ表示它的解集,即Γ=xC;AxQ=CA-1(Q),设H是Hilbert空间,〈·,·〉表示内积,‖·‖表示对应的范数,I表示Hilbert空间上的单位算子,Fix(T)=xx=T(x)表示算子T的不动点集合 全文用“”表示弱收敛,“→”表示强收敛下面给出本文所用到的一些定义和引理

定义1CH中的一个非空闭凸子集,令F:CH为非线性算子,称

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

F(x)-F(y)‖≤‖x-y‖, ∀x,yC;

(2)

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

F(x)-F(y)‖2≤〈x-yF(x)-F(y)〉, ∀x,yC;

(3)

3)Fα-平均算子,如果

F=(1-α)I+αS

(4)

其中α∈(0,1),I是单位算子,S:HH是非扩张算子

定义2CH的非空闭凸子集,定义

xC的正交投影

关于正交投影,有如下性质

引理1CH的一个非空闭凸子集,则对于任意的x,yH,有

x-PC(x),z-PC(x)〉≤0, ∀zC;

(5)

PC(x)-PC(y)‖≤〈x-y,PC(x)-PC(y)〉;

(6)

PC(x)-PC(y)‖≤‖x-y

(7)

引理2[14](demi-closed principle) 设CH的一个非空闭凸子集,T:CC是一个非扩张映象,如果并且xk-Txk→0,则x=T(x)

引理3[15] 假设αk是一个非负序列,满足

αk+1≤(1-γk)αk+δk,k≥0,

其中γk⊂(0,1),δk满足下列条件:

或者

则有

2 算法及收敛性

算法1C,Q分别是Hilbert空间H1,H2上的非空闭凸子集,对任意选取的初始点x0H1,令x0=u,定义迭代序列xk

xk+1=PC(αku+βkxk+γkUxk),k≥0,

(8)

其中U=I-λA*(I-PQ)A,系数列αk,βk,γk⊂(0,1)

引理4[9] 如果CA-1(Q)≠∅,设T(x)=PCU(x),其中U=I-λA*(I-PQ)A,那么

1)U是平均算子,即U=(1-β)I+βV,其中β∈(0,1)是一个常数,V是非扩张映象

2) Fix(U)=A-1(Q),且Fix(T)=Fix(PC)∩Fix(U)=CA-1(Q)

引理5U=I-λA*(I-PQ)A,则U是非扩张映象

证明 因为U平均算子,对于任意的x,yH1,有

U(x)-U(y)‖=‖(1-β)x+βV(x)-(1-β)y-βV(y)‖≤
(1-β)‖x-y‖+βV(x)-V(y)‖≤
(1-β)‖x-y‖+βx-y‖=‖x-y

所以U是非扩张映象

定理1 假设SFP的解集非空,非负序列αk,βk,γk⊂(0,1)且满足下列条件

αk+βk+γk=1,∀k≥0;

则由迭代序列(8)生成的序列xk强收敛到其中

证明T(x)=PCU(x),其中U=I-λA*(I-PQ)A接下来分5步完成证明

第1步 证明序列xkUxk是有界的

对于任意的x*∈Fix(T)=CA-1(Q),有x*CAx*Q,于是PC(x*)=x*,Ux*=x*,Tx*=x*由引理5知U是非扩张映象,即

U(xk)-x*‖≤‖xk-x*‖,

从而

xk+1-x*‖=‖PC(αku+βkxk+γkUxk)-x*‖≤
αku+βkxk+γkUxk-x*‖≤
αku-x*‖+βkxk-x*‖+γkUxk-x*‖≤
αku-x*‖+βkxk-x*‖+γkxk-x*‖≤
αku-x*‖+(1-αk)‖xk-x*‖≤
max‖u-x*‖,‖xk-x*

所以序列xkUxk是有界的

第2步 证明limk→∞xk+1-xk‖=0

xk+1-xk‖=‖PC(αku+βkxk+γkUxk)-PC(αk-1u+βk-1xk-1+γk-1Uxk-1)‖≤
‖(αku+βkxk+γkUxk)-(αk-1u+βk-1xk-1+γk-1Uxk-1)‖≤
‖(αku+βkxk+γkUxk)-(αku+βkxk-1+γkUxk-1)‖+
‖(αku+βkxk-1+γkUxk-1)-(αk-1u+βk-1xk-1+γk-1Uxk-1)‖≤
βk(xk-xk-1)+γk(Uxk-Uxk-1)‖+
‖(αk-αk-1)u+(βk-βk-1)xk-1+(γk-γk-1)Uxk-1

由于U是非扩张映象,于是

xk+1-xk‖≤(1-αk)‖xk-xk-1‖+αk-αk-1u‖+
βk-βk-1xk-1‖+γk-γk-1Uxk-1

由于前面所证序列xkUxk有界,令M=supk≥0u‖,‖xk‖,‖Uxk‖>0,从而

xk+1-xk‖≤(1-αk)‖xk-xk-1‖+
M(αk-αk-1+βk-βk-1+γk-γk-1)

由定理1的条件和引理3得到

(9)

第3步 令Txk=PCUxk,证明limk→∞xk-Txk‖=0

xk-Txk‖=‖xk-PCUxk‖=
xk-xk+1+xk+1-PCUxk‖≤
xk-xk+1‖+‖xk+1-PCUxk‖≤
xk-xk+1‖+‖PC[αku+βkxk+γkUxk]-PCUxk‖≤
xk-xk+1‖+‖αku+βkxk+γkUxk-Uxk‖≤
xk-xk+1‖+‖αku+βkxk‖+‖γk-1‖‖Uxk

由第1步所证序列xk,Uxk的有界性及定理1的条件

xk-T(xk)‖≤‖xk-xk+1‖+2(αk+βk)M

进一步,由式(9)及定理1的条件

(10)

第4步 设证明

(11)

由于

先证明xk的子列xki使得

(12)

由于xk有界,不失一般性,假定则由式(12)和引理1,可得

(13)

下面证明

(14)

由引理4知U是平均算子,所以可以表示为U=(1-β)I+βV,其中β∈(0,1),V是非扩张映象,任取z∈Fix(T)=Fix(PCU),有

xk+1-z2=‖PC[αku+βkxk+γkUxk]-z2
αku+βkxk+γkUxk-z2
αku-z2+βkxk-z2+γkUxk-z2
βkxk-z2+αku-z2+γk‖(1-β)xk+βVxk-z2
βkxk-z2+αku-z2+γk‖(1-β)(xk-z)+β(Vxk-z)‖2=
βkxk-z2+αku-z2+
γk[(1-β)‖xk-z2+
βVxk-z2-β(1-β)‖Vxk-xk2]≤
βkxk-z2+αku-z2+γk[(1-β)‖xk-z2+βxk-z2]-
γkβ(1-β)‖Vxk-xk2
(βk+γk)‖xk-z2+αku-z2-γkβ(1-β)‖Vxk-xk2
xk-z2+αku-z2-γkβ(1-β)‖Vxk-xk2

由于xk有界,取正数N使得‖xk-z‖<N,于是

γkβ(1-β)‖Vxk-xk2≤‖xk-z2-‖xk+1-z2+αku-z2=
(‖xk-z‖-‖xk+1-z‖)(‖xk-z‖+‖xk+1-z‖)+αku-z2
2Nxk-xk+1‖+αku-z2

结合定理1的条件和式(9)得

(15)

又因为U=(1-β)I+βV,所以上式说明式(14)成立 ,故式(11)成立

第5步 证明

(16)

式(16)即是

(17)

其中结合定理1的条件和式(11),得到lim supk→∞δk≤0由引理3可得xk强收敛到

定理1中取βk=0和αk,βk=0将得到如下两个推论

推论1 假设SFP的解集非空 ,对任意选取的初始点x0H1,令x0=u,序列定义为

xk+1=PC[αku+(1-αk)U(xk)],

(18)

其中αk⊂(0,1)且满足下列条件:

则由迭代序列(18)生成的序列xk强收敛到SFP的解集

推论2 假设SFP的解集非空 ,对任意选取的初始点x0H1,序列定义为

xk+1=PC[(1-αk)U(xk)],

(19)

其中αk⊂(0,1)且满足下列条件:

则由迭代序列(19)生成的序列xk强收敛到SFP的解集

3 结 论

在Hilbert空间中,求解分裂可行问题的CQ算法一般不具备强收敛性 为了得到其强收敛性,本文引入3个参数,利用改进的Halpern迭代,构造了求解分裂可行问题的新算法,并证明了在较弱的条件下该算法强收敛到分裂可行问题的一个解,推广了相关结果

参考文献

[1] BYRNE C. A unified treatment of some iterative algorithms in signal processing and image reconstruction[J].Inverse Problems, 2004,20(1): 103-120.

[2] CENSOR Y, ELFVING T, KOPF N, et al. The multiple-sets split feasibility problem and its applications for inverse problems[J].Inverse Problems, 2005,21(6): 2017-2084.

[3] CENSOR Y, BORTFELD T, MARTIN B, et al. A unified approach for inversion problems intensity-modulated radiation therapy[J].Physics in Medicine and Biology, 2006,51(10): 2353-2365.

[4] CENSOR Y, MOTOVA A, SEGAL A. Perturbed projections and subgradient projections for the multiple-sets split feasibility problem[J].Journal of Mathematical Analysis and Applications, 2007,327(2): 1244-1256.

[5] CENSOR Y, ELFVING T. A multiprojection algorithm using Bregman projections in a product space[J].Numerical Algorithms, 1994,8(2): 221-239.

[6] YANG Q Z. The relaxed CQ algorithm solving the split feasibility problem[J].Inverse Problems, 2004,20(4): 1261-1266.

[7] QU B, XIU N H. A note on the CQ algorithm for the split feasibility problem[J].Inverse Problems, 2005,21(5): 1655-1665.

[8] DANG Y Z,GAO Y. The strong convergence of a KM-CQ-like algorithm for split feasibility problem[J].Inverse Problems, 2011,27(1): 1-9.

[9] 杨丽, 李军. Hilbert空间中分裂可行性问题的改进Halpern 迭代和黏性逼近算法[J]. 应用数学和力学, 2017,38(9): 1072-1080.(YANG Li, LI Jun. Modified Halpern iteration and viscosity approximation methods for split feasibility problems in Hilbert spaces[J].Applied Mathematics and Mechanics, 2017,38(9): 1072-1080.(in Chinese))

[10] BYRNE C. Iterative oblique projection onto convex sets and the split feasibility problem[J].Inverse Problems, 2002,18(2): 441-453.

[11] XU H K. Iterative methods for the split feasibility problem in infinite-dimensional Hilbert spaces[J].Inverse Problems, 2010,26(10): 1-17.

[12] XU H K. A variable Krasnosel’skii-Mann algorithm and the multiple-set split feasibility problem[J].Inverse Problems, 2006,22(6): 2021-2034.

[13] WANG F H, XU H K. Approximating curve and strong convergence of the CQ algorithm for the split feasibility problem[J].Journal of Inequalities and Application, 2010,2010(1): 1-13.

[14] GOEBEL K, KIRK W A.Topics in Metric Fixed Point Theory[M]. Cambridge: Cambridge University Press, 1990.

[15] XU H K. Viscosity approximation methods for nonexpansive mappings[J].Journal of Mathematical Analysis and Applications, 2004,298(1): 279-291.

Strong Convergence of CQ Algorithms for Split Feasibility Problems in the Hilbert Spaces

ZHAO Shilian

(School of Mathematics and Information,China West Normal University,
Nanchong,Sichuan 637002,P.R.China)

Abstract: To study the strong convergence of split feasibility problems, a new CQ algorithm was proposed in the Hilbert spaces. Firstly, the modified Halpern iterative sequence was obtained with the CQ method. Furthermore, the split feasibility problem was transformed into the fixed point for operators, and it was proved that the sequence converges strongly to a solution of the split feasibility problem under some weak conditions. The findings generalize the corresponding results of Wang and Xu.

Key words: split feasibility problem; strong convergence; CQ method; modified Halpern iteration

Foundation item: The National Natural Science Foundation of China(11371015)

中图分类号 O177.91

文献标志码:A

DOI: 10.21656/1000-0887.390012

文章编号1000-0887(2019)01-0108-07

收稿日期 2018-01-08;

修订日期2018-03-26

基金项目 国家自然科学基金(11371015)

作者简介 赵世莲(1984—),女,讲师,硕士(E-mail: 14622959@qq.com).

引用本文/Cite thispaper:赵世莲. Hilbert空间中求解分裂可行问题CQ算法的强收敛性[J]. 应用数学和力学, 2019,40(1): 108-114.ZHAO Shilian. Strong convergence of CQ algorithms for split feasibility problems in the Hilbert spaces[J].Applied Mathematics and Mechanics, 2019,40(1): 108-114.