第二章：算子理论与不动点

2.1.1 五种映射的定义#

设映射 $T: \mathbb{R}^n \to \mathbb{R}^n$。

Lipschitz 连续映射。 若存在常数 $L > 0$ 使得

则称 $T$ 是 Lipschitz 连续的，$L$ 称为 Lipschitz 常数。映射的输出变化被输入变化的 $L$ 倍所控制。

Lipschitz 连续性在优化中最常见的体现是梯度算子。设 $f$ 是可微凸函数且 $\nabla^2 f(x) \preceq LI$（Hessian 矩阵的特征值不超过 $L$），则梯度映射 $T = \nabla f$ 满足 $\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|$，即 $\nabla f$ 是 Lipschitz 常数为 $L$ 的 Lipschitz 连续映射。这个条件在第三章梯度下降法的步长选取中起到关键作用：步长 $\eta$ 必须满足 $\eta \leq 1/L$ 才能保证收敛，$L$ 越大意味着梯度变化越剧烈，允许的步长越小。

压缩映射。 若存在常数 $c \in (0, 1)$ 使得

则称 $T$ 是压缩映射（contraction）。这是 Lipschitz 常数严格小于 1 的特殊情形，意味着 $T$ 会严格缩短任意两点之间的距离。

非扩张映射。 若

则称 $T$ 是非扩张映射（nonexpansive），即映射不增加两点间的距离，对应 Lipschitz 常数 $L = 1$。

稳定非扩张映射。 若

则称 $T$ 是稳定非扩张映射（firmly nonexpansive）。这一条件比非扩张性更强，其额外约束可以从内积的几何含义来理解。非扩张性只控制模长：$\|Tx-Ty\| \leq \|x-y\|$，即输出的位移不比输入的位移更长。稳定非扩张性进一步控制方向：右端的内积 $\langle x-y, Tx-Ty\rangle = \|x-y\|\cdot\|Tx-Ty\|\cos\theta$（$\theta$ 是 $x-y$ 与 $Tx-Ty$ 之间的夹角），因此定义式等价于 $\|Tx-Ty\| \leq \|x-y\|\cos\theta$，即输出位移 $Tx-Ty$ 的方向必须与输入位移 $x-y$ 的方向足够一致（$\cos\theta$ 接近 1），否则 $\|Tx-Ty\|$ 必须更小来补偿。换言之，稳定非扩张性排除了”保持距离但大幅改变方向”的行为——而这种旋转型行为恰恰是导致非扩张映射不动点迭代不收敛的根源（第 2.2.3 节将给出具体反例）。

稳定非扩张映射在优化中有一个非常重要的例子——闭凸集上的投影算子。第 2.4 节将证明投影算子 $P_\Omega$ 满足稳定非扩张性。直觉上，投影操作不仅不会增大两点之间的距离，而且投影后的位移方向与原始位移方向始终保持一定的一致性（因为投影总是朝着凸集”靠拢”，不会出现反向偏移的情况）。

余强制映射。 若存在常数 $\delta > 0$ 使得

则称 $T$ 是余强制映射（cocoercive），$\delta$ 称为余强制系数。当 $\delta = 1$ 时，余强制退化为稳定非扩张。

余强制性在优化中的典型体现是光滑强凸函数的梯度。若 $f$ 是 $L$-光滑凸函数（$\nabla f$ 的 Lipschitz 常数为 $L$），则 $\nabla f$ 是 $1/L$-余强制的，即 $\langle \nabla f(x) - \nabla f(y), x - y \rangle \geq \frac{1}{L}\|\nabla f(x) - \nabla f(y)\|^2$。这个性质称为 Baillon-Haddad 定理，它直接说明了梯度算子的收缩能力与函数光滑度之间的关系。

2.1.2 映射间的蕴含关系#

五种映射之间存在如下蕴含链：

前两条蕴含是直接的（令 $c \leq 1$ 或 $L = 1$）。后面的蕴含需要证明。

稳定非扩张 $\Rightarrow$ 非扩张。 对稳定非扩张的定义式右端应用 Cauchy-Schwarz 不等式：

若 $\|Tx - Ty\| = 0$ 则结论显然成立。否则两边除以 $\|Tx - Ty\|$，得 $\|Tx - Ty\| \leq \|x - y\|$，即非扩张性。

