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

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

©作者 | 李晶茂

学校 | 厦门大学

研究方向 | 高维统计

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

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

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

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

ADMM是个啥？

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

其中： ， ， ， ， ； ， 。

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

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

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

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

更新：；

更新：；

更新：；

这个更新步骤还是很容易看明白的。但朋友，你懵逼了没有？至少我第一次看这玩意的时候是不知道这三个更新步骤是什幺意思的。后来看了 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） 。其中它在第 步迭代的更新步骤包括：

更新：；

更新：；

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

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

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

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

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

此时仍然考虑优化问题：

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

其 中为拉格朗日乘子，，是矩阵的一个分量。

因此，使用对偶梯度下降法对这个问题求解时，第一步对的更新可以分解成几个同步进行的小步骤：

同时 。

其实这个对偶分解更像是对偶梯度下降里头一个计算上的 trick~ 因为 优化分量往往比优化一个合起来的目标函数简单。ADMM 之所以好用，很大一个原因也是因为这个。

当然，ADMM 算法和“对偶梯度下降+对偶分解”这个解法还是有差别的。我们还差最后一小块砖：增广拉格朗日方法~

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

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

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

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

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

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

更新：；

更新：；

这儿还有一个细节，第二步梯度下降的学习率直接取了，这个选择有助于更好地收敛~

考虑增广前的优化问题，假设它的解是。那幺我们有 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 用于求解如下最优化问题：

其中： ， ， ， ， ； ， 。

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

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

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

更新：；

更新：；

更新：；

和增广拉格朗日算法相比，上述步骤里对于 的更新步骤是一致的，差别在前两步：这两个步骤按顺序地对两个自变量分量 和 进行了更新。

这个算法在一定条件下是可以证明收敛的。可以看 Boyd 的 ADMM 小册子或者看这儿 ADMM 算法的详细推导过程是什幺？- 覃含章的回答~

至此，ADMM 算法就算是介绍得差不多了~

算法有关细节

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

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

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

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

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

更新：；

更新：；

更新：；

2.2 终止条件

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

Primal feasibility：；

Dual feasibility：，；

（假设 都是可导的）

（此处省略相关证明，直接给最终使用的时候的条件）

我们定义：

Primal residual：；

Dual residual：；

则 ADMM 收敛的条件是：

关于 和 的选取，Boyd 给出了如下建议值，该值由绝对部分和相对部分构成，具体而言：

（ 是线性约束的个数，也就是 ， ）（ 是 的维数， ）

ADMM为什幺强大——举个简单例子（Lasso）

高维统计里面往往需要求解 “loss+penalty”形式的优化问题，其中 loss 部分往往是可导的；而 penalty 部分往往是不可导的（比如 惩戒）。这个时候没法使用普通的梯度下降法、牛顿法是没法求解的。这个时候就需要使用其他的优化算法求解，比如：近端梯度下降（proximal gradient descent），坐标下降法（Coordinate Descent）等等。ADMM 也是里面很常用的方法。

这里我们以最简单的 Lasso 线性回归模型为例做一个简单介绍~

假设自变量矩阵 ，因变量 ，系数向量 。此时 Lasso 需要求解如下优化问题：

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

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

则 ADMM 的优化步骤包括：

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

为 soft-thresholding 函数（若为向量，则表示 element wise 地做这个计算）~

这儿三个子迭代步骤都有显示解，因此计算上效率还是相对比较高的~