交替方向乘子法（ADMM）

网上的一些资料根本就没有把ADMM的来龙去脉说清楚，发现只是一个地方简单写了一下流程，别的地方就各种抄，共轭函数，对偶梯度上升什么的，都没讲清楚，给跪了。下面我来讲讲在机器学习中用得很多的ADMM方法到底是何方神圣。

共轭函数

给定函数$f:{\mathbb{R}}^n\to \mathbb{R}$，那么函数
$$f^{\ast }(y)=\underset{x}{\max }(y^{T}x-f(x))$$
就叫做它的共轭函数。其实一个更直观的理解是：对一个固定的$y$，将$y^{T}x$看成是一条斜率为$y$的直线，它和$f(x)$关于$x$的距离的最大值，就是$f^{\ast }(y)$。百度百科有关于这个直观说法的一个解释，看看就明白了。

关于共轭函数有几点重要的说明：

• 不管$f$凸不凸，它的共轭函数总是一个凸函数。

• 如果$f$是闭凸的（闭指定义域是闭的），那么$f^{\ast \ast }=f$。

• 如果$f$是严格凸的，那么
  $$\nabla f^{\ast }(y)=\underset{z}{\mathrm{argmin}}(f(z)-y^{T}z)$$

• 共轭总是频频出现在对偶规划中，因为极小问题总是容易凑出一个共轭：$-f^{\ast }(y)={\min }_x(f(x)-y^{T}x)$。

关于$f^{\ast }$的凸性，这篇博客给了一个比较直观的图示说明，下面我从数学上，不太严格地做个简单证明。以一维的情况说明。

假设$f$是一个凸函数，下面都不妨考虑函数的最值都不再边界处取到。${\max }_x(yx-f(x))$的极值点在$f_x^{\prime }(x)=y$处取到，定义$g:=(f_x^{\prime }{)}^{-1}$，那么$x=g(y)$可能会是一堆点。则有
$$f^{\ast }(y)=\underset{x}{\max }(yx-f(x))=yg(x)-f(g(y))$$ 进而
$$(f^{\ast }(y){)}_y^{\prime }=g(y)+y{g}_y^{\prime }(y)-f_x^{\prime }(g(y))g_y^{\prime }(y)=g(y)$$ 那么
$$(f^{\ast }(y){)}_y^{\prime \prime }y=g_y^{\prime }(y)=((f_x^{\prime }{)}^{-1}{)}_y^{\prime }\ge 0$$ 故而，$f^{\ast }$是凸的。

关于$f^{\ast \ast }=f$，也是容易证明的。我们假设$f$是闭凸的。${\max }_y(zy-f^{\ast }(y))$的值在$g(y)=z$处取到，那么
$$f^{\ast \ast }(z)=\underset{y}{\max }(zy-f^{\ast }(y))=f(g(g^{-1}(z)))=f(z)$$
$z$换成$x$就是$f(x)$。

第三条非常重要，它说明了共轭函数的梯度，其实就是共轭函数取到极大值对应的$x$值，它从$(f\ast (y){)}_y^{\prime }=g(y)$就可以看出来。

对偶梯度上升法

有了上知识的铺垫，我们就可以说清楚对偶上升方法了。以考虑等式约束问题为例（一般约束问题也是类似的流程），假设$f(x)$是严格凸的，我们考虑问题：
$$\underset{x}{\min }f(x)\text{ subject to }Ax=b$$ 它的拉格朗日对偶问题是：
$$\underset{u}{\max }\underset{x}{\min }(f(x)+u^T(Ax-b))$$
有理论表明，若原问题和对偶问题满足强对偶条件，即对偶函数关于$u$的最大值等价于原优化问题关于$x$的最小。那么原问题和对偶问题对于$x$是同解的。也就是说只要找到使得对偶问题对应最大的$u$，其对应的$x$就是原优化问题的解，那么我们就解决了原始优化问题。

所以，下面我们来求解这个对偶问题。先把和$x$无关的变量提出${\min }_x$，再想办法凑出$f^{\ast }$，因为我们要用到对偶的性质。
KaTeX parse error: No such environment: split at position 7: \begin{̲s̲p̲l̲i̲t̲}̲ \max _u \min…

