机器学习与运筹优化(六)“敌进我退,分而治之”对偶算法与ADMM算法

摘要:

上文我们介绍了约束优化问题和拉格朗日对偶思想。对偶算法就像是男生女生互相挑选,最终走到一起的过程,今天我们具体介绍几种常见的对偶算法,特别介绍在大数据时代大放异彩的ADMM算法。

回忆一下男生女生互相挑选的过程,哦不,回忆一下对偶算法的思想——构造拉格朗日函数,把约束优化问题转化为无约束优化问题求解。

例如原问题是在线性约束下极小化函数f:

我们用之前介绍的梯度下降法求解这个无约束优化问题,对于原始变量求解极小化问题(如果f可微可以应用梯度下降),对于对偶变量应用梯度上升,这就是Uzawa算法,或者叫原始-对偶上升法,讲究的是“敌进我退”:

Uzawa算法的收敛性对函数f和步长均有要求,需要f是强凸的,并且梯度上升的步长不能太大,受到f的强凸性的限制。感兴趣的同学可以参考Nitfy Theorem,原函数的强凸性对应对偶函数的连续性。

我们希望增强f的凸性,一个自然的想法是给f加上一个凸二次函数,于是我们准备构造一个增广拉格朗日函数(Augmented Lagrangian):

Uzawa算法的收敛性对函数f和步长均有要求,需要f是强凸的,并且梯度上升的步长不能太大,受到f的强凸性的限制。感兴趣的同学可以参考Nitfy Theorem,原函数的强凸性对应对偶函数的连续性。

我们希望增强f的凸性,一个自然的想法是给f加上一个凸二次函数,于是我们准备构造一个增广拉格朗日函数(Augmented Lagrangian):

剑桥大学教授Michael J.D. Powell(1936-2015)与袁亚湘院士

对于这个新的拉格朗日函数,Uzawa算法可以改进为ALM算法(Augmented Lagrangian Method of Multipliers):

可以证明,由于增广拉格朗日的强凸性和步长的联系,ALM算法对于任意步长都是收敛的。

ALM算法的问题是,如果f不可微,每一步求解都需要解一个极小化的子问题,计算代价可能较大。而在机器学习的很多问题中,f具有特殊的结构,一般可以分解为两个或多个函数,单个函数是利于求解的,比如统计和图像处理中非常有名的LASSO问题:

其中第一步需要求解整个f+g的增广拉格朗日函数的极小值,而f和g单独的增广拉格朗日函数的极小值更易于求解,于是我们采用“分而治之”的思想,于是得到了交替方向乘子法,ADMM算法(Alternating Direction Method of Multipliers):

ADMM算法广泛应用于统计学习和机器学习的各个领域,包括LASSO和约束线性回归模型;支持向量机;压缩感知;稀疏优化;分布式计算;其他大型分布式机器学习问题等等。

原始-对偶上升法体现了兵法中的“敌进我退”思想,而ADMM算法则体现了兵法中的“分而治之”思想。研究者在提出和改进新算法时,idea往往都很简单易懂,但背后体现了研究者的深刻的洞察力,需要对问题结构和算法思想的足够的理解,加上一点点灵感的火花。也许下一次,读者也能应用“三十六计”,提出更有效的机器学习优化算法。

参考文献:

[1] Boyd Stephen, Parikh Neal,Chu Eric,Peleato Borja. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, 2010.

[2]Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[3]袁亚湘, 孙文瑜. "最优化理论与方法." 科学出版社, 1997 年 1 月 (1997).

作者:火龙果一号

编辑:蜜汁酱

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180607G20G6Z00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券