19. 次梯度法与ADMM

# 次梯度

# 定义

1. 次梯度的定义

   $g$ 是函数 $f$（不一定凸）在点 $x$ 处的次梯度（subgradient），如果对所有 $y$ 都有：

   $$f(y) \geq f(x) + g^T(y - x)$$

   几何解释：

   • $(g, -1)$ 在点 $(x, f(x))$ 处支撑 $f$ 的上图（epigraph）
   • $f(x) + g^T(y - x)$ 是 $f$ 的全局（仿射）下估计

2. 次微分（Subdifferential）

   函数 $f$ 在点 $x$ 处的所有次梯度的集合称为 $f$ 在 $x$ 处的次微分，记为 $\partial f(x)$，它是一个闭凸集（可能为空）。

   重要性质：

   • 如果 $f$ 是凸函数，则 $\partial f(x)$ 非空
   • 如果 $f$ 在 $x$ 处可微，则 $\partial f(x) = \{\nabla f(x)\}$
   • 如果 $\partial f(x) = \{g\}$（单点集），则 $f$ 在 $x$ 处可微且 $g = \nabla f(x)$

3. 次梯度计算

   弱次梯度计算：找到一个次梯度 $g \in \partial f(x)$

   强次梯度计算：找到整个次微分 $\partial f(x)$，即 $f$ 在 $x$ 处的所有次梯度

   许多不可微凸优化的算法在每步只需要一个次梯度，因此弱计算就足够了。但某些算法、最优性条件等需要整个次微分。

4. 次梯度运算法则

   • 缩放：$\partial (\alpha f) = \alpha \partial f$，如果 $\alpha > 0$
   • 加法：$\partial (f_1 + f_2) = \partial f_1 + \partial f_2$（右边是集合的加法）
   • 变量的仿射变换：如果 $g(x) = f(Ax + b)$，则 $\partial g(x) = A^T \partial f(Ax + b)$
   • 有限点式最大值：如果 $f = \max_{i=1,\ldots,m} f_i$，则

     $$\partial f(x) = \operatorname{Co} \bigcup \left\{\partial f_i(x) \mid f_i(x) = f(x)\right\}$$

     即，在 $x$ 处"活跃"函数的次微分的并集的凸包

5. 例子

   考虑 $f(x) = |x|$：

   • 当 $x > 0$ 时，$\partial f(x) = \{1\}$
   • 当 $x < 0$ 时，$\partial f(x) = \{-1\}$
   • 当 $x = 0$ 时，$\partial f(0) = [-1, 1]$

   考虑 $f = \max\{f_1, f_2\}$，其中 $f_1$、$f_2$ 是凸且可微的：

   • 如果 $f_1(x_0) > f_2(x_0)$：唯一次梯度 $g = \nabla f_1(x_0)$
   • 如果 $f_2(x_0) > f_1(x_0)$：唯一次梯度 $g = \nabla f_2(x_0)$
   • 如果 $f_1(x_0) = f_2(x_0)$：次梯度形成线段 $[\nabla f_1(x_0), \nabla f_2(x_0)]$

# 基于次梯度的最优化条件

1. 无约束问题的最优性条件

   对于可微凸函数 $f$，我们有：

   $$f(x^*) = \inf_x f(x) \quad \Leftrightarrow \quad 0 = \nabla f(x^*)$$

   推广到不可微凸函数 $f$：

   $$f(x^*) = \inf_x f(x) \quad \Leftrightarrow \quad 0 \in \partial f(x^*)$$

2. 证明思路

   $x^*$ 是最优的当且仅当对所有 $x$ 有 $f(x) \geq f(x^*)$，或等价地：

   $$f(x) \geq f(x^*) + 0^T(x - x^*) \quad \text{对所有 } x$$

   因此，$x^*$ 是最优的当且仅当 $0 \in \partial f(x^*)$。

3. 分段线性优化的最优性条件

   对于分段线性优化 $f(x) = \max_{i=1,\ldots,m} (a_i^T x + b_i)$，次微分为：

   $$\partial f(x) = \operatorname{Co} \{a_i \mid a_i^T x + b_i = f(x)\}$$

   因此，$x^*$ 最小化 $f$ 当且仅当存在 $\lambda$ 使得：

   $$\lambda \geq 0, \quad \mathbf{1}^T \lambda = 1, \quad \sum_{i=1}^{m} \lambda_i a_i = 0$$

   其中如果 $a_i^T x^* + b_i < f(x^*)$，则 $\lambda_i = 0$。

