交替方向乘子法（ADMM）算法原理详解

©作者 | 李晶茂

学校 | 厦门大学

研究方向 | 高维统计

作为统计学专业研究高维统计问题的菜鸟，自从学了 ADMM 算法，内心极度膨胀（不是）

遇事不决，ADMM；如果一个 ADMM 不能解决，那就 ADMM 套 ADMM！

（正经）ADMM 算法提供了一个求解含线性等式约束优化问题的框架，方便我们将原始的优化问题拆解成几个相对好解决的子优化问题进行迭代求解。这种“拆解”的功能是 ADMM 算法的核心要义。

去年刚学 ADMM 的时候写过一个 notes，按自己的想法整理了一套理解 ADMM 算法原理的流程，贴出来和大家交流交流~

ADMM是个啥？

ADMM 用于求解如下最优化问题：

其中：，，，，；，。

简单来讲，这一优化问题的目标函数包含两组可分离自变量（ 和 ），且存在线性等式约束。对于这一优化问题，ADMM 算法首先对目标函数进行增广，将原始优化问题转化为：

进一步写出该问题的拉格朗日函数式子：

其中 为拉格朗日乘子（向量）。

接着使用如下更新步骤进行迭代（第 步更新）直至收敛：

1. 更新 ： ；
2. 更新 ： ；
3. 更新 ： ；

这个更新步骤还是很容易看明白的。但朋友，你懵逼了没有？至少我第一次看这玩意的时候是不知道这三个更新步骤是什么意思的。后来看了 CMU 那个凸优化的课才慢慢搞清楚这个脑洞是怎么开来的。今天来说道说道......

相关发展脉络

1.1 对偶问题（Dual Problem）

对于如下一个优化问题（原问题，primal problem）：

其中：，， 三个函数均为凸函数。我们假设该优化问题存在可行解（设可行区域为 ）。并设 为最优值点， 为其中的最优解。

写出这个优化问题的的拉格朗日函数：

其中 ， 为拉格朗日乘子。且 满足 。

此时，对于任意可行区域内的点 ，（由于 ，）我们有：

据此，我们就可以推导出下面这一串不等式（划重点啊）：

根据这个不等式，我们发现对于函数 而言，在任意满足 条件的取值处，我们都有 。

据此，我们定义如下原问题的对偶问题（dual problem）：

虽然这儿取了 ，但仍然满足下面这个弱对偶性： 。

也就是，原问题的最优解大于等于对偶问题的最优解~

▲ Tibshrani课件上的一个二元优化问题的例子。把原问题目标函数曲面和对偶问题目标函数曲面画在了一张图里~ （不过要注意看坐标第一维和第二维坐标的定义(x1/u1, x2/u2)。本来原目标函数和对偶问题目标函数的自变量是不同的，但这图换了坐标之后把它两叠在了一起）

另外，从另一个角度想，如果我们可以证明 （强对偶性），那其实我们可以通过求解对偶问题得到原问题的最优取值，同时也可以很方便地得到最优解 。后面的对偶梯度下降和 ADMM 其实都可以看成是这个路子。

具体来看的话，我们假设对偶问题的最优解是 ， 这个时候因为 ，之前那个很长一段的不等式里的不等号可以全换成等号，也就是：

你看，这个时候你要求解最优解 就容易多了，最简单的是去解这个优化问题：，没了约束条件，各种方法（什么梯度下降，牛顿法）就都好使了~

ps. 根据 Slater's condition，其实很多优化问题都满足 的强对偶性。Slater's condition 说明，如果原优化问题是凸的（，， 三个函数均为凸函数），且存在强可行的解（strictly feasible）满足：，（注意这儿是严格的不等号），那这个优化问题就满足强对偶性。

1.2 对偶梯度下降法（Dual gradient descent）

接下来开始讲讲对偶梯度下降法。这个方法其实就用到了对偶问题和原问题之间的关联，本质上是使用梯度下降的方法把对偶问题给解出来，然后也得到原问题的最优解。

讲这个之前先介绍两个后续用得上的概念：

● 包络定理（Envelop Theorem）

简单来讲，包络定理其实研究的是：对于一个带超参数的优化问题而言，这个超参数的变动会对这一优化问题的最优值产生什么样的影响。

在线性规划里头常见的“影子价格”问题其实就是这个研究的一个特例~

具体来讲，考虑一个带超参数 的优化问题：

其中：；，； 是相关的超参数（可以是向量或标量）。

我们可以写出这个优化问题的拉格朗日函数：

其中： 为拉格朗日乘子向量。

假设这个优化问题的最优值点为 ，那么包络定理告诉我们：

