• 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]