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

申 遠(yuǎn), 李俊嶧

(南京財經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院, 南京 210023)

0 引 言

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

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

(1)

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

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

若將ADMM由兩塊推廣至多塊以求解模型(1), 一種解決方法是增加嚴(yán)格的假設(shè)條件, 即目標(biāo)函數(shù)中部分函數(shù)是強(qiáng)凸的且罰參數(shù)在一定范圍內(nèi), 文獻(xiàn)[10-12]在不同假設(shè)條件下證明了算法的收斂性.另一種方法是對算法進(jìn)行改進(jìn), 如廣義對稱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算法的迭代格式如下：

校正步驟為

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

1 預(yù)備知識

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

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

則稱F是單調(diào)的.設(shè)Ω?Rn是非空集合, 若

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

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

引理1[16]假設(shè)序列{xk}是關(guān)于ΩFejér單調(diào)的, 則序列{xk}是有界的, 并且序列{‖xk-x‖}對?x∈Ω收斂.

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

(2)

其中

(3)

2 算法框架和全局收斂性

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

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

(4)

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

(5)

產(chǎn)生新的迭代點;

步驟4)(終止) 若

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

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

(6)

其中

(7)

(8)

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

為便于表示, 設(shè)

(9)

(10)

GD=αM.

(11)

定義

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

(12)

可得

因此Q是一個正定矩陣當(dāng)且僅當(dāng)矩陣

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

(13)

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

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

(15)

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

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

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

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

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

(17)

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

(18)

(19)

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

(20)

(21)

結(jié)合式(19),(21), 可推導(dǎo)出

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

3 數(shù)值實驗

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

(22)

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

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

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

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個系數(shù)矩陣做一次分解, 以后每次子問題只需求解系數(shù)矩陣為上(下)三角矩陣的線性方程組兩次, 從而降低了子問題的計算量.取

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

表1 MSC-PRSM算法、APCM算法和算法1的數(shù)值實驗比較結(jié)果

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

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