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

趙 旭

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

0 引言

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

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

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

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

這個強收斂結果補充了文獻[2]的結果.

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

在Lions，Mercier和Giselsson的啟發下，本文考慮Douglas-Rachford算法的一個凸組合形式和Mann迭代形式的收斂性.基于文獻[4]的迭代方法，可以證明得到Douglas-Rachford算法的一個凸組合形式是強收斂的，以及Douglas-Rachford的Mann迭代形式是弱收斂的.這個結論拓展了收斂的Douglas-Rachford算法的形式，并且對這個結論做了一個簡單的應用，結合變分不等式，應用于一個法錐與強單調算子的和，可得到Douglas-Rachford算法的Mann迭代形式的弱收斂性.

1 預備知識

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

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

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

(1)

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

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

(2)

通過上面，可以看出1-Lipschitz連續也叫做非擴張算子.當算子A:β-Lipschitz連續，并且β系數屬于[0,1)，則把A稱作一個Banach壓縮算子.

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

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

(3)

這里的Id:H→H表示的是一個恒等算子，V:H→H為一個非擴張算子.

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

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

(4)

定義5[3]稱一個集值算子A:H→2H是μ-強單調，μ>0，如果

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

(5)

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

(6)

定義7[3]稱一個集值算子A:H→2H是單調的，如果

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

(7)

2 引理

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

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

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

(8)

引理2.2[4]設集合C是H中的一個非空閉凸子集，算子T:C→H是非擴張的，則T的不動點集Fix(T)也是閉凸集.

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

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

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

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

(c)單值算子A:H→H是β-Lipschitz且μ-強單調的;

(d)單值算子A:H→H是單調且β-Lipschitz連續的，集值算子B:H→2H極大單調且μ-強單調的；

證明：此結論在[3]和[5]中已有詳細證明.

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

3 主要結論

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

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

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

(9)

因此算子TDR:X→X是一個非擴張算子.則可以得到：

‖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)

根據α∈(0,1)，κ∈(0,1)可知[α+(1-α)κ]∈[0,1)，所以T′是一個Banach壓縮算子，由Banach壓縮不動點定理知，{un}強收斂于H中一點u.

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

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

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

‖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)

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

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

(14)

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

(15)

(16)

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

根據(16)式可以得到：

(17)

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

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

4 應用

設算子A:H→H是單調且β-Lipschitz連續的，β>0，

設算子F:H→2H是μ-強單調的，C?H為非空閉凸集.考慮變分不等式問題:

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

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

結合C的法錐的定義知：

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

即：

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

(18)

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

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

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

又因為F為μ-強單調算子，即：〈x-y,F(x)-F(y)〉≥μ‖x-y‖2，因此B=F+NC也是極大單調算子.

〈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為極大單調且μ-強單調的.

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

5 結語

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