ADMM – 交替方向乘子法

  • 1. 基础知识
    • 1.1 共轭函数
    • 1.2 对偶
    • 1.3 对偶上升法
    • 1.4 对偶分解
    • 1.5 增广拉格朗日乘子法
  • 2. 交替方向乘子法
    • 2.1 一般问题
    • 2.2 收敛性
    • 2.3 停止准则
  • 3. ADMM 算法加速
    • 3.1 Proximal operator
    • 3.2 Quadratic objective
    • 3.3 Smooth objective
    • 3.4 Decomposition
  • 4. 推广到 n-block
  • 5. ADMM 的应用
  • 6. 延伸阅读与引用

交替方向乘子法(ADMM)是一种普适性强的可并行的优化方法。整个思路大约是这样:

当原问题比较复杂的时候,我们可以考虑解它的对偶问题。但是对偶问题如果不可微,怎么办呢?

-> 对偶上升法,可以解不可微的对偶问题。但是如果原问题 $f$ 不是严格凸的,怎么办呢?

-> 增广拉格朗日乘数法,加个平方正则,就可以在 $f$ 不是严格凸时也保证收敛。但是这样就无法对偶分解,并行计算了,怎么办呢?

-> ADMM,既不严格,又能对偶分解,并行优化 👍

本文主要是 Boyd 大牛 [6] [12] 两份资料的学习总结。

1. 基础知识

1.1 共轭函数$^{[1]}$

共轭函数的定义:设函数 $f:R^n\rightarrow R$,定义函数 $f^*:R^n\rightarrow R$ 为

$$f^*(y) = \sup_{x \in \textbf{dom} f} (y^Tx – f(x))$$

函数 $f^*(y)$ 称为函数 $f$ 的共轭函数。差值 $y^Tx – f(x)$ 在 $\textbf{dom} f$ ($f(x)$ 的定义域)上有界的所有 $y\in R^n$ 构成了共轭函数的定义域(否则就没有上确界了)。

上图描述了这个定义:实线是 $f$,$y^Tx$ 是一条过原点的直线(上面的虚线)。如果 $f$ 可导,那么这个最大的差就是在 $f'(x) = y$ 的点 $x$ 处。这个最大的差也就是下面那条虚线的 $y$ 轴截距。

为了理解,举个例子:

$f(x) = -\log x$,定义域为 $\textbf{dom} f: \;x>0$。当 $y \ge 0$ 时,函数 $xy + \log x$ 无上界;当 $y < 0$ 时,函数 $xy + \log x$ 在 $x = -1/y$ 处达到最大值。因此,共轭函数为 $f^* = -\log (-y) – 1 \; (y<0)$。

共轭函数有如下基本性质:

  1. $f^*$ 是凸函数
  2. Fenhel 不等式:$f(x) + f^*(x) \ge x^Ty$
  3. 若 $f$ 为凸函数且 $f$ 是闭的($\textbf{epi} f$(上镜图)是闭集(所有边都是开的才是开集,否则就是闭集(只要有一边是闭的就是闭集))),则 $f^{**} = f$
  4. 若 $f(u,v) = f_1(u) + f_2(v)$,其中 $f_1,f_2$ 为凸函数,则 $f^*(w,z) = f^*_1(w) + f_2^*(z)$

1.2 对偶$^{[2]}$

标准形式的优化问题($f_i$ 为不等式约束,$h_i$ 为等式约束):

$$ \begin{aligned} \min \quad & f_0(x)\\ s.t. \quad & f_i(x) \le 0, \quad i = 1,···,m \qquad{(1.2.1)}\\ & h_i(x) = 0, \quad i = 1,···,p \end{aligned} $$

它的拉格朗日函数 $L: R^n \times R^m \times R^p → R$ 为

$$L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^m \lambda_if_i(x) + \sum_{i=1}^p\nu_ih_i(x)$$

那么定义 Lagrange 对偶函数 $g(\lambda,\nu)$,为关于对偶变量 $\lambda,\nu$ 的函数:

$$\begin{aligned} g(\lambda,\nu) =& \inf_{x \in D} L(x,\lambda,\nu) \\ \end{aligned} $$

Lagrange 对偶函数可以看做是 $x$ 取不同值时一族曲线的下界(绿线)$^{[3]}$。在对偶变量 $\lambda,\nu \ge 0$ 时,Lagrange 对偶函数是最优化解的下界。

那么优化问题(1.2.1)的对偶问题,就是对最优化值下界的最好估计:

$$ \begin{aligned} \max \quad & g(\lambda,\nu)\\ s.t. \quad & \lambda,\nu \ge 0 \end{aligned} $$

这时可能会有人问了,怎么由原问题得到对偶问题呢?在实际应用中,由于 Lagrange 对偶函数和共轭函数紧密相关,因此常用共轭函数推。

