Lecture 21-22 - Dual Decomposition and ADMM

References

Lecture: https://www.stat.cmu.edu/~ryantibs/convexopt-F18/

1. Introduction

1.1 Preliminary: Fenchel Conjugate

给定 $f : R^{n} \to R$ 是一个 proper, closed, convex 函数, 其 subgradient 在 $x \in R^{n}$ 处定义为:

\partial f (x) = {g \in R^{n} : f (z) \geq f (x) + g^{⊤} (z - x), \forall z \in R^{n}} .

其有性质如下.

Property 1. $y \in \partial f (x)$ 当且仅当 $x \in ar g min_{z \in R^{n}} {f (z) - y^{⊤} z}$ .

Proof

由 $y \in \partial f (x)$ 可得对任意 $z \in R^{n}$ , 有 $f (z) \geq f (x) + y^{⊤} (z - x)$ , 从而 $f (z) - y^{⊤} z \geq f (x) - y^{⊤} x$ , 即 $x \in ar g min_{z \in R^{n}} {f (z) - y^{⊤} z}$ .

$□$

$f$ 的 Fenchel conjugate 定义为:

f^{*} (y) = x \in R^{n} sup (y^{⊤} x - f (x)) ⟺ - f^{*} (y) = x \in R^{n} in f (f (x) - y^{⊤} x), y \in R^{n} .

其有如下性质.

Property 2. $y \in \partial f (x)$ 当且仅当 $x \in \partial f^{*} (y)$ .

Proof

由 $y \in \partial f (x)$ 可得 $x \in ar g min_{z \in R^{n}} {f (z) - y^{⊤} z}$ , 即 $f (x) - y^{⊤} x = in f_{z \in R^{n}} {f (z) - y^{⊤} z}$ . 根据 Fenchel conjugate 的定义, 可得 $f^{*} (y) = y^{⊤} x - f (x)$ . 而对任意 $u \in R^{n}$ , $f^{*} (u) = sup_{z \in R^{n}} (u^{⊤} z - f (z)) \geq u^{⊤} x - f (x)$ . 从而将两式相减, 有 $f^{*} (u) - f^{*} (y) \geq (u - y)^{⊤} x$ , 即 $x \in \partial f^{*} (y)$ .

$□$

Property 3. 若 $f$ 是 closed, proper, convex 函数, 则 $f$ 是 $m$ -strongly convex $⟺$ $\nabla f^{*}$ 是 $1/ m$ -Lipschitz 的.

Proof

$(\Rightarrow)$ 记 $x_{u} = ar g min_{x} {f (x) - u^{⊤} x}$ , $x_{v} = ar g min_{x} {f (x) - v^{⊤} x}$ . 由于 $f$ 是 $m$ -强凸的, 故 $f (x) - u^{⊤} x$ 也是 $m$ -强凸且唯一最小值取在 $x_{u}$ 的函数 (由强凸可推出 $f^{*}$ 可微, 故后文取 $\nabla f^{*}$ 合法). 根据强凸的性质, 对于任意 $y \in dom (f)$ 有:
$f (y) - u^{⊤} y \geq f (x_{u}) - u^{⊤} x_{u} + \frac{m}{2} ∥ y - x_{u} ∥_{2}^{2}$
再令 $y = x_{v}$ , 则有:
$f (x_{v}) - u^{⊤} x_{v} \geq f (x_{u}) - u^{⊤} x_{u} + \frac{m}{2} ∥ x_{v} - x_{u} ∥_{2}^{2} .$
同理, 对称地以 $v$ 为最优点、代入 $y = x_{u}$ 可以得到
$f (x_{u}) - v^{⊤} x_{u} \geq f (x_{v}) - v^{⊤} x_{v} + \frac{m}{2} ∥ x_{u} - x_{v} ∥_{2}^{2} .$
从而将两式相加, 化简整理有
$(u - v)^{⊤} (x_{u} - x_{v}) \geq m ∥ x_{u} - x_{v} ∥_{2}^{2} .$
再根据 Cauchy-Schwarz 不等式, 有:
$∥ u - v ∥∥ x_{u} - x_{v} ∥_{2} \geq m ∥ x_{u} - x_{v} ∥_{2}^{2} ⟺ ∥ x_{u} - x_{v} ∥_{2} \leq \frac{1}{m} ∥ u - v ∥$
最后根据 Fenchel conjugate 的性质 1,2, 有 $x_{u} = \nabla f^{*} (u)$ , $x_{v} = \nabla f^{*} (v)$ . 故命题成立.

$(\Leftarrow)$ 由于 $f^{*} (z)$ 是 $\frac{1}{m}$ -Lipschitz smooth, 故对任意参考点 $x$ , $f^{*} (z) - x^{⊤} z$ 同样也是 $\frac{1}{m}$ -Lipschitz smooth 的. 因此, 对于任意 $u, v \in dom (f^{*})$ , 有:
$f^{*} (u) - x^{⊤} u \leq f^{*} (v) - x^{⊤} v + ⟨ \nabla f^{*} (v) - x, u - v ⟩ + \frac{1}{2 m} ∥ u - v ∥_{2}^{2} .$
由上式 pointwise 成立, 故对左右两侧同时求关于 $u$ 的最小值, 有
$min RHS = f^{*} (v) - x^{⊤} v - \frac{m}{2} ∥\nabla f^{*} (v) - x ∥_{2}^{2},$
其最优值就是通过直接求导可得. 以及根据 Fenchel conjugate 的定义, 以及性质 $(f^{*})^{*} = f$ , 有:
$min LHS = u min {f^{*} (u) - x^{⊤} u} = - f (x)$
故我们能得到不等关系:
$f (x) \geq x^{⊤} v - f^{*} (v) + \frac{m}{2} ∥\nabla f^{*} (v) - x ∥_{2}^{2} .$
进一步, 取参考点 $y = \nabla f^{*} (v)$ , 则根据 conjugate 的两个事实: (a) $y = \nabla f^{*} (v) ⟺ v = \nabla f (y)$ ; (b) Fenchel-Young Inequality: $f^{*} (v) = y^{⊤} \nabla f (y) - f (y)$ (该不等式在 $\nabla f (y) = v$ 时取等). 因此将上述两个事实代入不等关系中, 即有:
$f (x) \geq (x - y)^{⊤} \nabla f (y) + f (y) + \frac{m}{2} ∥ x - y ∥_{2}^{2} .$
即 $f$ 是 $m$ -strongly convex

