凸優化問題的慣性Uzawa 方法

胡立亮， 方長杰

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

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

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

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

其中λ∈Rm是Lagrange乘子.令

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

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

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

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

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

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

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

1 預備知識

下面介紹兩個引理.

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

（i）H（λ）是連續可微的凹函數；

（ii）

其中

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

2 主要結果

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

算法2.1

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

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

和

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

在（12）式中，根據引理1.1（iii），只要

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

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

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

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

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

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

因此

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

類似地，根據（9）式有

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

結合（16）和（17）式有

根據（11a）式有

根據（11b），又可以得到

和

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

因此，根據（20）～（22）式有

從而（14）式成立.

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

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

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

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

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

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

因此，

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

從而（26）式成立.

3 數值實驗

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

其中，K，D∈Rn×n，c，l，u∈Rn，μ ＞0.該模型是求解具有盒約束的圖像去模糊問題，其中x 是待恢復的數字圖像的向量表示，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 表示服從標準正態分布的隨機向量，ρ 表示高斯噪聲的級別.使用MATLAB代碼：K ＝fspecial（‘average'，Ksize）和C ＝imfilter（X，K，‘circular'，‘conv'）+ρ*randn｛m，n｝由不同大小的模糊核產生的模糊圖像，其中Ksize表示模糊核的尺寸，X表示原始圖片，C表示觀察圖像.

圖1 原始圖片Fig. 1 Original picture

用峰值信噪比PSNR（dB）來度量去噪后圖片的質量，其定義如下：

其中

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

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

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

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

3.2 圖像去噪 本節將考察本文的方法在圖像去噪中的應用.結果主要基于表1 和表2 中的數據.這些數據結果表明，提出的算法能夠得到比文獻［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 與其他現有方法的比較 本節將算法2.1 與文獻［16］中的PDHG方法和文獻［6］中的CP方法進行比較.表3 給出了在前20 次迭代內3 個算法所用的時間和PSNR 值.另外，給出了當Ksize ＝21時，3 個算法的PSNR值得變化趨勢圖（圖4）.從圖4 可以看出，在運行時間比較接近的情況下，算法2.1（InUA）的PSNR 值更高；同時，從圖4 可以看出，的算法相對穩定，而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