胡立亮， 方長杰

（重慶郵電大學 理學院，重慶400065）

本文考慮具有線性等式或不等式約束的強凸極小化模型，即求解下列問題：

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

是閉凸集.在問題（1）中的目標函數(shù)f（x）被視為給定的黑匣子［1］，因此強凸系數(shù)σ 是不可計算的.假定問題（1）的目標函數(shù)是強凸的，因為這些模型在求解一些稀疏或低秩優(yōu)化模型等領域中有著廣泛的應用，參見文獻［2 -3］.對于原始問題（1），其Lagrange函數(shù)為

其中λ∈Rm是Lagrange乘子.令

那么，問題（1）的對偶問題為

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

稱點（x*，λ*）是L（x，λ）的鞍點，即

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

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

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

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

1 預備知識

下面介紹兩個引理.

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

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

（ii）

其中

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

2 主要結果

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

算法2.1

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

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

和

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

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

就得到（12）式滿足.于是，至少當

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

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

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

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

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

因此

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

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

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

結合（16）和（17）式有

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

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

和

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

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

從而（14）式成立.

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

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

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

其中（x*，λ*）是L（x，λ）的一個鞍點.

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

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

因此，

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

從而（26）式成立.

3 數(shù)值實驗

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

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

且CTol≤10-2.

測試了2 張圖片，如圖1 所示，圖1（a）：128 ×128，圖1（b）：256 ×256.觀測圖像c 可表示為c ＝Kˉx+ρr，其中ˉx表示原始圖片，r 表示服從標準正態(tài)分布的隨機向量，ρ 表示高斯噪聲的級別.使用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）來度量去噪后圖片的質量，其定義如下：

其中

進一步，相對誤差的“Rel”定義如下：

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

表1 測試圖1（a）的數(shù)值實驗結果Tab. 1 The numerical results of testing figure 1（a）

表2 測試圖1（b）的數(shù)值實驗結果Tab. 2 The numerical results of testing figure 1（b）

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

圖2 圖1（a）的原始圖片、噪聲圖片、UA算法恢復圖像和InUA算法恢復的圖像，模糊核尺寸為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算法恢復圖像和InUA算法恢復的圖像，模糊核尺寸為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 與文獻［16］中的PDHG方法和文獻［6］中的CP方法進行比較.表3 給出了在前20 次迭代內3 個算法所用的時間和PSNR 值.另外，給出了當Ksize ＝21時，3 個算法的PSNR值得變化趨勢圖（圖4）.從圖4 可以看出，在運行時間比較接近的情況下，算法2.1（InUA）的PSNR 值更高；同時，從圖4 可以看出，的算法相對穩(wěn)定，而PDHG 方法在處理模糊程度較高的模糊圖像（如ρ ＝3）時，其PSNR值有向下趨勢的，即處理能力逐漸下降.

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

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