余强制 $\Rightarrow$ Lipschitz 连续。 类似地，对余强制定义式右端应用 Cauchy-Schwarz 不等式：

两边除以 $\|Tx - Ty\|$（非零时），得 $\|Tx - Ty\| \leq \frac{1}{\delta}\|x - y\|$，即 Lipschitz 常数 $L = 1/\delta$。

这些蕴含关系的实际意义在于：越强的映射条件给出越好的收敛性保证。我们将在下一节看到，压缩映射保证线性收敛，非扩张映射只能保证有界性，而稳定非扩张映射恰好处在能证明收敛的”甜蜜点”上。学习这些映射类型不是为了分类学本身，而是因为后续每一章的算法收敛性证明都需要判断迭代算子属于哪一类映射，从而决定能够得到什么样的收敛性结论。

2.2.1 不动点方程与不动点迭代#

设映射 $T: \mathbb{R}^n \to \mathbb{R}^n$。若 $x^* = T(x^*)$，则称 $x^*$ 为 $T$ 的不动点，$x = T(x)$ 称为不动点方程。求解不动点方程的最自然方法是不动点迭代：从初始点 $x^0$ 出发，按

逐步更新。若序列 $\{x^k\}$ 收敛到某个极限 $x^*$，则对迭代公式两边取极限即得 $x^* = T(x^*)$，说明极限点就是不动点。

核心问题随之浮现：映射 $T$ 需要满足什么条件，不动点迭代才能收敛？

2.2.2 压缩映射下的收敛性#

当 $T$ 是压缩映射（$\|Tx - Ty\| \leq c\|x - y\|$，$c \in (0,1)$）时，收敛性证明最为直接。设 $x^*$ 是不动点，则

当 $k \to \infty$ 时，$c^k \to 0$，由夹逼准则得 $\|x^k - x^*\| \to 0$。这是 R-线性收敛，收敛率为 $c$。

压缩映射条件虽然很强，但使用简便——只需递推即可证明收敛。

2.2.3 非扩张映射下的困难#

当 $T$ 仅满足非扩张性（$\|Tx - Ty\| \leq \|x - y\|$）时，类似的递推只能给出

这说明序列 $\{x^k\}$ 有界（$\|x^k - x^*\|$ 单调不增），但无法证明 $\|x^k - x^*\| \to 0$。非扩张条件太弱，不足以保证收敛。

旋转映射的反例。 考虑二维平面上的 90 度旋转映射 $T(x_1, x_2) = (-x_2, x_1)$。首先验证 $T$ 是非扩张的：$\|Tx\|^2 = x_2^2 + x_1^2 = \|x\|^2$，即 $T$ 保持距离（实际上是等距映射），因此 $\|Tx - Ty\| = \|T(x-y)\| = \|x-y\|$，非扩张性成立。$T$ 的唯一不动点是原点 $x^* = (0,0)$。然而，从 $x^0 = (1, 0)$ 出发的迭代序列为

序列以周期 4 振荡，始终停留在单位圆上，不收敛到原点。这个反例精确地展示了非扩张映射不收敛的机制：旋转保持了距离（$\|x^k - x^*\| = 1$ 恒成立），但不断改变方向，导致迭代点在不动点周围”绕圈”而无法靠近。这也解释了第 2.1 节中稳定非扩张性的”方向一致性”要求为何必要——它正是为了排除这种旋转型行为。

2.2.4 稳定非扩张映射下的收敛性：四步标准范式#

稳定非扩张映射（$\|Tx - Ty\|^2 \leq \langle x - y, Tx - Ty \rangle$）的强度介于压缩和非扩张之间，恰好能够证明收敛。这里的证明过程分为四步，构成了优化理论中收敛性证明的标准范式——后续章节中几乎所有算法的收敛性分析都遵循同一框架。

第一步：建立 Fejér 单调性。 目标是证明

即每步迭代后，到不动点的距离严格下降，且下降量至少为步长的平方。

由 $x^{k+1} = Tx^k$ 和 $x^* = Tx^*$（不动点条件），有 $x^{k+1} - x^* = Tx^k - Tx^*$。将其拆分为

展开范数平方：

