求解可分離凸優(yōu)化問(wèn)題的慣性近似松弛交替方向乘子法

薛中會(huì)， 殷倩雯， 黨亞崢

（1. 上海出版印刷高等?？茖W(xué)校，上海 200093；2. 上海理工大學(xué) 管理學(xué)院，上海 200093）

1 問(wèn)題的提出

一個(gè)優(yōu)化問(wèn)題如果滿足：稱該問(wèn)題為一個(gè)凸優(yōu)化問(wèn)題。其中，目標(biāo)函數(shù)f為凸函數(shù)，不等式約束gi也為凸函數(shù)，而等式約束hj為一個(gè)仿射函數(shù)。

一個(gè)可分離的凸優(yōu)化問(wèn)題為

交替方向乘子法（ADMM）是一種求解具有可分離的凸優(yōu)化問(wèn)題的重要方法。由于其處理速度快、收斂性能好，ADMM 算法在統(tǒng)計(jì)學(xué)習(xí)、機(jī)器學(xué)習(xí)等領(lǐng)域有著廣泛應(yīng)用，在求解可分離凸優(yōu)化問(wèn)題上具有簡(jiǎn)單、靈活、實(shí)用性強(qiáng)的效果。其優(yōu)勢(shì)在于利用對(duì)偶上升算法的可分離性，可以將大規(guī)模問(wèn)題拆分成2 個(gè)甚至多個(gè)小規(guī)模的子問(wèn)題，隨后交替求解分解所得的各個(gè)小規(guī)模子問(wèn)題，從而提高了求解問(wèn)題的效率。ADMM 算法最早由Glowinski 等[1]和Gabay 等[2]提出，ADMM 算法的經(jīng)典迭代步驟為

ADMM 在每一步迭代中都能解決較簡(jiǎn)單的子問(wèn)題，并且可以分別利用f(x)和g(x)的結(jié)構(gòu)。眾所周知，如式（1）具有KKT 點(diǎn)，則由式（2）生成的對(duì)偶序列收斂到對(duì)偶問(wèn)題的最優(yōu)解，但是，在沒(méi)有附加條件的情況下，原始迭代序列不一定收斂。為了改善原始收斂性，Eckstein[3]首先通過(guò)向式（2）的子問(wèn)題添加一些二次項(xiàng)，提出了鄰近ADMM算法。經(jīng)研究發(fā)現(xiàn)，慣性技術(shù)也可以加入ADMM算法中，在適當(dāng)?shù)募僭O(shè)條件下能夠加速算法的收斂效果。Alvarez[4]最早提出慣性技術(shù)這一概念，其基本思想是利用當(dāng)前迭代和上一步迭代之間的相關(guān)聯(lián)系得到下一步迭代，這樣不僅能夠較快地得到所求問(wèn)題的最優(yōu)解，而且在收斂性證明上也相對(duì)容易。近年來(lái)，慣性技術(shù)被運(yùn)用于鄰近點(diǎn)算法（PPM）求解極大單調(diào)算子包含問(wèn)題。通常情況下，為了加速鄰近點(diǎn)算法的收斂速度，考慮二階微分包含問(wèn)題

基于慣性技術(shù)在加快收斂性方面具有很好的效果，本文對(duì)可分離凸優(yōu)化問(wèn)題采用慣性技術(shù)，同時(shí)引入隨機(jī)加速的隨機(jī)變量以更新步長(zhǎng)，提出了慣性近似松弛交替方向乘子法。在適當(dāng)?shù)募僭O(shè)條件下，基于慣性鄰近點(diǎn)法的收斂性證明了慣性鄰近ADMM 算法的收斂性。另外，數(shù)值實(shí)驗(yàn)驗(yàn)證了新算法在實(shí)踐中具有更好的數(shù)值表現(xiàn)。

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

則f在C上是單調(diào)的。

RnF:C→Rn

如果C是 上的一個(gè)緊凸集，且 是一個(gè)連續(xù)映射，那么，變分不等式問(wèn)題(VIP)至少有1 個(gè)解。進(jìn)而可知，若函數(shù)是單調(diào)的，那么，變分不等式問(wèn)題的解存在且唯一。

3 慣性近似松弛ADMM

現(xiàn)針對(duì)可分離凸優(yōu)化問(wèn)題構(gòu)建慣性近似松弛交替方向乘子法（IPR-ADMM）。