那么对偶问题就成了 $$\underset{u}{\max }-f^{\ast }\left(-A^{T}u\right)-b^{T}u$$
这里$f^{\ast }$是$f$的共轭，这里${\max }_u$后面不加括号，表示它管着下面的所有，下同，不再重述。定义$g(u)=-f^{\ast }\left(-A^{T}u\right)-b^{T}u$，我们希望能极大化$g(u)$，一个简单的想法是沿着$g(u)$梯度上升的方向去走。注意到，
$$\partial g(u)=A\partial f^{\ast }\left(-A^{T}u\right)-b$$
因此，利用共轭的性质，
$$\partial g(u)=Ax-b\text{ where }x\in \underset{z}{\mathrm{argmin}}f(z)+u^{T}Az$$
因为$f$是严格凸的，$f^{\ast }$是可微的，那么，就有了所谓的对偶梯度上升方法。从一个对偶初值$u^{(0)}$开始，重复以下过程：
$$\begin{array}{rl}& x^{(k)}=\underset{x}{\mathrm{argmin}}f(x)+{\left(u^{(k-1)}\right)}^{T}Ax\\ & u^{(k)}=u^{(k-1)}+t_k\left(A{x}^{(k)}-b\right)\end{array}$$
这里的步长$t_k$使用标准的方式选取的。近端梯度和加速可以应用到这个过程中进行优化。

交替方向乘子法

交替方向乘子法（ADMM）是一种求解具有可分离的凸优化问题的重要方法，由于处理速度快，收敛性能好，ADMM算法在统计学习、机器学习等领域有着广泛应用。ADMM算法一般用于解决如下的凸优化问题:
$$\underset{x,y}{\min }f(x)+g(y)\text{ subject to }Ax+By=c$$
其中的$f$和$g$都是凸函数。

它的增广拉格朗日函数如下：
$$L_p(x,y,\lambda )=f(x)+g(y)+{\lambda }^T(Ax+By-c)+(\rho /2)\Vert Ax+By-c{\Vert }_2^2,\rho >0$$

ADMM算法求解思想和推导同梯度上升法，最后重复迭代以下过程：
$$\begin{array}{rl}{x}^{k+1}& :=\arg \underset{x}{\min }{L}_p(x,y,\lambda )\\ x^{k+1}& :=\arg \underset{y}{\min }{L}_p(x,y,\lambda )\\ {\lambda }^{k+1}& :={\lambda }^k+\rho \left(A{x}^{k+1}+B{y}^{k+1}-c\right)\end{array}$$ 上述迭代可以进行简化。

• 第一步简化，通过公式$\Vert a+b{\Vert }_2^2=\Vert a{\Vert }_2^2+\Vert b{\Vert }_2^2+2a^{T}b$，替换掉拉格朗日函数中的线性项${\lambda }^T(Ax+By-c)$和二次项$\rho /2\Vert Ax+By-c{\Vert }_2^2$，可以得到
  $${\lambda }^T(Ax+By-c)+\rho /2\Vert Ax+By-c{\Vert }_2^2=\rho /2\Vert Ax+By-c+\lambda /\rho {\Vert }_2^2-\rho /2\Vert \lambda /\rho {\Vert }_2^2$$
  那么ADMM的过程可以化简如下： $$\begin{array}{rl}{x}^{k+1}& :=\arg \underset{x}{\min }(f(x)+\rho /2{\Vert Ax+B{y}^k-c+{\lambda }^k/\rho \Vert }_2^2\\ y^{k+1}& :=\arg \underset{y}{\min }(g(y)+\rho /2{\Vert A{x}^{k+1}+By-c+{\lambda }^k/\rho \Vert }_2^2\\ {\lambda }^{k+1}& :={\lambda }^k+\rho \left(A{x}^{k+1}+B{y}^{k+1}-c\right)\end{array}$$

• 第二步化简，零缩放对偶变量$u=\lambda /\rho$，于是ADMM过程可化简为：
  $$\begin{array}{rl}{x}^{k+1}& :=\arg \min (f(x)+\rho /2{\Vert Ax+B{y}^k-c+u^k\Vert }_2^2\\ y^{k+1}& :=\arg \min (g(y)+\rho /2{\Vert A{x}^{k+1}+By-c+u^k\Vert }_2^2\\ u^{k+1}& :=u^k+\left(A{x}^{k+1}+B{y}^{k+1}-c\right)\end{array}$$

ADMM相当于把一个大的问题分成了两个子问题，缩小了问题的规模，分而治之。