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

黄元元,刘三阳

(西安电子科技大学 理学院,西安 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}的某子列{xk……