慣性β-Douglas-Rachford分裂算法收斂性分析

張家樂,歐陽薇

(云南師范大學數學學院,云南 昆明 650091)

0 引言

Douglas-Rachford分裂算法[1]常用于求解兩個極大單調算子之和的零點集,即如下單調包含問題:

(1)

(2)

Douglas-Rachford算法最早由DOUGLAS和RACHFORD[6]于1956年提出.該方法最初用于求解熱傳導過程中產生的線性方程組的數值解,其弱收斂性和強收斂性已得到很好的證實[7-10].在強單調性、Lipschitz連續性和余強制性假設下,可以得到該算法及其對偶的線性收斂速度[11-17].

1979年,LIONS和MERCIER[1]推廣了Douglas-Rachford方法,提出了經典Douglas-Rachford分裂算法,其格式如下:

1979年,GOL’SHTEIN和TRET’YAKOV[18]結合ROCKAFELLAR[19]提出的臨近點算法,提出了廣義的 Douglas-Rachford分裂算法,其格式如下:

其中,cn是松弛因子,cn∈(0,2).當cn∈(0,1)時,稱cn為低松弛因子;當cn∈(1,2)時,稱cn為超松弛因子.

2015年,BOT等[4]提出了慣性Douglas-Rachford分裂算法,其格式如下:

2019年,WANG等[20]基于經典Douglas-Rachford算法進行了細微改動,提出了含參數的Douglas-Rachford分裂算法,其格式如下:

2020年,陶永凱[21]在WANG等[20]提出的α-Douglas-Rachford分裂算法基礎上進行了改進,提出了修正的αn-Douglas-Rachford分裂算法,其格式如下:

本文在BOT等[4]和陶永凱[21]提出的Douglas-Rachford分裂算法的基礎上進行了相應修改,提出了一種新型的帶參數的慣性Douglas-Rachford分裂算法,稱為慣性β-Douglas-Rachford分裂算法,其格式如下:

(3)

1 符號說明

2 預備知識

則稱映射A是μ-強單調的.當μ=0時,稱A是單調的.

則稱映射A是L-lipschitz連續的.當L=1時,稱映射A是非擴張的;當L∈(0,1)時,稱映射A是收縮的.

定義3 算子A的預解式和反射預解式分別定義如下:

JA∶=(A+Id)-1,RA∶=2JA-Id,

其中,Id表示恒等映射,即Id(x)=x.

注2 由算子A的β-增強算子的定義可知,A(β)是極大單調的.

(i)T是穩定非擴張的;

(ii)Id-T是穩定非擴張的;

(iii)2T-Id是非擴張的;

(iv)?x,y∈D,‖Tx-Ty‖2≤〈x-y,Tx-Ty〉;

(v)?x,y∈D,0≤〈Tx-Ty, (Id-T)x-(Id-T)y〉;

(vi)?x,y∈D,?α∈[0,1],‖Tx-Ty‖≤‖α(x-y)+(1-α)(Tx-Ty)‖.

‖(1-t)x+ty‖2=(1-t)‖x‖2+t‖y‖2-t(1-t)‖x-y‖2.

(4)

引理8[22]設(φn)n∈,(δn)n∈,(αn)n∈是[0,+∞)中的序列,使得對所有n≥1,有φn+1≤φn+αn(φn-φn-1)+δn成立,其中∞,并且存在一個實數α對所有n∈,有0≤αn≤α<1成立.則下列結論成立:

(ii)(xn)n∈的每個子序列的弱聚點都在C中.

則(xn)n∈弱收斂于C中的一個點.

zer(A+B)=JγB(FixRγARγB).

3 主要結論

下面建立逼近兩個極大單調算子之和的零點集的慣性β-Douglas-Rachford分裂算法,并研究其收斂性質.在研究慣性β-Douglas-Rachford分裂算法的收斂性質之前,先證明兩個輔助結果.

下面給出第一個輔助結果.

(i)T是非擴張的;

(ii)FixT≠?,且JB(FixT)=zer(A+B+(2-2β)Id).

