【ADMM笔记】（二）ADMM算法细节、变体和常见技巧

fwalker · 发表于 2022-1-31 16:09

论文题目：《Distributed optimization and statistical learning via the alternating direction method of multipliers》
论文地址：
这篇笔记对应论文的章节：

3 Alternating Direction Method of Multipliers	3.1 Algorithm
3.3 Optimality Conditions and Stopping Criterion
3.4 Extensions and Variations
4 General Patterns	4.3 Smooth Objective Terms

Algorithm

考虑问题：

$\min f(x) + g(z) \tag{1a} \\$

$subject \quad to. \quad Ax + Bz = c \tag{1b} \\$
ADMM两种形式

unscaled form ADMM
上一个文章已经给了一种形式的ADMM算法，我们称之为unscaled form：

$x^{k+1} := \arg\min_x L_{\rho} (x,z^k,y^k) \tag{2a} \\$

$y^{k+1} := y^k + \rho(Ax^{k+1} + Bz^{k+1} -c ) \tag{2c} \\$
scaled form ADMM

$L_{\rho}(x,z,y) = f(x) + y^T r + \frac{\rho}{2} ||r||^2_2,\quad r=Ax+Bz-c \\$
化简得：

$L_{\rho}(x,z,y) = f(x) +\frac{\rho}{2} ||r + \frac{1}{\rho} y||^2_2 - \frac{\rho}{2}||\frac{1}{\rho} y||^2_2 \\$
令 $u = \frac{1}{\rho} y$ ：

$L_{\rho}(x,z,u) = f(x) +\frac{\rho}{2} ||r + u||^2_2 - \frac{\rho}{2}||u||^2_2 \\$
由此ADMM方法变为：

$x^{k+1} := \arg\min_x (f(x) +\frac{\rho}{2} ||Ax+Bz^k-c + u^k||^2_2) \tag{3a} \\$

$z^{k+1} := \arg\min_z (g(z) +\frac{\rho}{2} ||Ax^{k+1} + Bz - c + u^k||^2_2) \tag{3b} \\$

$u^{k+1} := u^k + Ax^{k+1} + Bz^{k+1} -c \tag{3c} \\$
（3）被称为scaled form ADMM。
最优性条件

记原问题最优解为  ，对偶问题最优解为  。考虑（1）的KKT条件：

$L(x,y) = f(x) + g(z) + y^T(Ax +Bz -c) \\$

$\nabla_x L = \nabla f(x^*) + A^T y^*= 0 \tag{4a}\\$

$\nabla_z L = \nabla g(z^*) + B^T y^*= 0 \tag{4b}\\$
同时需要满足约束：

$Ax^* + By^* = c \tag{4c} \\$

根据对偶理论知：
（4a）、（4b）、（4c）是  、  分别为原问题和对偶问题最优解的充分必要条件。
Remark 1. （4a）、（4b）被称为dual feasibility，（4c）被称为primal feasibility。
终止准则

（4a）、（4b）、（4c）给了最优性的条件，根据这一条件，我们利用迭代点与最优性之间的差距作为终止条件。
比如对（4c）：

$r^{k+1} = Ax^{k+1} + Bz^{k+1} -c \tag{5a} \\$

$r^{k+1}$ 被称为primal residual，终止时显然需要有 $r^{k+1} \le \epsilon^{pri} \tag{6a}$
现在需要判断迭代结果尽可能接近（4a）、（4b）条件。
根据（2b）：

因此， $L_{\rho} (x^{k+1},z,y^k)$ 在 $z = z^{k+1}$ 处导数为0：

$0 = \nabla g(z^{k+1}) + B^Ty^k + \rho B^T(Ax^{k+1} + Bz^{k+1} - c) \\$

$= \nabla g(z^{k+1}) + B^Ty^k + \rho B^Tr^{k+1} = \nabla g(z^{k+1}) + B^Ty^{k+1} \\$
这说明在迭代的过程中（4b）始终成立。
同样，根据（2a）， $L_{\rho} (x,z^k,y^k)$ 在 $x = x^{k+1}$ 处导数为0：

$0 = \nabla f(x^{k+1}) + A^Ty^k + \rho A^T(Ax^{k+1} + Bz^k - c) \\$

$= \nabla f(x^{k+1}) + A^Ty^k + \rho A^T(Ax^{k+1} + Bz^{k+1} - c) + \rho A^TB(z^k - z^{k+1})= \nabla f(x^{k+1}) + A^Ty^{k+1} + \rho A^TB(z^k - z^{k+1}) \\$
因此：

$\nabla f(x^{k+1}) + A^Ty^{k+1} = \rho A^TB(z^{k+1} - z^k) \tag{7}\\$
根据（7）可知，（4a）并不满足。
我们定义dual residual： $s^{k+1} = \rho A^TB(z^{k+1} - z^k)$ 。
我们希望：

$s^{k+1} \le \epsilon^{dual} \tag{6b} \\$
由此（6a）、（6b）是终止条件，保证当前迭代点尽可能接近最优性条件（4a）、（4b）、（4c）。
Extenstions

（2）、（3）是Standard ADMM的两种形式。基于Standard ADMM有非常多的扩展，这里就列举两个例子。
可变的惩罚参数（Varying Penalty Parameter）

之前讨论的惩罚系数 $\rho$ 都是常数。论文中给了一个变化的惩罚参数：

一般性的增广项（General Argumenting Terms）

（2）的增广项为  ，现在可以用更一般的形式来代替： $\frac{\rho}{2} r^TPr$ 。其中P是自己设置的正定矩阵。当P=I是，就是。
Technique

ADMM算法迭代的时候也有很多小技巧。
非精确最小化（Inexact Minimization）

（2a）、（2b）计算最优解的时候，不用精确搜索，可以做一个非精确搜索，找一个次优解，这样会减少迭代次数。
热启动（Warm Start）

（2a）、（2b）迭代的时候，不用每次都从0点或者一个固定点开始迭代，每次迭代可以从上一次位置开始。

读书笔记小结

这篇笔记中讨论了ADMM算法的两种形式、最优性条件、终止准则。之后也补充了一些ADMM算法的扩展与技巧。
这些都是基于（1）这个问题的。（1）这个问题只有等式约束，如果遇到不等式约束怎么办，下一篇笔记会引入近端算子，来处理含不等式约束或者集合约束这一类问题。

acecase · 发表于 2022-1-31 16:13

韩德仁老师最近写了新的综述可以参考下，从DRS理解ADMM可以看18年开的一个会议，油管能搜到，汇报的都是这个领域活跃者[飙泪笑]

redhat9i · 发表于 2022-1-31 16:18

嗯嗯，感谢提醒

		自动登录	找回密码
密码			立即注册

【ADMM笔记】（二）ADMM算法细节、变体和常见技巧

本帖子中包含更多资源