郭 曉, 陶 越

(1.桂林電子科技大學材料科學與工程學院, 廣西 桂林 541004)

(2.江蘇省廣播電視總臺, 江蘇 南京 210000)

1 引言

考慮如下鞍點優(yōu)化問題

其中X ?Rn,Y ?Rm是兩個閉凸集合, Q(x,y) 是光滑的凸– 凹函數.該模型在圖像處理,高維統(tǒng)計, 機器學習中有著廣泛應用.注意到鞍點問題實際上可以轉化為單調變分不等式問題, 那么求解單調變分不等式的數值方法[1?3]都可以用來求解問題(1.1).令v = (x,y)T,F(v) = (?xQ(x,y),??yQ(x,y))T, K = X × Y, 那么尋找極小 – 極大問題 (1.1) 的鞍點(x?,y?) 就可以轉換為如下形式的變分不等式問題

易知, v?是上述變分不等式的解當且僅當其滿足不定點方程v?= PK(v??α?F(v?)), 其中P 是投影算子, α>0 是步長.鑒于約束集合K 的可分結構, 不動點方程可以具體寫為

基于此, Bonettini 和Ruggiero 在文獻[4]中提出了如下外梯度方案求解問題(1.1)

其中αk是自適應步長, 由線搜索確定.該方法中, 原始變量和對偶變量共用一個步長, 且能自適應確定, 這是該方法的優(yōu)點, 不必費大量時間調參.收斂性也能在較弱的條件下證明.該方法用在全變分圖像恢復問題中, 數值表現(xiàn)較好.

此外, 問題(1.1) 有著特殊的結構可以利用.因此, 許多高效的數值算法[5?10]提了出來.特別地, 即Q(x,y) = f(x)+ Bx,y ?g(y). 當f(x) 是二次數據擬合項, g(y) 為示性函數,B 是梯度算子時, 全變分圖像恢復模型可以看作是問題(1.1) 的一個特殊形式.著名的原始– 對偶混合梯度算法(PDHG) 在文獻[5]中提了出來.該方法雖然數值表現(xiàn)良好, 但收斂性還沒被確定.隨后, 許多學者開始關注此類型算法.He 等學者在文獻[6]中證明了如果目標函數中有一個函數是強凸的, 那么PDHG 是收斂的.如果算法中的步長序列滿足一定的條件, Bonettini 等在文獻[7]中亦證明了PDHG 的收斂性.Chambolle 和Pock 在文獻[8]中對PDHG 算法進行了改進, 并得到了收斂性結論和次線性收斂速率.利用相關的不動點理論, Chen 等在文獻[9]中提出了一個原始– 對偶不動點算法.當X = Rn時, Zhang 等在文獻[10]中給出了一個固定步長的原始– 對偶方法且原始變量的步長與對偶變量的步長不同,算法描述如下:

其中β,γ >0 為步長.可以看出該方法每步都有閉示解, 子問題無需內迭代求解及矩陣求逆,適合應用于計算機斷層成像和并行磁共振成像等大規(guī)模問題上.

可以看到算法(1.2) 和(1.3) 區(qū)別在于步長的選取不同.算法(1.2) 中, 每次迭代的步長相同由線搜索確定.在大規(guī)模問題中線搜索可能會增加一些額外的計算時間.算法(1.3) 可以取不同的固定步長, 但與(1.2) 相比, 它不能有效地處理變量全有約束的鞍點問題.本文希望結合兩個算法的優(yōu)點, 給出一個新算法.結合投影算子的性質和凸分析的相關知識, 給出算法的收斂性分析及收斂速率.最后, 將所設計的算法用于含有泊松噪音的圖像恢復問題上, 給出相應的數值實驗結果.

2 提出的方法

本節(jié)給出一個新的外梯度方法, 并分析算法的收斂性和收斂速率.結合算法(1.2) 和(1.3), 一個簡單的思路是用固定步長代替算法(1.2) 中線搜索確定的步長, 以期待減少算法的計算時間, 且能處理約束情形下的問題(1.1).提出的方法形式簡單, 有如下的迭代步驟

其中β,γ >0 滿足一定的條件, 這將會在下面給出具體的說明.

接下來的部分, 具體分析新方法(2.1) 產生的迭代序列收斂于問題(1.1) 的鞍點.在證明之前, 列舉需要用到的假設及投影算子的一些性質, 可在相關的文獻[11,12]中查到.

假設2.1存在一個常數L, 使得下面三個不等式成立

引理2.1令? 為非空閉凸集, w,z ∈Rn, u ∈?.

(ii) 令G(z) 為凸可微函數,w =P?(z ?θ?G(z)), 那么下式成立

基于以上假設和引理, 下面給出算法(2.1) 的收斂性證明.

定理 2.1如果 β,γ 滿足那么新方法 (2.1) 生成的迭代序列{(xk,yk)} 收斂于優(yōu)化問題(1.1) 的鞍點(x?,y?).

證對式(2.1) 中的第三個式子應用引理2.1 中的性質(ii), 對任意的y ∈Y, 可得

同理, 令y =yk+1, 由(2.1) 中的第一個式子得到

式(2.2) 和式(2.4) 相加后下式成立

現(xiàn)在考慮式(2.1) 中的第二個式子, 利用引理2.1 中的性質(iii), 對任意的x ∈X, 有

(2.6) 和(2.7) 式相加可得

由Q 關于變量y 為凹函數, 可知

不等式(2.8) 進一步轉化為

利用Cauchy-Schwartz 不等式(2.9) 寫為

由引理2.1 中的性質(i) 知

再由假設2.1 和不等式(2.11) 得到下式

由文獻[13]的結論可證序列{(xk,yk)} 收斂于優(yōu)化問題(1.1) 的鞍點(x?,y?).

