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

李瑩瑩

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

【關(guān)鍵詞】凸優(yōu)化 ADMM算法 隨機交替方向乘子方法

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

1.引言

本文我們主要考慮目標(biāo)函數(shù)二可分的線性約束凸優(yōu)化問題，其數(shù)學(xué)模型可以表示為：

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

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

2.SVR-ADMM算法

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

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

3.數(shù)值試驗

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

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

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

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

參考文獻：

[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.