第3章凸分析与对偶：从次梯度到近端算子

学习目标：

超越微积分：理解为何图像处理核心模型（TV, $\ell_1$）不可导，并掌握次梯度（Subgradient）这一工具。

变换的艺术：像傅里叶变换处理卷积一样，掌握Fenchel 共轭如何将“复杂的非光滑项”转化为“简单的约束项”。

算法积木：深入理解近端算子（Proximal Operator）的物理含义与计算规则，它是搭建 ISTA, ADMM, Primal-Dual 算法的核心原子。

对偶桥梁：熟练运用 Moreau 分解，在原始空间和对偶空间之间自由切换，找到求解的捷径。

3.1 为什么我们需要凸分析？

在经典的图像处理（如高斯滤波、维纳滤波）中，我们处理的是线性算子和二次函数（Least Squares）。这些问题闭式解存在，且处处可导。

然而，现代图像复原（Image Restoration）的统治级模型通常具有以下特征：

非光滑（Non-smooth）：为了保护边缘，我们使用全变分（TV）或 $\ell_1$ 范数。这些函数在原点或特定方向上存在“尖角”，无法计算传统梯度。
约束（Constrained）：图像像素必须非负（$x \ge 0$），或者受限于动态范围（$0 \le x \le 255$）。约束条件本质上是无穷大的势能壁垒，也是非光滑的。

传统的 $\nabla f(x) = 0$ 失效了。我们需要一套处理“广义导数”和“集合映射”的数学语言，这就是凸分析。本章将为您提供后续章节（ADMM, Primal-Dual）所需的所有数学武器。

3.2 凸集与凸函数：优化的基石

3.2.1 凸集 (Convex Set)

如果集合 $C$ 中任意两点 $x, y$ 的连线都完全包含在 $C$ 中，即 $\theta x + (1-\theta)y \in C, \forall \theta \in [0,1]$，则称 $C$ 为凸集。

ASCII 直觉图：

      (凸集)               (非凸集)
    ___________          ___________
   /     .     \        /     .     \
  /     / \     \      /     /   \   \
 |     x---y     |    |     x     y   |
  \             /      \     \___/   /  <-- 连线穿过了外部
   \___________/        \___________/

成像中的凸集：

非负象限：$\{x | x_i \ge 0\}$（NMF 的基础）

$\ell_2$ 球：$\{x | |x|_2 \le \epsilon\}$（噪声约束）

半正定锥：$\{X | X \succeq 0\}$（SDP, 矩阵补全）

3.2.2 凸函数与强凸函数

凸函数：函数上方的区域（Epigraph）是凸集。或者：Jensen 不等式 $f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y)$ 成立。
强凸函数 (Strongly Convex)：比普通凸函数“更弯曲”。如果存在 $\mu > 0$ 使得 $f(x) - \frac{\mu}{2}|x|^2$ 依然是凸函数，则称 $f$ 为 $\mu$-强凸。

Rule of Thumb (收敛速度)：

优化普通凸函数，收敛速度通常是 $O(1/k)$ 或 $O(1/\sqrt{k})$。

优化强凸函数，收敛速度通常是线性的 $O(c^k)$（即对数坐标下的直线）。

这就是为什么我们在工程中有时会人为加上 $\frac{\epsilon}{2}|x|^2$ 这一项（Elastic Net），用微小的偏差换取指数级的收敛速度。

3.3 次梯度 (Subgradient)：处理“尖角”

对于光滑函数，梯度是唯一的切线斜率。对于非光滑函数（如 $|x|$ 在 0 处），可能存在无数条直线“支撑”在函数下方。

3.3.1 定义

向量 $g \in \mathbb{R}^n$ 被称为凸函数 $f$ 在点 $x$ 处的次梯度，如果满足： $$ f(z) \ge f(x) + \langle g, z-x \rangle, \quad \forall z $$ 所有次梯度的集合称为次微分 (Subdifferential)，记为 $\partial f(x)$。

3.3.2 经典案例：绝对值函数

