一種求解3塊變量線性約束凸優(yōu)化問題的新鄰近部分平行分裂算法

王鈺淇， 申 遠(yuǎn)

(南京財(cái)經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院， 江蘇 南京 210023)

0 引言

討論如下可分離為3塊變量的線性約束凸優(yōu)化問題：

(1)

其中θi:Rni→(-∞,+∞)為凸函數(shù)(不一定光滑)；Ai∈Rl×ni為滿秩矩陣；b∈Rl為列向量；Xi?Rni為非空閉凸集；n1+n2+n3=n.

求解可分離為2塊變量的線性約束凸優(yōu)化問題一般使用交替方向乘子法(ADMM)，相較于求解該類問題的經(jīng)典算法——增廣Lagrange乘子法，ADMM更加高效.該算法利用了問題的可分離結(jié)構(gòu)，將迭代步驟分解為多個(gè)規(guī)模較小的子問題分別求解，并在所有子問題求解之后更新對(duì)偶變量(乘子).當(dāng)問題只可分離為2塊變量時(shí)，ADMM可以保證收斂性.

當(dāng)求解3塊及以上變量問題時(shí)，我們稱ADMM為直接擴(kuò)展的交替方向乘子法(EADMM).在求解實(shí)際問題時(shí)EADMM有較高的計(jì)算效率，例如線性相關(guān)圖像對(duì)齊[1]；給定矩陣的低秩和稀疏分量恢復(fù)[2];基追蹤、穩(wěn)健主成分分析和潛變量高斯圖形模型選擇[3]等.在大多數(shù)數(shù)值試驗(yàn)中EADMM表現(xiàn)出收斂性，并且數(shù)值表現(xiàn)較好.但已知EADMM在理論上無法保證收斂[4].目前主要有兩類方法可使算法收斂，一類是在不改變算法的前提下增加其他假設(shè)條件，包括但不限于：設(shè)目標(biāo)函數(shù)中含有一個(gè)強(qiáng)凸的函數(shù)，并適當(dāng)限制懲罰參數(shù)[5]；設(shè)目標(biāo)函數(shù)為若干個(gè)沒有耦合變量的凸函數(shù)之和，并且所涉及的函數(shù)具有強(qiáng)凸性[6].另一類是針對(duì)EADMM算法本身進(jìn)行改造，包括但不限于：基于ADMM，在優(yōu)化問題的目標(biāo)函數(shù)上加一個(gè)特殊的鄰近項(xiàng)[7]；對(duì)于目標(biāo)函數(shù)為二次函數(shù)的特殊多塊優(yōu)化模型，提出一種基于舍爾補(bǔ)的鄰近ADMM[8]；對(duì)迭代后的變量使用高斯回代法進(jìn)行校正[9]；利用定制PPA策略逐塊改造ADMM，并平行計(jì)算部分子問題[10]；基于ALM平行計(jì)算所有子問題，并且校正步驟需計(jì)算最優(yōu)步長[11]；將變量分為兩組，并在兩組之間增加一次乘子更新，同時(shí)擴(kuò)大參數(shù)范圍[12]；在部分子問題的求解過程中不全部使用最新迭代所得的變量，且增加延拓以保證收斂[13].更多可參考文獻(xiàn)[14].

本文提出新算法——基于ADMM的變化預(yù)測校正算法(VAPCM).

VAPCM的迭代步驟為

(2)

其中，Lβ(x1,x2,x3,λ)為問題的增廣拉格朗日函數(shù)

(3)

β>0為懲罰參數(shù).

VAPCM的校正步驟為

(4)

與傳統(tǒng)的順序計(jì)算方法相比，將第2、3個(gè)子問題同時(shí)計(jì)算，最多可能節(jié)約33%的計(jì)算時(shí)間.VAPCM中原始變量與對(duì)偶變量使用不同的校正步長，因此步長范圍更為放松，而更合理的步長設(shè)置可能會(huì)有更快的收斂速度.接著提出的新算法在此基礎(chǔ)之上對(duì)第2、3個(gè)子問題添加鄰近項(xiàng)，并對(duì)第2個(gè)原變量的迭代項(xiàng)進(jìn)行校正.