$□$

1.2 Dual First-Order Methods

Intuition.

考虑等式约束凸优化问题:

x \in R^{n} min f (x) s.t. Ax = b

其中 $f$ 是一个凸函数, $A \in R^{m \times n}$ 是一个矩阵, $b \in R^{m}$ 是一个向量.

考虑其 Lagrangian 函数: $L (x, u) = f (x) + u^{⊤} (Ax - b)$ 其中 $u \in R^{m}$ 是对偶变量.
对应的对偶函数为: $g (u) = x \in R^{n} in f L (x, u) = x \in R^{n} in f (f (x) + u^{⊤} (Ax - b)) = x \in R^{n} in f {f (x) + (A^{⊤} u)^{⊤} x} - u^{⊤} b .$

Gradient Information of Dual Function.

对于这类性质良好的凸优化问题 (凸且约束为 affine), 则只要约束本身是可行的, strong duality 就会自动满足. 因此求解原问题的最优解, 等价于求解对偶问题 $max_{u \in R^{m}} g (u)$ 的最优解. 故很自然地考虑用梯度法等一系列一阶方法来求解对偶问题. 不过由于 $g$ 本身是通过 inf 定义的, 因此需要更仔细分析其具体性质.

$f$ 的 Fenchel conjugate 定义为:

f^{*} (y) = x \in R^{n} sup (y^{⊤} x - f (x)) ⟺ - f^{*} (y) = x \in R^{n} in f (f (x) - y^{⊤} x), y \in R^{n} .

因此, 可以根据 Fenchel conjugate 的定义, 将对偶函数 $g$ 表示为: $g (u) = - f^{*} (- A^{⊤} u) - u^{⊤} b = x \in R^{n} in f {f (x) + (A^{⊤} u)^{⊤} x} - u^{⊤} b .$
若定义 $x^{⋆} \in ar g min_{x \in R^{n}} {f (x) + (A^{⊤} u)^{⊤} x}$ , 则根据 Preliminary 中的两条性质, 立即有 $x^{⋆} \in \partial f^{*} (- A^{⊤} u)$ (注意这里的 subgradient 是针对 $f^{*}$ 的 input 整体的). 若进一步表示成关于 $u$ 的 subgradient, 则有 $- A x^{⋆} \in \partial_{u} f^{*} (- A^{⊤} u)$ , 或等价地, $A x^{⋆} \in \partial_{u} f^{*} (- A^{⊤} u)$ . 又知 $\partial_{u} (- u^{⊤} b) = {- b}$ . 因此, 将两个 subgradient 相加, 即可得到最终结论: $A x^{⋆} - b \in \partial g (u), where x^{⋆} \in ar g x \in R^{n} min {f (x) + (A^{⊤} u)^{⊤} x}$
- 该式给我们的启发是: 对于 dual gradient 的计算, 不需要显式进行求导, 而只需要求解由给定 $u$ 所决定的 primal problem 的最优解.

Dual Gradient Ascent.

上式给我们提供了关于对偶函数的梯度信息. 因此全部的一阶方法都可以以此为基础进行设计. 例如最基本的 Dual Gradient Ascent 方法. 假设 $f$ 是 strictly convex 的. 则 (1) $f (x) + (A^{⊤} u)^{⊤} x$ 具有唯一解; (2) dual function $g (u)$ 是可微的, 即 $\nabla g (u) = A x^{⋆} - b$ . 故可以总结 Dual Gradient Ascent 方法. 初始化一个对偶变量 $u^{(0)}$ 后, 则可以依次开始对 $k = 1, 2, \dots$ 进行迭代:

x^{(k)} u^{(k)} = ar g x \in R^{n} min {f (x) + (A^{⊤} u^{(k - 1)})^{⊤} x} = u^{(k - 1)} + t_{k} (A x^{(k)} - b)

其中 $t_{k}$ 是 step size, 可以通过正常的 line search 等方法进行选择.

第一步 primal update, 就是最小化在当前迭代下原问题 $min_{x \in R^{n}} f (x)$ 的 Lagrangian (只相差了一个与优化变量 $x$ 无关的常数项 $- u^{⊤} b$ ). 通过该步, 就得到了当前迭代下的 dual function. 并且证明出, 最优点 $x^{(k)}$ 对应的 $A x^{(k)} - b$ 就是当前迭代下 dual function 的梯度.
第二步 dual update, 就是根据第一步得到的梯度信息, 对 dual function 进行梯度上升, 使得 dual function 的值不断增加, 从而逐渐逼近其最优值.

在 strong duality 被满足的条件下, 当求得 $u^{⋆} = ar g max g (u)$ 时, 由此诱导的

x^{⋆} (u) = ar g x \in R^{n} min {f (x) + (A^{⊤} u^{⋆})^{⊤} x}

将自动成为原问题的最优解.

Convergence Analysis.

Dual gradient method 只是 gradient method 应用在对偶问题上的一个特例. 因此其收敛性符合 gradient method 的正常分析. 例如,

若优化目标 $g$ 是凸且 $L$ -smooth 的, 则当 step size 选择为 $t_{k} = 1/ L$ 时, 有 sublinear 的收敛率 $O (1/ ε)$ , $ε$ 是目标精度.
若目标是 $μ$ -strongly convex 且 $L$ -smooth 的, 则 GD 方法是 linear convergence 的, 即当 step size 选择为 $t_{k} = \frac{2}{μ + L}$ 时, 有 $O (lo g (1/ ε))$ 的收敛率.

