一種超松弛原始對偶不動(dòng)點(diǎn)算法及其應(yīng)用

黃文麗, 唐玉超, 文 萌

(1. 南昌大學(xué)數(shù)學(xué)系，南昌 330031; 2. 西安工程大學(xué)理學(xué)院，西安 710048)

0 引言

信號和圖像處理[1]、醫(yī)學(xué)圖像重建[2]和機(jī)器學(xué)習(xí)[3]等中的許多問題都可以歸結(jié)為求解下列形式的優(yōu)化問題

事實(shí)上，迭代序列(4)恢復(fù)了Micchelli 等人[14]提出的不動(dòng)點(diǎn)鄰近點(diǎn)算法(Fixed Point Algorithm Based on Proximity Operator, FP2O)。基于文獻(xiàn)[14]的理論結(jié)果，可知由(4)式定義的迭代序列{xk}在有限維Hilbert 空間中收斂到如下優(yōu)化問題的解

另一方面，Condat[24]提出并研究了如下更加一般的三個(gè)凸函數(shù)和的優(yōu)化問題

其中f、φ和L同問題(1)，h:H →(?∞,+∞]是正則下半連續(xù)凸函數(shù)。易見，當(dāng)h(x)=0 時(shí)，問題(6)退化為(1)。為求解問題(6)，Condat 提出了一種原始對偶分裂算法，并基于向前向后算子分裂算法框架，證明了所提算法的收斂性。在這里，我們給出當(dāng)h(x)=0 時(shí)，Condat 所提出的原始對偶分裂算法格式

本文工作創(chuàng)新點(diǎn)歸納如下：

1) 建立求解優(yōu)化問題(1)的不動(dòng)點(diǎn)方程。通過構(gòu)造合適的范數(shù)，證明該不動(dòng)點(diǎn)方程中的算子是平均的。從而提出具有超松弛的原始對偶不動(dòng)點(diǎn)算法；

2) 基于現(xiàn)有不動(dòng)點(diǎn)結(jié)論，證明所提算法的收斂性。同時(shí)，我們分析算法的遍歷收斂率，所得結(jié)果對于PDFP2O 算法是新的。進(jìn)一步，在對目標(biāo)函數(shù)較強(qiáng)假設(shè)條件下，證明所提算法的線性收斂率；

3) 通過將所提算法應(yīng)用于圖像復(fù)原模型，數(shù)值結(jié)果表明，當(dāng)步長參數(shù)γ固定時(shí)，松弛參數(shù){αk}越大，算法收斂越快。本文所提算法所需迭代次數(shù)少于ADMM 算法[21]、PDS 算法[24]和PDFP2O 迭代算法[7]。雖然在某些情形下，所提算法的迭代次數(shù)多于PDFP2O AM 算法[19]，但后者需要假設(shè)圖像邊界條件是周期的，而所提算法適合于任何邊界條件的圖像復(fù)原問題，從而應(yīng)用范圍更廣。

本文具體安排如下，在第1 節(jié)中，我們給出一些證明所提算法收斂性需要的定義和引理。第2 節(jié)提出一種超松弛原始對偶不動(dòng)點(diǎn)算法求解問題(1)，同時(shí)分析和證明所提算法的收斂性和遍歷收斂率，以及線性收斂率。第3 節(jié)將算法應(yīng)用于求解全變分圖像復(fù)原模型，以驗(yàn)證算法的有效性和優(yōu)越性。最后，我們對全文進(jìn)行小結(jié)。

1 預(yù)備知識

在本節(jié)中，我們將回顧一些基本定義和引理，這些可參見文獻(xiàn)[35—36]等。設(shè)H是實(shí)Hilbert 空間，定義在H上的內(nèi)積為〈·,·〉和范數(shù)為//·//。設(shè)L:H →G是非零有界線性算子，其中G是實(shí)Hilbert 空間。L?:G →H表示L的伴隨算子，滿足〈y,Lx〉=〈L?y,x〉, ?x,y ∈H。

設(shè)A:H →2H是一集值算子，我們分別用graA={(x,u)∈H×H:u ∈Ax}和ranA={u ∈H:?x ∈H,u ∈Ax}表示A的圖和值域。算子A稱為單調(diào)的，如果〈x ?y,u ?v〉 ≥0, ?(x,u),(y,v)∈graA。A稱為極大單調(diào)的，如果A是單調(diào)的且不存在單調(diào)算子B，使得B的圖包含A的圖。A稱為τ-強(qiáng)單調(diào)的，τ>0，如果

下面，我們回顧非擴(kuò)張等算子定義。

