Douglas-Rachford分裂算法的Mann迭代形式的收斂性及其應(yīng)用

趙 旭

(西華師范大學(xué)數(shù)學(xué)與信息學(xué)院，四川南充 637009)

0 引言

Lions和Mercier在文獻(xiàn)[1]中介紹了Douglas-Rachford分裂算法，這個(gè)算法是應(yīng)用于尋找兩個(gè)算子和為零的一種有效方法，即

?x∈H，使得0∈A(x)+B(x).

這里的算子A:H→2H，B:H→2H都是極大單調(diào)算子.Douglas-Rachford分裂算法基于如下迭代形式：

其中初始值u0∈H，RA和RB為算子A，B的反射預(yù)解算子.

這個(gè)強(qiáng)收斂結(jié)果補(bǔ)充了文獻(xiàn)[2]的結(jié)果.

Douglas-Rachford分裂算法是應(yīng)用于尋找兩個(gè)次微分算子和為零的一種有效的方法，這樣的單調(diào)包含問(wèn)題可以用來(lái)表述凸優(yōu)化問(wèn)題的原最優(yōu)性條件、對(duì)偶最優(yōu)性條件、原對(duì)偶最優(yōu)性條件、凸凹對(duì)策的平衡條件、單調(diào)變分不等式和單調(diào)互補(bǔ)問(wèn)題.Douglas-Rachford算法在信號(hào)處理[12]、圖像去噪[13]和統(tǒng)計(jì)估計(jì)[14]等方面顯示出了巨大的應(yīng)用潛力.Douglas-Rachford算法還可以推導(dǎo)出其他重要的分裂方法，如文獻(xiàn)[15]中的交替方向乘子法(ADMM)、Spingarn的部分逆法以及文獻(xiàn)[16]中的原對(duì)偶混合梯度法、線性化ADMM等方法.

在Lions，Mercier和Giselsson的啟發(fā)下，本文考慮Douglas-Rachford算法的一個(gè)凸組合形式和Mann迭代形式的收斂性.基于文獻(xiàn)[4]的迭代方法，可以證明得到Douglas-Rachford算法的一個(gè)凸組合形式是強(qiáng)收斂的，以及Douglas-Rachford的Mann迭代形式是弱收斂的.這個(gè)結(jié)論拓展了收斂的Douglas-Rachford算法的形式，并且對(duì)這個(gè)結(jié)論做了一個(gè)簡(jiǎn)單的應(yīng)用，結(jié)合變分不等式，應(yīng)用于一個(gè)法錐與強(qiáng)單調(diào)算子的和，可得到Douglas-Rachford算法的Mann迭代形式的弱收斂性.

1 預(yù)備知識(shí)

整篇文章中，設(shè)H是一個(gè)實(shí)的希爾伯特空間，用符號(hào)〈·，·〉表示內(nèi)積，用符號(hào)‖·‖表示范數(shù).用符號(hào)A:H→2H，表示A是H到H上的集值算子, 算子A的有效域表示為 dom(A)={x∈H|Ax≠φ},用符號(hào)A:H→H表示單值算子，此時(shí)dom(A)=H.若{xn}是H中的一個(gè)序列，稱序列{xn}強(qiáng)收斂于H中一點(diǎn)x，若‖xn-x‖→0，當(dāng)n→∞時(shí)；稱序列{xn}弱收斂于H中一點(diǎn)x，?y∈H,若〈y,xn〉→〈y,x〉，當(dāng)n→∞時(shí).把算子A的圖表示為gra(A)={(x,u)∈H×H|u∈Ax}.算子A:H→2H的不動(dòng)點(diǎn)集表示為Fix(A)={x∈H|Ax=x}.算子A的預(yù)解算子為JA=(Id+A)-1,算子A的反射預(yù)解算子為RA=2JA-Id.

定義1[3]稱一個(gè)單值算子A:H→H為β-Lipschitz連續(xù)的，如果

‖Ax-Ay‖≤β‖x-y‖,?x,y∈H

(1)

定義2[4]稱一個(gè)單值算子A:H→H是一個(gè)非擴(kuò)張算子，如果

‖Ax-Ay‖≤‖x-y‖,?x,y∈H

(2)

通過(guò)上面，可以看出1-Lipschitz連續(xù)也叫做非擴(kuò)張算子.當(dāng)算子A:β-Lipschitz連續(xù)，并且β系數(shù)屬于[0,1)，則把A稱作一個(gè)Banach壓縮算子.

定義3[4]稱一個(gè)單值算子A:H→H為α-averaged，如果它可以被表示為

A=(1-α)Id+αV,并且α∈[0,1)

