最近研究二次判别分析（Quadratic Discriminant Analysis，QDA），发现运用到了交替方向乘数法（ADMM），就很迷。（关键是太菜）

很多博主都是直接翻译或者搬运的，搜罗且了解了很多相关知识，那就来个大总结及其一些自己的想法吧！

（内力有限，仅供学习交流）

确实很难，理论性很强，没有虚的，阅读完内容需要有“勇气”！

ADMM

背景

咱们先来了解了解，ADMM到底是个什么东西？

交替方向乘数法（Alternating Direction Method of Multipliers），从字面意思上理解，交替方向？是不是很迷？交替计算？交替求解？。。。难道是对偶问题？对偶求解？

先不管了，再看后半句，乘数法？咦~是不是感觉有点熟悉。

la.la.la…Lagrange乘数法？？？

（没错，就是Lagrange，直接干起来，等等，这里只说对了一半，具体咱们下面慢慢道来~）

ADMM是一个不算是太新的算法，其实就是一种求解优化问题的计算框架, 适用于求解分布式凸优化问题，特别是统计学习问题。 ADMM 通过分解协调（Decomposition-Coordination）过程，将大的全局问题分解为多个较小、较容易求解的局部子问题，并通过协调子问题的解而得到大的全局问题的解。

简单的理解就是，整个算法只是整合许多不少经典优化思路，然后结合现代统计学习所遇到的问题，提出了一个比较一般的比较好实施的分布式计算框架。

而他的历史可以追溯到看下面：

ADMM 最早分别由 Glowinski & Marrocco 及 Gabay & Mercier 于 1975 年和 1976年提出，并被 Boyd 等人于 2011 年重新综述并证明其适用于大规模分布式优化问题。由于 ADMM的提出早于大规模分布式计算系统和大规模优化问题的出现，所以在 2011 年以前，这种方法并不广为人知。

作为搞自动化、控制、优化、诊断…的本菜来说，当然是奔着优化求解去学习的。

先来看看一个大佬对目前大数据及其优化的见解，简直是一针见血，说出来我的心声：

业界一直在谈论大数据，对于统计而言，大数据其实意味着要不是样本量增加n → ∞ ，要不就是维度的增加p → ∞，亦或者两者同时增加，并且维度与样本量的增长速度呈线性或者指数型增长。在稀疏性的假设条件下，再加上一些正则性方法，统计学家可以证明各种加penalty的模型所给出的参数估计具有良好的统计性质，收敛速度也有保证，同时还会给出一些比较好的迭代算法，但是，他们并没有考虑真实环境下的所消耗的计算时间。虽然统计学家也希望尽量寻求迭代数目比较少的算法（比如one-step估计），但是面对真实的Gb级别以上的数据，很多时候我们还是无法直接用这些算法，原因是一般的硬件都无法支撑直接对所有数据进行运算的要求。如果想减少抽样误差，不想抽样，又想提高估计的精度，那么还是需要寻求其他思路，结合已有的模型思想来解决这些问题。在目前条件下，并行化、分布式计算是一种比较好的解决思路，利用多核和多机器的优势，这些好算法便可以大规模应用，处理大数据优势便体现出来了。对于统计而言，数据量越大当然信息越可能充分（假设冗余成分不是特别多），因为大样本性质本身就希望样本越多越好嘛。—源自此处

还需要知道的一点，我们都知道搞优化会遇到很多问题，无非是数据量上和维度的变化，关键词大都为：降维，收敛，迭代等等，而这里的ADMM算法不同于那些梯度下降法或其他改进的SGDM、RMSProp、Adam等等更多高级算法，应用的大多为以GB级别的数据量的数据集，如果与SGDM、Adam这些算法在同样的低维数据（这里指的是较GB级别低的）进行比较，收敛速度绝壁没它们好，很慢，实际的收敛速度往往比那些算法慢得多。ADMM的主要应用，主要是在解空间规模非常大的情况下（比如X、Y 都是存储空间上GB的超大规模矩阵），这个时候很多传统的方法不好用，强制需要分块求解，而且对解的绝对精度往往要求也没那么高。所以我觉得这是，需要提前知道的一点。