β‖JAx-JAy‖2≤‖JAx-JAy‖2≤〈JAx-JAy,x-y〉.

即

β‖JAx-JAy‖2≤〈JAx-JAy,x-y〉.

(5)

在(5)式兩邊同時乘4β,再加‖x-y‖2可得到

4β2‖JAx-JAy‖2+‖x-y‖2≤4β〈JAx-JAy,x-y〉+‖x-y‖2.

整理上式得到

4β2‖JAx-JAy‖2+‖x-y‖2-4β〈JAx-JAy,x-y〉≤‖x-y‖2.

根據完全平方公式,上式可變形為

‖2β(JAx-JAy)-(x-y)‖2≤‖x-y‖2,

即

‖(2βJA-Id)(x)-(2βJA-Id)(y)‖2≤‖x-y‖2.

(6)

由范數的非負性,(6)式可變形為

(ii)先證明JB(FixT)?zer(A+B+(2-2β)Id),即要證明:對于任意的x∈zer(A+B+(2-2β)Id),有x∈JB(FixT)成立.

由引理3可知,zer(A+B+(2-2β)Id)≠?,則對任意的x∈zer(A+B+(2-2β)Id),有

0∈(A+B+(2-2β)Id)(x)=A(x)+B(x)+(2-2β)x.

(7)

因此,存在一個z∈B(x),使得

(2β-2)x-z∈A(x).

(8)

令z=y-x,則(8)式等價于

(2β-1)x-y∈A(x).

(9)

又因為x=JB(y),故(9)式等價于

2βJB(y)-y∈A°JB(y)+JB(y)=(A+Id)°JB(y).

(10)

(10)式意味著

JB(y)=JA(2βJB(y)-y).

(11)

則有

0=2βJA(2βJB(y)-y)-2βJB(y)?

y=2βJA(2βJB(y)-y)-(2βJB(y)-y)?

y=(2βJA-Id)°(2βJB-Id)(y)?

(12)

因此,y是一個不動點,即FixT≠?.由于y∈FixT,x=JB(y),故x∈JB(FixT).

下面證明JB(FixT)?zer(A+B+(2-2β)Id),即要證明:對任意的x∈JB(FixT),使得x∈zer(A+B+(2-2β)Id)成立.

因為x∈JB(FixT),所以存在y∈FixT使得x=JB(y).又因為(7)至(12)式是相互等價的,故有

x∈zer(A+B+(2-2β)Id).

綜上可得,FixT≠?,且JB(FixT)=zer(A+B+(2-2β)Id).

下面給出第二個輔助結果,即慣性K-M算法.值得注意的是,由于迭代格式中存在仿射組合,所以需將設置限制為仿射子空間上的非擴張算子,在考慮極大單調算子的反射預解式的組成時,這一假設是完全成立的.下面證明第二個輔助結果.

(13)

(ii)(xn)n∈弱收斂到FixT中的一點.

證明 (i)記wn∶=xn+αn(xn-xn-1),則對于任意n≥1,迭代方案(13)可變形為

(14)

對于任意n≥1,任取y∈FixT.由(4)式和T的非擴張性可得

(15)

再次使用(4)式有

‖wn-y‖2=(1+αn)‖xn-y‖2-αn‖xn-1-y‖2+αn(1+αn)‖xn-xn-1‖2.

(16)

因此,由(15)和(16)式可得

(17)

此外,由(14)式得到:

‖Twn-wn‖2=‖2(xn+1-xn)+2αn(xn-1-xn)‖2=

(18)

由(17)和(18)式可推出:

‖xn+1-y‖2-(1+αn)‖xn-y‖2+αn‖xn-1-y‖2≤(αn-1)‖xn+1-xn‖2+2αn‖xn-xn-1‖2.

(19)

接下來,使用文獻[24]中的一些解題技巧來證明本文結論.