定義1[35]設(shè)C是H的一個(gè)非空子集，T:C →H，則：

1)T稱為κ-Lipschitz 連續(xù)的，如果

特別κ=1 時(shí)，T稱為非擴(kuò)張的；κ ∈(0,1)，T稱為壓縮的；

2)T稱為σ-余強(qiáng)制的，σ>0，如果

特別當(dāng)σ=1 時(shí)，T稱為固定非擴(kuò)張的；

3)T稱為α-平均的，α ∈(0,1)，如果存在非擴(kuò)張算子S，使得

f的次微分?f定義為

設(shè)f ∈Γ0(H), λ>0, λf的鄰近算子定義為

則有如下結(jié)論成立：

1){xk}關(guān)于Fix(T)是Fej′er 單調(diào)的，即//xk+1?x?//≤//xk ?x?//, ?x?∈Fix(T)；

2){Txk ?xk}強(qiáng)收斂于0；

3){xk}弱收斂于Fix(T)。

為建立本文算法的線性收斂率，我們將利用經(jīng)典的Banach 壓縮映射原理。

引理3(Banach 壓縮映射原理)[35]設(shè)(X,d)是完備度量空間，設(shè)T:X →X是θ-Lipschitz 連續(xù)算子，其中θ ∈(0,1)。定義Picard 迭代序列如下：任取x0∈X，定義xk+1=Txk，則存在x?∈X，使得以下結(jié)論成立：

和余弦等式

以及K是H上的一自伴隨強(qiáng)正算子。

這兩個(gè)結(jié)論在我們的證明中同樣起著重要的作用。

2 超松弛原始對偶不動(dòng)點(diǎn)算法收斂性和收斂率分析

為了求解問題(1)，我們首先給出超松弛原始對偶不動(dòng)點(diǎn)算法的算法格式如下。

算法1 超松弛原始對偶不動(dòng)點(diǎn)算法(Or PDFP2O)

Require: 任取x0 ∈H, v0 ∈G，選取λ ∈(0, 1//L//2)，γ ∈(0,2β)，以及αk ∈[0, 4β?γ 2β ]。當(dāng)k =0,1,2,···，計(jì)算(i) ～vk+1 =prox λγ φ?((I ?λLL?)vk+ λγ L(xk ?γ?f(xk)));(ii) ～xk+1 =xk ?γ?f(xk)?γL?～vk+1.(iii) vk+1 =(1 ?αk)vk+αk～vk+1;(iv) xk+1 =(1 ?αk)xk+αk～xk+1.當(dāng)滿足給定終止條件時(shí)，停止；否則，繼續(xù)。Ensure: xk+1, vk+1.

根據(jù)Moreau 恒等式，設(shè)f ∈Γ0(H)，對任意λ>0 和x ∈H，有

我們可知算法1 中(i)等價(jià)于

以及算法1 中(ii)等價(jià)于

定義T2:G×H →H為

進(jìn)一步，定義算子T:G×H →G×H為

引理4 設(shè)λ> 0, γ> 0，若(v?,x?)是算子T的不動(dòng)點(diǎn)，則x?是問題(1)的解。反之，若x?是問題(1)的解，則存在v?∈G，使得(v?,x?)是T的不動(dòng)點(diǎn)。

證明 由T的定義知，若(v?,x?)是T的不動(dòng)點(diǎn)，那么有

根據(jù)(13)式和(14)式，我們可得

于是，我們有

即x?滿足問題(1)的一階優(yōu)化條件，從而是該問題的解。

反過來，若x?是問題(1)的解，由一階優(yōu)化條件，我們有

根據(jù)(20)式，有v?=T1(v?,x?)，進(jìn)一步用T1(v?,x?)替代(18)式中v?，則有x?=T2(v?,x?)，從而(v?,x?)是T的不動(dòng)點(diǎn)。

2.1 收斂性分析

下面，我們通過在G×H空間中定義合適的范數(shù)，證明由(12)式定義的算子T不僅是非擴(kuò)張的，并且是一個(gè)平均算子。為了表達(dá)簡潔，我們引進(jìn)和定義一些符號，記

根據(jù)(12)式，并結(jié)合(24)式和(25)式，可得

又

其中(28)式中第一個(gè)不等式由?f是β-余強(qiáng)制算子得到，第二個(gè)不等式由Young 不等式得到。將(28)式代入(27)式，我們有

下面，我們證明算法1 的收斂性。

設(shè)序列{vk}和{xk}由算法1 生成，(v?,x?)∈Fix(T)，則有下列結(jié)論成立：

證明 根據(jù)算子T的定義，我們可知由算法1 定義的迭代序列{vk}和{xk}等價(jià)于

從而，根據(jù)引理2，我們可得結(jié)論1)～3)成立。

