簡(jiǎn)單約束鞍點(diǎn)優(yōu)化問(wèn)題的投影原始- 對(duì)偶算法

郭 曉, 陶 越

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

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

1 引言

考慮如下鞍點(diǎn)優(yōu)化問(wèn)題

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

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

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

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

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

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

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

2 提出的方法

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

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

接下來(lái)的部分, 具體分析新方法(2.1) 產(chǎn)生的迭代序列收斂于問(wèn)題(1.1) 的鞍點(diǎn).在證明之前, 列舉需要用到的假設(shè)及投影算子的一些性質(zhì), 可在相關(guān)的文獻(xiàn)[11,12]中查到.

假設(shè)2.1存在一個(gè)常數(shù)L, 使得下面三個(gè)不等式成立

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

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

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

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

證對(duì)式(2.1) 中的第三個(gè)式子應(yīng)用引理2.1 中的性質(zhì)(ii), 對(duì)任意的y ∈Y, 可得

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

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

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

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

由Q 關(guān)于變量y 為凹函數(shù), 可知

不等式(2.8) 進(jìn)一步轉(zhuǎn)化為

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

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

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

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

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

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

證由式(2.12) 可得到

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

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

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

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

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

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

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

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

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

為了評(píng)價(jià)算法恢復(fù)圖像的質(zhì)量, 采用相對(duì)誤差(RE) 作為指標(biāo), 定義為其中 xk為算法恢復(fù)的圖像, x 為原始圖像.它能衡量算法恢復(fù)的圖像與真實(shí)圖像的接近程度.顯然,相對(duì)誤差的值越小, 圖像恢復(fù)的質(zhì)量越好.

表1 數(shù)值結(jié)果

圖1 micro 圖像恢復(fù)效果對(duì)比圖: 真實(shí)圖像, 模糊噪音圖像, AEM 恢復(fù), LPD 恢復(fù), 算法1 恢復(fù)

圖2 circles 圖像恢復(fù)效果對(duì)比圖: 真實(shí)圖像, 模糊噪音圖像, AEM 恢復(fù), LPD 恢復(fù), 算法1 恢復(fù)

圖3 目標(biāo)函數(shù)隨時(shí)間變化曲線圖.

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

4 結(jié)語(yǔ)

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