下面，第1節(jié)介紹了一些分析所需的預(yù)備知識(shí)，第2節(jié)介紹了新算法的框架和算法的收斂性，第3節(jié)則是對(duì)新算法進(jìn)行數(shù)值實(shí)驗(yàn)，第4節(jié)為整篇文章的總結(jié).

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

首先，我們給出一些分析中將會(huì)用到的記號(hào)和基本性質(zhì).

函數(shù)f:Rn→(-∞,+∞)，其定義域?yàn)?/p>

domf:={x∈Rn|f(x)<+∞}.

假如對(duì)任意的x′,x∈domf，有下式成立

f(μx′+(1-μ)x)≤
μf(x′)+(1-μ)f(x),?μ∈[0,1],

則稱f為凸集C上的凸函數(shù).

定義函數(shù)F:Rn→Rn，對(duì)于任意x∈Rn，F(xiàn)(x)是Rn中的一個(gè)集合.假如F滿足下式

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

則稱F為單調(diào)算子.

假設(shè)Ω?Rn為非空集合.如果Ω中的序列{xk}?Rn滿足

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

則稱序列是Fejér單調(diào)的.

2 算法框架和收斂性分析

VI(U,F):θ(x)-θ(x*)+(u-u*)F(u*)≥0,
?u∈U,

(5)

其中

(6)

因?yàn)棣萯是閉凸函數(shù)，Ai是列滿秩矩陣，所以變分不等式(5)是有解的.因此，變分不等式(5)的解集是非空的，并記為U*.

由于引入更多參數(shù)可使參數(shù)條件放松，因此在上述VAPCM的基礎(chǔ)上添加鄰近項(xiàng)，新算法迭代格式如下:

算法1一種基于VAPCM的新的預(yù)測校正方法(N-VAPCM)

步驟2預(yù)測.

(7)

步驟3校正.

(8)

步驟4停機(jī)準(zhǔn)則.如果滿足

則迭代停止；否則，k=k+1，繼續(xù)步驟2.

(a) 固定α2，α3

由預(yù)測步(7)生成的預(yù)測值滿足

(9)

其中

(10)

且

(11)

為了方便討論，我們引入以下記號(hào)：

此外，我們還定義了以下矩陣：

(12)

(13)

GD=αM.

(14)

定義

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

(15)

又

則矩陣Q是正定的當(dāng)且僅當(dāng)矩陣

是正定的.通過計(jì)算順序主子式可知，若以上矩陣正定，需要滿足條件：

(16)

在證明N-VAPCM的收斂性之前，我們先給出以下的引理.

引理2序列{uk}由預(yù)測步(7)生成，則序列{vk}在集合V*上是Fejér單調(diào)的，并且

(17)

根據(jù)F(u)在U上的單調(diào)性和矩陣M、N的定義，有

(18)

(19)

另一方面，由校正步(8)可得

其中，D的定義見式(13).然后根據(jù)關(guān)系式(14)和(15)中Q的定義，有

其中不等式關(guān)系可由不等式(19)得到.

最后，基于前面的引理，我們可以證明N-VAPCM的收斂性.

證明：由不等式(17)知，序列{vk}是Fejér單調(diào)的，則{vk}是有界的.此外

令k=0,1,2,…，并疊加，則

由條件(16)知Q是正定矩陣，得到

(20)

(21)

(22)

再由預(yù)測步(7)、校正步(8)和A1的滿秩假設(shè)，可以得到

(23)

(24)

在變分不等式(9)中，令k=kj-1，j→∞，并利用關(guān)系式(22)、(24)得

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

這表明聚點(diǎn)u∞是變分不等式的一個(gè)解.

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

本節(jié)測試新算法N-VAPCM，代碼均由MATLAB(R2018a)編寫，在配置為AMD Ryzen 5 4600H CPU，16G內(nèi)存，Windows11操作系統(tǒng)的筆記本電腦上運(yùn)行.

同時(shí)新算法與VAPCM及改進(jìn)的嚴(yán)格壓縮PEACEMAN-RACHFORD分裂方法(SC-PRSM)進(jìn)行比較，其中SC-PRSM為使用具有恒定步長的簡單校正步驟來校正輸出的算法，常應(yīng)用于多塊凸優(yōu)化問題[15].