2.2 收斂率分析

在本小節(jié)中，我們將分析算法1 的遍歷收斂率和線性收斂率。首先我們證明遍歷收斂率。為此，我們給出優(yōu)化問題(1)的鞍點(diǎn)問題形式如下

由G(x,v)關(guān)于x的凸性和v的凹性，并結(jié)合Jensen 不等式，即得(34)式。

自然地

那么(34)式成立。

由(39)式，我們可得

根據(jù)Young 不等式，我們有

將(41)式代入(40)式，可得

(42)式中第二個(gè)不等號由?f是β-余強(qiáng)制的推得，第三個(gè)不等號由條件(A1)和(A2)推得。因此

根據(jù)定理3 的結(jié)論，顯然有ρ< 1，也就是說算子T是壓縮的。下面，我們給出算法1 的線性收斂率結(jié)果。

3 數(shù)值實(shí)驗(yàn)

在本節(jié)中，我們應(yīng)用所提出的算法1 求解經(jīng)典的L2+TV圖像復(fù)原模型

其中K ∈Rm×n表示模糊核矩陣，b ∈Rm×n表示觀測圖像，μ> 0 表示正則參數(shù)，以及//x//T V表示全變分。注意到全變分//x//T V可以表示為一凸函數(shù)φ和差分矩陣L復(fù)合的形式，即//x//T V=φ(Lx)，詳細(xì)可參見文獻(xiàn)[14,38]等。從而模型(44)是問題(1)的特殊情形。

本節(jié)所有的實(shí)驗(yàn)是在聯(lián)想筆記本E4430 完成的，其中CPU 2.3GHZ 和內(nèi)存4GB。實(shí)驗(yàn)編程軟件為Matlab R2014a。我們應(yīng)用Matlab 函數(shù)fspecial 和imfilter 生成模糊圖像，具體定義如下

其中η表示加入高斯噪聲的標(biāo)準(zhǔn)差，alpha 表示平均核的大小，x表示原始圖像，以及b表示觀測圖像，實(shí)驗(yàn)測試圖像見圖1。

圖1 測試圖像

實(shí)驗(yàn)1 在實(shí)驗(yàn)1 中，我們說明松弛參數(shù)對算法1 收斂速度的影響。對比原始PDFP2O算法2，本文提出的算法1 提供了更大的松弛參數(shù)選擇范圍。特別地，算法1 允許松弛參數(shù)大于1。因此，在接下來的實(shí)驗(yàn)中，我們通過固定步長參數(shù)γ，根據(jù)松弛參數(shù)αk的取值范圍，選擇不同αk，報(bào)告所得數(shù)值結(jié)果，詳細(xì)參數(shù)選取規(guī)則見表1。

表1 算法1 中步長參數(shù)γ 和松弛參數(shù)αk 的選取

根據(jù)文獻(xiàn)[14]，對于全變分一階差分矩陣L，知//L//2≈8，因此，我們?nèi)ˇ?。此外，在本實(shí)驗(yàn)中β=1。我們選取圖1中的文本圖像作為測試圖像。在實(shí)驗(yàn)中，我們?nèi)∑骄说拇笮ˇ? 3 以及η= 0.01。我們選取正則參數(shù)μ= 0.001。為評估復(fù)原圖像的質(zhì)量，我們選擇信噪比(SNR)作為評價(jià)指標(biāo)，其定義如下

這里x和xr分別表示原始圖像和恢復(fù)所得圖像。同時(shí)，我們給定算法的迭代停止準(zhǔn)則為

這里ε是一給定正數(shù)，所得數(shù)值結(jié)果見表2。

表2 不同步長參數(shù)γ 和松弛參數(shù)αk 的數(shù)值結(jié)果

續(xù)表

從表2 可以看出，當(dāng)步長參數(shù)γ固定，松弛參數(shù)越大，算法收斂越快。當(dāng)γ取值較保守時(shí)(γ ≤1)，松弛參數(shù)αk> 1(超松弛情形)顯然比松弛參數(shù)αk< 1 算法收斂更快。當(dāng)γ接近理論上界時(shí)，隨著求解精度的增高，超松弛參數(shù)算法所需迭代次數(shù)少于松弛參數(shù)αk=1 的情形。因此，在接下來的實(shí)驗(yàn)中，我們選取γ=1.9 和αk=1.04。

