凸優(yōu)化問(wèn)題的慣性Uzawa 方法

胡立亮， 方長(zhǎng)杰

（重慶郵電大學(xué) 理學(xué)院，重慶400065）

本文考慮具有線性等式或不等式約束的強(qiáng)凸極小化模型，即求解下列問(wèn)題：

其中，f：Rn→R 是σ -強(qiáng)凸但不必要光滑函數(shù)，強(qiáng)凸系數(shù)σ ＞0 未知，

是閉凸集.在問(wèn)題（1）中的目標(biāo)函數(shù)f（x）被視為給定的黑匣子［1］，因此強(qiáng)凸系數(shù)σ 是不可計(jì)算的.假定問(wèn)題（1）的目標(biāo)函數(shù)是強(qiáng)凸的，因?yàn)檫@些模型在求解一些稀疏或低秩優(yōu)化模型等領(lǐng)域中有著廣泛的應(yīng)用，參見(jiàn)文獻(xiàn)［2 -3］.對(duì)于原始問(wèn)題（1），其Lagrange函數(shù)為

其中λ∈Rm是Lagrange乘子.令

那么，問(wèn)題（1）的對(duì)偶問(wèn)題為

其中，如果Ax ＝b，則Λ ＝Rm.如果Ax≤b，則Λ ＝.設(shè)點(diǎn)（x*，λ*）∈X × Λ 是Lagrange 函數(shù)L（x，λ）的鞍點(diǎn).因此，點(diǎn)（x*，λ*）∈X×Λ滿足

稱點(diǎn)（x*，λ*）是L（x，λ）的鞍點(diǎn)，即

Uzawa方法是求解L（x，λ）的鞍點(diǎn)問(wèn)題的最基本方法［4］.利用Uzawa 方法求解問(wèn)題（1），可以得到下面迭代算法：

其中，τ ＞0 表示迭代步長(zhǎng)，‖·‖表示一般的2 -范數(shù).由于Uzawa方法在不同的領(lǐng)域中所起的重要作用，對(duì)Uzawa方法的研究吸引了許多學(xué)者的廣泛關(guān)注［5-6］.慣性型方法起源于含摩擦重球系統(tǒng)（HBF）的隱式離散化方法，其主要特點(diǎn)是每個(gè)新的迭代點(diǎn)依賴于前兩次迭代［7］.隨后，將該慣性技術(shù)推廣到求解極大單調(diào)算子的包含問(wèn)題［8］.近年來(lái)，慣性類型算法的研究越來(lái)越受到人們的關(guān)注；例如，慣性向前-向后分裂算法［9］，慣性Douglas -Rachford分裂算法［10］，慣性乘子交替方向法（inertial ADMM）［11］，變分不等式的慣性型方法［12］等.關(guān)于凸優(yōu)化問(wèn)題在圖像去噪中的應(yīng)用，可以參考文獻(xiàn)［6，13 -16］及其參考文獻(xiàn).

受上述研究工作的啟發(fā)，提出了求解凸優(yōu)化問(wèn)題（1）的如下慣性Uzawa方法：

其中，PΛ（·）表示在集合Λ上的投影.

1 預(yù)備知識(shí)

下面介紹兩個(gè)引理.

引理1.1［17］設(shè)f（x）為σ-強(qiáng)凸函數(shù)（其中σ未知），H（λ）為（3）式所定義，則有：

（i）H（λ）是連續(xù)可微的凹函數(shù)；

（ii）

其中

引理1.2［14］設(shè)C 是Rn中的一個(gè)非空閉凸子集，則

2 主要結(jié)果

在這一節(jié)中，首先給出求解問(wèn)題（1）的如下慣性Uzawa算法：

算法2.1

步驟0：任取λ0∈Λ，τ0＞0，αk≥0（k ＝1，2，...）及x0∈Rn.

步驟k：更新（λk，xk，τk）使其滿足

和

注2.1 根據(jù)（8）式，很容易看出（11a）式可以改寫(xiě)為

在（12）式中，根據(jù)引理1.1（iii），只要

就得到（12）式滿足.于是，至少當(dāng)

