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.”