一句话概括下，包络定理其实说的是：优化问题的最优值对超参数的偏导数等于拉格朗日函数函数在最优点处对该超参数的偏导。

有了这个定理，我们下面可以引出来凸优化问题里面的一个概念——共轭函数~

● 共轭函数（Conjugate Function）

函数 的共轭函数 定义为：

从定义上理解，共轭函数 可以理解成是 与过原点的直线 之间可能的最大间距。

▲ Tibshrani课件上的一个一元函数例子

共轭函数的一个最有用的性质是：即使函数 不是凸函数，它的共轭函数 仍然是凸函数。其他的一些讨论可以参考这个知乎问题共轭函数的意义。

但这儿主要要讨论一下共轭函数的导数，根据前面的包络定理，我们有：

这个结论等下会用到~

好了，现在继续回来介绍对偶梯度下降法~

我们考虑如下的优化问题：

ADMM 用于求解如下最优化问题：

其中：，，。 我们假设是一个凸的目标函数。

我们写出它的拉格朗日函数：

其中 为拉格朗日乘子向量。

据此我们可以洗出原问题的对偶函数：

其中 为函数 的共轭函数~ （翻前面对应一下）。

因为 函数是凸函数，我们知道这个优化问题是满足强对偶性的（根据 Slater's condition），也即可以通过求解对偶问题 帮助解决原问题。

这儿我们选择使用梯度下降法（这儿是求 max，可能得叫梯度上升~）求解这个对偶问题，我们先算一下梯度，发现：

其中，这儿用到了前面介绍的共轭函数的导数公式，我们有：

所以把 带入之后我们就得到：

这个公式真的凑得刚刚好， 正好就是拉格朗日函数给定 取值之后， 的最优值点~

根据 ，我们现在可以设计如下的梯度上升算法来求解对偶问题，其中第 步迭代的更新公式为：

其中， 是学习率。

（划重点分割线）

具体把之前介绍过的梯度计算细节加进去就构成了完整的对偶梯度下降算法（dual gradient descent）。其中它在第 步迭代的更新步骤包括：

1. 更新 ：；
2. 更新 ： ；

我们迭代上述两步直至收敛，就得到了 和 就分别是原问题和对偶问题的解。

ps. 是对偶问题的解好理解， 是原问题的解这个要稍微绕一步：注意到更新步骤 1，我们可以得知，当算法收敛时有 ，所以根据之前对偶问题那一块的内容（就那个很长的不等式那儿） 就是原问题的解。

观察一下这个迭代步骤和 ADMM 的迭代步骤，是不是有点像？但 ADMM 的自变量是包含 和 两部分的，也就是目标函数对于自变量是可以写成两部分可分离的情况。那这儿有没有对应的一个形式？肯定是有的。。。

对偶梯度下降法在目标函数 对于 是可分离的情况下可以有更简单的计算方式（其实就是各个分量拆开），对应的算法叫对偶分解（Dual Decomposition）。

具体来看的话，我们假设自变量 ，且有 其中 为相关的分量（ ）。假设目标函数可以写成可分离的形式，也即：

此时仍然考虑优化问题：

这个优化问题的拉格朗日可以写成是：

其中 为拉格朗日乘子，， 是矩阵 的一个分量。因此，使用对偶梯度下降法对这个问题求解时，第一步对 的更新可以分解成几个同步进行的小步骤：同时 。
其实这个对偶分解更像是对偶梯度下降里头一个计算上的 trick~ 因为优化分量往往比优化一个合起来的目标函数简单。ADMM 之所以好用，很大一个原因也是因为这个。
当然，ADMM 算法和“对偶梯度下降+对偶分解”这个解法还是有差别的。我们还差最后一小块砖：增广拉格朗日方法~

1.4 增广拉格朗日方法（Augmented Lagrangian Method）

增广拉格朗日方法其实和对偶梯度下降法只有一点点点点点点差别。只是这个方法对原始的目标函数做了一步增广使目标函数变得更“凸”了一些，也是算法更 robust 了一些。具体来看的话，我们考虑下面这个优化问题：

我们对它做一步增广，变成：

是一个惩罚参数（penalty parameter）（实际里感觉一般设成 1 就差不多了）。很明显，这个优化问题和原始的优化问题是一样的。

写出它的拉格朗日函数（增广拉格朗日函数）：

那么根据对偶梯度下降的算啊发，这个优化问题的迭代步骤包括：

1. 更新 ：；
2. 更新 ： ；

这儿还有一个细节，第二步梯度下降的学习率直接取了 ，这个选择有助于更好地收敛~
考虑增广前的优化问题，假设它的解是 。那么我们有 primal feasibility 和 dual feasibility 两点要求：

