廣義循環(huán)Douglas-Rachford算法

郭 科，張有才

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

0 引 言

在本文中，H是實希爾伯特空間，〈·，·〉和‖·‖分別表示相應(yīng)的內(nèi)積和范數(shù)。給定N個非空的閉凸集C1，C2，…，CN? H，假定Ci≠Φ，N集凸可行問題就是在交集中尋找到某一個點，即：

當N＝2時，（1）退化為經(jīng)典的凸可行問題

對于凸可行問題（2），有很多的求解方法，但最常用的方法是投影算法。值得注意的是，使用投影算法是通常需要假定在這些集合上的投影相對簡單且容易計算。一些著名的投影算法包括Von Neumann的交替投影算法［1-8］，Douglas-Rachford分裂算法（DRSM）［9-11］和 Dykstra算法［12-14］等。最近，文獻［15-17］指出，與經(jīng)典的投影類算法相比，DRSM具有更好的收斂性和明顯的數(shù)值優(yōu)勢。對于問題（2），Douglas-Rachford算子TC1，C2：H→ H定義為

這里，RS∶＝2PS-I是集合S的反射算子，PS為到集合S的投影算子，定義為

顯然，TA，B與TB，A通常不相等。雖然DRSM具有良好的收斂性，但它僅能處理兩個集合的凸可行問題。對于N集凸可行問題時，常用的辦法是采用乘積空間技術(shù)，N集凸可行問題轉(zhuǎn)化為兩個集合的凸可行問題來處理。然而，該方法增加了空間的維數(shù)，使計算變得復雜。最近，Borwein和Tam在文獻［18］中提出了循環(huán)DRSM來求解問題（1）。其迭代格式如下：

這里 T［C1C2，…，CN］為循環(huán) Douglas-Rachford算子，定義 T［C1C2…CN］：H→ H為

對于問題（2），循環(huán)Douglas-Rachford算子退化為

該算法與DRSM相比，其收斂速度更快而且能直接處理N集凸可行問題，彌補了DRSM不能直接處理N集凸可行問題的不足。

另一方面，DRSM可看作鄰近點算法（PPA）的一個應(yīng)用［9，16］。而PPA現(xiàn)已經(jīng)得到了很好的研究，其迭代格式為

其中，JcT∶＝（I+cT）-1為集值映射T的預解算子，c為鄰近參數(shù)且c＞0。PPA具有廣泛的應(yīng)用，比如文獻［19-20］中的增廣拉格朗日法（ALM）、文獻［21］中的乘子交替方向法（ADMM）、文獻［22］中的投影梯度法和文獻［23］中的外梯度法等都可看作PPA的應(yīng)用。鑒于PPA廣泛的應(yīng)用，文獻［24］中提出了廣義PPA，該算法可看作PPA的加速版本，其迭代格式為

其中，γ∈（0，2）為松弛參數(shù)。當γ＝1時，廣義PPA退化為PPA。文獻［25］指出，廣義PPA繼承了原PPA的所有重要性質(zhì)，且廣義PPA具有更好的收斂性和明顯的數(shù)值優(yōu)勢。研究發(fā)現(xiàn)，當γ越趨近于2時，廣義PPA的收斂速度更快。值得注意的是，當γ＝2時，最近文獻［25］中給出了γ＝2序列發(fā)散的例子。類似地，對廣義PPA做應(yīng)用可得到廣義ALM［26］，廣義ADMM［27］和廣義DRSM［28-29］等等。廣義DRSM比DRSM的靈活性更好，最近，文獻［30］中更是指出在保證凸性的條件下，松弛一些正則性條件，選擇合適的參數(shù)α可得到廣義DRSM線性收斂的結(jié)果。對于問題（2），廣義Douglas-Rachford算子：H→ H定義為

其中，α∈（0，1）。自然地，與通常是不相等的。然而廣義DRSM也僅能直接處理兩個集合的凸可行問題。對于N集凸可行問題時，通常使用的辦法也是乘積空間技術(shù)。

考慮到廣義DRSM的局限，受J.M.Borwein和M.K.Tam的研究成果［18］啟發(fā)，我們提出使用廣義循環(huán)DRSM來求解多集凸可行問題，借助均值算子的性質(zhì)，我們給出了算法的收斂性。

本文的安排如下：在第1節(jié)中，我們給出了一些理論分析所需的概念和結(jié)論；在第2節(jié)中，介紹我們的主要研究成果——廣義循環(huán)DRSM，以及其收斂性證明。

1 預備知識

我們首先回顧一些相關(guān)的概念和結(jié)論來作為我們理論分析的主要工具。

我們定義算子 T的不動點集為 Fix（T）∶＝｛x∶Tx＝x｝。令 D? H且 T∶D→ H，若對所有的x，y∈D，都有 ‖Tx-Ty‖ ≤ ‖x-y‖ 成立，我們則稱 T是非擴張的；若對所有的 x，y∈D，都有 ‖Tx-Ty‖2+‖（I-T）x-（I-T）y‖2≤ ‖x-y‖2成立，我們則稱T是穩(wěn)定非擴張的；若lnim∞‖Tnx-Tn+1x‖ ＝0，我