现在处理交叉项。对 $x^k - x^*$ 进行加减 $x^{k+1}$：

代入 $x^{k+1} - x^k = Tx^k - x^k$ 和 $x^{k+1} - x^* = Tx^k - Tx^*$：

下面对内积项 $\langle Tx^k - x^k,\, Tx^k - Tx^*\rangle$ 利用稳定非扩张性进行放缩。将 $Tx^k - x^k$ 改写为 $(Tx^k - Tx^*) - (x^k - Tx^*)$：

由稳定非扩张性 $\|Tx^k - Tx^*\|^2 \leq \langle x^k - x^*,\, Tx^k - Tx^*\rangle$，将右端改写为

（利用 $x^* = Tx^*$），于是稳定非扩张性给出 $\|Tx^k - Tx^*\|^2 \leq \langle x^k - Tx^*,\, Tx^k - Tx^*\rangle$。代入上式：

因此交叉项满足

代入 $(\dagger)$ 式：

Fejér 单调性得证。

满足 $\|x^{k+1} - x^*\|^2 \leq \|x^k - x^*\|^2$ 的序列称为关于 $x^*$ 的 Fejér 单调序列。Fejér 单调性是优化收敛性证明的核心中间结论：在研究论文中，证明的前半部分通常致力于建立 Fejér 单调性，后半部分则沿着下述标准化流程推进。

这一步是四步框架中最关键也最困难的一步。对于不同的算法，Fejér 单调性的具体形式和推导细节各不相同（下降量可能是 $\|x^{k+1} - x^k\|^2$，也可能是 $\|x^k - Nx^k\|^2$ 或其他量），但总体思路一致：通过算子的结构性质，从迭代的递推关系中挤出一个严格正的下降项。

第二步：证明相邻迭代差趋于零。 由 Fejér 单调性移项得

对 $k = 0, 1, \ldots, K$ 累加，右端形成 telescoping sum（逐项相消）：

令 $K \to \infty$，级数收敛。由级数收敛的必要条件，通项趋于零：$\|x^{k+1} - x^k\| \to 0$。

这一步的核心技巧是 telescoping sum：对 Fejér 单调性不等式从 $k=0$ 到 $K$ 求和后，右端大量项逐对相消，只剩下首尾两项之差。这一技巧之所以有效，是因为 Fejér 单调性保证了 $\|x^k - x^*\|^2$ 单调递减，从而求和的右端被初始距离 $\|x^0 - x^*\|^2$ 所控制。级数 $\sum_{k=0}^{\infty} \|x^{k+1} - x^k\|^2$ 的收敛意味着每一步的移动量终将趋于零，但尚不能说明序列收敛到何处。

第三步：证明子列收敛到不动点。 Fejér 单调性保证 $\|x^k - x^*\|$ 单调递减且有下界（$\geq 0$），故收敛（但尚不知收敛到什么值）。由三角不等式 $\|x^k\| \leq \|x^k - x^*\| + \|x^*\|$，序列 $\{x^k\}$ 有界。由 Bolzano-Weierstrass 定理，有界序列必有收敛子列 $x^{k_j} \to x_\infty$。

这里用到 Bolzano-Weierstrass 定理的原因是：我们只知道 $\{x^k\}$ 有界，还不知道它是否收敛。Bolzano-Weierstrass 定理保证有界序列至少有一个聚点，我们先证明这个聚点是不动点，然后再证明它是唯一的聚点。

利用第二步的结论 $\|x^{k+1} - x^k\| \to 0$ 和三角不等式，可得 $x^{k_j+1} \to x_\infty$。对迭代公式 $x^{k_j+1} = T(x^{k_j})$ 取极限，得 $x_\infty = T(x_\infty)$，即 $x_\infty$ 是不动点。

第四步：证明全序列收敛。 由第二步知 $\|x^k - x^*\|$ 收敛到某值 $a$。取 $x^* = x_\infty$（第三步已证 $x_\infty$ 是不动点），有 $\|x^{k_j} - x_\infty\| \to 0$，说明 $a = 0$。由收敛数列的性质——若存在趋于 0 的子列，则全序列趋于 0——得 $\|x^k - x_\infty\| \to 0$，即 $x^k \to x_\infty \in \text{Fix}(T)$。