对于 $f(x) = |x|$（一维）： $$ \partial |x| = \begin{cases} \{1\} & x > 0 \\ \{-1\} & x < 0 \\ [-1, 1] & x = 0 \quad (\text{核心：这里是一个区间}) \end{cases} $$ ASCII 直觉图：次梯度的几何意义

        f(z) = |z|
         \     /
          \   /
           \ /    <-- 尖点 x=0
      ------*------
       / /  |  \ \
      / /   |   \ \
    g=-1  g=-0.5  g=1

在 x=0 处，斜率为 -1 到 1 之间的任何直线，
都位于函数图像的下方（支撑线）。

3.3.3 费马定理的推广 (Fermat's Rule)

这是变分法中最核心的条件。$x^*$ 是凸函数 $f(x)$ 全局极小值点的充要条件是： $$ 0 \in \partial f(x^*) $$

物理直觉：如果不光滑点包含 0 斜率，那么它就是谷底。例如 $|x|$ 在 0 处，次微分 $[-1, 1]$ 包含 0，所以 0 是最小值。

3.4 Fenchel 共轭 (Conjugate)：换个角度看世界

在傅里叶变换中，时域的卷积等于频域的乘积。在凸分析中，我们有类似的对偶变换，称为 Fenchel-Legendre 变换。

3.4.1 定义

函数 $f(x)$ 的共轭函数 $f^*(y)$ 定义为： $$ f^*(y) = \sup_{x} \left( \langle y, x \rangle - f(x) \right) $$ 几何意义：给定斜率 $y$，寻找一个超平面 $\langle y, x \rangle - b$，使其刚好接触 $f(x)$ 的图像，此时的最大截距 $b$ 就是 $f^*(y)$。

3.4.2 关键共轭对（查表必备）

| 原函数 $f(x)$ | 共轭函数 $f^*(y)$ | 备注 |

原函数 $f(x)$	共轭函数 $f^*(y)$	备注
$\frac{1}{2}\|x\|_2^2$	$\frac{1}{2}\|y\|_2^2$	自共轭，二次函数的对偶还是二次
$\|x\|_1$	$\delta_{B_\infty}(y)$	$\ell_1$ 的对偶是 $\ell_\infty$ 球的指示函数
$\|x\|_2$	$\delta_{B_2}(y)$	$\ell_2$ 的对偶是 $\ell_2$ 球的指示函数
$\delta_C(x)$	$\sigma_C(y) = \sup_{x \in C} \langle y, x \rangle$	指示函数的对偶是支撑函数
$ax + b$	$\delta_{\{a\}}(y) - b$	线性函数的对偶是指示函数

深入理解：为什么 $\ell_1$ 的对偶是 Box 约束？ $\ell_1$ 正则化倾向于产生稀疏解（推向 0），其对偶问题则是将对偶变量“裁剪”到 $[-1, 1]$ 之间。这种投影操作往往比处理稀疏性更容易计算。这正是 Split Bregman 和 Primal-Dual 算法高效的原因。

3.5 近端算子 (Proximal Operator)：隐式梯度下降

在非光滑优化中，我们无法计算梯度，也不能直接令导数为 0。我们退而求其次，寻找一个“既能降低函数值，又不离当前点太远”的新点。

3.5.1 定义与物理意义

$$ \text{prox}_{\lambda f}(v) = \arg\min_x \left( f(x) + \frac{1}{2\lambda}|x - v|_2^2 \right) $$ 或者等价地写成（更常见的形式）： $$ \text{prox}_{\tau f}(v) = \arg\min_x \left( \frac{1}{2}|x - v|_2^2 + \tau f(x) \right) $$

物理直觉：假设 $v$ 是带噪观测，$f(x)$ 是先验能量。Prox 实际上就是在求 MAP 估计（去噪）。
动力学直觉：Prox 对应于梯度流的后向欧拉（Backward Euler）离散化，具有极好的数值稳定性。即使步长很大，它也不会像显式梯度下降那样爆炸。

3.5.2 常用 Prox 算子清单

软阈值 (Soft Thresholding) —— $\ell_1$ 范数 $$ f(x) = \lambda |x|_1 \implies [\text{prox}_{f}(v)]_i = \text{sign}(v_i)\max(|v_i| - \lambda, 0) $$ 代码实现常写作 shrink(v, lambda)。这是小波去噪、Lasso、压缩感知的核心。
投影 (Projection) —— 指示函数 $$ f(x) = \delta_C(x) \implies \text{prox}_f(v) = \text{proj}_C(v) = \arg\min_{x \in C} |x-v|^2 $$ 如果 $C$ 是非负象限，则投影就是 max(v, 0)。
线性收缩 —— 二次函数 $$ f(x) = \frac{\lambda}{2}|x|^2 \implies \text{prox}_f(v) = \frac{v}{1+\lambda} $$ Tikhonov 正则化的 Prox 只是简单的缩放。

3.5.3 Prox 的微积分性质

可分离性：如果 $f(x, y) = g(x) + h(y)$，则 $\text{prox}_f(v, w) = (\text{prox}_g(v), \text{prox}_h(w))$。这允许我们将图像像素并行处理。
仿射变换：一般情况下，$\text{prox}_{f(Ax)}$ 没有封闭解（这正是我们需要 ADMM 的原因）。但如果 $A$ 是正交基（如正交小波变换 $W$），且 $f(x) = |Wx|_1$，则： $$ \text{prox}_{f}(v) = W^T \cdot \text{soft}(W v, \lambda) $$

3.6 Moreau 分解 (Moreau Decomposition)

这是本章的杀手锏。它像线性代数中的“正交分解”一样，联系了原空间和对偶空间。

3.6.1 定理陈述

对于任意凸函数 $f$，适当的 $\lambda > 0$ 和向量 $v$，有： $$ v = \text{prox}_{\lambda f}(v) + \lambda \text{prox}_{f^*/\lambda}(v/\lambda) $$

3.6.2 威力展示：如何计算 TV 范数的 Prox？

求解全变分去噪（ROF 模型）的 Prox： $$ \min_x \frac{1}{2}|x-v|^2 + \lambda \text{TV}(x) $$ 直接求 $\text{prox}_{\text{TV}}$ 非常困难，因为 TV 项不可分且不可导。

利用 Moreau 分解的思路：

TV 范数可以看作是 $\ell_1$ 范数与梯度算子的复合，其对偶 $f^*$ 往往对应于一个凸集 $K$ 的指示函数（对于 TV，这个凸集是 $\text{div}(p)$ 形式的对偶球）。
$\text{prox}_{f^*}$ 就变成了投影到集合 $K$。
如果我们能快速计算投影（通过对偶算法），我们就能通过 Moreau 分解公式直接得到原问题的解： $$ \text{prox}_{\lambda \text{TV}}(v) = v - \lambda \cdot \text{proj}_K(v/\lambda) $$

结论：很多时候，求解“去噪”问题（Prox）等价于求解其对偶的“投影”问题，然后再用原信号减去残差。

3.7 光滑与非光滑的混合：Lipschitz 连续梯度

在第6章（PGD/FISTA）中，我们将处理 $F(x) = f(x) + g(x)$，其中 $f$ 光滑，$g$ 非光滑。

3.7.1 L-Lipschitz 连续梯度

函数 $f$ 的梯度是 $L$-Lipschitz 连续的，意味着梯度的变化速度有上限： $$ |\nabla f(x) - \nabla f(y)| \le L |x - y|, \quad \forall x, y $$ 其中 $L$ 称为 Lipschitz 常数。对于二次函数 $f(x) = \frac{1}{2}|Ax-y|^2$，其 $L = |A|^2_{op}$（$A$ 的最大奇异值的平方）。

3.7.2 为什么要关心 L？

它是步长（Step Size）的交警。

在显式梯度下降中，步长 $\tau$ 必须满足 $\tau < 2/L$（通常取 $1/L$）才能保证收敛。
步长选大了 $\to$ 震荡发散。
步长选小了 $\to$ 收敛极慢。
Rule of Thumb：在做图像反问题时，先用 Power Method 估算算子 $A$ 的谱范数，然后固定步长，比手动调参靠谱得多。

3.8 本章小结

不可导不是终点：次梯度提供了处理尖角的理论依据，费马定理 $0 \in \partial f(x)$ 是所有变分问题的起点。
对偶是捷径：$\ell_1$ 的对偶是 Box 约束，TV 的对偶是投影。掌握共轭函数表能让你在设计算法时看到“隐藏通道”。
Prox 是算子分裂的原子：现代优化算法（ADMM, Primal-Dual）本质上是在不断调用 Prox。$\text{prox}_{\ell_1}$ 是软阈值，$\text{prox}_{\ell_2^2}$ 是线性收缩。
Moreau 分解：$x = P_K(x) + P_{K^\circ}(x)$ 的广义形式，允许我们在原问题和对偶问题间灵活切换求解。

3.9 练习题

基础题

(次梯度的非唯一性) 画出函数 $f(x) = \max(x, 0) + |x-1|$ 的图像，并写出它在 $x=0, x=0.5, x=1$ 处的次微分。

Hint: 在不可导点，次微分是左导数和右导数构成的区间。
(Huber 函数的性质) Huber 函数定义为： $$ H_\delta(x) = \begin{cases} \frac{1}{2}x^2 & |x| \le \delta \\ \delta|x| - \frac{1}{2}\delta^2 & |x| > \delta \end{cases} $$ 证明 Huber 函数是凸的，且其梯度是 Lipschitz 连续的。

Hint: 计算其一阶导数，看是否连续且斜率有限。
(Moreau 分解验证) 令 $f(x) = \frac{1}{2}|x|^2$。计算 $\text{prox}_{\lambda f}(v)$ 和 $\text{prox}_{f^*/\lambda}(v/\lambda)$，并验证 Moreau 分解等式是否成立。

挑战题

(组稀疏 Group Lasso 的 Prox) 考虑函数 $R(x) = \sum_{g \in G} |x_g|_2$，其中 $x_g$ 是向量 $x$ 的分组子向量（非重叠）。推导其近端算子。

Hint: 问题可对每个组分离求解。这实际上是 Block Soft Thresholding：$x_g \leftarrow x_g \cdot \max(0, 1 - \lambda/|x_g|_2)$。
(对偶范数) 证明 $\ell_1$ 范数的对偶范数是 $\ell_\infty$ 范数，即 $|z|_\infty = \sup \{ \langle z, x \rangle : |x|_1 \le 1 \}$。这一性质如何解释 $\text{prox}_{\ell_1}$ 和投影到 $\ell_\infty$ 球的关系？
(核范数的 Prox) 矩阵核范数 $|X|_*$ 是矩阵奇异值之和。证明其近端算子（Singular Value Thresholding, SVT）等价于对奇异值做软阈值处理。

Hint: 利用酉不变性质，将矩阵问题转化为对角线向量的 $\ell_1$ 问题。

3.10 常见陷阱与错误 (Gotchas)

Lipschitz 常数估计错误： - 错误：直接设步长为 0.1 或 0.01 碰运气。 - 后果：对于去模糊等病态问题，$A$ 的奇异值跨度很大，瞎猜步长会导致高频噪声爆炸。 - 修正：务必计算 $|A|^2$，如果不确定，使用 Backtracking Line Search（回溯线搜索）。
Moreau 分解中的系数混乱： - 错误：记错公式为 $v = \text{prox}_f(v) + \text{prox}_{f^*}(v)$。 - 后果：分解完全失效，残差无法消除。 - 记忆法：$\lambda$ 总是成对出现的。如果是 $v/\lambda$ 作为输入，外面必须乘 $\lambda$ 来恢复量纲。
误用 Prox 算子求解 $f(Ax)$： - 错误：认为 $\text{prox}_{f(A\cdot)}(v) = A^{-1}\text{prox}_f(Av)$。 - 修正：除非 $A A^T = I$（正交/幺正），否则这是错的。对于一般线性算子，必须使用 ADMM 或 Primal-Dual 算法将其分裂为 $f$ 的 Prox 和 $A$ 的线性求解两个子问题。
对“不可导”产生恐惧： - 错误：试图通过加一个小量 $\epsilon$ 把 $|x|$ 平滑成 $\sqrt{x^2+\epsilon}$ 来用传统梯度下降。 - 观点：虽然这样能跑，但你失去了真正的稀疏性（结果会有很多 $10^{-6}$ 而不是 $0$）。学会使用 Soft Thresholding 才能得到真正的稀疏解。

第3章 凸分析与对偶：从次梯度到近端算子