因此, 根据上述原函数与 conjugate 的关系, 可以得到如下结论:

若 $f$ 是 $m$ -strongly convex 的, 则 $f^{*}$ 是 $\frac{1}{m}$ -smooth 的, 因此该 dual ascent 是 sublinear 收敛的, 并且最优步长 $t_{k} = m$ .
若 $f$ 是 $m$ -strongly convex 且 $M$ -smooth 的, 则 $f^{*}$ 是 $\frac{1}{m}$ -smooth 且 $\frac{1}{M}$ -strongly convex 的 (相当于同时将定理反过来用了一次), 因此该 dual ascent 是 linear 收敛的, 并且最优步长 $t_{k} = \frac{2}{\frac{1}{m} + \frac{1}{M}}$ .

不过更严谨地讲, 这里我们的目标函数事实上为 $g (u) = - f^{*} (- A^{⊤} u) - u^{⊤} b$ , 因此需要进一步考虑 $A$ 的影响. 根据算子范数的定义, 可以得到

∥\nabla g (u) - \nabla g (v) ∥_{2} = ∥ A \nabla f^{*} (- A^{⊤} u) - A \nabla f^{*} (- A^{⊤} v) ∥_{2} \leq σ_{m a x} (A) ∥\nabla f^{*} (- A^{⊤} u) - \nabla f^{*} (- A^{⊤} v) ∥_{2} \leq \frac{σ _{m a x} ( A )}{m} ∥ - A^{⊤} u + A^{⊤} v ∥_{2} \leq \frac{σ _{m a x}^{2} ( A )}{m} ∥ u - v ∥_{2}

其中 $σ_{m a x} (A)$ 是 $A$ 的最大奇异值. 因此各步长等还需要根据具体矩阵的条件数进行调整.

2. Dual Decomposition

2.1 Distributed Optimization via Dual Decomposition

Dual Decomposition for Equality Constraints.

上述的 Dual Gradient Ascent 方法还只是关于对偶的一个最基本的应用. 其更为核心的应用是将一个复杂问题进行分解, 从而实现并行分布式优化.

考虑如下 目标可分, 约束耦合 的优化问题:

x min s.t. i = 1 \sum B f_{i} (x_{i}) Ax = b

其中 $x = (x_{1}, \dots, x_{B}) \in R^{n}$ 是一个 block vector, 其中每一个 block $x_{i} \in R^{n_{i}}$ 是一个子向量, $\sum n_{i} = n$ , 并且每个 $f_{i}$ 仅依赖于 $x_{i}$ . 然而其约束却是耦合的, 即 $Ax = b$ 中 $A$ 是一个 $m \times n$ 的矩阵, 其每一行都可能同时依赖于多个 block $x_{i}$ .

因此我们可以 accordingly 地对 $A$ 进行 block partition, 即 $A = [A_{1}, \dots, A_{B}]$ , 其中 $A_{i}$ 是一个 $m \times n_{i}$ 的矩阵. 从而可以将原问题表示为:

x min s.t. i = 1 \sum B f_{i} (x_{i}) i = 1 \sum B A_{i} x_{i} = b

对该优化问题套用前面的 dual gradient ascent 方法, 则在每一次迭代中, 其 primal update 的步骤为:

x^{(k)} = ar g x \in R^{n} min {f (x) + (A^{⊤} u^{(k - 1)})^{⊤} x} = ar g x \in R^{n} min {i = 1 \sum B (f_{i} (x_{i}) + (A_{i}^{⊤} u^{(k - 1)})^{⊤} x_{i})}

而这里, 观察到其中的每一项 $f_{i} (x_{i}) + (A_{i}^{⊤} u^{(k - 1)})^{⊤} x_{i}$ 仅依赖于 $x_{i}$ , 因此这 $B$ 项独立解耦的最优化问题就可以被独立各自分开求解, 从而实现并行分布式优化. 这就是 Dual Decomposition 的核心思想. 故其 primal update 的步骤可以被改写为:

x_{i}^{(k)} u^{(k)} = ar g x_{i} \in R^{n_{i}} min {f_{i} (x_{i}) + (A_{i}^{⊤} u^{(k - 1)})^{⊤} x_{i}}, i = 1, \dots, B = u^{(k - 1)} + t_{k} (i = 1 \sum B A_{i} x_{i}^{(k)} - b)

Dual Decomposition for Inequality Constraints (Projected Subgradient Approach).

若进一步将上述等式约束改为不等式约束, 即

x min s.t. i = 1 \sum B f_{i} (x_{i}) i = 1 \sum B A_{i} x_{i} \leq b

则整个的 Dual Ascent 方法的框架仍然是一样的, 只是需要在每一次迭代中, 对更新后的 $u^{(k)}$ 进行一个 projection, 即

x_{i}^{(k)} u^{(k)} = ar g x_{i} \in R^{n_{i}} min {f_{i} (x_{i}) + (A_{i}^{⊤} u^{(k - 1)})^{⊤} x_{i}}, i = 1, \dots, B = Π_{R_{+}^{m}} (u^{(k - 1)} + t_{k} (i = 1 \sum B A_{i} x_{i}^{(k)} - b))

其中 $Π_{R_{+}^{m}} (\cdot) = max {\cdot, 0}$ 是一个逐元素的 projection operator, 将输入的每一个元素都投影到非负实数上.

从算法角度看, 该方法是 projected subgradient method 的一个特例. 在每一次迭代中, 必须要保证对应的 Lagrangian multiplier $u$ 是非负的, 因此需要在每一次迭代中进行 projection.

Distribution Optimization.

这是一个 synchronous 的分布式优化算法. 其每一次迭代中, 每一个 block $x_{i}$ 都可以分发 (broadcast) 到不同的计算节点上独立求解, 从而实现并行化. 然而在进行梯度迭代时, 需要将所有 block 的结果进行聚合 (gather), 等到收集齐全的 block 结果后才能进行下一步的迭代.