# 次梯度法

1. 基本思想

   次梯度法是梯度下降法在不可微凸函数上的推广。对于无约束问题 $\min_x f(x)$，次梯度法的迭代公式为：

   $$x^{(k+1)} = x^{(k)} - \alpha_k g^{(k)}$$

   其中 $g^{(k)} \in \partial f(x^{(k)})$ 是 $f$ 在 $x^{(k)}$ 处的次梯度，$\alpha_k > 0$ 是步长。

2. 与梯度下降的区别

   • 次梯度方向不一定是下降方向（$f(x^{(k+1)})$ 可能大于 $f(x^{(k)})$）
   • 步长选择更加关键，通常需要满足：

     $$\sum_{k=1}^{\infty} \alpha_k = \infty, \quad \sum_{k=1}^{\infty} \alpha_k^2 < \infty$$

   • 收敛速度通常较慢，为 $O(1/\sqrt{k})$ 或 $O(1/k)$

3. 步长选择策略

   • 固定步长：$\alpha_k = \alpha$（适用于有界次梯度的情况）
   • 递减步长：$\alpha_k = \alpha_0 / \sqrt{k}$ 或 $\alpha_k = \alpha_0 / k$
   • 自适应步长：根据函数值变化调整

# 约束问题的次梯度法

# 原问题的投影次梯度法

1. 投影次梯度法

   对于约束问题 $\min_{x \in C} f(x)$，其中 $C$ 是闭凸集，投影次梯度法的迭代公式为：

   $$x^{(k+1)} = \mathcal{P}_C(x^{(k)} - \alpha_k g^{(k)})$$

   其中 $\mathcal{P}_C(\cdot)$ 是到集合 $C$ 的投影算子，$g^{(k)} \in \partial f(x^{(k)})$。

2. 投影算子

   投影算子定义为：

   $$\mathcal{P}_C(x) = \arg\min_{y \in C} \|y - x\|_2$$

   对于简单约束集（如盒子约束、球约束、单纯形等），投影算子有解析表达式。

# 对偶问题的投影次梯度法

1. 对偶问题

   对于原问题：

   $$\begin{array}{l} \min \quad f(x) \\ \text{s.t.} \quad Ax = b, \quad x \in C \end{array}$$

   对偶问题为：

   $$\max_{\nu} \quad g(\nu) = \inf_{x \in C} (f(x) + \nu^T(Ax - b))$$

2. 对偶次梯度法

   对偶函数 $g(\nu)$ 的次梯度可以通过求解原问题得到。对偶次梯度法的迭代公式为：

   $$\nu^{(k+1)} = \nu^{(k)} + \alpha_k h^{(k)}$$

   其中 $h^{(k)} \in \partial g(\nu^{(k)})$ 是对偶函数的次梯度。

# 约束优化的次梯度法

1. 一般约束问题

   对于问题：

   $$\begin{array}{l} \min \quad f(x) \\ \text{s.t.} \quad c_i(x) \leq 0, \quad i = 1, \ldots, m \\ \quad \quad \quad h_j(x) = 0, \quad j = 1, \ldots, p \end{array}$$

   可以使用罚函数法或增广拉格朗日法将其转化为无约束或简单约束问题，然后应用次梯度法。

2. 罚函数方法

   构造罚函数：

   $$\phi(x) = f(x) + \mu \sum_{i=1}^{m} \max(0, c_i(x))^2 + \mu \sum_{j=1}^{p} h_j(x)^2$$

   然后对 $\phi(x)$ 应用次梯度法，逐步增大罚参数 $\mu$。

# 原对偶次梯度法

1. 基本思想

   原对偶次梯度法同时更新原变量和对偶变量，利用原问题和对偶问题的结构。

2. 算法框架

   对于问题 $\min_{x \in C} f(x)$，其对偶为 $\max_{\nu} g(\nu)$，原对偶次梯度法同时更新：

   $$\begin{array}{l} x^{(k+1)} = \mathcal{P}_C(x^{(k)} - \alpha_k g_x^{(k)}) \\ \nu^{(k+1)} = \nu^{(k)} + \alpha_k g_\nu^{(k)} \end{array}$$

   其中 $g_x^{(k)}$ 和 $g_\nu^{(k)}$ 分别是原函数和对偶函数的次梯度。