不等式（12）是滿足的，即｛τk｝存在上界.在算法2.1中，任意給定正數(shù)τ0，在每次外循環(huán)中內(nèi)嵌一個(gè)內(nèi)循環(huán)用于更新τk，通過(guò)有限次減小τk，必定能夠使得τ（i）k滿足（12）式，并令τk＝τ（i）k，i ＝1，2，….因此，根據(jù)算法2.1 得到的序列｛τk｝是有界的，即對(duì)任意整數(shù)k，

注2.2 現(xiàn)在，比較下算法2.1 與文獻(xiàn)［15］中的算法1.首先，算法中初始迭代點(diǎn)x0∈Rn是任意選取的，而文獻(xiàn)［15］中，選擇初始點(diǎn)x0為目標(biāo)函數(shù)為L(zhǎng)（·，λ）極小化模型的最優(yōu)解；其次，與文獻(xiàn)［15］的算法1 相比，增加了慣性項(xiàng)，參見(jiàn)（6b）；此外，非負(fù)數(shù)αk（k ＝1，2，…）可以任意選擇；參見(jiàn)算法2.1 中的（11b）.此外，得到了與文獻(xiàn)［15］的方法相同的收斂速度；同時(shí)，通過(guò)數(shù)值實(shí)驗(yàn)，驗(yàn)證了所提出方法的有效性.

引理2.1 假設(shè)｛（xk，λk）｝是由算法2.1 產(chǎn)生的序列對(duì)，則

其中xλ由（9）式所定義，λ∈Λ.

證明 根據(jù)（11c）有，存在yk-1∈?f（xk-1）使得

因此

其中第一個(gè)不等式根據(jù)f（x）的凸性，第二個(gè)不等式根據(jù)（15）式，而最后一個(gè)不等式是根據(jù)（12）式.

類似地，根據(jù)（9）式有

其中yλ∈?f（xλ）.因此

結(jié)合（16）和（17）式有

根據(jù)（11a）式有

根據(jù)（11b），又可以得到

和

在（19）式中令λ ＝λk-1有

因此，根據(jù)（20）～（22）式有

從而（14）式成立.

注2.3 如果在（23）式中取λ ＝λk-1，則有

這說(shuō)明算法2.1 產(chǎn)生的序列｛L（xk，λk）｝是單調(diào)非減的.

定理2.1 假設(shè)序列對(duì)（xk，λk）由算法2.1 所產(chǎn)生，則

其中（x*，λ*）是L（x，λ）的一個(gè)鞍點(diǎn).

證明 根據(jù)鞍點(diǎn)的定義，左邊第一個(gè)不等式顯然成立.現(xiàn)在證明第二個(gè)不等式.在（25）中取k ＝n，根據(jù)｛τk｝的有界性（參見(jiàn)（13）式）有

那么，序列｛L（xn，λn）-L（x*，λ*）｝單調(diào)遞增.在（14）式中，令xλ＝x*，λ ＝λ*，k ＝n有

因此，

根據(jù)｛L（xn，λn）-L（x*，λ*）｝的單調(diào)性和（27）式有

從而（26）式成立.

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

在這一節(jié)中，將提供一些數(shù)值實(shí)驗(yàn)來(lái)驗(yàn)證算法的有效性.這些數(shù)值都是用Matlab 在CPU 型號(hào)為Inter（R）I5 -5200U 的筆記本電腦上運(yùn)行的結(jié)果，Matlab版本為5.5.0.197613（R2015A）SP1.It表示迭代次數(shù)，CPU表示運(yùn)行時(shí)間，Tol表示迭代停止條件，由（30）式所定義，PSNR 表示峰值信噪比，該指標(biāo)用于衡量圖像恢復(fù)的質(zhì)量，由（31）式所定義，Rel表示相對(duì)誤差，用以衡量圖像恢復(fù)質(zhì)量的準(zhǔn)確度，由（32）式定義.考慮一個(gè)具有盒約束的圖像去模糊模型并應(yīng)用算法2.1 求解下列約束線性最小二乘問(wèn)題［15］

其中，K，D∈Rn×n，c，l，u∈Rn，μ ＞0.該模型是求解具有盒約束的圖像去模糊問(wèn)題，其中x 是待恢復(fù)的數(shù)字圖像的向量表示，K是模糊算子（積分算子），c是模糊圖像的矢量表示，l、u 分別是像素值的上下界.假設(shè)N（K）∩N（D）＝｛0｝，其中N（·）表示零空間，重寫(xiě)問(wèn)題（28）得到