借此场景进一步讨论一下这种 synchronous 的分布式优化算法.

在许多现实场景中, 事实上并不是数据被分发到不同的计算节点上, 而是数据本身就天然地分布在不同的计算节点上. 例如以现实场景为例. 一共有 $B$ 个单位, 每个单位 $i$ 都有自己的本地数据, 这些数据或因隐私政策, 或因数据规模等种种原因, 无法进行集中式的存储和处理. 然而与此同时, 整个系统又想在共享约束 (由于总资源 $b$ 的分配等原因, 导致约束耦合) 的条件下, 对各自 local objective $f_{i}$ 的加总进行优化, 其中 $x_{i}$ 是第 $i$ 个单位的本地决策变量. 这时, Dual Decomposition 就提供了一个非常自然的解决方案.
这里梳理整个优化系统的各方角色.
- Master (中心): 持有对偶变量 $u \in R^{m}$ , 以及全局的约束 $b \in R^{m}$ . 其不持有任何具体的 block $x_{i}$ 或 local objective $f_{i}$ . 其主要负责在每一次迭代中, 将当前的对偶变量 $u$ 分发给各个 worker, 等待收集齐全的 block 结果后, 对 $u$ 进行梯度更新. $u^{(k)} = u^{(k - 1)} + t_{k} (i = 1 \sum B A_{i} x_{i}^{(k)} - b)$ 其中 $A_{i} x_{i}^{(k)}$ 是每一个 worker 计算得到的 block 结果, 需要被 master 收集后才能进行下一步的迭代. 并且对于 master 来说这是一个 $m$ 维的黑盒结果, 其并不知道具体的 $x_{i}$ 或 $f_{i}$ 的任何信息.
- Worker (计算节点): 每一个 worker $i$ 持有一个 block $x_{i}$ 和 local objective $f_{i}$ . 其主要负责在每一次迭代中, 根据 master 分发的对偶变量 $u$ , 以及本地的 block $x_{i}$ 和 local objective $f_{i}$ , 来求解该 block 的最优化问题, 从而得到 block 结果 $A_{i} x_{i}^{(k)}$ , 并将该结果上传给 master. $x_{i}^{(k)} = ar g x_{i} \in R^{n_{i}} min {f_{i} (x_{i}) + (A_{i}^{⊤} \underline{u^{(k - 1)}})^{⊤} x_{i}}, i = 1, \dots, B$

因此可以汇总该种方法的特性.

劣势:
- Straggler effect. 由于每一个 block 的计算时间可能不一样, 因此在每一次迭代中, 若有节点的子问题特别困难或通信等出现问题, 那么其余的 worker 即使已经完成了计算, 也只能等着该节点完成后才能进行下一步的迭代. 因此 straggler effect 就会导致整体的效率降低.
优势:
- 通信量小. 每轮每个 worker 只需要传输 $A_{i} x_{i}^{(k)}$ 和 $u^{(k)}$ 两个 $m$ (即约束维度) 维的向量, 其往往远小于 block $x_{i}$ 的维度 $n_{i}$ . 因此通信量较小, 适合于通信受限的分布式系统.
- 隐私保护. 每个 worker 只需要将 $A_{i} x_{i}^{(k)}$ 这样的 block 结果上传给 master, 而不需要上传具体的 $x_{i}$ 或 local objective $f_{i}$ 的任何信息. 节点之间同样也不需要直接进行通信. 因此该方法适合于隐私受限的分布式系统.
- 可扩展. 中心的计算复杂度不会因节点数的增加而增加.

Price Coordination Interpretation (Vandenberghe).

此外, 进一步沿用当前的现实例子进一步加深对于对偶问题的理解.

对于每个单位 $i$ , 其可以自行决定自己的 local decision $x_{i}$ , 从而得到 local cost $f_{i} (x_{i})$ . 但是由于整个系统的资源是有限的, 因此每个单位的决策都必须满足一个全局的约束 $\sum_{i = 1}^{B} A_{i} x_{i} \leq b$ . 其中 $b \in R^{m}$ 中的每一行就代表了一个资源的总量 (例如电力, 总带宽, 总预算等).
对应的对偶变量 $u \in R_{+}^{m}$ , 其就相当于每一项资源的单位价格. 回顾每个 worker 解决的子问题
$x_{i} \in R^{n_{i}} min {f_{i} (x_{i}) + u^{⊤} A_{i} x_{i}}$
其第二项 $\sum_{j} u_{j} (A_{i} x_{i})_{j}$ 就相当于每个单位 $i$ 需要为自己使用的各项资源的用量 $(A_{i} x_{i})_{j}$ , 以单价 $u_{j}$ 进行支付的成本. 因此, 每个单位 $i$ 在做决策时, 不仅要考虑自己的 local cost $f_{i} (x_{i})$ , 还要考虑自己使用的资源所带来的成本 $u^{⊤} A_{i} x_{i}$ .
而 master 的更新步骤
$u^{(k)} = Π_{R_{+}^{m}} (u^{(k - 1)} + t_{k} (i = 1 \sum B A_{i} x_{i}^{(k)} - b))$
可以理解为一个价格调整的过程. 定义 slack variable $s = b - \sum_{i = 1}^{B} A_{i} x_{i}$ , 其中 $s \in R^{m}$ 中的每一项 $s_{j}$ 就代表了第 $j$ 个资源的剩余量. 当 $s_{j} < 0$ , 就说明该项资源已经被过度使用了, 因此 master 会以 $t_{k}$ 的幅度增加该资源的价格 $u_{j}$ , 从而在下一轮迭代中, 促使各个单位减少对该资源的使用. 反之亦然. 此外, 整个系统还会加上一个价格触底的保护机制, 即 $u_{j}$ 不会被调整到负数 (倒贴钱), 从而保证了价格的合理性.

3. Augmented Lagrangian Method (ALM) / Method of Multipliers

