交替方向乘子法

本文是继拉格朗日乘子以后有一个讲优化算法，建议先读完拉格朗日乘子然后阅读本文效果更佳。

首先我们来考虑以下什么是优化问题，它的数学表达是怎么样的，如果阅读了上面这个博客，你能很好的回答的这个问题，最简单的表达实际上就是。

$$min_x=f(x)$$

其中$x$是优化变量，也就是可以改变的数值，通过调节$x$的大小，使得目标函数$f(x)$的数值达到最小。

实际上对于上面的表达式，$min_x$的优化是无约束的，但是在生产和生活中，大部分$x$是有一定条件的，而且条件还不少。 例如我们经常想要赚更多钱的同时还要不累，就是这个道理了。

所以对于一个最优化的问题经常会有如下的约束。

$$subject.to\ Ax=b$$

$$subject.to\ Ax<=b$$

组合了原始的式子和受约束的条件就组成了一个优化问题。

ADMM算法

话说回来，ADMM是解决怎样的问题呢？

$$min_{x,z} f(x) + g(z)$$

$$st.\ Ax+By=c$$

也就意味着ADMM通常解决的是等式约束的优化问题，而且这个优化问题还有两个优化变量$x$ 跟 $z$.

这个时候我们需要知道变量x、z在满足一定的约束条件，这样的问题显然复杂了许多。

如何求解上面的问题呢？

简单问题求解

我们先从一个简单的问题入手。

$$min_x\ f(x)$$

$$st.\ Ax=b$$

第一步我们需要将原始的式子和受约束的条件用一个$\lambda$的变量耦合起来，形成Lagrange函数，如下

$$L(x,\lambda)=f(x)+\lambda^T(Ax+b)$$

原始的问题是

$$min_x f(x)$$

现在的问题是

$$max_{\lambda}min_xL(x,\lambda)$$

这两个问题的最优解是等价的，并且还有什么便利的环境，就是我们没有预约束条件，咱们现在只需要将精力放到这一个式子上就行了。

对偶上升法

名字咱们就暂且记下把，我们来看看我们接下来怎么做？

$$x^{k+1}=arg\ min_xL(x, \lambda^k)$$

$$\lambda^{k+1}=\lambda^k+ \rho A(x^{k+1}-b)$$

后来有人嫌弃这个Lagrange函数还不够凸，又对约束增加一个惩罚项，变成增广拉格朗日函数

$$L(x, \lambda)=f(x)+\lambda^T(Ax-b)+\frac{\rho}{2}||(Ax-b)||^2$$

ADMM算法流程

ADMM的想法跟上面的思路就很一致啦，作为一个primal-dual原对偶方法，首先，它要有个对偶函数，也就是增广拉格朗日函数：

$$L(x,z,\lambda)=f(x)+g(z)+\lambda^T(Ax+Bz-c)+\frac{\rho}{2}||(Ax+Bz-c)||^2$$

然后，它像对偶上升法一样分别固定另外两个变量，更新其中一个变量：(也就是其名：交替方向)

$$x^{k+1}=arg\ min_xL(x, z^k,\lambda^k)$$

$$z^{k+1}=arg\ min_z\ L(x^{k+1},z,\lambda^k)$$

$$\lambda^{k+1}=\lambda^k+ \rho A(x^{k+1}+Bz^{k+1}-c)$$

至于怎么求解 $\arg\min L$ ，因为无约束使用梯度下降法，牛顿法都可以_{其实就是大循环里嵌套的小循环，step1}3是大循环，求解里面的 $\arg\min L$ 是小循环

这里就能接上个文章提到的KTT条件求解了，