問(wèn)題（1）的增廣拉格朗日函數(shù)為

c. 停止準(zhǔn)則。計(jì)算

4 收斂性證明

現(xiàn)利用變分不等式證明算法1 的全局收斂性。根據(jù)式（8）的變分不等式形式生成如下形式的迭代方案：

其中，第2 個(gè)不等式由假設(shè)1 的b 得到。

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

數(shù)值實(shí)驗(yàn)所用軟件為Matlab 2017b，電腦配置為Intel 四核i7 2.4GHz CPU，并在Vista 操作系統(tǒng)上運(yùn)行8GB RAM。

例1 首先考慮財(cái)務(wù)和統(tǒng)計(jì)問(wèn)題[15]，

迭代式（43）的X-子問(wèn)題通過(guò)奇異值分解（SVD）進(jìn)行求解，它承擔(dān)每次迭代過(guò)程中的主要計(jì)算負(fù)荷。迭代式（43）的Y-子問(wèn)題是一個(gè)投影，有如下形式：

表1 為參數(shù)R,S取不同值時(shí)的數(shù)值實(shí)驗(yàn)結(jié)果；表2 為參數(shù) τk取不同值時(shí)的數(shù)值實(shí)驗(yàn)結(jié)果；表3 為期望值 ρ取不同值時(shí)的數(shù)值實(shí)驗(yàn)結(jié)果。其中，n表示不同的維數(shù)，取50，100，200。顯然，從表1～3 可以看出，R，S的取值越大，迭代次數(shù)越少，算法收斂所消耗的時(shí)間也越少；而參數(shù) τk的值越小，算法表現(xiàn)出的數(shù)值性能越好。此外，隨機(jī)變量的不同期望值 ρ產(chǎn)生的迭代次數(shù)相近，在ρ=1.9時(shí)表現(xiàn)相對(duì)較好。綜上，慣性技術(shù)和隨機(jī)變量更新步長(zhǎng)都有利于加速算法的收斂。

表1 參數(shù)R, S 不同取值的數(shù)值結(jié)果比較Tab.1 Comparison of numerical results on different values of parameters R and S

表2 參數(shù) τk不同取值的數(shù)值結(jié)果比較Tab.2 Comparison of numerical results with different values of parametersτk

表3 期望值ρ 不同取值的數(shù)值結(jié)果比較Tab.3 Comparison of numerical results with different values of expected value ρ

表4 為不同維數(shù)下分別應(yīng)用IPR-ADMM 和ePADM[49]解決該問(wèn)題所用的時(shí)間和迭代次數(shù)。其中，n=50，100，200。s為迭代所用的時(shí)間，k為迭代次數(shù)。慣性近似松弛ADMM 算法中參數(shù)τk=0.5， 隨機(jī)變量 ηk的期望值 ρ=1.9。

表4 例1 的數(shù)值結(jié)果(ρ=1.9)Tab.4 Numerical results of example 1 (ρ=1.9)

圖1 為n=50，100，200 的條件下，IPR-ADMM和ePADM 算法的對(duì)比結(jié)果。其中，橫軸表示迭代次數(shù)，縱軸表示停止準(zhǔn)則，即收斂停止時(shí)間。顯然，由表4 和圖1 可以看出，算法1 的性能明顯比ePADM 算法好，因?yàn)樗牡螖?shù)和計(jì)算時(shí)間要少得多；并且從圖1 看出，n的取值越大，算法收斂越快，越趨于穩(wěn)定。

圖1 ePADM 和IPR-ADMM 算法對(duì)比（ρ=1.9）Fig. 1 Comparison of ePADM and IPR-ADMM algorithms（ρ=1.9）

結(jié)果表明，算法1 對(duì)于解決問(wèn)題（1）是有效的，而且算法1 的性能更良好，實(shí)驗(yàn)結(jié)果展現(xiàn)了加速策略的有效性。

6 結(jié) 論

通過(guò)應(yīng)用PPM 算法求解ADMM 分解的子問(wèn)題，并使用慣性外推項(xiàng)，構(gòu)建了一種用于求解線性約束可分離凸問(wèn)題的乘數(shù)的慣性近似交替方向方法，而且使用隨機(jī)變量來(lái)加快收斂速度。在適當(dāng)?shù)募僭O(shè)下，證明了該方法的全局收斂性。數(shù)值結(jié)果表明，該算法是有效的，收斂效果優(yōu)于現(xiàn)有算法。