接下來分析算法(2.1) 的次線性收斂速率.為了確定算法的復雜性, 需要一些額外的記號.令 N ≥ 1 為正整數,

定理 2.2如果 β,γ 滿足那么

證由式(2.12) 可得到

對式 (2.14) 從 k =0,1,··· ,N 相加, 那么

再由函數Q(x,y) 的凸凹性和Jensen 不等式可知

結合式(2.15) 和(2.16), 易知要證的結論成立.

3 數值實驗

本節(jié)給出泊松噪音下圖像去模糊的數值表現(xiàn).令g ∈Rm是觀測數據, 每個觀測值gi由含有泊松隨機變量的(Hx+b)i期望值確定, 其中x 是原始圖像, H 可認為是采集系統(tǒng)造成的失真模糊矩陣, b ∈Rm是一個正的常數背景項.在泊松噪音的假設下, Kullback–Leibler 函數經常用來作為數據擬合項.由于問題的病態(tài)性, 選取能保持圖像邊緣的全變分[14]作為正則項.令外, 也可以增加一些物理約束, 如像素的非負性.綜上, 圖像去模糊問題轉化為如下的最優(yōu)化問題

其中(?x)i是x 在像素i 處的梯度.如果gi=0, 那么gilngi=0.

模型(3.1) 是非光滑凸優(yōu)化問題, 直接求解有一定的難度.利用全變分函數的對偶公式,可轉化為光滑的鞍點優(yōu)化問題

易知模型(3.2) 是問題(1.1) 的特殊形式, 且關于原始變量x 為凸的, 關于對偶變量y 是凹的.當Q(x,y) 由式(3.2) 定義, 其梯度表達式為?xQ(x,y) = en?HTZ(x)?1g ?α?·y, ?yQ(x,y) = α?x, 其中 en= (1,1,··· ,1)T∈ Rn, ?· 是散度算子; Z(x) 是對角矩陣, 對角元素由(Hx+b)i給定.當b0 時, 由文獻[12]中引理4.6 知?xQ(x,y) 李布希茲連續(xù),可知該問題滿足假設2.1.故所提算法可以應用于問題(3.2).

記所提算法為算法1,對比算法為文獻[4]中的交替外梯度方法(AEM),可在www.unife.it/prin/software 下載, 以及算法(1.3), 按照文獻[10]建議記為LPD.計算環(huán)境如下, Matlab版本為R2011a, 內存為2GB, 處理器為i3 的個人電腦.在兩個實驗中, 圖像分別為128×128的micro 數據和256×256 的circles 數據, 詳細可見文獻[4]的說明.背景數據項均為b=3.根據文獻 [12]知, 李布希茲常數為由此可計算出L 在兩個問題中的值分別為0.14和0.1.據此, 測試了滿足定理2.1 條件下的不同參數, 選取了恢復效果比較好的參數, 具體如下: 在第一個實驗中, 算法1 參數設置為α = 0.09, β = 1.2, γ = 3.5; 第二個實驗中, 參數設置為α=0.25, β =1.3, γ =1.6.其它兩個算法按其文章里的建議設置.三個算法的停止準則為

為了評價算法恢復圖像的質量, 采用相對誤差(RE) 作為指標, 定義為其中 xk為算法恢復的圖像, x 為原始圖像.它能衡量算法恢復的圖像與真實圖像的接近程度.顯然,相對誤差的值越小, 圖像恢復的質量越好.

表1 數值結果

圖1 micro 圖像恢復效果對比圖: 真實圖像, 模糊噪音圖像, AEM 恢復, LPD 恢復, 算法1 恢復

圖2 circles 圖像恢復效果對比圖: 真實圖像, 模糊噪音圖像, AEM 恢復, LPD 恢復, 算法1 恢復

圖3 目標函數隨時間變化曲線圖.

表1 給出了算法在兩個含有泊松噪音數據上的去模糊表現(xiàn).在micro 問題中, 雖然算法1 的迭代步數多于AEM, 但發(fā)現(xiàn)計算時間稍微少于AEM.這說明由線搜索確定的步長在一定程度上會消耗一點時間.LPD 算法無論是迭代步數, 計算時間和相對誤差均不占優(yōu)勢.在circles 問題中, 無論迭代步數和計算時間都少于AEM.LPD 方法雖然相對誤差較小, 但計算步數較多, 計算時間較長.圖1 和圖2 顯示了兩個算法恢復的效果圖, 可以看到算法基本上都能很好的恢復模糊的圖像.這也可以從表1 的評價標準相對誤差中得到, 因為相對誤差的值相差不大.為更清楚地說明算法的表現(xiàn), 在圖3 中畫出了目標函數值隨計算時間的曲線圖.從曲線下降趨勢看, 算法1 在迭代的前幾步或十幾步函數值下降快于AEM, 隨后兩個算法函數值基本保持不變.表明算法1 可以更快的收斂于最優(yōu)解.雖然算法LPD 的目標函數值在micro 問題中下降較快, 但它是在目標函數(3.2) 在X =Rn的情況下.由于無相關物理條件下的約束, 故其相對誤差較大.這也說明了如果有先驗知識的加入, 如非負約束, 則可能得到較好的恢復結果.最后, 和相關算法對比的數值結果表明了新方法是有效的.

4 結語

對帶有凸集約束的光滑鞍點優(yōu)化問題, 提出了一個簡單的原始– 對偶梯度方法.算法每步具有顯示解, 不需要內迭代求解子問題.新方法應用在全變分正則化泊松噪音圖像恢復問題上, 結果表明在計算時間上具有一定的優(yōu)勢.值得注意的是該方法也可以拓展求解其它噪音類型的圖像恢復問題.