求解三塊變量約束凸優化問題的鄰近部分平行分裂算法

申 遠, 李俊嶧

(南京財經大學 應用數學學院, 南京 210023)

0 引 言

去模糊去噪[1]、主成分分析[2]、高維統計[3]和隱變量高斯圖形模型選擇[4]的許多應用均可歸結為目標函數是三塊可分離的凸最小化模型.交替方向乘子法(ADMM)近年來在許多領域應用廣泛[5], 該算法的收斂性與計算復雜性已得到廣泛關注[6-8].因此將ADMM直接推廣到目標函數為兩個以上可分離凸函數的最小化問題, 有較強的實用價值.但研究表明, ADMM的直接擴展不一定收斂[9].

考慮如下三塊線性等式約束凸極小化問題：

(1)

其中θi:Rni→(-∞,+∞]是閉的凸函數(不一定光滑),Ai∈Rl×ni是列滿秩矩陣,b∈Rl是一個向量,χi?Rni是非空的凸集, 并且n1+n2+n3=n.問題(1)的增廣Lagrange函數為

其中β>0是罰參數.假設問題(1)的解集非空.

若將ADMM由兩塊推廣至多塊以求解模型(1), 一種解決方法是增加嚴格的假設條件, 即目標函數中部分函數是強凸的且罰參數在一定范圍內, 文獻[10-12]在不同假設條件下證明了算法的收斂性.另一種方法是對算法進行改進, 如廣義對稱ADMM(generalized symmetric ADMM, GS-ADMM)[13]和MSC-PRSM(modified strictly contractive Peaceman-Rachford splitting method)[14]算法；或加校正步驟, 如部分平行分裂算法，簡稱APCM(ADMM based prediction-correction method)[15].

APCM算法的迭代格式如下：

校正步驟為

本文在部分平行分裂算法的基礎上，提出一種鄰近部分平行分裂方法(PAPCM)，并證明其收斂性.該算法可用于求解三塊變量的線性約束凸優化問題.一方面，它的子問題像ADMM一樣易求解；另一方面，它在x3子問題的目標函數中加入了正則項，且校正步長的條件比APCM更放松.

1 預備知識

函數F:Rn?Rn即?x∈Rn,F(x)是Rn中的一個函數.若

(x-y)T(F(x)-F(y))≥0, ?x,y∈Rn,

則稱F是單調的.設Ω?Rn是非空集合, 若

‖xk+1-x‖≤‖xk-x‖, ?x∈Ω,k≥1,

則序列{xk}?Rn在Ω中被稱為Fejér單調的.

引理1[16]假設序列{xk}是關于ΩFejér單調的, 則序列{xk}是有界的, 并且序列{‖xk-x‖}對?x∈Ω收斂.

θ(x)-θ(x*)+(u-u*)TF(u*)≥0, ?u∈U,

(2)

其中

(3)

2 算法框架和全局收斂性

算法1PAPCM: 對問題(1)提出的一種鄰近部分平行分裂算法.

步驟2)(預測步驟) 利用

(4)

步驟3)(校正步驟) 利用

(5)

產生新的迭代點;

步驟4)(終止) 若

圖1 參數(γ,α)的取值范圍Fig.1 Value ranges of parameter (γ,α)

則停止；否則, 令k=k+1, 轉步驟2).

(6)

其中

(7)

(8)

所有θi是閉凸函數,Ai是列滿秩矩陣.因此, 式(2)的解集(用U*表示)是非空的.

為便于表示, 設

(9)

(10)

GD=αM.

(11)

定義

Q=α(M+MT+N+NT)-DGD,

(12)

可得

因此Q是一個正定矩陣當且僅當矩陣

引理3設序列{uk}由算法1生成, 若

(13)

成立, 則序列{vk}相對于集合V*是Fejér單調的.

由F(u)在U上的單調性和矩陣M,N的定義, 得

(15)

另一方面, 由式(5)可知

其中D由式(10)定義.再由式(12)中Q的定義, 可得

式(16)中不等式由式(15)得到, 由式(16)可知式(13)成立, 從而序列{vk}相對于集合V*是Fejér單調的.

下面建立算法1的全局收斂性.

證明: 由引理3可知, {vk}相對于V*是Fejér單調的, 因此, {vk}是有界的.此外, ?k有

(17)

對不等式(17)關于k=0,1,…求和, 得

(18)

(19)

由于式(4)中第四個恒等式、式(5)中第一個的恒等式和假設A1是滿秩的, 因此有

(20)

(21)

結合式(19),(21), 可推導出

表明u∞∈U*(v∞∈V*).

3 數值實驗

考慮求解如下三塊變量線性等式約束的二次凸優化問題:

(22)

下面用算法1求解問題(22), 并將算法1與APCM算法、MSC-PRSM算法進行比較, 驗證其計算效率.所有程序均利用MATLAB編制, 測試平臺配置為Intel Core i5-8250U CPU, 8 GB內存, Windows10操作系統和MATLAB R2017a.

2) 隨機生成系數矩陣A,B,C:A,B,C的元素取值按i.i.d.N(0,1)分布隨機生成;

3) 隨機生成向量x*,y*,z*,λ*:x*,y*,z*,λ*的元素取值按i.i.d.N(0,1)分布隨機生成;

4) 通過滿足的KKT(Karush-Kuhn-Tucker)條件

Mx+q-ATλ=0,Ly+p-BTλ=0,Nz+v-CTλ=0,

可得向量q,p,v;

5) 通過Ax+By+Cz=b得到右端項b.

在算法開始時對3個系數矩陣做一次分解, 以后每次子問題只需求解系數矩陣為上(下)三角矩陣的線性方程組兩次, 從而降低了子問題的計算量.取

作為停機準則.測試幾組不同(m,n1,n2,n3)設置下, 隨機生成10個問題, 并對計算結果取平均值.最后, 將3種算法的數值結果進行比較, 不同算法的數值結果列于表1.

表1 MSC-PRSM算法、APCM算法和算法1的數值實驗比較結果

由表1可見, 算法1平均每次計算迭代步數比MSC-PRSM算法約少49.67%, 計算時間約少45.85%；算法1平均每步計算迭代次數比APCM算法約少36.86%, 計算時間約少33.30%.可見帶隨機步長的算法1比MSC-PRSM算法和APCM算法更高效, 并且隨著問題規模的增長, 算法1的計算時間增長相對較慢, 表明算法1的計算效率有更好的尺度適應性.例如, 設置的問題(300,200,200,200)與(2 000,1 000,1 000,1 000)結果相比, APCM算法的計算時間約增長了148倍, 而算法1只增長了約97倍, 說明算法1更適合處理大規模問題.實驗結果表明, 與MSC-PRSM算法、APCM算法相比, 算法1的計算效率更高且具有更好的尺度適應性.

綜上所述, 本文在線性約束三塊變量凸優化問題部分平行分裂算法的校正步驟中選取不同步長參數的基礎上, 提出了一種鄰近部分平行分裂算法(PAPCM).該算法在預測步驟上一個原始子問題的目標函數中加入正則項, 校正步長的條件比APCM算法更放松, 并給出了相應的收斂性證明.數值實驗結果表明, 在求解帶有三塊變量的結構型凸優化問題時, 算法1的計算效率明顯優于MSC-PRSM算法和APCM算法.