對于n∈,定義序列φn∶=‖xn-y‖2和ψn∶=φn-αnφn-1+2αn‖xn-xn-1‖2,其中ψ1=φ1≥0(因為α1=0).對于n∈,利用(αn)n≥0的單調性和φn≥0的事實,可得到

ψn+1-ψn≤φn+1-(1+αn)φn+αnφn-1+2αn+1‖xn+1-xn‖2-2αn‖xn-xn-1‖2.

由(19)式可得

ψn+1-ψn≤(αn-1)‖xn+1-xn‖2+2αn+1‖xn+1-xn‖2=

(αn-1+2αn+1)‖xn+1-xn‖2,?n≥1.

(20)

由(αn)n≥0及α的選取可得

αn-1+2αn+1≤α-1+2α<0, ?n≥1.

故序列(ψn)n≥0是非增的(嚴格減).

由ψn∶=φn-αnφn-1+2αn‖xn-xn-1‖2,序列(ψn)n≥0的非增性和(αn)n≥0的上界可得

-αφn-1≤φn-αφn-1≤ψn≤ψ1, ?n≥1.

(21)

因為

φn≤αφn-1+ψ1≤α(αφn-2+ψ1)+ψ1=α2φn-2+ψ1+αψ1≤…≤αnφ0+ψ1+αψ1+…+αn-1ψ1,

故

由(20)和(21)式可得

設x是(xn)n∈的子序列(xnk)k∈的一個弱聚點,選取(wn)n∈的一個子列(wnk)k∈,則由(i)以及(wn)n∈的定義和(αn)n≥0的上界可得,當k→+∞時,wnk?x.此外,通過(14)式可得

‖Twn-wn‖=2‖xn+1-wn‖≤2(‖xn+1-xn‖+α‖xn-xn-1‖).

(22)

因此,由(i)可得,當k→+∞時,Twnk-wnk→0.將引理7應用到序列(wnk)k∈上,則有x∈FixT.

由于引理9的兩個條件已得到驗證,因此(xn)n∈弱收斂于FixT中的一點.

之所以要先證明兩個輔助結果,是因為在接下來的證明中這兩個輔助結果將產生重要作用.下面給出慣性β-Douglas-Rachford分裂算法的收斂性質并給出詳細的證明.

(23)

其中,參數αn的選取滿足定理1中的條件.

(ii)當n→+∞時,yn-zn→0;

(iii)序列(xn+1-wn)n∈→0;

(iv)(xn)n∈?x*;

證明 記wn=xn+αn(xn-xn-1),根據修正的反射預解式的定義,(23)式可變形為

(i)由定理1直接可得.

故由(22)式,當n→+∞時,有yn-zn→0.

(iii)由(23)式,序列(xn)n∈滿足下式:

xn+1=wn+β(zn-yn)?xn+1-wn=β(zn-yn),

由(ii)可知,序列 (zn-yn)n∈強收斂于0,所以序列(xn+1-wn)n∈強收斂于0.

(iv)由命題1和定理1可得,序列(xn)n∈弱收斂于中的一點x*,即 (xn)n∈?x*.

(v)由命題1可知,FixT≠?,且JB(FixT)=zer(A+B+(2-2β)Id).應用定理1,則存在x*∈FixT,使得JBx*∈zer(A+B+(2-2β)Id).

又由命題1可知,x∈zer(A+B+(2-2β)Id),即

0∈A(x)+B(x)+(2-2β)x.

(24)

由定義6,有

0∈A(β)(z)+B(β)(z).

(25)

則由(25)式可得z∈zer(A(β)+B(β)),故zer(A(β)+B(β))≠?.

又因為A(β),B(β)都是單調算子,故由引理10可得

JB(β)(x*)∈zer(A(β)+B(β)).

由引理5可得

JB(β)(x*)=βJB(x*).

進一步,由引理4可得

由于極大單調算子的預解式是單值映射,所以,

由此定理2得證.

4 結論與展望

在接下來的工作中,將繼續圍繞慣性β-Douglas-Rachford分裂算法等相關問題進行研究,如將其用于求解變分不等式、原始對偶問題等.