求解极大单调包含问题的改进混合外梯度邻点方法

黄元元,刘三阳

(西安电子科技大学 理学院,西安 710071)

考虑下列单调包含问题：寻找x∈H,使得

0∈T(x),

(1)

其中: H是实Hilbert空间;T: H→2H是给定的极大单调算子.凸函数的极小化问题、变分不等式等都可以转化为模型(1)进行求解.

求解问题(1)的混合外梯度邻点算法由Solodov等[1]提出,简称HPE方法,其迭代格式如下：已知xk,选取ck>0,εk≥0,寻找(yk,vk),使得vk∈Tεk(yk),‖ckvk+(yk-xk)‖2+2ckεk≤σ2‖yk-xk‖2,其中σ∈[0,1).产生新的迭代点:xk+1=xk-ckvk.

定义1设T: H→2H,若对任意的x,y∈X,u∈T(x),v∈T(y),有〈x-y,u-v〉≥0,则称T是单调的.若算子T单调且对任意的单调算子T′: H→2H,Gph(T)⊂Gph(T′),有T=T′,则称算子T是极大单调的.

定义2给定极大单调算子T: H→2H,α>0,定义(I+αT)-1为T的预解式,其在H上连续且非扩张.对于ε≥0,Tε: H→2H定义为Tε(x)∶={v∈H|〈u-v,y-x〉≥-ε,∀y∈H,u∈T(y)}.

定义3设X⊆H为非空闭凸集,点x∈H到X的投影定义为

PX(x)∶=arg min{‖y-x‖|y∈H }.

投影算子PX具有非扩张性,即对任意的x,y∈H,‖PX(x)-PX(y)‖≤‖x-y‖.

引理1[5]设B: H→2H是单调的,对于任意的x,z∈H,记r(x,α)=x-(I+αB)-1(x+αz),α>0,则当α≥α′>0时,不等式 ‖r(x,α)‖≥‖r(x,α′)‖和‖r(x,α)‖/α≤‖r(x,α′)‖/α′成立.

假设：

(H1) 问题(1)的解集T-1(0)是非空的,若问题(1)的解包含在某非空闭凸集X中,则假设X∩T-1(0)=Ø;

(H2) 对于任意的有界向量x,y∈domA且x≠y,假设‖A(y)-A(x)‖/‖y-x‖<+∞.

1 改进的HPE方法及其收敛性分析

算法1改进的HPE算法.

任取x0∈X,α-1>0,0<δ≤αmax<∞,β,ρ∈(0,1)及可和序列{εk|εk≥0}.令k∶=0.步骤如下:

1) 取αk=max{δβi,i=0,1,…},满足:

αk〈J(xk,αk)-xk,A(J(xk,αk))-A(xk)〉≤ρ‖J(xk,αk)-xk‖2,

(2)

(3)

2) 令xk+1=PX(xk-ckvk),置k∶=k+1,转1).

注1不等式(3)等价于寻找0∈ckT(·)+(·-xk)的近似解(yk,vk).该改进的HPE方法可视为对HPE方法的松弛.HPE方法要求ck有正下界,却未给出ck的具体选取方法,算法1在步骤1)中给出了ck的一个特定选取方法,但不要求其有正下界.

定理1设{xk}是由算法1产生的序列,x*是问题(1)的一个解点,则

(4)

证明：因为x*∈X∩T-1(0),则PX(x*)=x*.结合xk+1=PX(xk-ckvk),有

由于0∈T(x*)且vk∈Tεk(yk),则〈yk-x*,vk〉≥-εk,从而〈yk-x*,-ckvk〉≤ckεk,结合式(3),(5),有

定理2令{xk}和{(yk,vk)}是由算法1产生的序列,则:

1) 序列{xk}是有界的,序列{xk-yk}强收敛到零;

2) 序列{vk}强收敛到零,且序列{xk}弱收敛到问题(1)的一个解点.

(6)

(7)

(8)

由1)可知,序列{xk}和{yk}有界且有相同的弱聚点.不失一般性,设{xk}的某子列{xki}弱收敛到x∞,{yki}也弱收敛到x∞.任取x∈H且u∈T(x),注意到vk∈Tεk(yk),则对任意的指标i,不等式〈u-vki,x-yki〉≥-εki成立,从而

〈u-0,x-yki〉≥〈vki,x-yki〉-εki,

(9)

又因为序列{vk}强收敛到零,序列{εk}可和,则式(9)关于ki求极限得〈u-0,x-x∞〉≥0.由T的极大性可知0∈T(x∞).因为X是闭的且序列{xk}⊂X,则x∞∈X,从而x∞是问题(1)的一个解点.

2 改进HPE方法的特例

下面说明Tseng方法和求解非线性算子的分裂方法是改进HPE方法的特例.先证明文献[3-4]中的分裂方法是改进HPE方法的一个特例.基本框架如下：

其中αk满足

αk〈yk-xk,A(yk)-A(xk)〉≤ρ‖yk-xk‖2,

(12)

(13)

由式(10)有xk-yk-αkA(xk)+αkA(yk)∈αkT(yk).定义

vk∶=(xk-yk-αkA(xk)+αkA(yk))/αk,rk∶=γkαkvk+yk-xk.

(14)

取εk=0,则vk∈Tεk(yk),且

将式(13),(14)中的γk,vk代入式(15)得

(16)

由A的单调性可知

(18)

‖yk-xk‖≤‖(I+αmaxB)-1(I-αmaxA)(xk)-xk‖.

(19)

下面证明Tseng方法也是HPE方法的一个特例.Tseng方法是将式(11)中的参数γk换为常数1,将不等式(12)换为

αk‖A(yk)-A(xk)‖≤ρ‖yk-xk‖.

(20)

由Cauchy-Schwarz不等式和式(20),有

αk〈A(yk)-A(xk),yk-xk〉≤αk‖A(yk)-A(xk)‖‖yk-xk‖≤ρ‖yk-xk‖2,

从而αk满足不等式(2).如式(14)定义vk和rk,因为γk=1,则rk=αk(A(yk)-A(xk)),且满足‖rk‖≤σk‖yk-xk‖,其中σk=ρ<1.从而,vk∈Tεk(yk)且满足不等式(3).综上,Tseng方法也可视为改进HPE方法的一个特例.

[1] Solodov M V,Svaiter B F.A Hybrid Approximate Extragradient-Proximal Point Algorithm Using the Enlargement of a Maximal Monotone Operator [J].Set-Valued Analysis,1999,7(4): 323-345.

[2] Tseng P.A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings [J].Siam J Control Optim,2000,38(2): 431-446.

[3] DONG Yun-da.Splitting Methods for Monotone Inclusions [D].Nanjing: Nanjing University,2003.(董云达.一类求解单调包含问题的分裂方法 [D].南京: 南京大学,2003.)

[4] DONG Yun-da.A Splitting Method for Two Nonlinear Operators [J].Numerical Mathematics A Journal of Chinese Universities,2010,32(3): 202-208.

[5] HUANG Yuan-yuan.The Splitting Algorithms and Resolvent Dynamic Systems for Monotone Inclusions [D].Zhengzhou: Zhengzhou University,2011.(黄元元.求解单调包含问题的分裂算法及预解动力系统 [D].郑州: 郑州大学,2011.)