先来说明 Lagrange 对偶函数和共轭函数的相关性:

我们考虑一个一般的优化问题,其具有线性不等式及等式约束

$$ \begin{aligned} \min \quad & f_0(x)\\ s.t. \quad & Ax \le 0 \qquad{(1.2.2)}\\ & Cx = d \end{aligned} $$

问题(1.2.2)的对偶函数为

$$g(\lambda,\nu) = \inf_x L(x,\lambda,\nu) = \inf_x(f_0(x) + \lambda^T(Ax-b) + \nu^T(Cx-d))$$

可以提取 $x$ 相关的项,凑出共轭函数形式:

$$ \begin{aligned} g(\lambda,\nu) &= \inf_x(f_0(x) + \lambda^T(Ax-b) + \nu^T(Cx-d))\\ &= -b^T\lambda – d^T\nu + \inf_x(f_0(x) + (A^T\lambda + C^T\nu)^Tx)\\ &= -b^T\lambda – d^T\nu – f_0^*(-A^T\lambda – C^T\nu) \qquad{(1.2.3)}\\ \end{aligned} $$

先求共轭函数,再带入公式(1.2.3),即得到对偶函数。

为什么要用对偶方法呢?如果 $f(x)$ 复杂,而 $g(\lambda,\nu)$ 简单,可以通过对偶方式求解原问题:

  1. 求解 $\max g(\lambda,\nu)$ 得到 $\lambda^*,\nu^*$
  2. 求解 $\min L(x,\lambda^*,\nu^*)$ 得到 $x^*$

[4] 非常好地解释了原问题和对偶问题的关系

什么时候能用对偶方法呢?若强对偶性成立,则原问题和对偶问题的最优值相等,可以用求解对偶问题来求解原始问题。而要满足强对偶性,则需要满足 KKT 条件$^{[5]}$,KKT 条件等我正式学凸优化再说叭。

1.3 对偶上升法(Dual Ascent)$^{[6]}$

对偶上升法是用梯度上升解决对偶问题。

考虑等式约束问题(1.3.1)

$$ \begin{aligned} \min \quad & f_(x)\\ s.t. \quad & Ax = b \qquad{(1.3.1)} \end{aligned} $$

(1.3.1)的 Lagrange 函数: $L(x,y) = f(x) + y^T(Ax-b)$

(1.3.1)的对偶函数: $g(y) = \inf_xL(x,y) = -f^*(-A^Ty) – b^Ty$,其中 $y$ 是对偶变量,$f^*$ 是 $f$ 的共轭函数。

(1.3.1)的对偶问题:$\max \; g(y)$

对偶上升法就是用梯度上升的方法解 $\max \; g(y)$ ($g(y)$ 不可微的时候)primal variable 迭代方向取拉格朗日函数对 primal variable 的次微分,dual variable 迭代方向取拉格朗日函数对 dual variable 的次微分。

从对偶函数可以得到,$\bigtriangledown g(y) = Ax-b$,因此对偶上升的迭代更新为:

$$ \begin{aligned} x^{(k+1)} :=& \mathop{\arg\min}\limits_{x}L(x,y^{(k)})\qquad{(1.3.2)}\\ y^{(k+1)} :=& y^{(k)} + \alpha^{(k)}(Ax^{(k)} – b) \end{aligned} $$

其中 $^{(k)}$ 表示第 $k$ 个迭代,$\alpha^{(k)} > 0$,是梯度上升的步长,使得每步迭代之后,$g(y^{(k+1)}) > g(y^{(k)})$

对偶上升法需要满足一些条件,对 $\alpha^{(k)}$ 选择也有要求,所以实际上难以应用。

1.4 对偶分解(Dual Decomposition)

类似 1.1 中提到的共轭函数的性质 4,如果目标函数 $f$ 可以分解 (with respect to a partition or splitting of the variable into subvectors)

$$f(x) = \sum_{i=1}^Nf_i(x_i)$$

其中 $x$ 被划分成 $(x_1,···,x_N)$,$A$ 被划分成 $(A_1,···,A_N)$,Lagrange 函数可以写成:

$$L(x,y) = \sum_{i=1}^{N}L_i(x_i,y) = \sum_{i=1}^{N}(f_i(x_i) + y^TA_ix_i – \frac{1}{N}y^Tb)$$

那么对偶上升中 $x$ 的迭代就分成了 $N$ 个子问题:

$$ \begin{aligned} x^{(k+1)}_i :=& \mathop{\arg\min}\limits_{x_i}L(x_i,y^{(k)})\\ y^{(k+1)} :=& y^{(k)} + \alpha^{(k)}(Ax^{(k+1)} – b) \end{aligned} $$

