李瑩瑩

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

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

【中圖分類(lèi)號(hào)】TP181 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】2095-3089（2016）10-0240-01

1.引言

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

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

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

2.SVR-ADMM算法

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

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

3.數(shù)值試驗(yàn)

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

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

下圖顯示了通過(guò)運(yùn)行時(shí)間來(lái)研究各種算法得到的試驗(yàn)結(jié)果。

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

參考文獻(xiàn)：

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