3. 收敛性

   在适当的步长选择下，原对偶次梯度法可以同时收敛到原问题和对偶问题的最优解。

# 交替方向乘子法（ADMM）

1. 问题形式

   ADMM 适用于如下形式的问题（$f$、$g$ 为凸函数）：

   $$\begin{array}{l} \min \quad f(x) + g(z) \\ \text{s.t.} \quad Ax + Bz = c \end{array}$$

   两个变量集合，目标函数可分离。

2. 增广拉格朗日函数

   $$L_{\rho}(x, z, y) = f(x) + g(z) + y^T(Ax + Bz - c) + \frac{\rho}{2}\|Ax + Bz - c\|_2^2$$

   其中 $\rho > 0$ 是惩罚参数，$y$ 是对偶变量（拉格朗日乘子）。

3. ADMM 算法

   $$\begin{array}{l} x^{k+1} := \arg\min_x L_{\rho}(x, z^k, y^k) \quad \text{// $x$-最小化} \\ z^{k+1} := \arg\min_z L_{\rho}(x^{k+1}, z, y^k) \quad \text{// $z$-最小化} \\ y^{k+1} := y^k + \rho(Ax^{k+1} + Bz^{k+1} - c) \quad \text{// 对偶更新} \end{array}$$

   关键特点：

   • 如果对 $x$ 和 $z$ 联合最小化，则退化为乘子法
   • 相反，我们执行一次 Gauss-Seidel 方法
   • 由于固定 $z$ 最小化 $x$，反之亦然，我们得到了分离

4. 最优性条件

   对于可微情况，最优性条件为：

   • 原可行性：$Ax + Bz - c = 0$
   • 对偶可行性：$\nabla f(x) + A^T y = 0$，$\nabla g(z) + B^T y = 0$

   由于 $z^{k+1}$ 最小化 $L_{\rho}(x^{k+1}, z, y^k)$，我们有：

   $$\begin{array}{l} 0 = \nabla g(z^{k+1}) + B^T y^k + \rho B^T(Ax^{k+1} + Bz^{k+1} - c) \\ = \nabla g(z^{k+1}) + B^T y^{k+1} \end{array}$$

   因此，使用 ADMM 对偶变量更新，$(x^{k+1}, z^{k+1}, y^{k+1})$ 满足第二个对偶可行性条件。原可行性和第一个对偶可行性在 $k \to \infty$ 时达到。

5. 与乘子法的关系

   乘子法（Method of Multipliers）：

   • 使用增广拉格朗日函数来增强对偶上升法的鲁棒性
   • 迭代公式：

     $$\begin{array}{l} x^{k+1} := \arg\min_x L_{\rho}(x, y^k) \\ y^{k+1} := y^k + \rho(Ax^{k+1} - b) \end{array}$$

   • 优点：在更宽松的条件下收敛（$f$ 可以不可微、取值为 $+\infty$ 等）
   • 缺点：二次惩罚项破坏了 $x$-更新的分离性，无法进行分解

   ADMM：

   • 结合了乘子法的鲁棒性和分解能力
   • 可以看作是"鲁棒的对偶分解"或"可分解的乘子法"
   • 由 Gabay、Mercier、Glowinski、Marrocco 在 1976 年提出

6. 对偶分解

   如果 $f$ 是可分离的：

   $$f(x) = f_1(x_1) + \cdots + f_N(x_N), \quad x = (x_1, \ldots, x_N)$$

   则 $L$ 在 $x$ 中可分离：$L(x, y) = L_1(x_1, y) + \cdots + L_N(x_N, y) - y^T b$，其中 $L_i(x_i, y) = f_i(x_i) + y^T A_i x_i$。

   对偶上升法中的 $x$-最小化可以分解为 $N$ 个独立的最小化：

   $$x_i^{k+1} := \arg\min_{x_i} L_i(x_i, y^k)$$

   这些可以并行执行。

7. 应用

   ADMM 广泛应用于：

   • 分布式优化
   • 统计学习
   • 图像处理
   • 稀疏优化
   • 机器学习中的大规模优化问题