交替方向乘子法（ADMM）是一种求解具有可分离的凸优化问题的重要方法，由于处理速度快，收敛性能好，ADMM算法在统计学习、机器学习等领域有着广泛应用。ADMM算法一般用于解决如下的凸优化问题:  

$$\begin{aligned}\min f(x)+g(x)\\ s.t. Ax+By=c \end{aligned} $$

其中，$x\in R^n$为目标函数$f(x)$的优化变量，$y\in R^m$为目标函数$g(x)$的优化变量，$A\in R^{p\times n}$，$B\in R^{p\times m}$，$c\in R^p$。 函数$f$和$g$是凸函数。

它的增广拉格朗日函数如下:

$$L_p(x,y,\lambda)=f(x)+g(y)+\lambda^T(Ax+By-c)+(\rho/2)\|Ax+By-c\|_2^2, \rho>0$$

其中，$\lambda$称为拉格朗日乘子，$\rho$是惩罚参数且$\rho>0$。此时，用ADMM算法进行求解，则过程如下：

$$\begin{split} x^{k+1}&:=\arg\min L_p(x,y,\lambda)\\ x^{k+1}&:=argmin L_p(x,y,\lambda) \\ \lambda&:=\lambda^k+\rho(Ax^{k+1}+By^{k+1}-c)\end{split} $$

第一步简化：

通过公式$2a^Tb+\|b\|^2_2=\|a+b\|^2_2-\|a\|^2_2$替换增广拉格朗日函数中的线性项$\lambda^T(Ax+By-c)$和二次项$\rho\|Ax+By-c\|_2^2$

$\lambda^T(Ax+By-c)+\rho\|Ax+By-c\|_2^2=\rho/2\|AX+By-c+\rho/\lambda\|_2^2-\rho/2\|\lambda/\rho\|_2^2$

于是ADMM求解过程可以简化为如下形式：

$$\begin{split} x^{k+1}&:=argmin (f(x)+\rho/2\|Ax+By^k-c+\lambda^k/\rho\|^2_2\\ y^{k+1}&:=argmin (g(y)+\rho/2\|Ax^{k+1}+By-c+\lambda^k/\rho\|^2_2\\ \lambda&:=\lambda^k+\rho(Ax^{k+1}+By^{k+1}-c)\end{split}$$

第二步简化：

令缩放对偶变量为$u=(1/\rho)\lambda$，于是ADMM求解过程再次简化为如下形式：

$$\begin{split} x^{k+1}&:=argmin (f(x)+\rho/2\|Ax+By^k-c+\lambda^k/\rho\|^2_2\\ y^{k+1}&:=argmin (g(y)+\rho/2\|Ax^{k+1}+By-c+\lambda^k/\rho\|^2_2 \\ \lambda&:=\lambda^k+\rho(Ax^{k+1}+By^{k+1}-c)\end{split}$$