求解極大單調包含問題的改進混合外梯度鄰點方法

黃元元,劉三陽

(西安電子科技大學 理學院,西安 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.)