ADMM:Alternating Direction Method of Multipliers
问题定义
\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)
- 问题原始的拉格朗日函数存在鞍点。此步保证了强对偶形式的存在。
求解方法
问题的增广拉格朗日函数为:
对应方法中的“交替方向”,在 ADMM 方法中,变量 $x, z$ 是被迭代地优化:
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$,增广拉格朗日函数的线性项与二次项就可以写成:
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$ 是缩放的对偶变量。使用这个形式,问题的优化过程可以被化简为:
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$ 足够小的时候,就可以保证函数值与目标值之间的差距较小,可以选择优化算法中较为常见的终止条件:
\|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
s.t. \bm{x} – \bm{z} = \bm 0
使用 ADMM 方法的求解过程为:
\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$ 是一个软化阈值函数:
\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}$ 进一步写成:
例如多标记文章中的 [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 的形式:
s.t. \bm{S}_j – \bm{z} = \bm{0}
这个和上文中的形式完全一致,其附录中的推到公式也和上文中的形式相同。
Reference
- 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 节开始,绝大多数内容从此得到。 - https://www.cnblogs.com/wildkid1024/p/11041756.html
- https://www.zhihu.com/question/309568920/answer/580226096
- https://www.zhihu.com/question/36566112
- Feng, An, and He, “Collaboration Based Multi-Label Learning.”

原文链接:ADMM:Alternating Direction Method of Multipliers
WNJXYKの博客 版权所有,转载请注明出处。
还没有任何评论,你来说两句吧!