每次迭代就要加个 broadcast 和 gather 的过程:$A_ix_i^{(k+1)}$ gather 到一起来计算 $Ax^{(k+1)} – b$;得到 $y^{(k)}$ 之后,要 broadcast 给各子问题,分别计算 $\mathop{\arg\min}\limits_{x_i}L(x_i,y^{(k)})$

1.5 增广拉格朗日乘子法(Augmented Lagrangian methods)

增广拉格朗日乘子法是为了给对偶上升法增强鲁棒性,所以加个正则项(也可以当做 proximal operator $^{[13]}$)。为了不需要 $f$ 一定要是严格凸(strictly convex)或值域有限(只要是一般的凸函数就行了)然后也能保证收敛性。

对于等式约束问题(1.3.1),其增广拉格朗日函数为

$$ \begin{aligned} L_\rho(x,y) = f(x) + y^T(Ax-b) + \frac{\rho}{2}\|Ax-b\|_2^2 \qquad{(1.5.1)} \end{aligned} $$

其中 $\rho > 0$,为惩罚系数。增广拉格朗日函数其实就对应着如下问题的拉格朗日函数:

$$ \begin{aligned} \min \quad & f(x)+ \frac{\rho}{2}\|Ax-b\|_2^2\qquad{(1.5.2)}\\ s.t. \quad & Ax = b \end{aligned} $$

这个问题与(1.3.1)是显然等价的,因为任何可行解 $x$ 必然满足 $\|Ax-b\|_2^2 = 0$。那么它的拉格朗日函数为 $g_{\rho}(y) = \inf_xL_\rho(x,y)$

加入惩罚项可以使对偶问题在更一般情况下(例如目标函数不严格凸)可微(# TODO 不懂)。增广拉格朗日乘子法的对偶上升迭代过程如下:

$$ \begin{aligned} x^{(k+1)} :=& \mathop{\arg\min}\limits_{x}L_\rho(x,y^{(k)})\qquad{(1.5.3)}\\ y^{(k+1)} :=& y^{(k)} + \rho(Ax^{(k+1)} – b) \end{aligned} $$

这样就不用再费尽心思设计 $\alpha^{(k)}$,步长变成了固定的 $\rho$;并且在更一般情况下(例如目标函数不严格凸)收敛,解释如下:

为了简便,我们假设 $f$ 可微(尽管这个算法并不要求 $f$ 必须可微),那么原问题和对偶问题将满足 KKT 条件:

$$ \begin{aligned} Ax^{\bigstar}-b =& 0\\ \bigtriangledown f(x^{\bigstar}) + a^Ty^{\bigstar} =& 0 \qquad{(1.5.4)} \end{aligned} $$

其中 $x^{\bigstar},y^{\bigstar}$ 表示最优解。(1.5.3)中要 $\mathop{\arg\min}\limits_{x}L_\rho(x,y^{(k)})$,所以:

$$ \begin{aligned} 0 =& \bigtriangledown_xL_\rho(x^{(k+1)},y^{(k)}) \\ =& \bigtriangledown_xf(x^{(k+1)}) + A^T(y^{(k)} + \rho (Ax^{(k+1)} -b)) \text{(带入 1.5.1)}\\ =& \bigtriangledown_xf(x^{(k+1)}) + A^Ty^{(k+1)} \text{(带入 1.5.3.2)} \end{aligned} $$

发现得到的形式与(1.5.4)是一致的,表明 $k+1$ 步的对偶问题有可行解,于是这一轮就有最优解。以此类推,$Ax^{(k+1)} – b$ 最终会收敛至 0。

但是,增广拉格朗日乘子法也有缺点:本来对偶上升方法是可以分解参数(broadcast),并行计算的,现在多了 $\frac{\rho}{2}\|Ax-b\|_2^2$ 这一项,无法分解。下面的 ADMM 就来解决这个问题。

2. 交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)

2.1 一般问题

为了对偶分解,我们把等式约束问题(1.3.1)分解:

$$ \begin{aligned} \min \quad & f_(x) + g_(z)\\ s.t. \quad & Ax + Bz = c \qquad{(2.1)} \end{aligned} $$

(1.3.1)中的自变量 $x$ 被分解成(2.1)中的 $x,z$ 两部分。[10] 说“这种结构可以很容易地处理统计学习问题优化目标中的正则化项”,我不太明白。另外,[10] 说 ADMM 的分解(decomposition)是指 $f(x)$ 或 $g(z)$ 可分时,去分解 $f(x)$ 或 $g(z)$——这个也没错,但是我认为,是原来的 $x$ 分解成两组变量 $x \in R^n,z \in R^n$,“AD” 就指 $x,z$ 交叉迭代,(2.1)也叫 “2-block” 的凸优化问题。实际上,ADMM 几个 block 都可用,2-block 比较方便分析。

(2.1)的增广拉格朗日函数为