最后这一步利用了实数列的一个基本性质：单调有界数列收敛，且若其某个子列收敛到 $0$，则全序列收敛到 $0$。$\{\|x^k - x_\infty\|\}$ 恰好满足这两个条件——它单调不增（Fejér 单调性），且存在趋于 $0$ 的子列（$\|x^{k_j} - x_\infty\| \to 0$）。

这四步证明框架——Fejér 单调性、telescoping 求和、子列收敛、全序列收敛——将在第三章梯度下降法、第四章投影梯度法、第五章邻近算法的收敛性分析中反复出现。

2.3.1 均值算子的定义#

设 $N$ 是一个非扩张算子，$I$ 是恒等映射，$\alpha \in (0, 1)$。定义算子

这样的 $T$ 称为均值算子（averaged operator）。直觉上，$T$ 是恒等映射与非扩张算子 $N$ 的凸组合，以系数 $\alpha$ 控制两者的混合比例。均值算子有两条核心性质：

1. $T$ 是非扩张的；进一步，当 $\alpha = 1/2$ 时，$T$ 是稳定非扩张的。
2. Krasnosel’skii-Mann 定理（KM 定理）：不动点迭代 $x^{k+1} = Tx^k$ 产生的序列 $\{x^k\}$ 收敛到不动点。

在展开证明之前，先建立一个贯穿全局的代数工具。

2.3.2 凸组合范数展开等式#

引理。 设 $a + b = 1$，$a, b \in [0, 1]$，则对任意 $x, y$：

$$\|ax + by\|^2 = a\|x\|^2 + b\|y\|^2 - ab\|x - y\|^2$$

证明。 在一维情形下验证。将 $b = 1 - a$ 代入右端：

展开 $(x - y)^2 = x^2 - 2xy + y^2$：

合并 $x^2$ 的系数：$a - a(1-a) = a^2$；合并 $y^2$ 的系数：$(1-a) - a(1-a) = (1-a)^2 = b^2$。于是

一维情形成立后，推广到内积空间同样成立。$\blacksquare$

这一等式的价值在于：它将凸组合的范数平方表达为各分量范数平方的加权和减去一个”交叉惩罚项” $ab\|x - y\|^2$。在后续证明中，这个惩罚项正是产生 Fejér 单调性所需的”下降量”。

2.3.3 均值算子的非扩张性#

目标。 证明 $\|Tx - Ty\| \leq \|x - y\|$。

将 $T$ 的定义代入：

这是一个凸组合的范数平方（$(1-\alpha) + \alpha = 1$），应用上述引理得

式 $(\star)$ 的最后一项 $\alpha(1-\alpha)\|(x-y) - (Nx - Ny)\|^2 \geq 0$，因此

再利用 $N$ 的非扩张性 $\|Nx - Ny\| \leq \|x - y\|$，得

因此 $\|Tx - Ty\|^2 \leq \|x - y\|^2$，即 $T$ 是非扩张的。$\blacksquare$

2.3.4 $\alpha = 1/2$ 时的稳定非扩张性#

目标。 当 $\alpha = 1/2$ 时，证明 $\|Tx - Ty\|^2 \leq \langle x - y,\, Tx - Ty \rangle$。

取 $\alpha = 1/2$，此时 $T = \frac{1}{2}I + \frac{1}{2}N$。代入定义展开平方：

利用 $\|u+v\|^2 = \|u\|^2 + \|v\|^2 + 2\langle u, v\rangle$ 展开并整理：

利用 $N$ 的非扩张性 $\|Nx - Ny\|^2 \leq \|x - y\|^2$：

将右端改写为内积形式：注意 $\|x-y\|^2 = \langle x-y, x-y \rangle$，因此

于是

这正是稳定非扩张的定义。$\blacksquare$

2.3.5 Krasnosel’skii-Mann 定理#

KM 定理。 若 $T = (1-\alpha)I + \alpha N$ 是均值算子（$N$ 非扩张，$\alpha \in (0,1)$），$x^*$ 是 $T$ 的不动点，则不动点迭代 $x^{k+1} = Tx^k$ 产生的序列收敛到 $x^*$。

