机器学习与运筹优化（六）“敌进我退，分而治之”对偶算法与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).

作者：火龙果一号

编辑：蜜汁酱