[Algorithm]ADMM简明理解
问题来源
在读论⽂的时候，遇到了ADMM(交替⽅向乘⼦法)算法，不明所以，于是查了⼀下，⼤概是⼀个凸优化算法，下⾯⼤概讲⼀下其原理和过程。
简介电信话费查询
交替⽅向乘⼦法（ADMM）是⼀种求解具有可分离的凸优化问题的重要⽅法，由于处理速度快，收敛性能好，ADMM算法在统计学习、机器学习等领域有着⼴泛应⽤。
独上兰舟
⽂献来源
Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends® in Machine learning, 2011, 3(1): 1-122.
凸优化问题
⾸先正常的优化问题为：
min x f(x)
这是最简单的优化问题，其中 x 是优化变量，也就是可以改变的数值，通过调节 x 的⼤⼩，使得⽬标函数 f(x) 的数值达到最⼩。值得注意的是，x的值并⼀定是数值，也可能是向量或者矩阵。
像上式那样，只有函数，对于变量 x没有要求，其实是最简单的⼀类优化问题：⽆约束优化问题。那么什么是凸优化问题呢，对应凸函数下的带约束的问题便是凸优化问题，凸函数的⼀个显著特征是该函数上的任意两点的连线都在该函数之上，在⼆维上最简单的凸函数即为:
y=x2
在三维图像上可以理解为形状为⼭⾕的函数。
实际上x不可能完全没有约束条件，否则那样的话我们直接通过求解函数的导数便可以找到最优解。实际问题往往会对x做⼀些约束，⼀共有两种约束：
1. 等式约束：subjecttoAx=b
2. 不等式约束：subjecttoAx<=b
帅气的名字网名
其中等式约束时要求x满⾜⼀定的等式，实际上任何复杂的等式约束都可以化简为上述的形式，进⾏求解。不等式约束也很容易理解，往往是某些约束的最低值或者最⾼值。如果同时有最低和最⾼，可拆成两个不等式。
基于以上的理解，⼀个包含等式约束的凸优化问题应该是这样的：
min x f(x)
ADMM算法
解决的问题
我的初三生活
ADMM算法解决的是两个变量下的优化问题，从原来问题的⼀个变量，变为两个变量，实际上任意个变量的问题都可以拆解为2变量问题？那么上⾯的优化公式就变为了：
min x,z f(x)+g(z)
耳朵英语怎么说
这也就意味着ADMM算法解决的是⼀个等式约束的问题，且该问题两个函数f(x)和g(x)是成线性加法的关系。这意味着两者实际上是整体优化的两个part，两者的资源占⽤符合⼀定等式，对整体优化贡献不同，但是是简单加在⼀起的。
事实上分布式中的⼀致性优化问题（connsus），分享问题（sharing problem）等等都很好写成这样的形式，因为每个节点的变量还要跟周围节点变量产⽣关联，但真正⽤ADMM的原因可能还是因为ADMM⼜快⼜好⽤吧。
使⽤的⽅法
与ADMM最为相关的⼤概就是原始对偶⽅法中的增⼴拉格朗⽇法（ALM）。拉格朗⽇函数实际上是解决多个约束条件下的优化问题的，这种
⽅法可以将⼀个有n个变量与k个约束条件的最优化问题转换为⼀个解有n + k个变量的⽅程组的解的问题。构造拉格朗⽇函数的⽅法在⼀般的⾼等数学教材⾥也可以找到。⽽增⼴拉格朗⽇法是加了惩罚项的拉格朗⽇法，⽬的是使得算法收敛的速度更快。
那么对上述的简单的凸优化问题构造拉格朗⽇函数，便可以得到：
L(x,λ)=f(x)+λT(Ax−b)
原来带约束求解min x f(x) ，现在求解对偶问题max，两个问题的最优解等价，并且没有了约束条件。
然后使⽤对偶上升法，得到：你温暖了我的岁月
step1: x ^{k+1} = arg min_x L(x;\lambda^{k}) \\ step2: \lambda ^{k+1} = \lambda^{k} + \rho (Ax^{k+1} - b)
新百伦鞋对偶上升法实际上是将：
\max_{\lambda}\min_{x}L(x,\lambda)
拆成了两步，第⼀步，先固定\lambda然后求解
min_x L(x;\lambda)
将求解后的x代⼊到拉格朗⽇函数当中，⽤类似于梯度下降的⽅法，得到\lambda的更新公式。
有时候为了加快算法收敛速度，会再增加⼀些惩罚项来加快收敛，于是就有了增⼴拉格朗⽇：
L(x;\lambda)= f(x) + \lambda ^T(Ax - b) + \rho/2 * ||Ax -b ||^2
ADMM
ADMM其实也是⼀直增⼴拉格朗⽇函数，只不过由⼀个变量变为了两个变量，那么对应的ADMM就成为了
L(x,z;\lambda)= f(x) + g(z) + \lambda ^T(Ax + Bz - c) + \rho/2 * ||Ax + Bz -c ||^2
那么，使⽤和增⼴拉格朗⽇类似的⽅法，固定其中两个变量，去更新第三个变量的值，于是便有：
step1: x^{k+1} = arg min_x L(x,z^k,\lambda^k) \\ step2: z^{k+1} = arg min_z L(x^{k+1},z,lambda^k) \\ step3: \lambda ^ {k+1} = \lambda^k + \rho (Ax + Bz - c) \\
于是问题就变化为了如何求解arg min_x L，那么就可以很开⼼地使⽤梯度下降法了。
Loading [MathJax]/jax/element/mml/optable/BasicLatin.js
>儿童常见疾病