证明的关键第一步是建立 Fejér 单调性。后续步骤（有界性、收敛子列、全序列收敛）与第 2.2.4 节的四步框架完全平行，此处仅详证 Fejér 单调性。

Fejér 单调性的建立。 由不动点迭代 $x^{k+1} = Tx^k$ 和 $T$ 的定义：

应用凸组合范数展开等式：

这里需要一个关键观察：$x^*$ 是 $T$ 的不动点，即 $x^* = (1-\alpha)x^* + \alpha Nx^*$，化简得 $\alpha x^* = \alpha Nx^*$。由于 $\alpha \neq 0$，所以 $x^* = Nx^*$——$T$ 的不动点也是 $N$ 的不动点。于是 $\|Nx^k - x^*\|^2 = \|Nx^k - Nx^*\|^2$。利用 $N$ 的非扩张性：

代入并合并前两项：

由于 $\alpha \in (0,1)$，有 $\alpha(1-\alpha) > 0$，Fejér 单调性成立。$\blacksquare$

后续步骤。 建立 Fejér 单调性后，完整证明的剩余步骤如下：

1. 由 Fejér 单调性，$\{\|x^k - x^*\|^2\}$ 单调递减有下界，故收敛。对递推式从 $k=0$ 到 $\infty$ 求和得 $\sum_{k=0}^{\infty} \alpha(1-\alpha)\|x^k - Nx^k\|^2 < \infty$，从而 $\|x^k - Nx^k\| \to 0$。
2. 由 $\|x^k - x^*\|$ 有界，$\{x^k\}$ 有界，存在收敛子列 $x^{k_j} \to x_\infty$。
3. 由 $x^{k_j} \to x_\infty$ 和 $\|x^{k_j} - Nx^{k_j}\| \to 0$，三角不等式给出 $\|Nx^{k_j} - x_\infty\| \leq \|Nx^{k_j} - x^{k_j}\| + \|x^{k_j} - x_\infty\| \to 0$，故 $Nx^{k_j} \to x_\infty$。另一方面，$N$ 是非扩张映射，因此是连续的（$\|Nx - Ny\| \leq \|x-y\|$ 直接给出 Lipschitz 连续性），所以 $Nx^{k_j} \to Nx_\infty$。由极限唯一性，$Nx_\infty = x_\infty$，即 $x_\infty$ 是 $N$ 的不动点，从而也是 $T$ 的不动点。
4. 利用 Fejér 单调性证明整个序列 $x^k \to x_\infty = x^*$。

这些步骤与第 2.2.4 节中稳定非扩张映射的证明框架完全一致，仅系数不同，不影响论证结构。KM 定理的意义在于：即使原始算子 $N$ 仅满足非扩张性（不足以保证收敛），将其与恒等映射做凸组合后得到的均值算子 $T$ 的不动点迭代仍然收敛。这为算法设计提供了一种通用的”升级”策略。

2.4.1 投影算子及其钝角性质#

设 $\Omega \subseteq \mathbb{R}^n$ 是一个非空闭凸集。点 $x \in \mathbb{R}^n$ 在 $\Omega$ 上的投影定义为 $\Omega$ 中距 $x$ 最近的点，记作 $P_\Omega(x)$。投影算子有一个核心的钝角性质（第一章已经建立）：对任意 $z \in \Omega$，

几何含义是：向量 $z - P_\Omega(x)$（从投影点指向凸集内任意一点）与向量 $x - P_\Omega(x)$（从投影点指向原始点）之间的夹角不小于 90 度。

2.4.2 稳定非扩张性的证明#

目标。 证明投影算子 $P_\Omega$ 满足稳定非扩张性，即对任意 $x, y \in \mathbb{R}^n$：

第一步：写出两个投影不等式。 由 $P_\Omega(x)$ 的投影性质，对任意 $z \in \Omega$ 有

同理，由 $P_\Omega(y)$ 的投影性质：

第二步：交叉代入。 由于 $P_\Omega(x), P_\Omega(y) \in \Omega$，可以在式 (1) 中令 $z = P_\Omega(y)$，在式 (2) 中令 $z = P_\Omega(x)$：

第三步：两式相加。 将 $(1')$ 和 $(2')$ 相加。注意第二个内积中 $P_\Omega(x) - P_\Omega(y) = -(P_\Omega(y) - P_\Omega(x))$，提取公因子 $P_\Omega(y) - P_\Omega(x)$：