考慮下面目標(biāo)為2次函數(shù)的3塊變量線性約束問題

A∈Rm×n1,B∈Rm×n2,C∈Rm×n3,b∈Rm.

該問題的增廣拉格朗日函數(shù)為

其中λ∈Rm為拉格朗日乘子，β>0是懲罰參數(shù).

為了簡單起見，令n1=n2=n3=n.對(duì)于不同的m和n，我們需要調(diào)整算法中的參數(shù)，使得所有算法達(dá)到各自的最佳性能.令N-VAPCM中重要的參數(shù)α2=0.25，ν2=0.5，ν3=0.8.所有算法的終止條件均為所有變量相鄰兩步的相對(duì)變化小于所設(shè)精度或達(dá)到最大迭代步數(shù)(1000步).同樣，我們對(duì)所有算法均使用隨機(jī)生成的初始點(diǎn)(x0,y0,z0,λ0).

首先，確定計(jì)算精度，再設(shè)置5種不同的(m,n)，每組設(shè)置下，我們對(duì)所有算法運(yùn)行10次并記錄平均迭代次數(shù)和平均計(jì)算時(shí)間，其中平均計(jì)算時(shí)間(單位為秒)用“Time”表示，平均迭代次數(shù)用“Iter”表示，計(jì)算精度用“tol”表示.數(shù)值結(jié)果記錄如表1所示.

表1 N-VAPCM、VAPCM和SC-PRSM的數(shù)值實(shí)驗(yàn)比較結(jié)果(tol=10-10)

然后，在固定的(m,n)設(shè)置下改變計(jì)算精度，并記錄下平均迭代次數(shù)和平均計(jì)算時(shí)間.數(shù)值結(jié)果記錄如表2所示.

表2 N-VAPCM、VAPCM和SC-PRSM的數(shù)值實(shí)驗(yàn)比較結(jié)果(m=250,n=500)

從表1可以看出，新算法N-VAPCM比VAPCM、SC-PRSM更加高效.當(dāng)m=50，n=100時(shí)，N-VAPCM在計(jì)算時(shí)間上比VAPCM節(jié)約了約65.96%，在迭代次數(shù)上比VAPCM減少了約68.52%；當(dāng)m=500，n=1000時(shí)，N-VAPCM在計(jì)算時(shí)間上比VAPCM節(jié)約了約66.08%，在迭代次數(shù)上比VAPCM減少了約68.13%；當(dāng)m=2000，n=4000時(shí)，N-VAPCM在計(jì)算時(shí)間上比VAPCM節(jié)約了約61.03%，在迭代次數(shù)上比VAPCM減少了約67.49%.由表2則可以看出，新算法N-VAPCM在高計(jì)算精度下也有明顯優(yōu)勢，當(dāng)計(jì)算精度為10-12時(shí)，N-VAPCM在計(jì)算時(shí)間上比VAPCM節(jié)約了約57.97%，在迭代次數(shù)上比VAPCM減少了約58.93%；當(dāng)計(jì)算精度為10-13時(shí)，N-VAPCM在計(jì)算時(shí)間上比VAPCM節(jié)約了約58.11%，在迭代次數(shù)上比VAPCM減少了約58.27%.

測試的幾組問題的數(shù)值結(jié)果表明：N-VAPCM無論是計(jì)算時(shí)間還是迭代次數(shù)都明顯優(yōu)于VAPCM，在高精度計(jì)算下依舊保持優(yōu)勢，且性能優(yōu)勢具有較好的尺度適應(yīng)性.

4 總結(jié)

文章基于VAPCM算法，在其基礎(chǔ)之上對(duì)并行計(jì)算的兩個(gè)子問題添加鄰近項(xiàng)，并且在校正步驟上松弛其對(duì)應(yīng)的變量，提出了新算法N-VAPCM.建立了新算法的收斂性，初步的數(shù)值實(shí)驗(yàn)結(jié)果表明新算法比VAPCM具有更高的計(jì)算效率.