→們則稱T是漸進正則的。

下面，我們給出在后文中對廣義循環(huán)DRSM收斂性的證明所需要的定義和引理。

定義1［31-32］令D?H且D≠Φ，若存在算子R∶D→H是非擴張的，使得T＝（1-α）I+αR，α∈（0，1），則稱算子T為α-均值算子。

引理1［33］令A?H是閉凸的，PA是到集合A的投影算子，RA＝2PA-I是集合A的反射算子，則PA是穩(wěn)定非擴張的，RA是非擴張的。

引理 2［33］（Kolmogorov’s Critrerion）令 C? H是閉凸的且 C≠ Φ，則

引理3 令C1，C2?H是非空閉凸集，則RC2RC1是非擴張的，從而TC1，C2＝（1-α）I+αRC2RC1為α-均值算子。

證明：由引理 1知，RC1和RC2是非擴張的，則對任意x，y∈ H，有

故RC2RC1非擴張，從而由定義1知TC1，C2是 α-均值算子。

引理4 令 D? H且 D≠ Φ，m≥2為整數(shù)，指標集 I＝｛1，…，m｝，（Ti）i∈l是 D到 D的算子集簇，且（αi）i∈l是 （0，1）內(nèi)的實數(shù)，對每個 i∈ I，Ti是 αi-均值算子，令

則T是α-均值算子。

證明：詳細證明過程可查閱文獻［34］。

引理5 令 D? H且 D≠ Φ，m為正整數(shù)，指標集 I＝｛1，…，m｝，（Ti）i∈l是 D到 D的 α-均值算子集簇，且 ∩i∈IFix（Ti）≠ Φ，則令 T＝T1…Tm，我們有 Fix（T）＝∩i∈lFix（Ti）。

證明：詳細證明過程可查閱文獻［34］。

引理6 令 A，B? H為閉凸集且 A∩ B≠ Φ，則 PAFix（TA，B）＝A∩ B。

證明：詳細證明過程可查閱文獻［11］或者［35］。

引理 7［36］令 ｛δn｝和 ｛γn｝為非負序列，且滿足和 γn+1≤ γn+δn，n＝1，2，… ，則 ｛γn｝是收斂序列。

引理8［37］令 T∶H→H為 α-均值算子，若對任意 x0＝H，序列 ｛Tnx0｝有界，則序列 ｛Tnx0｝弱收斂到T的不動點x。

引理9 （Opial）令 T∶H→ H是非擴張，漸進正則的，且 Fix（T）≠ Φ。則對任意 x0∈ H，序列 ｛Tnx0｝弱收斂到Fix（T）上的一點。

證明：詳細證明過程可查閱文獻［34］。

2 廣義循環(huán)DRSM及其收斂性

使用廣義DRSM來解決問題（2）時，廣義Douglas-Rachford算子∶H→ H寫為

則對于問題（1），我們定義廣義循環(huán) Douglas-Rachford算子∶H→ H為

對于問題（2），廣義循環(huán) Douglas-Rachford算子變?yōu)?，∶H→ H定義為使用廣義循環(huán)DRSM來解決問題（1），給定x0∈H，其迭代序列為

為了方便書寫和表達美觀，我們將一些表達式進行縮寫。我們?nèi)≈笜四Ｓ?N，將縮 寫 為縮寫為。特別地，∶＝

定理1 令C1，C2，…，CN?H為閉凸集且 Ci≠ Φ，對任意的 x0∈ H，以及任意的指標 i，j，i，j∈ ｛1，2，…，N｝，則序列 ｛｝弱收斂到點 x，使得 PCix＝PCjx。此外，對于每個指標 j，有 PCjx∈Ci≠ Φ。

證明：首先，我們證明序列｝有界。

由引理3知，對每個指標i，是 α-均值算子，α∈ （0，1）。又由引理 4可知，是 α-均值算子。此外，

由引理 7，令 γn+1∶＝‖xn+1-x*‖ ，γn∶＝‖xn-x*‖ 和 δn≡0，則‖xn+1-x*‖存在，故序列 ｛｝有界。

其次，由引理8，可得序列 ｛｝弱收斂到的不動點 x，下證 PCix＝PCjx，我們計算

其中，最后一個不等式由引理2可得。從而，對每個指標i，都有PCix＝PCi-1x，即有PCix＝PCjx。

最后由引理6，對于每個指標 i，都有 PCix∈ Ci+1，從而

推論1 （循環(huán) DRSM）令 C1，C2，…，CN?H為閉凸集且 Ci≠ Φ，對任意的x0∈H，以及任意的指標i，j，i，j∈ ｛1，2，…，N｝，則序列 ｛｝弱收斂到點 x，使得 PCix＝PCjx。此外，對于每個指標 j，有 PCjx