整理括号内的项：

第四步：展开并移项。 利用内积的双线性性展开：

将第一项移到右边并取负号：

$\blacksquare$

证明的关键技巧在于交叉代入：投影的钝角性质对凸集内任意点 $z$ 成立，而两个投影点 $P_\Omega(x)$ 和 $P_\Omega(y)$ 本身就在凸集内，因此可以将一个投影点作为另一个不等式中的 $z$，从而将两个独立的投影不等式耦合在一起。

2.4.3 对不动点迭代的意义#

由第 2.2.4 节的一般理论，稳定非扩张算子的不动点迭代 $x^{k+1} = T(x^k)$ 收敛到不动点。现在取 $T = P_\Omega$，上述证明确认了投影算子是稳定非扩张的，因此投影迭代

收敛到 $P_\Omega$ 的不动点。投影算子的不动点恰好是 $\Omega$ 中的点（对 $\Omega$ 中的点 $x^*$，有 $P_\Omega(x^*) = x^*$）。这一结论为第四章中基于投影的优化算法提供了收敛性的理论基础。

2.5.1 次梯度与次微分#

设 $f: \mathbb{R}^n \to \mathbb{R}$ 是凸函数。若存在向量 $v \in \mathbb{R}^n$ 使得对任意 $y \in \mathbb{R}^n$ 均成立

则称 $v$ 为 $f$ 在 $x$ 处的一个次梯度（subgradient）。$f$ 在 $x$ 处所有次梯度的集合称为 $f$ 在 $x$ 处的次微分（subdifferential），记为 $\partial f(x)$。

将此定义与第一章中凸函数的一阶条件 $f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle$ 对比，可以看出次梯度的定义形式完全一致，只是将梯度 $\nabla f(x)$ 替换为一般的向量 $v$。这正是”次微分是梯度的推广”的含义。

与梯度的关系。 当 $f$ 在 $x$ 处可微时，满足上述不等式的 $v$ 只有一个，即 $v = \nabla f(x)$，此时次微分退化为单点集 $\partial f(x) = \{\nabla f(x)\}$。当 $f$ 在 $x$ 处不可微时，次微分 $\partial f(x)$ 通常包含多个元素。

几何解释。 定义仿射函数 $g(y) = f(x) + \langle v, y - x \rangle$。次梯度条件 $f(y) \geq g(y)$ 意味着 $g$ 的图像始终位于 $f$ 的图像下方（或与之相切），即次梯度对应的仿射函数是 $f$ 的一个支撑超平面。

次微分的基本性质。 次微分 $\partial f(x)$ 作为一个集合，具有以下基本性质。对任意 $x \in \text{dom}\,f$，$\partial f(x)$ 是闭凸集（可能为空集）。若 $x \in \text{int}\,\text{dom}\,f$（定义域的内点），则 $\partial f(x)$ 是非空有界集。闭凸性直接从定义得出：两个次梯度的凸组合仍然是次梯度，且次梯度序列的极限仍然是次梯度。有界性的证明需要在 $x$ 的邻域内取若干方向的函数值来控制次梯度的大小。

2.5.2 绝对值函数的次微分#

考虑 $f(x) = |x|$。在 $x > 0$ 和 $x < 0$ 处 $f$ 可微，梯度分别为 1 和 $-1$，次微分就是单点集。关键是求 $x = 0$ 处的次微分——这是一个不光滑点。

根据次微分定义，需找所有满足 $|y| \geq vy$ 对任意 $y$ 成立的 $v$：

• 当 $y > 0$ 时：$y \geq vy$，两边除以 $y > 0$ 得 $v \leq 1$。
• 当 $y < 0$ 时：$-y \geq vy$，两边除以 $y < 0$（不等号翻转）得 $v \geq -1$。

因此 $\partial f(0) = [-1, 1]$。

这个例子揭示了次微分的本质：在光滑点次微分退化为梯度（单点），在非光滑点次微分是一个集合，“填补”了梯度缺失的信息。

2.5.3 次微分的运算规则#

