簡單約束鞍點優化問題的投影原始- 對偶算法

郭 曉, 陶 越

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

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

1 引言

考慮如下鞍點優化問題

其中X ?Rn,Y ?Rm是兩個閉凸集合, Q(x,y) 是光滑的凸– 凹函數.該模型在圖像處理,高維統計, 機器學習中有著廣泛應用.注意到鞍點問題實際上可以轉化為單調變分不等式問題, 那么求解單調變分不等式的數值方法[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是自適應步長, 由線搜索確定.該方法中, 原始變量和對偶變量共用一個步長, 且能自適應確定, 這是該方法的優點, 不必費大量時間調參.收斂性也能在較弱的條件下證明.該方法用在全變分圖像恢復問題中, 數值表現較好.

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

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

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

2 提出的方法

本節給出一個新的外梯度方法, 并分析算法的收斂性和收斂速率.結合算法(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)} 收斂于優化問題(1.1) 的鞍點(x?,y?).

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

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

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

現在考慮式(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)} 收斂于優化問題(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 數值實驗

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

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

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

易知模型(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) 李布希茲連續,可知該問題滿足假設2.1.故所提算法可以應用于問題(3.2).

記所提算法為算法1,對比算法為文獻[4]中的交替外梯度方法(AEM),可在www.unife.it/prin/software 下載, 以及算法(1.3), 按照文獻[10]建議記為LPD.計算環境如下, 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 給出了算法在兩個含有泊松噪音數據上的去模糊表現.在micro 問題中, 雖然算法1 的迭代步數多于AEM, 但發現計算時間稍微少于AEM.這說明由線搜索確定的步長在一定程度上會消耗一點時間.LPD 算法無論是迭代步數, 計算時間和相對誤差均不占優勢.在circles 問題中, 無論迭代步數和計算時間都少于AEM.LPD 方法雖然相對誤差較小, 但計算步數較多, 計算時間較長.圖1 和圖2 顯示了兩個算法恢復的效果圖, 可以看到算法基本上都能很好的恢復模糊的圖像.這也可以從表1 的評價標準相對誤差中得到, 因為相對誤差的值相差不大.為更清楚地說明算法的表現, 在圖3 中畫出了目標函數值隨計算時間的曲線圖.從曲線下降趨勢看, 算法1 在迭代的前幾步或十幾步函數值下降快于AEM, 隨后兩個算法函數值基本保持不變.表明算法1 可以更快的收斂于最優解.雖然算法LPD 的目標函數值在micro 問題中下降較快, 但它是在目標函數(3.2) 在X =Rn的情況下.由于無相關物理條件下的約束, 故其相對誤差較大.這也說明了如果有先驗知識的加入, 如非負約束, 則可能得到較好的恢復結果.最后, 和相關算法對比的數值結果表明了新方法是有效的.

4 結語

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