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

薛中會， 殷倩雯， 黨亞崢

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

1 問題的提出

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

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

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

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

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

2 預備知識

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

RnF:C→Rn

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

3 慣性近似松弛ADMM

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

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

c. 停止準則。計算

4 收斂性證明

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

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

5 數(shù)值實驗

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

例1 首先考慮財務(wù)和統(tǒng)計問題[15]，

迭代式（43）的X-子問題通過奇異值分解（SVD）進行求解，它承擔每次迭代過程中的主要計算負荷。迭代式（43）的Y-子問題是一個投影，有如下形式：

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

表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ù)下分別應用IPR-ADMM 和ePADM[49]解決該問題所用的時間和迭代次數(shù)。其中，n=50，100，200。s為迭代所用的時間，k為迭代次數(shù)。慣性近似松弛ADMM 算法中參數(shù)τk=0.5， 隨機變量 η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 算法的對比結(jié)果。其中，橫軸表示迭代次數(shù)，縱軸表示停止準則，即收斂停止時間。顯然，由表4 和圖1 可以看出，算法1 的性能明顯比ePADM 算法好，因為它的迭代次數(shù)和計算時間要少得多；并且從圖1 看出，n的取值越大，算法收斂越快，越趨于穩(wěn)定。

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

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

6 結(jié) 論

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