直接从定义出发计算次微分往往很繁琐。与微积分中的求导法则类似，次微分也有一套运算规则，可以将复杂函数的次微分归结为简单函数的次微分的组合。

非负线性组合。 设 $f_1, f_2$ 是凸函数，$\alpha_1, \alpha_2 \geq 0$，$f = \alpha_1 f_1 + \alpha_2 f_2$。若 $\text{int}\,\text{dom}\,f_1 \cap \text{dom}\,f_2 \neq \emptyset$（称为约束规范条件），则

其中右端的加号是 Minkowski 和，即 $A + B = \{a + b \mid a \in A, b \in B\}$。约束规范条件要求两个函数的定义域有足够的重叠，这在实际中几乎总是满足的。

包含关系 $\alpha_1 \partial f_1(x) + \alpha_2 \partial f_2(x) \subseteq \partial(\alpha_1 f_1 + \alpha_2 f_2)(x)$ 从次梯度定义直接可得。反向包含的证明需要用到凸集分离定理（Moreau-Rockafellar 定理），这也是约束规范条件发挥作用的地方。

和的次微分（Moreau-Rockafellar 定理）。 上述规则的特例（$\alpha_1 = \alpha_2 = 1$）尤为重要：当 $\text{int}\,\text{dom}\,f_1 \cap \text{dom}\,f_2 \neq \emptyset$ 时，

这个等式在优化中频繁使用。例如，对复合优化问题 $\min_x f(x) + h(x)$（$f$ 光滑，$h$ 非光滑），最优性条件 $0 \in \partial(f + h)(x^*)$ 可以展开为 $0 \in \nabla f(x^*) + \partial h(x^*)$，即 $-\nabla f(x^*) \in \partial h(x^*)$，这正是第五章邻近梯度法的理论基础。

线性变量替换。 设 $f(x) = h(Ax + b)$，其中 $h$ 是适当凸函数，$A \in \mathbb{R}^{n \times m}$，$b \in \mathbb{R}^n$。若存在 $x^\sharp$ 使得 $Ax^\sharp + b \in \text{int}\,\text{dom}\,h$，则

这是微积分链式法则 $\nabla f(x) = A^\top \nabla h(Ax + b)$ 的次微分推广。与可微情形相比，形式完全一致，只是将 $\nabla$ 替换为 $\partial$。

逐点最大值。 设 $f_1, \ldots, f_m$ 是凸函数，$f(x) = \max\{f_1(x), \ldots, f_m(x)\}$。记活跃集 $I(x) = \{i \mid f_i(x) = f(x)\}$（即在 $x$ 处取到最大值的那些函数的下标），则

其中 $\text{conv}$ 表示凸包。直觉上，在 $f$ 的不光滑点（即多个 $f_i$ 同时取到最大值的点），次微分是各个活跃函数次微分的凸包。在光滑点（只有一个活跃函数），次微分退化为该活跃函数的梯度。例如，$\ell_1$ 范数 $\|x\|_1 = \max_{s \in \{-1,1\}^n} s^\top x$ 的次微分就可以通过这条规则计算：在 $x_k = 0$ 的分量上，次微分是 $[-1, 1]$；在 $x_k \neq 0$ 的分量上，次微分是 $\{\text{sign}(x_k)\}$。

复合函数的链式法则。 设 $f_1, \ldots, f_m$ 是凸函数，$h: \mathbb{R}^m \to \mathbb{R}$ 是关于各分量单调递增的凸函数，$f(x) = h(f_1(x), \ldots, f_m(x))$。若 $z = (z_1, \ldots, z_m) \in \partial h(f_1(\hat{x}), \ldots, f_m(\hat{x}))$ 且 $g_i \in \partial f_i(\hat{x})$，则

这条规则的适用前提是外层函数 $h$ 关于各分量单调递增。与可微情形的链式法则 $\nabla f = \sum_i \frac{\partial h}{\partial u_i} \nabla f_i$ 对比，形式完全平行。

2.5.4 次微分与方向导数的关系#

对于凸函数，方向导数与次微分之间有一个深刻的联系。设 $f$ 是凸函数，$x_0 \in \text{int}\,\text{dom}\,f$，方向 $d \in \mathbb{R}^n$。凸函数在 $x_0$ 处沿方向 $d$ 的方向导数定义为