$$L_{\rho}(x,z,y) = f(x) + g(z) + y^{T} (Ax + Bz – c) + (\rho / 2)\ | Ax + Bz – c \| _{2}^{2}$$

那么它用对偶上升法的迭代形式为

$$ \begin{aligned} x^{(k + 1)} &:= \arg\min_{x} L_{\rho}(x, z^{(k)}, y^{(k)}) \\ z^{(k + 1)} &:= \arg\min_{z} L_{\rho}(x^{(k + 1)}, z, y^{(k)}) \\ y^{(k + 1)} &:= y^{(k)} + \rho (Ax^{(k + 1)} + Bz^{(k + 1)} – c) \end{aligned} $$

看上去,似乎这每一步都是按照 $x →z → y$ 的顺序优化的,就还是没能 decompose 成可以并行的。而由于 $x,z$ 地位是对称的(交换 $x$ 和 $z$,$f$ 和 $g$,$A$ 和 $B$,还是同一个 ADMM 问题,只是 $x$ 和 $z$ 更新顺序交换),因此实际上,$x → z → y$ 或者 $z → x → y$ 都是可以的,我们就两条线并行 broadcast:由 $y,z$ 推 $x$,由 $y,x$ 推 $z$。最后再 gather,由 $x,z$ 推 $y$。这样就能并行实现了。([12] P15: we get splitting since we minimize over x with z fixed, and vice versa)

接下来介绍它的 Scaled Form:

由于有公式 $2a^Tb + \|b\|^2_2 = \|a+b\|_2^2 – \|a\|^2_2$,替换 $L_{\rho}(x,z,y)$ 中的 $y^{T} (Ax + Bz – c) + (\rho / 2) \| Ax + Bz – c \| _{2}^{2}$:

令 $r = Ax – Bz – c$,$u = (1/\rho)y$,则有

$$ \begin{aligned} y^{T} 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} $$

那么 ADMM 的 scaled form 为

$$ \begin{aligned} x^{(k + 1)} &:= \arg\min_{x} \Big( f(x) + (\rho / 2) \| Ax + Bz^{(k)} – c + u^{(k)} \|_{2}^{2} \Big) \\ z^{(k + 1)} &:= \arg\min_{z} \Big( g(z) + (\rho / 2) \| Ax^{(k + 1)} + Bz – c + u^{(k)} \|_{2}^{2} \Big) \\ u^{(k + 1)} &:= u^{(k)} + Ax^{(k + 1)} + Bz^{(k + 1)} – c \end{aligned} $$

scaled form 好像只是为了方便写 = =

现在我们便搞清楚了 ADMM 这个方法,至于实际优化、并行实现等,先不学了就。

还有一个事情要注意:我们推导 ADMM 使用的是 2-block 问题,推广到 n-block,并不是“显然”的。这个后文再说。

2.2 收敛性(convergence)

见 [11]

2.3 停止准则

在原空间和对偶空间的残差 $r^{(k)},s^{(k)}$ 都比较小的时候终止。[7] 总结的比较好,图我直接拿来了:

3. ADMM 算法加速

$x$ 的更新即 $min \; f(x) + (\rho/2)\|Ax-v\|^2_2)$($v = Bz^{(k)} – c + u^{(k)}$ 在 $x$ 更新时是常数),$z$ 的更新也是对称的。很多特例中,能有对应的方法用来简化更新的过程。作者介绍了这四类:

3.1 Proximal operator

3.2 Quadratic objective

3.3 Smooth objective

3.4 Decomposition

看不懂,跳过。

4. 推广到 n-block

[14]

5. ADMM 的运用

[14,7]

6. 延伸阅读与运引用

[1] S. Boyd, Convex Optimization. Cambridge University Press, § 3.3

[2] S. Boyd, Convex Optimization. Cambridge University Press, § 5.1

[3] 【优化】对偶上升法(Dual Ascent)超简说明

[4] 拉格朗日乘子法,KKT条件,对偶问题

[5] 拉格朗日对偶问题(Lagrange duality)

[6] S. Boyd, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers

[7] 对偶上升法到增广拉格朗日乘子法到ADMM

[8] 凸优化:ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法系列之三:ADMM)(这大哥写了十几篇 ADMM 的文章,大约完整翻译了 boyd 的小册子,可惜太监了)

[9] 交替方向乘子法(ADMM)算法的流程和原理是怎样的? – 覃含章的回答 – 知乎

[10] 用ADMM实现统计学习问题的分布式计算

[11] ADMM算法的详细推导过程是什么? – 覃含章的回答 – 知乎

[12] S. Boyd, ADMM Slides

[13] Proximal Algorithm 入门

[14] 交替方向乘子法(ADMM)算法的流程和原理是怎样的? – 门泊东吴的回答 – 知乎

[mathjax]

Leave a Comment

电子邮件地址不会被公开。