Hilbert空间上多集合分裂可行问题的KM迭代算法

罗 俊,刘 健

(1．南京邮电大学 理学院，江苏 南京 210023；2．南京邮电大学 通信与信息工程学院，江苏 南京 210003)

Hilbert空间上多集合分裂可行问题的KM迭代算法

罗 俊1,刘 健2

(1．南京邮电大学 理学院，江苏 南京 210023；2．南京邮电大学 通信与信息工程学院，江苏 南京 210003)

多集合分裂可行问题就是寻找与一族非空闭凸集距离最近的点，并使得该点在线性变换下的像与另一族非空闭凸集的距离最近。分裂可行问题是一类重要的最优化问题，产生于工程实践，在医学、信号处理和图像重建等领域中有着广泛的应用。文中基于n维线性空间上求解分裂可行问题的KM迭代算法，目的是要将算法在Hilbert空间中加以推广应用。通过在Hilbert空间中运用投影压缩定理，并且利用逼近函数将多集合分裂可行问题转化为最小值问题，方便了对算法的推导证明。利用上述方法可得，多集合分裂可行问题的KM迭代算法在Hilbert空间中也有较好的收敛性。因此，可以将多集合分裂可行问题的KM迭代算法在Hilbert空间中加以推广。

多集合分裂可行问题；优化问题；KM迭代；Hilbert空间

1 概 述

分裂可行问题(Split Feasibility Problem,SFP)是一类非常重要的约束优化问题，它最早出现在Censor和Elfving(1994)的文献[1]中，定义如下：

设A是实矩阵且A∈Rm×n，C,Q分别是Rn,Rm中的非空闭凸子集，分裂可行问题就是要寻找这样的元素x(如果这样的元素x是存在的),使得x∈C,Ax∈Q。

多集合分裂可行问题(Multiple-SetsSplitFeasibilityProblem,MSSFP)是SFP的推广，是很多问题的反问题的数学模型。MSSFP是这样一个问题：

多集合分裂可行问题产生于工程实践，是一类重要的最优化问题，在医学[3]、信号处理[2]和图像重建[4]等领域中有着广泛的应用。MSSFP是SFP的推广与泛化，XuHongkun在文献[2]中最早提出了MSSFP。已经有不少人对MSSFP的求解算法进行了研究，也取得了一定的进展。Censor等在文献[3-4]中给出了一种求解MSSFP的投影算法：

定义逼近函数:

随着人们对分裂可行问题研究的深入，衍生了一系列反问题，定义如下：

设C,Q分别是Rn,Rm中的非空闭凸子集，A是Rm×n中实矩阵，A+是A的Moore-Penrose广义逆。SFP的反问题ISFP形如：寻找元素y(如果这样的y存在)：

y∈Q,A+y∈C

根据SFP与ISFP的对偶性，可以通过研究SFP的求解算法进而研究ISFP的求解。杨庆之[5]给出了一种ISFP问题的求解算法，迭代格式如下：

在此基础上，王新艳和屈彪[6]给出了下列推广形式：

推广之后的算法在迭代点的选取上具有更大的灵活性与更多的选择性。

后来，在前人的基础之上，Krasnoselski-Mann提出了形如式(1)的迭代格式称为KM迭代[7]。

xk+1=(1-ηk)xk+ηkN(xk),k=0,1,…

(1)

其中，N是Rn中的非扩张算子；ηk∈(0,1)，特别地，当N是强制非扩张算子时[8]，ηk∈(0,2)。

KM迭代的目标是寻找算子N的不动点，许多领域的很多问题及反问题都可以归结为寻找某个算子N的不动点[9]。虽然KM迭代格式简单，但是它在求非扩张算子N的不动点时效果非常显著，并且为许多领域的算法提供了一个统一的框架。在文献[5]中，给出了Rn空间中的一些算法。为了扩展算法的适用范围，而不仅仅局限于Rn空间，现在希望将其中的某些算法在Hilbert空间中加以推广利用。

2 预备知识