Primal feasibility：

Dual feasibility：

而在第 k 步迭代的时候，由于

我们有：

（上面第三个等式把第二步更新后的 的表达式带入进去了）
这个式子说明：每一步迭代之后，我们得到的 都满足原优化问题的 dual feasibility。！这个性质保证了，我们只需要关注 primal feasibility，当 primal feasibility 也得到满足的话，迭代的结果就是最优值。这一定程度上也加快了算法收敛速度。
然而这么做的代价是：增广后的目标函数和拉格朗日函数不再是可分离的，所以我们不能像前面对偶分解那样简便地做计算。比如，假如我们的目标函数可以写成：

那增广后变成：

这个函数就拆不开了~
那如果我们还是想拆，这个问题怎么解决呢？ADMM 算法来了！

1.5 ADMM（Alternating Direction Method of Multipliers）算法

ADMM 算法实际上就是为了解决增广拉格朗日算法不能做分解的问题。它考虑了自变量由两个部分（标准的 ADMM 只针对两个部分的情况，虽然很多时候多个部分的情况在实际中也能收敛）组合而成时候，如何分解优化的问题。
这边把文章最前面写的 ADMM 部分的介绍再搬运一遍下来（人类的本质是复读机......hhhh）

ADMM 用于求解如下最优化问题：

其中：，，，，；，。

写出该优化问题的增广拉格朗日函数式子：

其中 为拉格朗日乘子（向量）。
接着使用如下更新步骤进行迭代（第 步更新）直至收敛：

1. 更新 ： ；
2. 更新 ： ；
3. 更新 ： ；

和增广拉格朗日算法相比，上述步骤里对于 的更新步骤是一致的，差别在前两步：这两个步骤按顺序地对两个自变量分量 和 进行了更新。
这个算法在一定条件下是可以证明收敛的。可以看 Boyd 的 ADMM 小册子或者看这儿 ADMM 算法的详细推导过程是什么？- 覃含章的回答~
至此，ADMM 算法就算是介绍得差不多了~

算法有关细节

2.1 Scaled Form——表示形式更简单的ADMM算法等价写法

我们刚刚介绍过，标准的 ADMM 算法里头对应的增广拉格朗日函数是如下式子~ 后续对 和 都是基于这个式子。

我们定义 ，则上述式子可以化简为如下更简单的式子：

这个式子本质上就是把一次项的部分凑到前面的二次项里面，使得整个拉格朗日函数形式更加简单，写程序推公式的时候更方便一些。 是与 无关的量（对参数更新没有帮助）。

这个时候拉格朗日函数的更新步骤需要相应地变更为：

1. 更新 ： ；
2. 更新 ： ；
3. 更新 ： ；

2.2 终止条件

是原优化和对偶问题的解的两个条件是：

1. Primal feasibility： ；
2. Dual feasibility：， ；

（假设 都是可导的）
（此处省略相关证明，直接给最终使用的时候的条件）

我们定义：

1. Primal residual： ；
2. Dual residual： ；

则 ADMM 收敛的条件是：
关于 和 的选取，Boyd 给出了如下建议值，该值由绝对部分和相对部分构成，具体而言：
（ 是线性约束的个数，也就是 ， ）（ 是 的维数， ）
ADMM为什么强大——举个简单例子（Lasso）

高维统计里面往往需要求解 “loss+penalty”形式的优化问题，其中 loss 部分往往是可导的；而 penalty 部分往往是不可导的（比如 惩戒）。这个时候没法使用普通的梯度下降法、牛顿法是没法求解的。这个时候就需要使用其他的优化算法求解，比如：近端梯度下降（proximal gradient descent），坐标下降法（Coordinate Descent）等等。ADMM 也是里面很常用的方法。
这里我们以最简单的 Lasso 线性回归模型为例做一个简单介绍~
假设自变量矩阵 ，因变量 ，系数向量 。此时 Lasso 需要求解如下优化问题：

这个优化问题可以等价为：

这儿我们引入了一个新的变量 把惩戒项里的 替换掉，这样分开可以更为方便地进行优化。我们使用 Scaled Form ADMM 进行求解。写出这个问题的拉格朗日函数（忽略优化无关项）：

则 ADMM 的优化步骤包括：

1. 更新 ：
2. 更新 ：
3. 更新 ：

这其中，第 1 步为二次优化问题，有显示解（凑平方或者求导都行）；第 2 步也有显示解，其中函数

为 soft-thresholding 函数（若 为向量，则表示 element wise 地做这个计算）~这儿三个子迭代步骤都有显示解，因此计算上效率还是相对比较高的~

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

···