ALM 是一类解决有约束问题的经典方法. 其既可以是在 Dual Ascent 的视角出发, 视作是其对 primal 的一种 regularization; 可以看作是对 penalty method 的一种改进, 通过引入对偶变量来避免 penalty method 中的数值不稳定问题. ALM 的细致分析将单独进行展开, 这里现只单纯在 dual decomposition 的基础上, 介绍一下 ALM 的基本思想.

3.1 Intuition of ALM

回忆在前面的 Dual Ascent 中, 若对偶目标函数期望达到线性收敛, 则需要对偶目标函数光滑且强凸, 这对应着原函数需要同时满足强凸和光滑. 因此, 一种理解 ALM 的 motivation 的思路就是, 通过在 primal problem 中引入一个 quadratic penalty term 来增强原函数的强凸性, 从而放松对于原函数 $f$ 的要求.

对于原始问题

x \in R^{n} min s.t. f (x) Ax = b

其对应的 ALM 的 primal 为:

x \in R^{n} min s.t. f (x) + \frac{ρ}{2} ∥ Ax - b ∥_{2}^{2} Ax = b

其中 $ρ > 0$ 是一个 penalty parameter.

可以看到, 这两个问题在可行域上是完全等价的. 然而通过额外引入的二次项, 使得 ALM 的 primal objective function 具有更好的性质.

例如, 考虑其 Hessian: $\nabla^{2} f (x) + ρ A^{⊤} A$ 其中 $ρ A^{⊤} A ≻ 0$ 只要 $A$ 是 full column rank 的. 这也就使得 primal objective function 不论原函数 $f$ 的性质如何, 都具有强凸性.

3.2 ALM as Dual Ascent of Augmented Primal Problem

故对 Augmented primal problem 进行 dual decomposition, 则其 primal update 的步骤为:

x^{(k)} u^{(k)} = ar g x \in R^{n} min {f (x) + \frac{ρ}{2} ∥ Ax - b ∥_{2}^{2} + (A^{⊤} u^{(k - 1)})^{⊤} x} = u^{(k - 1)} + ρ \cdot (A x^{(k)} - b)

注意到, 这里的步长 $t_{k}$ 已经被固定为 $ρ$ . 下将证明, 这样的选择会恰好让每次的 dual 迭代点满足原始问题的 Stationarity 最优条件:

由于 $x^{(k)}$ 是 primal update 的最优点, 则其满足该问题的 KKT 条件, 即 $0 \in \partial f (x^{(k)}) + ρ A^{⊤} (A x^{(k)} - b) + A^{⊤} u^{(k - 1)} = \partial f (x^{(k)}) + A^{⊤} dual update (u^{(k - 1)} + ρ (A x^{(k)} - b)) = \partial f (x^{(k)}) + A^{⊤} u^{(k)}$
由上式可见, 每一次迭代的 dual variable $u^{(k)}$ 只要按照步长 $ρ$ 进行更新, 就能保证 primal variable $x^{(k)}$ 满足原始问题的 stationarity 条件.

同时另一方面, dual update 也起到了对于 primal variable 的 feasibility 的促进作用. 当且仅当 primal variable $x^{(k)}$ 满足可行性条件 $A x^{(k)} = b$ 时, dual variable $u^{(k)}$ 才会保持不变.

总的而言, 考虑原始问题 $min f (x) s.t. Ax = b$ 的 KKT 条件:

Stationary: $0 \in \partial f (x) + A^{⊤} u$ 这在 ALM 中每一个 primal update 的步骤中都被满足了.
Feasibility: $Ax = b$ 这在 ALM 中通过 dual update 中 asymptotically 满足.

因此通过 ALM 的 primal update 和 dual update 的交替迭代, 就能同时满足原始问题的 stationarity 和 feasibility 条件, 从而最终收敛到原始问题的最优解. 进而, 只要 $f$ 满足一些 mild conditions 等, 就可以满足 strong duality, 从而保证 ALM 的收敛性. 这相比于 Dual Ascent 来说, 其对于原函数 $f$ 的要求被大大放宽.

然而, ALM 的 primal update 中引入了一个 quadratic penalty term, 考虑前述的分块结构, 可以观察到

\frac{ρ}{2} ∥ Ax - b ∥_{2}^{2} = \frac{ρ}{2} i = 1 \sum B A_{i} x_{i} - b_{2}^{2} = \frac{ρ}{2} [i \sum ∥ A_{i} x_{i} ∥_{2}^{2} + 2 i < j \sum (A_{i} x_{i})^{⊤} (A_{j} x_{j}) - 2 i \sum (A_{i} x_{i})^{⊤} b + ∥ b ∥_{2}^{2}]

而这里由于 $\sum_{i < j} \cdot$ 这一项的存在, 导致不同 block 之间的耦合, 从而无法进行分解. 因此 ALM 的代价是破坏了 decomposability, 从而无法进行分布式优化. 这也为后文的 ADMM 的设计提供了一个重要的启发.

4. Alternating Direction Method of Multipliers (ADMM)

ADMM 同样也是在有约束优化领域的重要经典方法. 其主体内容也将详细地进行展开分析. 这里同样也只是站在上面提到的 ALM 的基础上, 尝试通过进一步的改进, 整合 ALM 和 Dual Decomposition 的优势.

4.1 Intuition of ADMM

考虑一个两块分块的优化问题:

x, z min s.t. f (x) + g (z) Ax + Bz = c

这样的问题在很多现实场景中都非常常见, 例如:

在 Lasso regression 等中, $f$ 是损失函数, $g$ 是正则项, 约束 $x = z$ .
在复合优化中, $f$ 是 smooth function, $g$ non-smooth 但 proximal-friendly.
在分布式优化中, $f$ 是 local objective, $g$ 是 global objective, 约束 $Ax + Bz = c$ 则是耦合约束.

沿用前面 ALM 的思路, 对其进行 Augmentation:

x, z min s.t. f (x) + g (z) + \frac{ρ}{2} ∥ Ax + Bz - c ∥_{2}^{2} Ax + Bz = c