定义1[10]：假设X为带有内积〈·,·〉和范数‖·‖的Hilbert空间，对给定的Ω∈X,v∈X,如下问题：

min{‖u-v‖|u∈Ω}

的解称之为v在Ω上的投影,记作PΩ(v)。可以写成：

PΩ(v)=arg min{‖u-v‖|u∈Ω}

若Ω是闭凸集，则对∀v∈X,PΩ(v)是唯一存在的。

定义2[10]：设Ω是非空闭凸集，X1,X2为Hilbert空间；F是Ω⊂X1到X2的映射。

(4)如果存在常数λ>0，使得‖F(u)-F(v)‖≤λ‖u-v‖,∀u,v∈Ω，那么称F在Ω上是Lipschitz连续的，特别地，λ=1时，称F为非扩张算子；

定义3[10]：

(2)给定∀ρ≥0，Hilbert空间中算子H1,H2的ρ-距离定义为：

Dρ(H1,H2)=

(2)

(3)设C1,C2是Hilbert空间中非空闭凸子集，C1,C2之间的ρ-距离定义为：

dρ(C1,C2)=

(3)

投影的性质有以下定理：

定理1[12]：若Ω是Hilbert空间X中的非空闭凸集，则有：

证明：根据投影定义得到

‖v-PΩ(v)‖2≤‖v-w‖2,∀w∈Ω

因为Ω⊂X是非空闭凸集，则对于∀u∈Ω，0<σ<1有：

整理后得：

令σ→0+，得：

证毕。

定理2[11-12]：若Ω⊂X是非空闭凸集，∀v,u∈X,z∈Ω则有：

下面介绍收敛性分析中需要用到的KM定理。

xk+1=(1-ηk)xk+ηkHk(xk)

(4)

3 算法及其证明

对于多集合分裂可行问题，首先作下面的假设：

(H1)MSSFP的解集非空；

(H3)对∀x∈X1，至少存在一个次梯度ξ∈∂ci(x)，其中

对∀y∈X2，至少存在一个次梯度η∈∂qj(y)，其中

为了求解MSSFP，定义逼近函数：

那么寻找MSSFP的一个解，就可以转化为求解如下最小值问题：

Censor等提出了以下的迭代公式：

后来又有研究者对单集合分裂可行问题的CQ算法进行了改进，令上述迭代公式中s=αk=βγmk,其中β,γ是给定的常数，且满足β>0,γ∈(0,1)，mk是使下列不等式：

f(xk+1)≤f(xk)-σ

成立的最小非负整数，常数σ∈(0,1)。

将算法将推广到多集合分裂可行问题，在已有算法的基础上，利用KM迭代得到一种自适应不精确算法1。

(5)

其中，λk=γlmk,mk是使下式成立的最小非负整数。

(6)

令

(7)

(8)

定义算子：

(9)

(10)

由于正交投影PCi,k是强制非扩张算子，于是有：

‖Hkx-Hky‖2

所以，Hk是强制非扩张算子。同理，H也是强制非扩张算子。

由式(8)知式(7)可以写成：

xk+1=(1-ηk)xk+ηkHk(xk)

(11)

(12)

证明：记

(13)

(14)

对∀x∈H，‖x‖≤ρ，ρ>0有

(15)

由于正交投影是非扩张的，所以

‖yk-y‖

(16)

将式(13)、(14)代入式(15)再结合式(16)得到:

‖Hk(xk)-H(xk)‖≤

(17)

根据对任意有界线性算子B[14]，有‖Bx‖≤‖B‖‖x‖，可以得到：

‖Hk(xk)-H(xk)‖≤

由式(2)和式(3)得到：

(18)

4 结束语

多集合分裂可行问题在现实中的许多领域有着广泛的应用。到目前为止，多集合分裂可行问题的许多算法的求解都是在Rn空间中完成的，而在Hilbert空间中的推广应用还有待完善。文中基于Rn空间中求解多集合分裂可行问题的KM迭代算法，给出了Hilbert空间中的一种自适应不精确算法，以及算法的收敛性证明。

