3.7. 交替方向乘子法

交替方向乘子法 ( Alternating Direction Method of Multipliers, ADMM) [1] 结合了对偶分解 (dual decomposition) 和增广拉格朗日方法的优点, 最早可追溯到20世纪70年代中期 [2][3].

主页 1 中提供了所有相关论文, 代码及应用文档.

该问题与如下约束优化问题等价

\[{P_1}: {\rm min}_{{\bm x}, {\bm y}} f({\bm x}) + g({\bm y})\ \ {\rm s.t.} \ \ {\bm x} = {\bm y}. \]

尽管这种变化可能看起来微不足道, 但现在可以使用约束优化方法来解决这个问题, 如增广拉格朗日方法. 此时目标函数被 \({\bm x}\)\({\bm y}\) 分离, 对偶更新问题在于求解一个同时满足 \({\bm x}, {\bm y}\) 的近似函数. ADMM算法通过交替迭代的方法求解该问题, 即先固定变量 \({\bm y}\) 优化另一个变量 \(\bm x\), 再固定变量 \({\bm x}\) 优化变量 \(\bm y\), 如此交替优化求解. 虽然这并非准确地最优化求解, 但该方法最终可以收敛到很好的解.

3.7.1. ADMM原理

ADMM 用于求解如下形式的约束优化问题

(3.11)\[\begin{array}{ll}{\text { min }} & {f({\bm x})+g({\bm y})} \\ {\text {s.t. }} & {{\bm A} {\bm x} + {\bm B}{\bm y} = {\bm c}}\end{array} \]

其中, \(f,g\) 为凸函数, \({\bm x}\in{\mathbb R}^N\), \({\bm y}\in{\mathbb R}^M\), \({\bm A}\in{\mathbb R}^{p\times N}\), \({\bm B}\in{\mathbb R}^{p\times M}\), \({\bm c}\in{\mathbb R}^{p}\).

与乘子法类似, 式.3.11 的增广拉格朗日形式为

(3.12)\[L({\bm x}, {\bm y}, {\bm \lambda}) = f({\bm x}) + g({\bm y}) + {\bm \lambda}^T({\bm A}{\bm x}+{\bm B}{\bm y}-{\bm c}) + \frac{\mu}{2}\|{\bm A}{\bm x}+{\bm B}{\bm y}-{\bm c}\|_2^2, \]

其中, \(\mu\) 为惩罚因子.

ADMM算法的参数迭代更新规则为

\[\begin{aligned} {\bm x}^{k+1} & :=\underset{\bm x}{\operatorname{argmin}}\ L_{\mu}\left({\bm x}, {\bm y}^{k}, {\bm \lambda}^{k}\right) \\ {\bm y}^{k+1} & :=\underset{\bm y}{\operatorname{argmin}}\ L_{\mu}\left({\bm x}^{k+1}, {\bm y}, {\bm \lambda}^{k}\right) \\ {\bm \lambda}^{k+1} & :={\bm \lambda}^{k}+\mu\left({\bm A} {\bm x}^{k+1} + {\bm B}{\bm y}^{k+1} - {\bm c}\right) \end{aligned} \]

式.3.11 增广拉格朗日乘子法参数更新规则为

(3.13)\[\begin{aligned}\left({\bm x}^{k+1}, {\bm y}^{k+1}\right) & :=\underset{{\bm x}, {\bm y}}{\operatorname{argmin}} L_{\mu}\left({\bm x}, {\bm y}, {\bm \lambda}^{k}\right) \\ {\bm \lambda}^{k+1} & :={\bm \lambda}^{k}+\mu\left({\bm A} {\bm x}^{k+1}+{\bm B} {\bm y}^{k+1}-{\bm c}\right) \end{aligned} \]

可以看出, 增广拉格朗日乘子法需要同时优化两个原始变量 \(\bm x\), \(\bm y\). 与增广拉格朗日乘子法不同的是, 在ADMM中, \(\bm x\)\(\bm y\) 采用交替迭代 (alternating direction) 更新的方法.

3.7.2. Scale版ADMM原理

通过组合增广拉格朗日函数中的线性项与二次项并缩放对偶变量.

\[\begin{aligned} {\bm \lambda}^T{\bm r} + {\frac{\mu}{2}}\|{\bm r}\|_2^2 &= \frac{\mu}{2}\|{\bm r}+{\frac{1}{\mu}}{\bm \lambda}\|_2^2 - \frac{1}{2\mu}\|\bm \lambda\|_2^2 \\ &= \frac{\mu}{2} \|{\bm r} + {\bm u}\|_2^2 - \frac{\mu}{2}\|{\bm u}\|_2^2 \end{aligned} \]

其中, \({\bm r} = {\bm A}{\bm x} + {\bm B}{\bm y} - {\bm c}\) 为残差, \({\bm u} = \frac{1}{\mu}{\bm \lambda}\) 为scale版对偶变量, 对应的scale版更新规则为

\[\begin{aligned} {\bm x}^{k+1} & :=\underset{{\bm x}}{\operatorname{argmin}}\left(f({\bm x})+(\mu / 2)\left\|{\bm A} {\bm x}+{\bm B} {\bm y}^{k}-{\bm c}+{\bm u}^{k}\right\|_{2}^{2}\right) \\ {\bm y}^{k+1} & :=\underset{{\bm y}}{\operatorname{argmin}}\left(g({\bm y})+(\mu / 2)\left\|{\bm A} {\bm x}^{k+1}+{\bm B} {\bm y}-{\bm c}+{\bm u}^{k}\right\|_{2}^{2}\right) \\ {\bm u}^{k+1} & :={\bm u}^{k}+{\bm A} {\bm x}^{k+1}+{\bm B} {\bm y}^{k+1}-{\bm c} \end{aligned} \]

记第 \(k\) 次的残差为 \({\bm r}^k = {\bm A}{\bm x}^k + {\bm B}{\bm y}^k - {\bm c}\), 则有scale版对偶变量更新规则

\[{\bm u}^k = {\bm u}^0 + \sum_{j=1}^k {\bm r}^j. \]

3.7.3. 收敛性分析

3.7.4. 最优条件与停止准则