这个优化问题对应的 Lagrangian function 为:

L_{ρ} (x, z, u) = f (x) + g (z) + \frac{ρ}{2} ∥ Ax + Bz - c ∥_{2}^{2} + u^{⊤} (Ax + Bz - c)

回顾, 若沿用 ALM 的 primal update 的步骤, 则需要同时对 $x$ 和 $z$ 进行联合优化, 即

(x^{(k)}, z^{(k)}) = ar g x, z min L_{ρ} (x, z, u^{(k - 1)}) = ar g x, z min {f (x) + g (z) + \frac{ρ}{2} ∥ Ax + Bz - c ∥_{2}^{2} + (u^{(k - 1)})^{⊤} (Ax + Bz - c)}

然而同样地, 由于 $\frac{ρ}{2} ∥ Ax + Bz - c ∥_{2}^{2}$ 这一项的存在, 导致 $x$ 和 $z$ 之间的耦合, 从而无法进行分解.

因此 ADMM 的核心思想就是, 不再联合求解 primal Lagrangian 的最小值, 而是通过 alternating optimization 的方式, 交替地对 $x$ 和 $z$ 进行优化. 具体而言, ADMM 的 primal update 的步骤为:

x^{(k)} z^{(k)} = ar g x min L_{ρ} (x, z^{(k - 1)}, u^{(k - 1)}), = ar g z min L_{ρ} (x^{(k)}, z, u^{(k - 1)}),

然后再进行 dual update:

u^{(k)} = u^{(k - 1)} + ρ \cdot (A x^{(k)} + B z^{(k)} - c) .

注意, 这里的 decomposition 是通过交替更新实现的, 应当区分其与 Dual Decomposition 中的 parallel decomposition.

因此, ADMM 对于一般的温和条件

不要求 $A, B$ 是 full column rank
不要求 $f, g$ 是强凸或可微的
只需要是正常凸, 约束有可行解等即可

都能保证收敛到原始问题的最优解, 并且同时和步长 $ρ$ 无关, 其只会影响收敛的速度但不会影响收敛的结果. 并且一般有如下收敛保证:

Feasibility Convergence: $r^{(k)} = A x^{(k)} + B z^{(k)} - c \to 0$ .
Objective Convergence: $f (x^{(k)}) + g (z^{(k)}) \to f^{⋆} + g^{⋆}$ .
- 注意, 这里只保证了 objective value 的收敛, 并不保证 primal variable $x^{(k)}, z^{(k)}$ 的收敛. 例如, 在某些 degenerate 的问题中, 可能存在多个 primal optimal solution, 从而导致 primal variable 的震荡, 但其 objective value 却是收敛的.
Dual Convergence: $u^{(k)} \to u^{⋆}$ .

4.2 Scaled Form of ADMM

Scaled Form ADMM 和 ADMM 在本质上完全等价. 其事实上就是在对 $L_{ρ} (x, z, u)$ 进行适当的变量替换进行配方, 以得到一个更为简洁的形式.

通常引入 scaled dual variable $w := u / ρ$ . 则 Lagrangian 可以写为:

L_{ρ} (x, z, w) = f (x) + g (z) + \frac{ρ}{2} ∥ Ax + Bz - c + w ∥_{2}^{2} - \frac{ρ}{2} ∥ w ∥_{2}^{2}

因此 ADMM 的更新公式可以用 scaled dual variable 来表示, 从而得到更为简洁的形式:

x^{(k)} z^{(k)} w^{(k)} = ar g x min f (x) + \frac{ρ}{2} ∥ Ax + B z^{(k - 1)} - c + w^{(k - 1)} ∥_{2}^{2}, = ar g z min g (z) + \frac{ρ}{2} ∥ A x^{(k)} + Bz - c + w^{(k - 1)} ∥_{2}^{2}, = w^{(k - 1)} + (A x^{(k)} + B z^{(k)} - c)

不过确实在进行缩放之后, $w$ 起到了 running sum of residuals 的作用, 用来记录历史上所有约束违反的总和.

4.3 Examples

4.3.1 Alternating Projections

Alternating Projections 是一种经典的 ADMM 应用场景.

给定两个凸集 $C, D \subseteq R^{n}$ , 优化的目标是寻找两个凸集的交集中的点. 若引入 indicator function:

I_{Ω} (x) = {0, \infty, x \in Ω x \in / Ω

则可以将寻找交集中的点的问题转化为如下优化问题:

x min I_{C} (x) + I_{D} (x) .

尝试使用 ADMM 解决该问题. 对应标准形式, 则有

x, y min f (x) + g (y) s.t. x = y .

其中 $f (x) = I_{C} (x), g (y) = I_{D} (y)$ .

代入 ADMM 的更新公式, 则有

x^{(k)} y^{(k)} w^{(k)} = ar g x min I_{C} (x) + \frac{ρ}{2} ∥ x - y^{(k - 1)} + w^{(k - 1)} ∥_{2}^{2}, = ar g y min I_{D} (y) + \frac{ρ}{2} ∥ x^{(k)} - y + w^{(k - 1)} ∥_{2}^{2}, = w^{(k - 1)} + (x^{(k)} - y^{(k)}) .

观察这里的更新公式, 可以发现

ar g x min I_{C} (x) + \frac{ρ}{2} ∥ x - y^{(k - 1)} + w^{(k - 1)} ∥_{2}^{2} ⟺ ar g x \in C min \frac{ρ}{2} ∥ x - y^{(k - 1)} + w^{(k - 1)} ∥_{2}^{2} .

而后者恰恰是将点 $y^{(k - 1)} - w^{(k - 1)}$ 投影到集合 $C$ 上的数学定义. 对于 $y^{(k)}$ 同理. 因此我们的更新公式可以写作:

x^{(k)} y^{(k)} w^{(k)} = P_{C} (y^{(k - 1)} - w^{(k - 1)}), = P_{D} (x^{(k)} + w^{(k - 1)}), = w^{(k - 1)} + (x^{(k)} - y^{(k)}) .

综上, 这样的 ADMM 其实就相当于交替进行集合 $C$ 和集合 $D$ 上的投影, 而投影对许多集合都有简单的闭式解, 因此极大地简化了求解过程.

若再对比对于该问题的经典 von Neumann 算法, 则其迭代公式为

x^{(k)} = P_{C} (y^{(k - 1)}), y^{(k)} = P_{D} (x^{(k)}) .

其唯一的区别在于 ADMM 引入了一个 dual variable $w$ 作为当前位置的 offset, 这体现了通过历史偏差的累积这一信息, 对当前投影进行了修正.

4.3.2 Group Lasso

给定 $y \in R^{n}, X \in R^{n \times p}$ , 以及 $β \in R^{p}$ , 其中 $β$ 被分为 $G$ 个子向量 (groups), 记为 $β_{1}, β_{2}, \dots, β_{G}$ , 其中 $β_{g} \in R^{p_{g}}$ 且 $\sum_{g = 1}^{G} p_{g} = p$ . Group Lasso 的优化问题可以写为:

β min \frac{1}{2} ∥ y - X β ∥_{2}^{2} + λ g = 1 \sum G c_{g} ∥ β_{g} ∥_{2}

直接对该问题进行求解可能会比较困难, 因为平方损失和不光滑的组范数正则化项混合在一起. 但是我们可以通过引入一个新的变量 $α$ 来将问题分解为两个部分:

β, α min s.t. \frac{1}{2} ∥ y - X β ∥_{2}^{2} + λ g = 1 \sum G c_{g} ∥ α_{g} ∥_{2} α = β

代入 ADMM 的迭代更新公式, 我们可以得到:

$β$ -update:
$β^{k} = ar g β min {\frac{1}{2} ∥ y - X β ∥_{2}^{2} + \frac{ρ}{2} ∥ β - α^{k - 1} + w^{k - 1} ∥_{2}^{2}} = (X^{⊤} X + ρ I)^{- 1} (X^{⊤} y + ρ (α^{k - 1} - w^{k - 1}))$
这是 ridge regression 的闭式解.
$α$ -update:
$α_{g}^{k} = ar g α_{g} min {λ c_{g} ∥ α_{g} ∥_{2} + \frac{ρ}{2} ∥ β_{g}^{k} - α_{g} + w_{g}^{k - 1} ∥_{2}^{2}} = R_{λ c_{g} / ρ} (β_{g}^{k} + w_{g}^{k - 1})$
其中
$R_{t} (v) = (1 - \frac{t}{∥ v ∥ _{2}})_{+} v$
是 $ℓ_{2}$ -norm 的 soft-thresholding proximal operator. 其作用是, 如果输入向量 $v$ 的模长小于阈值 $t$ , 则整组被置为零, 否则将其模长收缩 $t$ .
$w$ -update:
$w^{k} = w^{k - 1} + (β^{k} - α^{k})$

说明:

在具体计算时, 可以对 $X^{⊤} X + ρ I$ 进行一次 Cholesky 分解, 然后在每次迭代中使用该分解来高效地求解 $β$ -update.
只要某个范数的 prox 乘子是给定的, 都可以高效地进行推广计算.

4.3.3 Sparse + Low-Rank Matrix Decomposition

给定矩阵 $M \in R^{m \times n}$ (如视频中每一帧拉直后堆叠成的矩阵), 我们希望将其分解为一个稀疏矩阵 $S$ 和一个低秩矩阵 $L$ 的和:

S, L min s.t. ∥ L ∥_{tr} + λ ∥ S ∥_{1} M = L + S

$∥ \cdot ∥_{tr}$ 是矩阵的 trace norm, 也称为 nuclear norm, 是矩阵奇异值的和, 用于鼓励低秩解. 在数据中, 对应相对稳定, 低维的背景或主结构部分.
$∥ \cdot ∥_{1}$ 是矩阵的 entry-wise $ℓ_{1}$ norm, 用于鼓励稀疏解, 用来吸收局部突出的异常或前景部分.

同样可以使用 ADMM 来求解该问题, 迭代过程如下:

L^{k} S^{k} W^{k} = S_{1/ ρ}^{tr} (M - S^{k - 1} + W^{k - 1}) = S_{λ / ρ}^{ℓ_{1}} (M - L^{k} + W^{k - 1}) = W^{k - 1} + (M - L^{k} - S^{k})

其中 $S_{t}^{tr} (\cdot)$ 是 trace norm 的 proximal operator, 其先对矩阵进行 SVD 分解, 然后对奇异值进行 soft-thresholding, 最后再重构矩阵.

4.4 Discussion

这里限定为无约束的 ADMM 问题:

x \in R^{n}, z \in R^{m} min f (x) + g (z) s.t. x = z .

即标准形式中对应 $A = I, B = - I, c = 0$ .

回顾, proximal operator 的定义为:

prox_{f, t} (v) = ar g x min {f (x) + \frac{1}{2 t} ∥ x - v ∥_{2}^{2}}

因此, 若对照 scaled ADMM 的更新公式, 取 $t = 1/ ρ$ , 则可以看出 ADMM 的更新步骤可以看作是对 $f$ 和 $g$ 的 proximal operator 的调用, 然后再对结果进行修正.

x^{k} z^{k} w^{k} = prox_{f, 1/ ρ} (z^{k - 1} - w^{k - 1}) = ar g x min {f (x) + \frac{ρ}{2} ∥ x - (z^{k - 1} - w^{k - 1}) ∥_{2}^{2}} = prox_{g, 1/ ρ} (x^{k} + w^{k - 1}) = ar g z min {g (z) + \frac{ρ}{2} ∥ z - (x^{k} + w^{k - 1}) ∥_{2}^{2}} = w^{k - 1} + (x^{k} - z^{k})

在实践当中, ADMM 有时会遇到如下问题.

ADMM 通常会快速收敛到一个还不错的解, 但是在追求高精度时会变慢;
ADMM 的收敛速度对 $ρ$ 的选择非常敏感, 需要进行调参;
对同一个原问题采用不同的分解方式, 会得到不同的 ADMM 算法, 其收敛速度也会不同.

4.5 Consensus ADMM

前面的 dual decomposition 中曾经实现过分布式优化, 但在 vanilla 的 ADMM 中, 由于 $x$ 和 $z$ 的耦合, 使得其无法直接进行分布式优化. Consensus ADMM 是 ADMM 的一个重要变体, 其主要用于解决分布式优化问题.

假设共有 $B$ 个 worker, 每个 worker $i$ 有自己的 local data 以及对应的损失 $f_{i} (\cdot)$ , 但所有 worker 都共享一组 global variable $z$ . 其优化问题可以写为:

z min i = 1 \sum B f_{i} (z)

Consensus ADMM 的核心思想是, 给每个 $f_{i}$ 引入一个 local copy $x_{i}$ , 然后强制所有的 local copy 都等于 global variable $z$ 以 “达成共识(consensus)“. 于是问题可以改写为:

x_{1}, \dots, x_{B}, z min s.t. i = 1 \sum B f_{i} (x_{i}) x_{i} = z, i = 1, \dots, B

通过这种分解, 全局原本耦合的问题被拆分为 $B$ 个局部问题, 每个 worker 只需要处理自己的 local copy $x_{i}$ , 并且通过与 global variable $z$ 的交互来达成共识. 这恰好变成了 ADMM 可以处理的标准形式问题:

x_{i}^{(k)} z^{(k)} w_{i}^{(k)} = ar g x_{i} min f_{i} (x_{i}) + \frac{ρ}{2} ∥ x_{i} - z^{(k - 1)} + w_{i}^{(k - 1)} ∥_{2}^{2}, i = 1, \dots, B = \frac{1}{B} i = 1 \sum B (x_{i}^{(k)} + w_{i}^{(k - 1)}) := \overset{ˉ}{x}^{(k)} + \overset{ˉ}{w}^{(k - 1)} = w_{i}^{(k - 1)} + (x_{i}^{(k)} - z^{(k)}), i = 1, \dots, B

进一步, 观察到 $\overset{ˉ}{w}^{(k)} = \frac{1}{B} \sum_{i = 1}^{B} w_{i}^{(k)} = 0$ , 因此 $\overset{ˉ}{w}^{(k)}$ 可以被省略, 从而简化了 $z$ 的更新公式:

x_{i}^{(k)} z^{(k)} w_{i}^{(k)} = ar g x_{i} min f_{i} (x_{i}) + \frac{ρ}{2} ∥ x_{i} - z^{(k - 1)} + w_{i}^{(k - 1)} ∥_{2}^{2}, i = 1, \dots, B := \overset{ˉ}{x}^{(k)} = \frac{1}{B} i = 1 \sum B x_{i}^{(k)} = w_{i}^{(k - 1)} + (x_{i}^{(k)} - z^{(k)}), i = 1, \dots, B

因此, 这里各个 worker 的 $x_{i}$ -update 可以并行进行, 而 $z$ -update 则是一个简单的平均操作, 这使得 Consensus ADMM 非常适合分布式计算环境.

若考虑更一般的 Consensus ADMM, 其优化问题可以写为:

z min i = 1 \sum B f_{i} (a_{i}^{⊤} z + b_{i}) + g (z)

每个 worker 独立地在自己的数据 $(a_{i}, b_{i})$ 上计算 local loss $f_{i}$ , 而 $g$ 则是对全局变量 $z$ 的约束或正则化.

同样引入 global copies, reparametrize:

x_{1}, \dots, x_{B}, z min s.t. i = 1 \sum B f_{i} (a_{i}^{⊤} x_{i} + b_{i}) + g (z) x_{i} = z, i = 1, \dots, B

注意到, 这里的正则项是没有进行分解的, 其需要汇总到中心节点进行处理.

则应用 ADMM, 其更新公式为:

x_{i}^{(k)} z^{(k)} w_{i}^{(k)} = ar g x_{i} min f_{i} (a_{i}^{⊤} x_{i} + b_{i}) + \frac{ρ}{2} ∥ x_{i} - z^{(k - 1)} + w_{i}^{(k - 1)} ∥_{2}^{2}, i = 1, \dots, B = ar g z min \frac{Bρ}{2} ∥ z - \overset{ˉ}{x}^{(k)} - \overset{ˉ}{w}^{(k - 1)} ∥_{2}^{2} + g (z) = w_{i}^{(k - 1)} + (x_{i}^{(k)} - z^{(k)}), i = 1, \dots, B

4.6 Special Decomposition

需要说明, 不同的 reparametrization 会导致不同的 ADMM, 不同的方式会极大地影响收敛速度. 这里给出粗略的讨论. ADMM 在形式上和 block coordinate descent 非常类似, 其每次迭代只更新一部分变量, 而其他变量保持不变. 因此, 在设计 ADMM 的拆分形式引入辅助变量时, 应当尽量保证不同块之间彼此正交, 从而减少耦合震荡, 以加快收敛速度.

BYNotes

Explorer

Lecture 21-22 - Dual Decomposition and ADMM

1. Introduction

1.1 Preliminary: Fenchel Conjugate

1.2 Dual First-Order Methods

2. Dual Decomposition

2.1 Distributed Optimization via Dual Decomposition

3. Augmented Lagrangian Method (ALM) / Method of Multipliers

3.1 Intuition of ALM

3.2 ALM as Dual Ascent of Augmented Primal Problem

4. Alternating Direction Method of Multipliers (ADMM)

4.1 Intuition of ADMM

4.2 Scaled Form of ADMM

4.3 Examples

4.3.1 Alternating Projections

4.3.2 Group Lasso

4.3.3 Sparse + Low-Rank Matrix Decomposition

4.4 Discussion

4.5 Consensus ADMM

4.6 Special Decomposition

Graph View

Table of Contents

Backlinks