實(shí)驗(yàn)2 在實(shí)驗(yàn)2 中，我們比較所提迭代算法1 與現(xiàn)有其他算法，包括ADMM 算法[21]、PDS 算法[24]、PDFP2O 算法[7]和PDFP2O AM 算法[19]。我們選取圖1 中的四幅圖像作為測試圖像，我們?nèi)煞N不同大小的平均核分別是α= 3 和α= 7，并對每幅相應(yīng)圖像分別添加均值為零，標(biāo)準(zhǔn)差為0.01 和0.05 的高斯噪聲。我們假定邊界條件為周期邊界條件，這時(shí)，對于ADMM 算法和PDFP2O AM 算法中矩陣的逆，可以通過快速Fourier 變換計(jì)算。我們調(diào)整正則參數(shù)μ以期達(dá)到最佳的圖像復(fù)原結(jié)果，相應(yīng)正則參數(shù)選取規(guī)則見表3。除了信噪比(SNR)以外，我們使用結(jié)構(gòu)相似性指數(shù)(SSIM)[39]來評估恢復(fù)圖像質(zhì)量，SSIM 具體定義如下

表3 不同噪聲水平下，最佳正則參數(shù)μ的選取規(guī)則

其中μx和μxr分別表示原始圖像和恢復(fù)所得圖像的平均灰度值，σx和σxr表示的是兩幅圖像的標(biāo)準(zhǔn)差，C1和C2為給定的非零常數(shù)。所得數(shù)值結(jié)果見表4 和表5。

從表4 和表5 可以看出，當(dāng)ε=10?8時(shí)，分別取兩種不同的平均核α=3, α=7 和噪聲水平η= 0.01，對于風(fēng)景和靜物的測試圖像，本文所提算法(算法1)比其他算法所需迭代次數(shù)更少。在其他情形下，算法1 僅次于PDFP2O AM 算法。由于PDFP2O AM 算法只在周期邊界條件下才能執(zhí)行，而本文所提算法與PDS 算法以及PDFP2O 算法可以適合于任何邊界條件的圖像復(fù)原問題，從而更具有廣泛的應(yīng)用性。為了更加直觀觀察恢復(fù)圖像，圖2 至圖5 分別展示了當(dāng)ε=10?8時(shí)，五種算法恢復(fù)所得圖像。

表4 平均核α=3 時(shí)，比較不同迭代算法所得數(shù)值結(jié)果

續(xù)表

表5 平均核α=7 時(shí)，比較不同迭代算法所得數(shù)值結(jié)果

續(xù)表

圖2 至圖5 中的第一行是模糊和噪聲圖像；第二行是由ADMM 恢復(fù)的圖像；第三行是由PDS 恢復(fù)的圖像；第四行是由PDFP2O 恢復(fù)的圖像；第五行是由PDFP2O AM 恢復(fù)的圖像；第六行是由算法1 恢復(fù)的圖像。

圖2 模糊和噪聲圖像(文本)

圖5 模糊和噪聲圖像(靜物)

圖3 模糊和噪聲圖像(人像)

圖4 模糊和噪聲圖像(風(fēng)景)

4 結(jié)論

本文提出了一種超松弛原始對偶不動(dòng)點(diǎn)算法求解兩個(gè)凸函數(shù)和的優(yōu)化問題(1)。相比于現(xiàn)有的原始對偶不動(dòng)點(diǎn)算法(2)，本文的算法允許松弛參數(shù)大于1，從而擴(kuò)大了原算法的松弛參數(shù)的選擇范圍。通過構(gòu)造合適的范數(shù)，基于不動(dòng)點(diǎn)理論，我們證明了所提算法的收斂性，同時(shí)證明了算法的遍歷收斂率。進(jìn)一步，在對目標(biāo)函數(shù)較強(qiáng)假設(shè)條件下，我們證明了算法的線性收斂率。為驗(yàn)證算法的有效性和優(yōu)越性，我們應(yīng)用于求解全變分圖像復(fù)原模型(44)，數(shù)值實(shí)驗(yàn)結(jié)果表明，超松弛參數(shù)算法優(yōu)于松弛參數(shù)小于等于1 的情形。

無論是PDFP2O 算法，還是本文提出的超松弛PDFP2O 算法(算法1)，算法的步長參數(shù)依賴于目標(biāo)函數(shù)梯度的Lipschitz 常數(shù)，當(dāng)該常數(shù)未知時(shí)，只能憑經(jīng)驗(yàn)選取步長。因此如何克服這個(gè)不足，使得算法更加方便執(zhí)行，這將是我們接下來研究的問題。