改進的隨機交替方向乘子方法

李瑩瑩

【摘要】最近，隨著信息技術的高速發展和大數據時代的到來，在解決優化問題時常常會遇到大規模問題。因此能夠找到一個有效的方法去解決此問題變得越來越重要。針對目標函數是兩個可分凸函數和的大規模凸優化問題模型，本文主要提出一個新的改進的隨機交替方向乘子方法，并給出了它的具體算法。同時數值試驗結果也驗證了此算法的可行性和有效性。

【關鍵詞】凸優化 ADMM算法 隨機交替方向乘子方法

【中圖分類號】TP181 【文獻標識碼】A 【文章編號】2095-3089（2016）10-0240-01

1.引言

本文我們主要考慮目標函數二可分的線性約束凸優化問題，其數學模型可以表示為：

解決上述問題的一個有效的方法是交替方向乘子方法（ADMM）[1]。但是當n非常大時，ADMM算法就變得計算困難。最近，Ouyang，etal.[2]研究了隨機設置的優化問題，用f（x）的一階近似去改寫增廣拉格朗日函數，并提出了一個隨機ADMM算法（數值試驗中用STOC-ADMM表示）。然后Suzuki，T.[3]研究了應用在結構正則化領域中的倆個算法即：近似梯度下降ADMM方法（OPG-ADMM）和正則化對偶平均ADMM算法（RDA-ADMM）.并證明了它們的有效性。接著LeonWenliang Zhong，James T. Kwok.[4]（2013）提出來一個結合隨機平均梯度方法（SAG）與ADMM的一個對隨機ADMM改進的一個快的隨機ADMM算法即：SA-ADMM。關于解決此問題的隨機算法還有很多，這里就不一一列舉了。

本文這要是結合SVRG算法[5]和ADMM算法的思想基礎上，提出一個改進的隨機交替方向乘子方法（SVR-ADMM）。下面我們分別給出此方法的具體算法，并通過數值實驗說明此算法的可行性和有效性。

2.SVR-ADMM算法

針對引言中的線性約束凸優化問題，下面我們來給出新提出方法的具體算法。此算法每次迭代與其他隨機算法一樣，每次迭代只需要計算一個樣本的梯度信息。

從算法1可以看出：新提出的SVR-ADMM算法與SVRG算法的迭代框架類似，它被分成多階段來完成且每個階段包含次內層循環迭代，內層迭代采用ADMM的迭代格式。接下來，我們通過數值試驗來驗證新提出算法的可行性和有效性。

3.數值試驗

在本節，針對廣義Lasso模型的一個具體實例，在ADMM的框架下可以表示為：

在接下來我們與文獻中提到的STOC-ADMM、OPG-ADMM和SA-ADMM算法作比較。為了檢驗新提出算法的性能，數據對（ai，bi）的選取我們用數據集a9a（來自網站LIBSVM archive）。所有算法需要的參數設置通過調試得到。

下圖顯示了通過運行時間來研究各種算法得到的試驗結果。

從上圖各種算法的試驗結果可以看出，我們新提出的算法可行性和有效性，有相對較快的收斂速率。

參考文獻：

[1]Boyd， S. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning， 3（1）：1–122，2010.

[2]Ouyang， H.， He， N.， Tran， L.， and Gray， A. Stochastic alternating direction method of multipliers. In Proceedings of the 30th International Conference on Machine Learning，Atlanta， GA， USA， 2013.

[3]Suzuki， T. Dual averaging and proximal gradient descent for online alternating direction multiplier method. In Proceedings of the 30th International Conference on Machine Learning， pp. 392–400， Atlanta， GA， USA，2013.

[4]L. W. Zhong and J. T. Kwok， Fast stochastic alternating direction method of multipliers，arXiv：1308.3558， （2013）.

[5]R.Johnson and T.Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems 26， pages 315-323. 2013.