且CTol≤10-2.

測(cè)試了2 張圖片，如圖1 所示，圖1（a）：128 ×128，圖1（b）：256 ×256.觀測(cè)圖像c 可表示為c ＝Kˉx+ρr，其中ˉx表示原始圖片，r 表示服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)向量，ρ 表示高斯噪聲的級(jí)別.使用MATLAB代碼：K ＝fspecial（‘a(chǎn)verage'，Ksize）和C ＝imfilter（X，K，‘circular'，‘conv'）+ρ*randn｛m，n｝由不同大小的模糊核產(chǎn)生的模糊圖像，其中Ksize表示模糊核的尺寸，X表示原始圖片，C表示觀察圖像.

圖1 原始圖片F(xiàn)ig. 1 Original picture

用峰值信噪比PSNR（dB）來(lái)度量去噪后圖片的質(zhì)量，其定義如下：

其中

進(jìn)一步，相對(duì)誤差的“Rel”定義如下：

3.1 所提出算法有效性的數(shù)值結(jié)果 在表1、表2中，UA和InUA 分別表示文獻(xiàn)［15］中的算法1 和本文算法2.1，Tot表示步長(zhǎng)τk調(diào)整的次數(shù).表1 為圖1（a）圖像的測(cè)試結(jié)果，其參數(shù)選擇如下：τ0＝1.0，λ0＝0，αk＝1.8，η ＝3，測(cè)試Ksize分別為11、17、23 和25 的不同情形下的模糊圖像.表2 為圖1（b）圖像的測(cè)試結(jié)果，參數(shù)設(shè)定為：τ0＝0. 9，λ0＝0，αk＝1.0，η ＝3，測(cè)試Ksize分別為15、19、21和25 的不同情形下的模糊圖像.

表1 測(cè)試圖1（a）的數(shù)值實(shí)驗(yàn)結(jié)果Tab. 1 The numerical results of testing figure 1（a）

表2 測(cè)試圖1（b）的數(shù)值實(shí)驗(yàn)結(jié)果Tab. 2 The numerical results of testing figure 1（b）

3.2 圖像去噪 本節(jié)將考察本文的方法在圖像去噪中的應(yīng)用.結(jié)果主要基于表1 和表2 中的數(shù)據(jù).這些數(shù)據(jù)結(jié)果表明，提出的算法能夠得到比文獻(xiàn)［15］中的算法1 更好的恢復(fù)圖像的質(zhì)量（即更高的PSNR值）.

圖2 圖1（a）的原始圖片、噪聲圖片、UA算法恢復(fù)圖像和InUA算法恢復(fù)的圖像，模糊核尺寸為11Fig. 2 Original image，noise image，UA algorithm restored image and InUA algorithm restored image of Fig. 1（a），the size of blurred core is 11

圖3 圖1（b）的原始圖片、噪聲圖片、UA算法恢復(fù)圖像和InUA算法恢復(fù)的圖像，模糊核尺寸為15Fig. 3 Original image，noise image，UA algorithm restored image and InUA algorithm restored image of Fig. 1（b），the size of blurred core is 15

3.3 與其他現(xiàn)有方法的比較 本節(jié)將算法2.1 與文獻(xiàn)［16］中的PDHG方法和文獻(xiàn)［6］中的CP方法進(jìn)行比較.表3 給出了在前20 次迭代內(nèi)3 個(gè)算法所用的時(shí)間和PSNR 值.另外，給出了當(dāng)Ksize ＝21時(shí)，3 個(gè)算法的PSNR值得變化趨勢(shì)圖（圖4）.從圖4 可以看出，在運(yùn)行時(shí)間比較接近的情況下，算法2.1（InUA）的PSNR 值更高；同時(shí)，從圖4 可以看出，的算法相對(duì)穩(wěn)定，而PDHG 方法在處理模糊程度較高的模糊圖像（如ρ ＝3）時(shí)，其PSNR值有向下趨勢(shì)的，即處理能力逐漸下降.

表3 不同尺寸下PSNR值和運(yùn)行時(shí)間的比較Tab. 3 Comparison of PSNR value and running time under different sizes

圖4 20 次迭代，PSNR值曲線圖Fig. 4 PSNR value curve by 20 iterations