(3)

這里的Id:H→H表示的是一個(gè)恒等算子，V:H→H為一個(gè)非擴(kuò)張算子.

定義4[4]稱一個(gè)集值算子A:H→2H是β-cocoercive，β>0，如果

〈x-y,u-v〉≥β‖u-v‖2,?(x,u),(y,v)∈gra(A)

(4)

定義5[3]稱一個(gè)集值算子A:H→2H是μ-強(qiáng)單調(diào)，μ>0，如果

〈x-y,u-v〉≥μ‖x-y‖2,?(x,u),(y,v)∈gra(A)

(5)

定義6[3]C?H的法錐NC定義為：

(6)

定義7[3]稱一個(gè)集值算子A:H→2H是單調(diào)的，如果

〈x-y,u-v〉≥0,?(x,u),(y,v)∈gra(A).

(7)

2 引理

如下引理在后面的證明中有重要作用.

引理2.1[4]設(shè)x∈H,y∈H,α∈R，則有：

‖αx+(1-α)y‖2+α(1-α)‖x-y‖2=α‖x‖2+(1-α)‖y‖2

(8)

引理2.2[4]設(shè)集合C是H中的一個(gè)非空閉凸子集，算子T:C→H是非擴(kuò)張的，則T的不動(dòng)點(diǎn)集Fix(T)也是閉凸集.

引理2.3[5]若{xn}是H中的一個(gè)序列，存在一個(gè)非空閉凸集C?H滿足下列條件：

(2)若序列{xn}的子序列{xnj}弱若收斂于x*，且x*∈C,

則存在x0∈C,使得{xn}弱收斂于x0.

引理2.4[2]設(shè)β≥μ>0，若算子A、B滿足下列四種情況之一：

(c)單值算子A:H→H是β-Lipschitz且μ-強(qiáng)單調(diào)的;

(d)單值算子A:H→H是單調(diào)且β-Lipschitz連續(xù)的，集值算子B:H→2H極大單調(diào)且μ-強(qiáng)單調(diào)的；

證明：此結(jié)論在[3]和[5]中已有詳細(xì)證明.

引理2.5[4]設(shè)集合C是H中的一個(gè)非空閉凸子集，算子T:C→H是非擴(kuò)張的，{xn}是集合C中一個(gè)序列，x為集合C中一點(diǎn).若{xn}弱收斂于x，且xn-Txn→0，則x∈Fix(T).

3 主要結(jié)論

定理3.1假設(shè)算子A、B滿足引理2.4(a)-(d)中任一種條件，且α∈(0,1)，則下列結(jié)論成立：

證明：(1)由引理2.4知TDR是關(guān)于常數(shù)κ的Banach壓縮算子，且κ∈(0,1)；即

‖TDRx-TDRy‖≤κ‖x-y‖≤‖x-y‖,?x,y∈H.

(9)

因此算子TDR:X→X是一個(gè)非擴(kuò)張算子.則可以得到：

‖T′x-T′y‖=‖αx+(1-α)TDRx-αy+(1-α)TDRy‖，

=‖α(x-y)+(1-α)(TDRx-TDRy)‖，

≤α‖x-y‖+(1-α)‖TDRx-TDRy‖，

≤α‖x-y‖+(1-α)κ‖x-y‖，

=[α+(1-α)κ]‖x-y‖.

(10)

根據(jù)α∈(0,1)，κ∈(0,1)可知[α+(1-α)κ]∈[0,1)，所以T′是一個(gè)Banach壓縮算子，由Banach壓縮不動(dòng)點(diǎn)定理知，{un}強(qiáng)收斂于H中一點(diǎn)u.

(1)設(shè)xn+1=Tnxn=αnxn+(1-αn)TDRxn，則{xn}弱收斂于S中一點(diǎn)x；

證明：由xn+1=Tnxn=αnxn+(1-αn)TDRxn，則Tn=αnId+(1-αn)TDR，并且TDR是非擴(kuò)張算子，所以TDR是(1-αn)-averaged算子.由于算子TDR是非擴(kuò)張的，根據(jù)引理2.2可知：算子TDR的不動(dòng)點(diǎn)集Fix(TDR)是一個(gè)閉凸集.

取x*∈Fix(TDR)，由引理2.1及不等式性質(zhì)有：

‖xn+1-x*‖2=‖αn(xn-x*)+(1-αn)(TDRxn-x*)‖2，

=αn‖xn-x*‖2+(1-αn)‖TDRxn-x*‖2-αn(1-αn)‖xn-TDRxn‖2，

