ADMM:Alternating Direction Method of Multipliers

问题定义

\begin{aligned}
\mathop{\min}\limits_{x, z} & f(x) + g(z)\\
s.t. & Ax+Bz = b
\end{aligned}

其中 x \in \mathbb R^n, z \in \mathbb R^m, A \in \mathbb R^{p\times n}, B \in \mathbb R^{p\times m}, c \in \mathbb R^p 并且满足:

  • $f, g$ 是适当的封闭凸函数,这个条件允许函数可以是不可导函数,同时可以取到 $+\infty$。此步限制了优化中的前两部一定是存在解的。(closed, proper, convex)
  • 问题原始的拉格朗日函数存在鞍点。此步保证了强对偶形式的存在。

求解方法

问题的增广拉格朗日函数为:

L_\rho(x,z,y) = f(x) + g(z) + y^{\top}(Ax+Bz-c)+\frac{\rho}{2}\|Ax+Bz-c\|_2^2

对应方法中的“交替方向”,在 ADMM 方法中,变量 x, z 是被迭代地优化:

\begin{aligned}
x^{k+1} &= \mathop{\arg\min}\limits_{x} L_{\rho}(x, z^k, y^k)\\
z^{k+1} &= \mathop{\arg\min}\limits_{z} L_{\rho}(x^{k+1}, z, y^k)\\
y^{k+1} &= y^k + \rho(A x^{k+1} + B z^{k+1} – c)
\end{aligned}

通过这种分两步优化变量,再更新对偶变量的形式,我们可以完成对 f,g 两个函数优化的过程。

缩放形式

定义 r = Ax+Bz-c,增广拉格朗日函数的线性项与二次项就可以写成:

\begin{aligned}
y^{\top}r + (\rho / 2)\|r\|_2^2
&= (\rho / 2)\|r+(1+\rho)y\|_2^2 – (1/2\rho)\|y\|_2^2 \\
&= (\rho / 2)\|r+u\|_2^2 – (\rho / 2)\|u\|_2^2
\end{aligned}

其中 u=(1/\rho)y 是缩放的对偶变量。使用这个形式,问题的优化过程可以被化简为:

\begin{aligned}
x^{k+1} &= \mathop{\arg\min}\limits_{x} (f(x) + (\rho / 2)\|Ax + Bz^k – c + u^k\|_2^2) \\
z^{k+1} &= \mathop{\arg\min}\limits_{z} (g(z) + (\rho / 2)\|Ax^{k+1}+Bz-c + u^k\|_2^2) \\
u^{k+1} &= u^k + Ax^{k+1}+Bz^{k+1}-c
\end{aligned}

终止条件

原始残差 (primal residual):r^{k+1} = Ax^{k+1} + Bz^{k+1} – c

对偶残差(dual residual):s^{k+1} = \rho A^TB(z^{k+1} – z^k)

由 ADMM 的收敛性证明[3],可以知道 f(x^k) + g(z^k) – p^* \leq -(y^k)^{\top}r^k + (x^k – x^{*})^{\top}s^k,也就是说当这两项残差 r^k, s^k 足够小的时候,就可以保证函数值与目标值之间的差距较小,可以选择优化算法中较为常见的终止条件:

\begin{cases}
\|r^k\|_2 \leq
\sqrt{p} \epsilon^{abs} + \epsilon^{rel} \max\left\{\|Ax^k\|_2, \|Bz^k\|_2, \|c\|_2\right\}\\
\|s^k\|_2 \leq
\sqrt{n} \epsilon^{abs} + \epsilon^{rel}\|A^{\top}y^k\|_2
\end{cases}

其中, \epsilon^{abs} 是绝对的误差容忍项、\epsilon^{rel} 是相对的误差容忍项。实际中,\epsilon^{rel} 由应用不同设置为 1e-3,1e-4\epsilon^{abs} 由变量值的大小决定。

ADMM 方法在实际中,能很快地收敛到一个中低精度的解,而收敛到高精度的解相对来说比较缓慢。

应用:机器学习标准范式:Loss + Regularization

\mathop{\min}\limits_{\bm{x}, \bm{z}} l(\bm{x}) + \lambda\|\bm{z}\|_1 \\
s.t. \bm{x} – \bm{z} = \bm 0

使用 ADMM 方法的求解过程为:

\begin{aligned}
\bm x^{k+1} &= \mathop{\arg\min}\limits_{\bm x} l(\bm x) + \frac{\rho}{2} \| \bm x – \bm z^k + \bm \mu^k \| _2^2 \\
\bm z^{k+1} &= S_{\lambda / \rho}(\bm x^{k+1} + \bm \mu^k) \\
\bm \mu^{k+1} &= \mu^{k} + (\bm x^{k+1} – \bm z^{k+1})
\end{aligned}

其中,函数 S 是一个软化阈值函数:

S_{k}(a) =
\begin{cases}
a-k, a> k,\\
0, |a| < k,\\
a + k. a < -k.
\end{cases}

额外的,如果损失函数定义成线性的形式 l(\bm x) = \frac{1}{2}\|A\bm x + \bm b\|_2^2,我们就可以将 \bm x^{k+1} 进一步写成:

\bm x^{k+1} = (A^{\top}A + \rho I)^{-1}(A^{\top}b + \rho(\bm z^k – \bm \mu^k))

例如多标记文章中的 [5],通过 ADMM 算法计算出标记空间中标记关系的稀疏重构。重构的目标式为 |\bm{Y}_{-j} \bm{S}_j – \bm{Y}_j|_2^2 针对每个标记是使用其他标记恢复此标记的预测值。稀疏项为 \lambda |\bm{S}_j|_1,让矩阵 S 尽可能的稀疏。
使用 ADMM 算法进行优化,只需要将新建一个替身变量 \bm{z} = \bm{S}_j,就可以把目标是更换成 ADMM 的形式:

\mathop{\min}\limits_{\bm{S}_j, \bm{z}} \frac{1}{2} \|\bm{Y}_{-j} \bm{S}_j – \bm{Y}_j\|_2^2 + \lambda \|\bm{z}\|_1\\
s.t. \bm{S}_j – \bm{z} = \bm{0}

这个和上文中的形式完全一致,其附录中的推到公式也和上文中的形式相同。

Reference

  1. 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.
    P.S. ADMM的内容从第一篇参考文献的第 3 节开始,绝大多数内容从此得到。
  2. https://www.cnblogs.com/wildkid1024/p/11041756.html
  3. https://www.zhihu.com/question/309568920/answer/580226096
  4. https://www.zhihu.com/question/36566112
  5. Feng, An, and He, “Collaboration Based Multi-Label Learning.”