确实，这个算法很难理解，公式也很难，不敢保证，我能将其解释清楚，抱着互相学习的态度写这篇Blog！（望各位大佬批评指正）

具体结构，从ADMM需要用到的背景知识、ADMM原理、具体应用这几块进行解释。

下面咱们从基本框架结构入手吧~

背景知识

《Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers》文章中提到了一些预备知识，学过最优化或最优估计等优化课程的童鞋应该能够很快能够理解，对偶问题若很陌生的小伙伴，可以补充补充相关的知识。

先来了解一些基本算法思想吧~

对偶上升

对于凸函数的优化问题，对偶上升法核心思想就是引入一个对偶变量，然后利用交替优化的思路，使得两者同时达到optimal。

读到这里，让我们想起咱们的主题，“交替方向”，是不是有点感觉了。

对于凸函数，我们只需要知道，凸优化问题有一个良好的性质即：局部最优解便是全局最优解

对凸函数有不解的地方，可看这位大佬的博客。

一个凸函数的对偶函数其实就是原凸函数的一个下界，因此可以证明一个较好的性质：在强对偶性假设下，即最小化原凸函数（primal）等价于最大化对偶函数（dual），两者会同时达到optimal。这种转化可以将原来很多的参数约束条件变得少了很多，以利于做优化。具体表述如下：

对于对偶问题有所不解的，可以简单理解成为原函数是Y关于X的函数，那么对偶的函数则为X关于Y的函数，这样理解是不是更容易一点呢。

在强对偶的假设下，原问题和对偶问题的解都是一样的，同时达到最优。

什么是强对偶性？就是指原问题的解与对偶问题的解是相同的，也即是：

arg 是变元（即自变量argument）的英文缩写。

arg min 就是使后面这个式子达到最小值时的变量的取值>

arg max 就是使后面这个式子达到最大值时的变量的取值

假如g ( y )可求其导数，那么利用梯度上升法，交替更新参数，使得同时收敛到最优。迭代如下：

对偶分解

虽然对偶上升的方法有所缺陷，导致我们在实际操作中会遇到重重困难。

但是世界万物都是存在着两面，有其弊也有其利，就如下面的太极双鱼图

那么，我们可以利用其优秀的一面，当目标函数 f 是可分的（separable）时候（参数亦或feature可分），整个问题可以拆解成多个子参数问题，分块优化后汇集起来整体更新。

这也就是快接近咱们的主题了，分布式凸优化问题。

我们可以分块，然后并行化处理。

由此，我们可分离的目标函数为：

对偶分解是非常经典的优化方法，可追溯到1960年代。这种思想对后面的分布式优化方法影响较大，比如近期的graph-structure优化问题。（具体可自行查询一下下）

增广的拉格朗日乘数法

反正，记住一点即可：增加惩罚项，扩大约束条件的容纳范围，放松假设条件。

可使其收敛的更快。

那么，增加惩罚项的拉格朗日项为：

其中，最后加了的L2正则化，二范数，也就是岭回归优化项就是惩罚项。ρ 则为我们的松弛因子（惩罚系数），用于更加精细的调节扩大的范围边界。

我们可以将其等价为优化的目标函数形式：

我们增加的惩罚函数的好处是为了让对偶函数

更具有可导性，更新参数的计算过程和对偶上升的一致。除最小化x 的时候加上惩罚项：

ADMM算法原理

在上述的层层递进的方法中，你是否也发现了其中的奥秘，对偶上升法解决了可分解性问题，增广乘子法解决了严格的凸函数限制条件，增强了收敛性。那么是否，我们可以将二者集合在一起，取其各自的优点呢？