≤αn‖xn-x*‖2+(1-αn)‖xn-x*‖2-αn(1-αn)‖xn-TDRxn‖2，

=‖xn-x*‖2-αn(1-αn)‖xn-TDRxn‖2.

(11)

由前面(11)式移向整理后可得到：

αn(1-αn)‖xn-TDRxn‖2≤‖xn-x*‖2-‖xn+1-x*‖2，

因此由上式得到：

(12)

‖xn+1-yn+1‖=‖αnxn+(1-α)TDRxn-yn+1‖=‖αnxn+(1-αn)yn-yn+1‖，

=‖αn(xn-yn+1)+(1-αn)(yn-yn+1)‖，

≤αn‖xn-yn+1‖+(1-αn)‖yn-yn+1‖，

=αn‖xn-yn+1‖+(1-αn)‖TDRxn-TDRxn+1‖，

≤αn‖xn-yn+1‖+(1-αn)‖xn+1-xn‖，

≤αn(‖xn-xn+1‖+‖xn+1-yn+1‖)+(1-αn)‖xn+1-xn‖，

=‖xn-xn+1‖+αn‖xn+1-yn+1‖，

=‖xn-(αnxn+(1-αn)yn)‖+αn‖xn+1-yn+1‖，

=(1-αn)‖xn-yn‖+αn‖xn+1-yn+1‖.

(13)

對(duì)上述(13)式進(jìn)行移向整理得到:

(1-αn)‖xn+1-yn+1‖≤(1-αn)‖xn-yn‖

(14)

由于{αn}?(a,b)?(0,1)，結(jié)合(12)式則可以得到：‖xn+1-yn+1‖≤‖xn-yn‖，

(15)

(16)

取序列{xn}的一個(gè)子序列{xnj}，使得xnj弱收斂于z.

根據(jù)(16)式可以得到：

(17)

結(jié)合(17)式和引理2.5知：z∈Fix(TDR)=S.

因此由引理2.3知：?x0∈S，使得{xn}弱收斂于x0，即{xn}弱收斂于S中一點(diǎn)x0.

4 應(yīng)用

設(shè)算子A:H→H是單調(diào)且β-Lipschitz連續(xù)的，β>0，

設(shè)算子F:H→2H是μ-強(qiáng)單調(diào)的，C?H為非空閉凸集.考慮變分不等式問(wèn)題:

〈(A+F)x,y-x〉≥0，?y∈C.

那么，若x為上述變分不等式的解，則：〈-A(x)-F(x),y-x〉≤0，

結(jié)合C的法錐的定義知：

-A(x)-F(x)∈NC(x)，

即：

0∈A(x)+F(x)+NC(x)，

(18)

命題4.1 設(shè)算子A:H→H是單調(diào)且β-Lipschitz連續(xù)的，β>0，算子F:H→2H是μ-強(qiáng)單調(diào)的，x∈C為變分不等式〈(A+F)x,y-x〉≥0的解，?y∈C.令算子B=F+NC，則算子B:H→2H為極大單調(diào)且μ-強(qiáng)單調(diào)的.

證明：由于NC為集合C?H的法錐，則NC為極大單調(diào)算子，也滿足單調(diào)的性質(zhì)，即：

〈x-y,u-v〉≥0,?(x,u),(y,v)∈gra(A).

又因?yàn)镕為μ-強(qiáng)單調(diào)算子，即：〈x-y,F(x)-F(y)〉≥μ‖x-y‖2，因此B=F+NC也是極大單調(diào)算子.

〈x-y,B(x)-B(y)〉=〈x-y,F(x)+u-F(x)-v〉=〈x-y,F(x)-F(y)〉+〈x-y,u-v〉，

≥μ‖x-y‖2，

因此算子B為極大單調(diào)且μ-強(qiáng)單調(diào)的.

證明：由命題4.1知算子B為極大單調(diào)且μ-強(qiáng)單調(diào)的.又由于算子A:X→X是單調(diào)且β-Lipschitz連續(xù)的，β>0，則滿足引理2.4中的條件(d).

5 結(jié)語(yǔ)

在尋找兩個(gè)算子和為0時(shí)，Douglas-Rachford算法是一種有效的辦法.本文證明得到了Douglas-Rachford算法的凸組合形式收斂于實(shí)的Hilbert空間中一點(diǎn)，Douglas-Rachford算法的Mann迭代形式弱收斂于Douglas-Rachford算法的不動(dòng)點(diǎn)集中一點(diǎn).此外，將該方法應(yīng)用于變分不等式問(wèn)題，得到了Douglas-Rachford算法的凸組合形式的強(qiáng)收斂性以及其Mann迭代形式的弱收斂性.