改进的随机交替方向乘子方法

李莹莹

【摘要】最近，随着信息技术的高速发展和大数据时代的到来，在解决优化问题时常常会遇到大规模问题。因此能够找到一个有效的方法去解决此问题变得越来越重要。针对目标函数是两个可分凸函数和的大规模凸优化问题模型，本文主要提出一个新的改进的随机交替方向乘子方法，并给出了它的具体算法。同时数值试验结果也验证了此算法的可行性和有效性。

【关键词】凸优化 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.