[1]CensorY,ElfvingT.Amulti-projectionalgorithmusingBregmanprojectionsinaproductspace[J].NumberAlgorithms,1994,8:221-239.

[2]XuHongkun.AvariableKrasnosel’ski-Mannalgorithmandthemultiple-setsplitfeasibilityproblem[J].InverseProblems,2006,22:2021-2034.

[3]CensorY.Row-actionmethodsforhugeandsparsesystemsandtheirapplications[J].SIAMReview,1981,23(4):444-466.

[4]CensorY,BortfeldT,MartinB,etal.Unifiedapproachforinversionproblemsinintensity-modulatedradiationtherapy[J].PhysicsinMedicineandBiology,2006,51:2353-2365.

[5] 杨庆之,赵金玲.分裂可行问题(SFP)的投影算法[J].计算数学,2006,28(2):121-132.

[6] 王新艳,屈 彪.求解分裂可行问题逆问题的算法推广[J].泰山学院学报,2010(6)：10-14.

[7]ZhaoJinling,YangQingzhi.AnoteontheKrasnoselski-Manntheoremanditsgeneralizations[J].InverseProblems,2007,23:1011-1016.

[8]CensorY,MotovaA,SegalA.Perturbedprojectionsandsubgradientprojectionsforthemultiple-setssplitfeasibilityproblem[J].JournalofMathematicalAnalysisandApplications,2007,327(2):1244-1256.

[9]BauschkeHH,BorweinJM.Onprojectionalgorithmsforsolvingconvexfeasibilityproblems[J].SIAMReview,1996,38:367-426.

[10]EickeB.Iterationmethodsforconvexlyconstrainedill-posedproblemsinHilbertspace[J].NumericalFunctionalAnalysisandOptimization,1992,13(5-6):413-429.

[11]WangC,XiuN.Convergenceofthegradientprojectionmethodforgeneralizedconvexminimization[J].ComputationalOptimizationandApplications,2000,16(2):111-120.

[12]ZarantonelloEH.ProjectionsonconvexsetsinHilbertspaceandspectraltheory[D].Wisconsin:UniversityofWisconsin,1971.

[13] 何炳生.论求解单调变分不等式的一些投影收缩算法[J].计算数学,1996(1):97-103.

[14] 徐成贤，陈志平，李乃成.近代优化方法[M].北京: 科学出版社,2002:18-35.

KM Iterative Algorithm for Multiple-sets Split Feasibility Problem in Hilbert Space

LUO Jun1，LIU Jian2

(1.College of Science,Nanjing University of Posts & Telecommunications,Nanjing 210023,China;2.College of Communication and Information Engineering,Nanjing University of Posts &Telecommunications,Nanjing 210003,China)

The multiple-sets spilt feasibility problem requires finding a point closest to a family of closed convex sets in one space,so that its image under a linear transformation will be closest to another family of closed convex sets in the image space.The multiple-sets spilt feasibility problem is an important type of optimization problem,which is generated from engineering practice and already has been widely applied in medical science,signal processing,image reconstruction.Based on KM iterative methods for solving the multiple-sets spilt feasibility problem in Rn space,try to spread this algorithm in Hilbert Space.Using projection compression theorem and approximation function transformed the multiple-sets spilt feasibility problem into a minimum value problem,making the algorithm proving more easily.By deducing and proving,the multiple-sets spilt feasibility problem has good convergence in Hilbert Space.So the result shows that the KM iterative methods are spread in Hilbert Space perfectly.

multiple-sets split-feasibility problem;optimization problem;KM iteration;Hilbert Space

2015-04-22

2015-07-23

时间：2016-01-04

国家自然科学基金面上项目(61070234)

罗 俊(1989-)，男，硕士研究生，研究方向为数值方法与应用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160104.1505.036.html

TP

A

1673-629X(2016)01-0043-05

10.3969/j.issn.1673-629X.2016.01.009