三分塊凸優(yōu)化問(wèn)題的改進(jìn)Peaceman-Rachford分裂法

劉學(xué)念,黃 甜

(1.湖北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,湖北 黃石 43500;2.山東外事職業(yè)大學(xué) 教育學(xué)院,山東 威海 264500)

0 引言

考慮如下帶有線性約束的兩分塊可分凸優(yōu)化問(wèn)題的數(shù)學(xué)模型:

(1)

其中θi∶ni→∪(+∞)(i=1,2)是閉正常函數(shù)(不一定光滑),Ai∈m×ni(i=1,2),b∈m是給定的矩陣和向量,χi∈ni(i=1,2)是非空閉凸集。假設(shè)此問(wèn)題的解集非空,則問(wèn)題(1)的增廣拉格朗日函數(shù)為:

(2)

其中λ∈m是拉格朗日乘子,β>0是罰參數(shù)。

(3)

Gabay在文獻(xiàn)[6]中指出,較ADMM相比,PR分裂法的魯棒性較差,即需要在更嚴(yán)格的條件下才能收斂。但在確保收斂前提下,它的收斂速度更快。很多學(xué)者對(duì)此加以研究,He等人[7]于2014年提出對(duì)兩個(gè)乘子迭代中加入相同的松弛因子以保證其迭代序列的嚴(yán)格收縮。于2016年,He等[8]又采取不同的步長(zhǎng)來(lái)更新拉格朗日乘數(shù),減少了算法中的迭代次數(shù)。Gu等[9]在子問(wèn)題中加入半鄰近項(xiàng),提出半鄰近PR分裂法,使該方法更加靈活。Du等人[10]于2020年通過(guò)變分不等式研究證明了帶有Bregman距離的對(duì)稱(chēng)ADMM的全局收斂性,該算法的迭代形式為:

(4)

本文主要考慮三分塊凸優(yōu)化問(wèn)題:

(5)

其中θi∶ni→∪(+∞)(i=1,2,3)是閉正常函數(shù)(不一定光滑),Ai∈m×ni(i=1,2,3),b∈m是列滿秩的矩陣和向量,Xi∈ni(i=1,2,3)是非空閉凸集。假設(shè)此問(wèn)題的解集非空。提出帶有Bregman距離的PR分裂法的改進(jìn)迭代形式為:

(6)

其中β>0,α和γ是松弛因子且α∈(0,1),γ∈(0,1-α),引入的Bregman距離函數(shù)為δ-強(qiáng)凸。本文從變分不等式的角度去研究算法(6)的全局收斂性,以及該算法在遍歷意義O(1/t)下的最壞收斂速率。

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

w*∈Ω,θ(u)-θ(u*)+(w-w*)TF(w*)≥0,?w∈Ω

(7)

根據(jù)上述定義,很容易得知映射F是單調(diào)的,也就是F滿足:

所以公式(7)可以改寫(xiě)為:

w*∈Ω,θ(u)-θ(u*)+(w-w*)TF(w)≥0,?w∈Ω

(8)

設(shè)定義變分不等式(7)的解集是Ω*,并且在問(wèn)題(5)的解集非空的情況下Ω*非空。

為了后面的分析更加方便,在此說(shuō)明幾個(gè)用到的理論。

引理1[12]設(shè)集合X∈n是一個(gè)閉凸集,θ(x)為凸函數(shù),f(x)為可微凸函數(shù),假設(shè)min{θ(x)+f(x)|x∈X}的解集非空,則:

x*∈arg min{θ(x)+f(x)|x∈X}

成立當(dāng)且僅當(dāng)

命題1[11]設(shè)ρ(x)是可微凸函數(shù),Bρ(x,y)是Bregman距離,對(duì)任意x,y∈dom(ρ)有:

1) 一般情況下,Bρ(x,y)=Bρ(y,x)是不成立的;

2)Bρ(x,y)≥0,Bρ(x,x)=0;

3)y固定時(shí),Bρ(x,y)關(guān)于x時(shí)凸的;

命題2[10]如果ρA,對(duì)于任意x,y∈dom(ρ),則有

引理2[14]對(duì)于可微凸函數(shù)σ,給定向量a,b,c,d,有:

命題3[10]對(duì)于可微凸函數(shù)ρ,ψ,φ,以下式子成立:

2 收斂性檢驗(yàn)

(9)

并定義下列矩陣:

(10)

(11)

則能得到以下結(jié)論。

(12)

(13)

(14)

(15)

(16)

聯(lián)立(13)至(16)可得引理(3)成立。

引理4 設(shè){wk}是由算法(6)產(chǎn)生的序列,則有:

(17)

接著,我們定義如下矩陣:

(18)

根據(jù)式(10)和式(11)中Q,M的定義可以得到H=QM-1.因?yàn)棣痢?0,1),γ∈(0,1-α),對(duì)稱(chēng)矩陣H的所有順序主子式均大于零,所以H為正定矩陣。

接著定義G=QT+Q-MTHM,其中:

在松弛因子α∈(0,1)范圍下,矩陣QT+Q為對(duì)稱(chēng)正定陣。

則:

(19)

由簡(jiǎn)單分析可得上述對(duì)稱(chēng)矩陣G是不定的,所以此時(shí)算法(6)的收斂結(jié)果不能由文獻(xiàn)[14]中的結(jié)果來(lái)保證,需要對(duì)矩陣G進(jìn)一步計(jì)算,矩陣G可改寫(xiě)為:

當(dāng)α∈(0,1),γ∈(0,1-α),把矩陣G分成兩部分G=G1+G2,其中

其中A2,A3是列滿秩的矩陣,則矩陣G20.再假設(shè)ψ,φ是δ-強(qiáng)凸的,并滿足δI+G1? 0,則有

(20)

定理1 設(shè){wk}是由算法(6)產(chǎn)生的序列,由(9)定義,則:

(21)

(22)

(23)

聯(lián)立(22)(23)兩式,定理(1)得證。

證明 對(duì)(20)式按k=0,1,…,n累加可得:

(24)

將上式代入式(24)就可以得到

(25)

θ(u)-θ(u∞)+(w-w∞)TF(w∞)≥0,?w∈Ω

(26)

對(duì)于{wk}的其他任意聚點(diǎn)wρ,則

所以wρ=w∞,即w∞是唯一的聚點(diǎn)。

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

本節(jié)所有的測(cè)試代碼都在MATLAB-R2020a進(jìn)行編寫(xiě),運(yùn)行環(huán)境為惠普筆記本電腦(Intel(R) Core(TM) i5-1135G7,16.0 GB)。在數(shù)值實(shí)驗(yàn)中,我們把記迭代次數(shù)記為“Ite.”,把運(yùn)行時(shí)間記為“CPU(s)”。

我們針對(duì)以下模型進(jìn)行數(shù)值實(shí)驗(yàn):

(27)

很明顯,上述最小化問(wèn)題是問(wèn)題(5)的標(biāo)準(zhǔn)表述,其中

把我們的算法應(yīng)用于(27)時(shí),產(chǎn)生的子問(wèn)題求解如下:

上述問(wèn)題可等價(jià)于

其中軟閾值shrink、算子D由下式定義

shrink(N,c)∶=sign(N)max{|N|-c,0},N∈s×n

Dc(N)∶=Udiag(shrink(∑,c))VT,N∈s×n

并且U∑VT是矩陣N的奇異值分解。

我們用所提出的改進(jìn)帶有Bregman距離的PR分裂法,即算法(6)與He等人在文獻(xiàn)[17]中提出的分裂增廣拉格朗日算法(以下簡(jiǎn)稱(chēng)SPALM)和文獻(xiàn)[18]中針對(duì)多塊的廣義Peaceman-Rachford(以下簡(jiǎn)稱(chēng)GPRSM)m取3時(shí)進(jìn)行比較,且終止條件為

其中fk表示問(wèn)題(27)第k步目標(biāo)函數(shù)的函數(shù)值。

能得到以下結(jié)果,如表1所示。

表1 算法SPALM和GPRSM的數(shù)值結(jié)果比較

從表1中可以看出,本文提出的算法在迭代步數(shù)和時(shí)間上優(yōu)于 SPALM 和GPRSM.我們?cè)趫D1中繪制了目標(biāo)函數(shù)值、X的秩、Y的稀疏度和誤差相對(duì)于迭代次數(shù)的演變。與帶有近端項(xiàng)的PRSM相比有更好的恢復(fù)效果:目標(biāo)函數(shù)值較低,X秩較低,Y稀疏度較高。這些現(xiàn)象可能表明,在追求更好的結(jié)果質(zhì)量時(shí),本文的算法比GPRSM更為可靠。此外算法和SPALM相比,目標(biāo)函數(shù)值較低,Y稀疏度偏低,X秩和誤差結(jié)果相近,但不難看出在迭代次數(shù)和時(shí)間方面,本文的算法更具有競(jìng)爭(zhēng)力?？傮w來(lái)說(shuō),本文提出的算法效果較好,因此是有意義的。

圖1 m=1 000,n=800時(shí)目標(biāo)函數(shù)值、X的低秩、Y的稀疏度和誤差與迭代步數(shù)的關(guān)系圖

4 結(jié)論

本文針對(duì)帶有線性約束的三塊可分凸優(yōu)化問(wèn)題,提出了帶有Bregman距離的Peaceman-Rachford分裂法的改進(jìn)算法,在對(duì)稱(chēng)Bregman ADMM的基礎(chǔ)上選擇不同的松弛因子更新拉格朗日乘子。當(dāng)Bregman距離函數(shù)為δ-強(qiáng)凸時(shí),從變分不等式的角度證明了該算法的全局收斂性和在遍歷情形下O(1/t)的最壞收斂速率。最后用數(shù)值實(shí)驗(yàn)初步驗(yàn)證了本文所提的算法在迭代步數(shù)和迭代時(shí)間上具有一定的優(yōu)勢(shì)。

5 致謝

感謝編輯和審稿人提供的意見(jiàn)以提高論文的質(zhì)量,特別感謝湖北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院的王陽(yáng)老師在后期工作中提供的幫助。