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

薛中會， 殷倩雯， 黨亞崢

（1. 上海出版印刷高等專科學校，上海 200093；2. 上海理工大學 管理學院，上海 200093）

1 問題的提出

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

一個可分離的凸優化問題為

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

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

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

2 預備知識

則f在C上是單調的。

RnF:C→Rn

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

3 慣性近似松弛ADMM

現針對可分離凸優化問題構建慣性近似松弛交替方向乘子法（IPR-ADMM）。

問題（1）的增廣拉格朗日函數為

c. 停止準則。計算

4 收斂性證明

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

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

5 數值實驗

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

例1 首先考慮財務和統計問題[15]，

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

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

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

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

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

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

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

圖1 為n=50，100，200 的條件下，IPR-ADMM和ePADM 算法的對比結果。其中，橫軸表示迭代次數，縱軸表示停止準則，即收斂停止時間。顯然，由表4 和圖1 可以看出，算法1 的性能明顯比ePADM 算法好，因為它的迭代次數和計算時間要少得多；并且從圖1 看出，n的取值越大，算法收斂越快，越趨于穩定。

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

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

6 結 論

通過應用PPM 算法求解ADMM 分解的子問題，并使用慣性外推項，構建了一種用于求解線性約束可分離凸問題的乘數的慣性近似交替方向方法，而且使用隨機變量來加快收斂速度。在適當的假設下，證明了該方法的全局收斂性。數值結果表明，該算法是有效的，收斂效果優于現有算法。