答案当然是肯定的，那就是ADMM算法，同时解决了将原函数进行分解和扩展函数的约束范围问题。使得f ( x ) f(x)f(x)能够适应于更多的更广泛的约束条件求解问题。

结合两者的优点，就有了下式目标函数：

从中，我们可以看出，优化后的目标函数增加了新的变量g ( z )，约束条件则增加了B z，可以看出，我们将原X 分解了，原始变量和目标函数都拆分开了，对于原论文中的解释，感觉有一些蹊跷。但简单的理解就是将最初的原始变量就拆分为x xx和z zz两个变量，这样在后面的优化求解中，就不需要在融合到一起，最后求解出来也是两个值，也即是从一开始就将其分解开来。保证了前面优化过程的可分解性。

紧接着，我们的增广拉格朗日项：

和上面的增广拉格朗日一样，只不过增加了新的变量z 而已。

于是ADMM的优化就变成了如下序贯型迭代（这正是被称作alternating direction交替方向的缘由）：

可以看出，每次迭代分为三步：

求解与 x 相关的最小化问题，更新变量 x

求解与 z 相关的最小化问题，更新变量 z

更新对偶变量 u

ADMM名称中的“乘子法”是指这是一种使用增广拉格朗日函数（带有二次惩罚项）的对偶上升（Dual Ascent）方法，而“交替方向”是指变量 x 和 z 是交替更新的。两变量的交替更新是在 f ( x )或 g ( z )可分时可以将优化问题分解的关键原因。

到此，通过以上的内容来理解“交替方向乘数法（ADMM）”是不是就豁然开朗了许多，开篇说很难，其实是不是并没有那么的难。

当然，写成这种形式有利于后面简化优化问题，也可不作任何的处理。

具体应用

大佬回答及点评

ADMM( Alternating Direction Method of Multipliers)算法是机器学习中比较广泛使用的约束问题最优化方法，它是ALM算法的一种延伸，只不过将无约束优化的部分用块坐标下降法（block coordinate descent，或叫做 alternating minimization）来分别优化。产生这种方法主要是为了弥补二次惩罚的缺点。

在一些问题当中，用二次惩罚来近似约束问题在最优点附近需要惩罚项的系数趋近于无穷，而这种要求会使得海森矩阵很大，因此近似的目标函数很不稳定。为了解决这个问题，引入了线性逼近的部分，通过线性项系数不断的接近最优解（对偶上升），使得在二次惩罚项的系数很小的情况下，也能得到满足要求精度的解。ADMM目前是比较成熟，比较受欢迎的约束问题最优化通用框架。（引用源自知乎大佬）

受约束的凸优化问题

一般的受约束的凸优化问题可以写成如下形式：

可将此类型写成ADMM形式，增加新变量，以分解原始变量：

相应的增广拉格朗日项为：

其中的 g 函数即 C 的示性函数，上述是scaled形式，那么具体算法就是:

示性函数，顾名思义，是表示自变量性态的一个函数。

统计学习中的应用

统计学习问题也是模型拟合问题（我们知道有拟合和过拟合），可表示为：

对于带L1正则化项的线性回归（Lasso），其平方损失函数为

对于逻辑回归（Logistic Regression），其极大似然损失函数为

对于线性支持向量机（Linear Support Vector Machine），其合页（Hinge）损失函数为

将训练数据在其原始样本M维度下将其划分为N块：

由此我们可得到分块的目标函数来实现分布式计算：

相应的简洁迭代更新D 、 d 、 x D、d、xD、d、x的计算方式为：

个人见解

最后说两句，虽然优化算法千千万，在不同时期，随着科技的发展与进步，老的算法暂时过时，新的算法逐步崛起，但终归要落实到实际应用当中才是真正的好算法，并不是说一味的提高求解速度，提高精度，有些时候成本会很高，有些时候老的算法会被拾起成为yyds，新的算法未必就好。终究说来，希望能够有更多更实际应用范围更加广泛的优化算法逐步崛起吧~