凸分析基础¶

前置自测¶

📋 前置自测（答不出 ≥ 2 题 → 先回线性代数与实分析基础复习）

什么是向量空间的内积？$\langle x, y \rangle = \sum_i x_i y_i$ 的几何含义是什么？

矩阵 $A$ 的特征值全部为正意味着什么几何性质？

什么是开集、闭集、紧集？它们之间的包含关系如何？

给定函数 $f: \mathbb{R}^n \to \mathbb{R}$，什么是梯度 $\nabla f(x)$ 和 Hessian $\nabla^2 f(x)$？

解释"上确界"（$\sup$）和"下确界"（$\inf$）的含义，以及它们与最大值/最小值的区别。

本章目标¶

学完本章后，你将能够：(1) 判断任意集合/函数是否凸，并利用保凸运算系统性地构造凸性证明；(2) 精确陈述并证明分离超平面定理，理解其作为 KKT 条件和对偶理论几何根源的角色；(3) 计算常见函数的次梯度，用 $0 \in \partial f(x^*)$ 判定最优性；(4) 区分凸、严格凸与强凸，理解条件数 $\kappa = L/\mu$ 对算法收敛率的决定性影响。

1.1 为什么凸分析是优化理论的绝对地基 ⭐¶

动机¶

机器人工程师每天都在解优化问题——SLAM 后端的非线性最小二乘、MPC 的二次规划、RL 的策略优化。但在投入具体算法之前，有一个根本问题必须回答：什么样的优化问题是"好"的？

所谓"好"，指的是：局部最优就是全局最优（不会陷入坑里）、解的存在性和唯一性有理论保证、算法收敛速度有定量刻画。凸分析提供的正是这些保证的数学基础。

如果不学凸分析会怎样¶

想象你在调试一个轨迹优化算法。优化器返回了一个解，但你无法确定： - 这个解是全局最优还是只是局部最优？ - 换一个初始点会不会得到更好的解？ - 算法需要多少步才能收敛到足够精确？

如果问题是凸的，这些问题都有明确答案。如果不是，你只能靠经验和运气。凸分析就是那把让你**从猜测走向确定**的钥匙。

凸分析在机器人学中的角色¶

本质洞察：凸分析提供的不是一类特殊问题的解法，而是整个优化理论的语法规则。它定义了什么是"结构良好"的问题，就像线性代数定义了什么是"结构良好"的方程组。

具体联系如下：

凸分析概念	机器人应用
凸集的分离定理	KKT 条件和强对偶的几何根源
次梯度	非光滑优化（L1正则化、ADMM）的微分工具
强凸性	梯度下降线性收敛的充分条件
半正定锥	Certifiable SLAM 的 SDP 松弛
保凸运算	CVXPY 的 DCP（纪律凸编程）验证规则

本章知识地图¶

凸分析基础
├── 凸集理论（§1.2-1.4）
│   ├── 凸集定义与典型例子
│   ├── 保凸运算
│   └── 分离超平面定理
├── 凸函数理论（§1.5-1.7）
│   ├── 四种等价定义
│   ├── 保凸运算
│   └── 闭凸函数与下半连续性
├── 次梯度理论（§1.8-1.9）
│   ├── 次梯度定义与几何
│   ├── 计算规则
│   └── 最优性条件
└── 强凸性与光滑性（§1.10-1.11）
    ├── 三种等价定义
    ├── 条件数与收敛率
    └── 共推论（co-coercivity）

1.2 凸集的定义与直觉 ⭐¶

动机¶

在解约束优化问题时，可行域的形状决定了问题的难度。如果可行域是凸的，那么沿着任意可行方向走都不会"跳出"可行域——这个性质使得很多算法（如投影梯度法）可以高效工作。

严格定义¶

定义 1.2.1（凸集）：集合 $C \subseteq \mathbb{R}^n$ 是凸集，当且仅当对所有 $x, y \in C$ 和所有 $\theta \in [0, 1]$，有：

\[\theta x + (1 - \theta) y \in C\]

几何直觉：凸集是"没有凹陷的集合"。任取集合中两点连线段，线段上所有点仍在集合中。等价地说，凸集从任何方向看都是"鼓起来"的，没有"内凹"的部分。

跨领域类比：凸集就像一个充了气的气球——你无法从外部往里按出一个凹坑。非凸集就像一个有凹陷的橡皮泥，两点之间的直线可能穿出集合。

凸组合与凸包¶

定义 1.2.2（凸组合）：$x_1, ..., x_k$ 的凸组合是形如 $\theta_1 x_1 + ... + \theta_k x_k$ 的点，其中 $\theta_i \geq 0$ 且 $\sum_i \theta_i = 1$。

定义 1.2.3（凸包）：集合 $S$ 的凸包 $\text{conv}(S)$ 是包含 $S$ 的最小凸集，等价于 $S$ 中所有点的凸组合的全体：

\[\text{conv}(S) = \left\{ \sum_{i=1}^k \theta_i x_i \,\middle|\, x_i \in S, \theta_i \geq 0, \sum_i \theta_i = 1, k \in \mathbb{N} \right\}\]

几何意义：凸包是用最少的"材料"包裹住 $S$ 中所有点的凸集。在二维中，有限点集的凸包是一个多边形；在三维中是一个多面体。

仿射集与仿射包¶

定义 1.2.4（仿射集）：集合 $A$ 是仿射集，如果对所有 $x, y \in A$ 和所有 $\theta \in \mathbb{R}$（注意没有 $[0,1]$ 的限制），有 $\theta x + (1-\theta)y \in A$。

仿射集的直觉：它们是"直线的推广"。仿射集一定是凸集（凸集只要求 $\theta \in [0,1]$，仿射集要求对所有 $\theta$ 成立，条件更强）。

仿射集的结构定理：任何仿射集都可以写成 $A = \{x_0 + v \mid v \in V\}$，其中 $x_0$ 是 $A$ 中任意一点，$V$ 是一个子空间。

锥与凸锥¶

定义 1.2.5（锥）：集合 $K$ 是锥，如果对所有 $x \in K$ 和 $\theta \geq 0$，有 $\theta x \in K$。

定义 1.2.6（凸锥）：既是凸集又是锥的集合。等价条件：对所有 $x_1, x_2 \in K$ 和 $\theta_1, \theta_2 \geq 0$，有 $\theta_1 x_1 + \theta_2 x_2 \in K$。

本质洞察：凸锥是优化理论中最重要的结构之一。整个锥规划（LP、SOCP、SDP）的层级结构建立在不同凸锥的包含关系之上：非负象限 $\mathbb{R}^n_+$（对应 LP）$\subset$ 二阶锥（SOCP）$\subset$ 半正定锥（SDP）。

⚠️ 常见陷阱¶

💡 概念误区：认为"边界上有角的集合不是凸的" - 错误想法：正方形有角，看起来"不光滑"，所以不凸 - 实际上：正方形是凸集。凸性只要求连线段在集合内，与边界光滑性无关 - 根本原因：凸性是代数性质（线性组合封闭），不是微分性质（边界光滑）

🧠 思维陷阱：混淆"凸集"与"凸函数的 sublevel set" - 凸函数的下水平集 $\{x \mid f(x) \leq \alpha\}$ 一定是凸集 - 但反过来不成立：下水平集是凸集不能推出函数是凸的 - 反例：$f(x) = \sqrt{|x|}$ 的每个下水平集都是对称区间（凸集），但 $f$ 不是凸函数

练习¶

证明两个凸集的交是凸集，但并一般不是凸集（给出反例）。
证明仿射集一定是凸集，但凸集不一定是仿射集。给出一个凸集但非仿射集的最简单例子。
（跨章综合）回顾线性代数中的子空间概念：证明 $\mathbb{R}^n$ 的任何子空间都是凸锥。子空间有哪些凸锥不具备的额外结构？

1.3 重要凸集家族 ⭐⭐¶

动机¶

认识一批"常备"的凸集，就像掌握一套常用零件库——遇到新问题时能快速判断"这个可行域长什么样"。

超平面与半空间¶

超平面：$\{x \mid a^\top x = b\}$，其中 $a \neq 0$。几何上是法向量为 $a$ 的"平面"。

半空间：$\{x \mid a^\top x \leq b\}$。超平面把空间分成两半，半空间是其中一半（含边界）。

为什么重要：半空间是最基本的凸集构建块。任何闭凸集都是半空间的交（可能需要无穷多个）。

多面体¶

定义：有限个半空间和超平面的交：$P = \{x \mid Ax \preceq b, Cx = d\}$。

多面体是优化中最常见的可行域。线性规划的可行域就是多面体，二次规划通常也在多面体约束下进行。

顶点与极值点：多面体的顶点是不能写成集合中其他两点凸组合的点。线性规划的最优解一定在顶点取到——这就是单纯形法的理论基础。

欧氏球与椭球¶

欧氏球：$B(x_c, r) = \{x \mid \|x - x_c\|_2 \leq r\}$

椭球：$\mathcal{E} = \{x \mid (x - x_c)^\top P^{-1}(x - x_c) \leq 1\}$，其中 $P \succ 0$。

椭球的半轴方向由 $P$ 的特征向量决定，半轴长度由 $P$ 的特征值的平方根决定。在 MPC 中，椭球常用来表示状态估计的不确定性区域。

二阶锥（SOC / Lorentz 锥） ⭐⭐¶

定义： $$\text{SOC}_n = \{(x, t) \in \mathbb{R}^{n+1} \mid \|x\|_2 \leq t\}$$

凸性证明：取 $(x_1, t_1), (x_2, t_2) \in \text{SOC}_n$ 和 $\theta \in [0,1]$。需证 $\|\theta x_1 + (1-\theta)x_2\|_2 \leq \theta t_1 + (1-\theta)t_2$。

第一个不等号是三角不等式，第二个用了 $\|x_i\|_2 \leq t_i$。

机器人应用：SOCP（二阶锥规划）约束出现在摩擦锥约束（接触力必须在摩擦锥内）、推力约束（火箭着陆问题）、鲁棒约束（不确定参数的 worst-case 保证）中。

半正定锥 $\mathbb{S}^n_+$ ⭐⭐⭐¶

定义： $$\mathbb{S}^n_+ = \{X \in \mathbb{S}^n \mid X \succeq 0\} = \{X \in \mathbb{S}^n \mid v^\top X v \geq 0, \forall v \in \mathbb{R}^n\}$$

其中 $\mathbb{S}^n$ 是 $n \times n$ 对称矩阵的集合。

凸性证明：设 $X_1, X_2 \succeq 0$，$\theta \in [0,1]$。对任意 $v$： $$v^\top (\theta X_1 + (1-\theta)X_2) v = \theta (v^\top X_1 v) + (1-\theta)(v^\top X_2 v) \geq 0$$

因此 $\theta X_1 + (1-\theta) X_2 \succeq 0$。

半正定锥是自对偶的：$\mathbb{S}^n_+$ 的对偶锥（所有与锥中每个元素内积非负的矩阵）恰好是它自身。这个性质使得 SDP 的对偶理论特别优美。

机器人应用： - Certifiable SLAM（SE-Sync）中，旋转矩阵的约束 $R^\top R = I$ 被松弛为 $X \succeq 0$ - LMI 控制综合中，Lyapunov 稳定性条件 $A^\top P + PA \prec 0, P \succ 0$ 是 SDP 可行性问题 - SOS（Sum of Squares）多项式验证通过 SDP 求解

相对内部（relative interior）⭐⭐⭐¶

定义：凸集 $C$ 的相对内部 $\text{ri}(C)$ 是 $C$ 在其仿射包 $\text{aff}(C)$ 中的内部： $$\text{ri}(C) = \{x \in C \mid B(x, r) \cap \text{aff}(C) \subseteq C, \text{ 对某个 } r > 0\}$$

为什么需要这个概念：考虑 $\mathbb{R}^3$ 中的一条线段 $[a, b]$。它的内部（在 $\mathbb{R}^3$ 意义下）是空的！但它的相对内部（在自身仿射包——一条直线——中的内部）是 $(a, b)$，即去掉两端点。

反事实推理：如果不引入相对内部，很多定理（如"凸函数在 ri(dom f) 上连续"、"分离定理的强版本"）就无法正确陈述。用普通内部的话，低维凸集的定理全部失效。

集合	内部（$\mathbb{R}^3$ 中）	相对内部
球体	开球	同内部
圆盘（2D，嵌入3D）	$\emptyset$	开圆盘
线段	$\emptyset$	开线段
单点	$\emptyset$	该点本身

⚠️ 常见陷阱¶

⚠️ 编程陷阱：半正定判定只检查对角元 - 错误做法：if (A.diagonal().minCoeff() >= 0) → "PSD" - 现象：对角元全正的矩阵不一定 PSD。如 $\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$ 对角元全正，但特征值为 $3, -1$，不是 PSD - 根本原因：PSD 要求所有特征值非负，这是全局性质，不能从对角元推出 - 正确做法：用 Eigen::SelfAdjointEigenSolver 计算特征值，检查最小特征值是否 $\geq 0$

💡 概念误区：混淆 interior 和 relative interior - 低维凸集（如 $\mathbb{R}^3$ 中的线段）的 interior 为空但 ri 非空 - 很多定理的条件是"在 ri(dom f) 处"，不是"在 int(dom f) 处" - Boyd 的教材对此几乎不讲，但 Rockafellar §6 和对偶理论都依赖这个概念

练习¶

证明单纯形 $\Delta_n = \{x \in \mathbb{R}^n \mid x \geq 0, \mathbf{1}^\top x = 1\}$ 是凸集，并描述其极值点。
证明谱范数球 $\{X \mid \|X\|_2 \leq 1\}$（最大奇异值 $\leq 1$）是凸集。（提示：利用范数是凸函数，下水平集是凸集。）
对半正定锥 $\mathbb{S}^2_+$（2×2对称PSD矩阵），画出其在参数 $(a, b, c)$（其中矩阵为 $\begin{pmatrix}a & b \\ b & c\end{pmatrix}$）空间中的形状。

1.4 保凸运算与分离超平面定理 ⭐⭐¶

动机¶

实际问题中，可行域往往不是单一的简单凸集，而是通过各种运算组合而来。**保凸运算**告诉我们：哪些操作施加在凸集上，结果仍然是凸集。这是系统性判断凸性的核心工具。

保凸运算大全¶

1. 交集运算：任意（甚至无穷）多个凸集的交仍为凸集。

证明：设 $\{C_\alpha\}_{\alpha \in \mathcal{A}}$ 是凸集族。取 $x, y \in \bigcap_\alpha C_\alpha$，则对每个 $\alpha$，$x, y \in C_\alpha$。由 $C_\alpha$ 的凸性，$\theta x + (1-\theta)y \in C_\alpha$ 对所有 $\alpha$ 成立，故在交集中。

重要推论：任何闭凸集都是半空间的交。这是线性规划、多面体表示的理论基础。

2. 仿射变换的像与原像：若 $C$ 凸且 $f(x) = Ax + b$ 是仿射映射，则 $f(C)$ 和 $f^{-1}(C)$ 都是凸集。

3. 透视函数：$P: \mathbb{R}^{n+1} \to \mathbb{R}^n$，$P(x, t) = x/t$（$t > 0$）。若 $C$ 凸，则 $P(C)$ 凸。

4. 线性分式映射：$f(x) = (Ax + b)/(c^\top x + d)$。若 $C$ 凸且 $c^\top x + d > 0$ 在 $C$ 上成立，则 $f(C)$ 凸。

5. 和集（Minkowski 和）：$C_1 + C_2 = \{x + y \mid x \in C_1, y \in C_2\}$。若 $C_1, C_2$ 凸，则 $C_1 + C_2$ 凸。

6. 笛卡尔积：$C_1 \times C_2$ 凸当且仅当 $C_1, C_2$ 都凸。

分离超平面定理 ⭐⭐¶

这是凸分析中最重要的定理之一，是 KKT 条件和对偶理论的几何根源。

定理 1.4.1（分离超平面定理）：设 $C$ 和 $D$ 是两个不相交的凸集（$C \cap D = \emptyset$）。则存在 $a \neq 0$ 和 $b$ 使得： $$a^\top x \leq b, \quad \forall x \in C$$ $$a^\top x \geq b, \quad \forall x \in D$$

几何直觉：两个不相交的凸集之间一定能找到一个"超平面"把它们分开——一个在超平面的一侧，另一个在另一侧。

为什么这很重要：

它是 KKT 条件的几何本质——最优解处约束的梯度与目标函数的梯度之间存在"分离"关系
它是强对偶的几何证明的关键步骤——Lagrange 对偶的几何解释
它保证了凸问题的最优性可以通过"局部"条件判定

分离定理的三种强度：

分离类型	条件	结论	适用场景
弱分离	$C \cap D = \emptyset$，$C$、$D$ 凸	$a^\top x \leq b \leq a^\top y$	一般不相交凸集
严格分离	至少一个闭、另一个紧	$a^\top x < b < a^\top y$	闭凸集与外部点
强分离	$\text{dist}(C, D) > 0$	$a^\top x \leq b - \epsilon \leq b + \epsilon \leq a^\top y$	闭凸集之间有正距离

反事实推理：如果集合不凸，分离定理还成立吗？考虑平面上的两个半月形（非凸集），它们虽然不相交，但可能"交错嵌套"，无法用一条直线分开。凸性正是排除了这种"嵌套"的可能性——凸集的边界是"向外鼓"的，不会深入另一个集合的内部。

证明（闭凸集版本，完整严格证明）：

设 $C$ 是闭凸集，$x_0 \notin C$。我们证明存在严格分离超平面。

Step 1（最近点存在性与唯一性）：由 $C$ 闭凸，存在唯一最近点 $p = \text{proj}_C(x_0) = \arg\min_{x \in C} \|x - x_0\|_2$。

存在性证明：设 $d = \inf_{x \in C}\|x - x_0\|$。取点列 $\{x_k\} \subset C$ 使 $\|x_k - x_0\| \to d$。我们证明 $\{x_k\}$ 是 Cauchy 列。由平行四边形恒等式： $$\|x_k - x_l\|^2 = 2\|x_k - x_0\|^2 + 2\|x_l - x_0\|^2 - 4\left\|\frac{x_k + x_l}{2} - x_0\right\|^2$$

由 $C$ 凸，$\frac{x_k + x_l}{2} \in C$，故 $\left\|\frac{x_k + x_l}{2} - x_0\right\| \geq d$。当 $k, l$ 充分大时，$\|x_k - x_0\|^2, \|x_l - x_0\|^2 \to d^2$，因此： $$\|x_k - x_l\|^2 \leq 2d^2 + 2d^2 + 2\epsilon - 4d^2 = 2\epsilon \to 0$$

故 $\{x_k\}$ 是 Cauchy 列，极限存在。由 $C$ 闭，极限在 $C$ 中。

唯一性证明：若 $p_1, p_2$ 都是最近点且 $p_1 \neq p_2$，由凸性 $\frac{1}{2}(p_1 + p_2) \in C$。由平行四边形恒等式： $$\left\|\frac{p_1 + p_2}{2} - x_0\right\|^2 = \frac{1}{2}\|p_1 - x_0\|^2 + \frac{1}{2}\|p_2 - x_0\|^2 - \frac{1}{4}\|p_1 - p_2\|^2 < d^2$$

这与 $d$ 是下确界矛盾。

Step 2（投影的变分不等式特征化）：$p = \text{proj}_C(x_0)$ 当且仅当： $$\langle x_0 - p, x - p \rangle \leq 0, \quad \forall x \in C$$

证明：对任意 $x \in C$ 和 $t \in [0,1]$，由 $C$ 凸：$p + t(x-p) \in C$。由 $p$ 是最近点： $$\|x_0 - p\|^2 \leq \|x_0 - p - t(x-p)\|^2 = \|x_0 - p\|^2 - 2t\langle x_0-p, x-p\rangle + t^2\|x-p\|^2$$

化简：$0 \leq -2t\langle x_0-p, x-p\rangle + t^2\|x-p\|^2$。除以 $t > 0$ 再令 $t \to 0$：$\langle x_0-p, x-p\rangle \leq 0$。

Step 3（构造分离超平面）：定义 $a = x_0 - p$，$b = a^\top p + \frac{1}{2}\|a\|^2$。我们证明 $a^\top x \leq a^\top p < b \leq a^\top x_0$ 对所有 $x \in C$。

对任意 $x \in C$，由变分不等式：$a^\top(x - p) = \langle x_0 - p, x - p\rangle \leq 0$，故 $a^\top x \leq a^\top p$。

而 $a^\top x_0 = a^\top p + \|a\|^2 > a^\top p$（因为 $a = x_0 - p \neq 0$）。

超平面 $\{x \mid a^\top x = b\}$ 严格分离 $x_0$ 和 $C$。

Step 4（推广到两个不相交闭凸集）：若 $C, D$ 是不相交闭凸集且至少一个有界，考虑 $E = C - D = \{x - y \mid x \in C, y \in D\}$。由保凸运算，$E$ 是凸集，且 $0 \notin E$（否则 $C \cap D \neq \emptyset$）。对 $\bar{E} = \text{cl}(E)$，若 $0 \notin \bar{E}$，由 Step 1-3 分离 $0$ 和 $\bar{E}$，得到超平面同时分离 $C$ 和 $D$。

从分离到支撑超平面：

定理 1.4.2（支撑超平面定理）：设 $C$ 是凸集，$x_0 \in \partial C$（边界点）。则存在 $a \neq 0$ 使得 $a^\top x \leq a^\top x_0$ 对所有 $x \in C$。

完整证明：

由 $x_0 \in \partial C$（边界点），存在 $C$ 外的点列 $\{y_k\}$ 使 $y_k \to x_0$。对每个 $y_k \notin \text{cl}(C)$（若 $C$ 闭则自动成立），由分离定理存在非零 $a_k$ 使得： $$a_k^\top x \leq a_k^\top y_k, \quad \forall x \in C$$

不妨设 $\|a_k\| = 1$（单位化）。单位球面是紧集，故存在子列 $a_{k_j} \to a^*$，$\|a^*\| = 1$。

对任意 $x \in C$，由连续性：$a^{*\top} x = \lim_{j} a_{k_j}^\top x \leq \lim_j a_{k_j}^\top y_{k_j} = a^{*\top} x_0$。

故 $a^{*\top} x \leq a^{*\top} x_0$ 对所有 $x \in C$，$a^*$ 是支撑超平面的法向量。

支撑函数的角度看支撑超平面：支撑超平面法向量 $a$ 方向上，$C$ 的最远点恰在 $x_0$。用支撑函数语言：$\sigma_C(a) = \sup_{x \in C} a^\top x = a^\top x_0$，即 $x_0$ 是 $C$ 在方向 $a$ 上的"极端点"。

本质洞察：分离超平面定理的本质是说——凸集在其边界上不会"缠绕"或"自交"。这使得我们总能用线性不等式（超平面）从外部"逼近"凸集。这正是线性规划对偶、Lagrange 乘子法、以及所有一阶最优性条件的几何根源。

分离定理的推论与应用 ⭐⭐¶

推论 1（闭凸集是半空间的交）：任何闭凸集 $C$ 可以写成： $$C = \bigcap {x \mid a^\top x \leq b} \quad \text{（交遍所有包含 $C$ 的半空间）}$$

证明：设 $H = \bigcap{x : a^\top x \leq b, \text{ 所有包含 $C$ 的半空间}}$。显然 $C \subseteq H$。若 $x_0 \notin C$，由分离定理存在严格分离超平面，对应一个不包含 $x_0$ 的半空间，故 $x_0 \notin H$。因此 $H = C$。

推论 2（凸函数是仿射下界的上确界）：设 $f$ 是闭凸函数，则： $$f(x) = \sup\{a^\top x + b \mid a^\top z + b \leq f(z), \forall z\}$$

即闭凸函数可以用其所有仿射下界（支撑超平面对应的函数）的逐点上确界恢复。这正是 $f^{**} = f$ 的另一种表述。

推论 3（Farkas 引理——分离定理的线性代数版本）：设 $A \in \mathbb{R}^{m \times n}$，$b \in \mathbb{R}^m$。下列两个系统恰有一个有解： - (I) $Ax \leq b$ 有解 $x$ - (II) $y \geq 0$, $A^\top y = 0$, $b^\top y < 0$ 有解 $y$

证明思路：可行域 $C = \{Ax : x \in \mathbb{R}^n\}$（一个子空间）和 $D = \{z : z \leq b\} \setminus C$ 之间应用分离定理。Farkas 引理是线性规划强对偶的直接推论，也是 KKT 条件中对偶可行性的代数根源。

支撑函数 ⭐⭐⭐¶

定义 1.4.3：凸集 $C$ 的支撑函数 $\sigma_C: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ 定义为： $$\sigma_C(y) = \sup_{x \in C} \langle y, x \rangle$$

几何意义：$\sigma_C(y)$ 给出了 $C$ 在方向 $y$ 上的"最大延伸"。如果你沿着方向 $y$ 用一个超平面去"推" $C$，$\sigma_C(y)$ 就是超平面能推到的最远位置。

关键性质： - 支撑函数完全刻画了闭凸集：$C_1 = C_2 \Leftrightarrow \sigma_{C_1} = \sigma_{C_2}$ - 支撑函数永远是凸的（作为 $y$ 的函数）、正齐次的 - 支撑函数是指示函数 $\delta_C$ 的共轭：$\sigma_C = \delta_C^*$

极锥 ⭐⭐⭐¶

定义 1.4.4：锥 $K$ 的对偶锥（极锥）为： $$K^* = \{y \mid \langle y, x \rangle \geq 0, \forall x \in K\}$$

重要例子： - $(\mathbb{R}^n_+)^* = \mathbb{R}^n_+$（非负象限自对偶） - $(\mathbb{S}^n_+)^* = \mathbb{S}^n_+$（半正定锥自对偶） - $(\text{SOC}_n)^* = \text{SOC}_n$（二阶锥自对偶）

自对偶性在锥规划的对偶理论中扮演核心角色。

⚠️ 常见陷阱¶

💡 概念误区：认为"凸集的并也是凸集" - 这是错误的。两个凸集的并一般不凸（如两个不相交的球） - 只有交保凸，不是并 - 但凸集的 Minkowski 和是凸集——注意区分"并"和"和"

🧠 思维陷阱：分离定理只适用于闭凸集 - 弱分离定理（$\leq$ 和 $\geq$）适用于任意不相交凸集 - 严格分离（$<$ 和 $>$）需要至少一个集合是闭的 - 强分离（有正距离间隔）需要闭凸集且点在集合外

练习¶

证明椭球 $\mathcal{E} = \{x \mid (x-c)^\top P^{-1}(x-c) \leq 1\}$ 可以写成单位球在仿射变换下的像。利用这个事实和保凸运算说明椭球是凸集。
计算 $\ell_1$ 单位球 $\{x \mid \|x\|_1 \leq 1\}$ 的支撑函数。（答案应该是 $\|y\|_\infty$。）
证明半正定锥的对偶锥是它自身（自对偶性）。

1.5 凸函数的四种等价定义 ⭐¶

动机¶

判断一个函数是否凸是优化中最基本的操作。但"凸"有多种等价定义，每种适用于不同场景： - 定义式适用于任何函数 - epigraph 定义把函数凸性转化为集合凸性 - 一阶条件适用于可微函数，给出几何直觉 - 二阶条件适用于二次可微函数，用 Hessian 判定

定义式¶

定义 1.5.1（凸函数）：$f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ 是凸函数，如果 $\text{dom}(f)$ 是凸集，且对所有 $x, y \in \text{dom}(f)$ 和 $\theta \in [0,1]$：

\[f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta) f(y)\]

几何直觉：函数图形上任意两点的连线段位于函数图形的上方或重合。等价地说，函数"碗状向上弯曲"。

跨领域类比：凸函数就像一个碗——无论你从碗的哪两个点之间拉一根绳子，绳子总在碗面上方。非凸函数就像一个有凹槽的地形，绳子可能穿过地面以下。

Epigraph 定义¶

定义 1.5.2（上图）：函数 $f$ 的上图（epigraph）为： $$\text{epi}(f) = \{(x, t) \mid x \in \text{dom}(f), t \geq f(x)\}$$

等价性：$f$ 是凸函数 $\Leftrightarrow$ $\text{epi}(f)$ 是凸集。

为什么有用：这个定义把函数的凸性问题转化为集合的凸性问题。当我们想用集合论的工具（如分离定理）研究凸函数时，就通过 epigraph 来"翻译"。

一阶条件（需可微）⭐⭐¶

定理 1.5.3：设 $f$ 可微。则 $f$ 凸 $\Leftrightarrow$ 对所有 $x, y \in \text{dom}(f)$：

\[f(y) \geq f(x) + \nabla f(x)^\top (y - x)\]

几何直觉：凸函数的任何切线（一阶 Taylor 展开）都是函数的全局下界。函数图形总在每一点的切平面之上。

证明（$\Rightarrow$ 方向）：由凸性定义，对 $\theta \in (0, 1]$： $$f(x + \theta(y-x)) \leq (1-\theta)f(x) + \theta f(y)$$

即 $f(x + \theta(y-x)) - f(x) \leq \theta(f(y) - f(x))$。

除以 $\theta > 0$：$\frac{f(x + \theta(y-x)) - f(x)}{\theta} \leq f(y) - f(x)$。

令 $\theta \to 0^+$，左边趋于方向导数 $\nabla f(x)^\top(y-x)$，得 $\nabla f(x)^\top(y-x) \leq f(y) - f(x)$。

证明（$\Leftarrow$ 方向）：设一阶条件成立。取 $z = \theta x + (1-\theta)y$。分别对 $(z, x)$ 和 $(z, y)$ 应用一阶条件： $$f(x) \geq f(z) + \nabla f(z)^\top(x - z)$$ $$f(y) \geq f(z) + \nabla f(z)^\top(y - z)$$

将第一式乘以 $\theta$，第二式乘以 $(1-\theta)$，相加： $$\theta f(x) + (1-\theta)f(y) \geq f(z) + \nabla f(z)^\top(\theta x + (1-\theta)y - z) = f(z)$$

因为 $\theta x + (1-\theta)y - z = 0$。

二阶条件（需二次可微）⭐⭐¶

定理 1.5.4：设 $f$ 二次可微。则 $f$ 凸 $\Leftrightarrow$ $\nabla^2 f(x) \succeq 0$ 对所有 $x \in \text{dom}(f)$。

直觉：Hessian 半正定意味着函数在每一点的"曲率"都非负——函数在任何方向上都是"向上弯"或"不弯"的，不会"向下凹"。

证明（$\Rightarrow$ 方向）：假设 $f$ 凸但存在 $x_0$ 使 $\nabla^2 f(x_0)$ 不半正定，即存在方向 $v$ 使 $v^\top \nabla^2 f(x_0) v < 0$。

考虑 $g(t) = f(x_0 + tv)$，则 $g''(0) = v^\top \nabla^2 f(x_0) v < 0$。

由 $g''(0) < 0$，存在 $\epsilon > 0$ 使 $g$ 在 $(- \epsilon, \epsilon)$ 上严格凹，即 $g(\theta t_1 + (1-\theta)t_2) > \theta g(t_1) + (1-\theta) g(t_2)$ 对某些点成立。

但 $g$ 是凸函数 $f$ 限制在一条直线上的结果，应该也是凸的。矛盾。

证明（$\Leftarrow$ 方向）：设 $\nabla^2 f(x) \succeq 0$ 处处成立。对任意 $x, y$，由 Taylor 展开： $$f(y) = f(x) + \nabla f(x)^\top(y-x) + \frac{1}{2}(y-x)^\top \nabla^2 f(\xi)(y-x)$$

其中 $\xi$ 在 $x$ 和 $y$ 的连线上。由 $\nabla^2 f(\xi) \succeq 0$，最后一项 $\geq 0$，故一阶条件成立。

四种定义的关系总结¶

定义	适用范围	主要用途
定义式（Jensen 型）	任何函数	最一般的凸性判定
Epigraph	任何函数	连接函数凸性与集合凸性
一阶条件	可微函数	最优性条件、几何直觉
二阶条件	二次可微函数	实际计算中最常用

严格凸与强凸的区分 ⭐⭐¶

定义 1.5.5： - 凸：$f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$ - 严格凸：$f(\theta x + (1-\theta)y) < \theta f(x) + (1-\theta)f(y)$（当 $x \neq y$, $\theta \in (0,1)$） - 强凸（$\mu$-强凸）：$f - \frac{\mu}{2}\|\cdot\|^2$ 是凸函数（$\mu > 0$）

层级关系：强凸 $\Rightarrow$ 严格凸 $\Rightarrow$ 凸，反向均不成立。

关键区别：$f(x) = x^4$ 是严格凸但不强凸的。强凸要求函数的曲率有正的下界（"至少像二次函数那样弯曲"），而严格凸只要求"比直线弯一点点"就够了。

为什么强凸比严格凸重要得多：强凸保证了梯度下降的线性收敛和最小值点的唯一性，而严格凸只保证唯一性，不给收敛速度。

⚠️ 常见陷阱¶

💡 概念误区：认为"凸函数一定连续" - 凸函数在 $\text{ri}(\text{dom}\,f)$ 上自动连续 - 但在定义域边界上可以不连续 - 例如指示函数 $\delta_C(x) = \begin{cases} 0 & x \in C \\ +\infty & x \notin C \end{cases}$ 在 $C$ 边界上不连续

🧠 思维陷阱：认为二阶条件是判断凸性的唯一方法 - 二阶条件只适用于二次可微函数 - $f(x) = |x|$ 是凸函数但在 $x=0$ 不可微，无法用二阶条件 - 对非光滑函数，需要用定义式或 epigraph 方法

练习¶

证明 $f(x) = e^x$ 是凸函数（用三种方法：定义式、一阶条件、二阶条件）。
证明 log-sum-exp $f(x) = \log(\sum_i e^{x_i})$ 是凸函数。（提示：计算 Hessian 并证明其半正定。）
给出一个严格凸但不强凸的函数例子，并证明其性质。

1.6 凸函数的保凸运算 ⭐⭐¶

动机¶

实际优化问题中的目标函数往往不是简单的初等函数，而是通过复杂的运算组合而成。保凸运算让我们能"模块化"地判断凸性——只要每个模块是凸的，且组合方式保凸，整体就是凸的。这正是 CVXPY 的 DCP（Disciplined Convex Programming）规则的数学基础。

非负加权和¶

若 $f_1, ..., f_k$ 凸，$w_i \geq 0$，则 $\sum_i w_i f_i$ 凸。

仿射复合¶

若 $f$ 凸，则 $g(x) = f(Ax + b)$ 凸。

证明：$g(\theta x + (1-\theta)y) = f(A(\theta x + (1-\theta)y) + b) = f(\theta(Ax+b) + (1-\theta)(Ay+b)) \leq \theta f(Ax+b) + (1-\theta)f(Ay+b) = \theta g(x) + (1-\theta)g(y)$。

逐点上确界 ⭐⭐¶

定理 1.6.1：若 $f_\alpha$ 对每个 $\alpha \in \mathcal{A}$ 都是凸函数，则 $g(x) = \sup_\alpha f_\alpha(x)$ 也是凸函数。

证明：$\text{epi}(g) = \bigcap_\alpha \text{epi}(f_\alpha)$。每个 $\text{epi}(f_\alpha)$ 是凸集，凸集的交仍凸，故 $\text{epi}(g)$ 凸，即 $g$ 凸。

应用示例： - $\max(x_1, ..., x_n) = \sup_i x_i$ 是凸的（每个 $x_i$ 是仿射的，因此凸的） - 矩阵的最大特征值 $\lambda_{\max}(A) = \sup_{\|v\|=1} v^\top A v$ 是凸的 - 支撑函数 $\sigma_C(y) = \sup_{x \in C} y^\top x$ 是凸的

本质洞察：$\sup$ 运算保凸，但 $\inf$ 运算不一定保凸。这个不对称性非常重要：它解释了为什么"最坏情况"（max/sup）容易在凸框架内处理，而"最好情况"（min/inf）需要更多条件。

部分最小化 ⭐⭐⭐¶

定理 1.6.2：若 $f(x, y)$ 关于 $(x, y)$ 联合凸，且 $C$ 是凸集，则 $g(x) = \inf_{y \in C} f(x, y)$ 是凸函数（若 $g > -\infty$）。

证明：取 $x_1, x_2$，$\theta \in [0,1]$。对任意 $\epsilon > 0$，存在 $y_1, y_2 \in C$ 使 $f(x_i, y_i) \leq g(x_i) + \epsilon$。由 $C$ 凸，$\theta y_1 + (1-\theta)y_2 \in C$。

\[g(\theta x_1 + (1-\theta)x_2) \leq f(\theta x_1 + (1-\theta)x_2, \theta y_1 + (1-\theta)y_2)$$ $$\leq \theta f(x_1, y_1) + (1-\theta)f(x_2, y_2) \leq \theta g(x_1) + (1-\theta)g(x_2) + \epsilon\]

令 $\epsilon \to 0$。

机器人应用：Moreau 包络 $M_f^\lambda(v) = \inf_x \{f(x) + \frac{1}{2\lambda}\|x-v\|^2\}$ 就是部分最小化的实例。它把非光滑的 $f$ 变成光滑的 $M_f^\lambda$，是 proximal 算法的核心工具。

透视变换 ⭐⭐⭐¶

若 $f$ 凸，则 $g(x, t) = tf(x/t)$（$t > 0$）凸。

证明：取 $(x_1, t_1)$，$(x_2, t_2)$（$t_i > 0$），$\theta \in [0,1]$。 $$g(\theta x_1 + (1-\theta)x_2, \theta t_1 + (1-\theta)t_2) = (\theta t_1 + (1-\theta)t_2) f\left(\frac{\theta x_1 + (1-\theta)x_2}{\theta t_1 + (1-\theta)t_2}\right)$$

设 $\alpha = \frac{\theta t_1}{\theta t_1 + (1-\theta)t_2}$，则 $1-\alpha = \frac{(1-\theta)t_2}{\theta t_1 + (1-\theta)t_2}$，且： $$\frac{\theta x_1 + (1-\theta)x_2}{\theta t_1 + (1-\theta)t_2} = \alpha \frac{x_1}{t_1} + (1-\alpha)\frac{x_2}{t_2}$$

由 $f$ 凸： $$f\left(\alpha \frac{x_1}{t_1} + (1-\alpha)\frac{x_2}{t_2}\right) \leq \alpha f\left(\frac{x_1}{t_1}\right) + (1-\alpha)f\left(\frac{x_2}{t_2}\right)$$

乘以 $\theta t_1 + (1-\theta)t_2$： $$g(\theta(x_1, t_1) + (1-\theta)(x_2, t_2)) \leq \theta t_1 f(x_1/t_1) + (1-\theta)t_2 f(x_2/t_2) = \theta g(x_1,t_1) + (1-\theta)g(x_2,t_2)$$

应用：KL 散度 $D_{KL}(p\|q) = \sum_i p_i \log(p_i/q_i)$ 可以通过 $x\log x$ 的透视变换得到。具体地，$f(x) = x\log x$ 凸，其透视 $g(x,t) = t \cdot (x/t)\log(x/t) = x\log(x/t)$，对 $(x,t)$ 联合凸。取 $x = p_i$，$t = q_i$ 并求和，得 $D_{KL}(p\|q)$ 是 $(p, q)$ 的联合凸函数。

保凸运算的反面——非保凸运算¶

理解哪些运算不保凸同样重要，能避免错误的凸性判断：

运算	为什么不保凸	反例
凸函数之积	$f \cdot g$ 可以不凸	$f(x) = x$，$g(x) = x$，$fg = x^2$（碰巧凸）；$f = x$，$g = -x$，$fg = -x^2$（凹）
凸函数之差	$f - g$ 可以不凸	$f = x^2$，$g = 2x^2$，$f-g = -x^2$（凹）
$\inf$ 的 $\inf$	嵌套 inf 不一定保凸	需要联合凸性条件
凸函数的复合（无单调性）	$h(g(x))$，$h$ 凸 $g$ 凸不够	$h(t)=t^2$，$g(x)=-x^2+1$：$h(g(x))=(1-x^2)^2$ 非凸

复合规则总结¶

运算	条件	结论
$f(x) = h(g(x))$	$h$ 凸不减，$g$ 凸	$f$ 凸
$f(x) = h(g(x))$	$h$ 凸不增，$g$ 凹	$f$ 凸
非负加权和	$w_i \geq 0$，$f_i$ 凸	$\sum w_i f_i$ 凸
仿射复合	$f$ 凸	$f(Ax+b)$ 凸
逐点 sup	$f_\alpha$ 凸	$\sup_\alpha f_\alpha$ 凸
部分最小化	$f(x,y)$ 联合凸	$\inf_y f(x,y)$ 凸

⚠️ 常见陷阱¶

⚠️ 编程陷阱：CVXPY 的 DCP 规则比保凸运算更严格 - CVXPY 拒绝 cp.sqrt(cp.quad_form(x, P)) 即使结果是凸的 - 原因：DCP 是保凸运算的子集，要求组合方式可被自动验证 - 解决：用 DCP-compatible 的 atom 替代，如 cp.norm(P_sqrt @ x)

💡 概念误区：认为复合函数 $h(g(x))$ 只要 $h$ 凸、$g$ 凸就凸 - 反例：$h(t) = t^2$ 凸，$g(x) = -x^2$ 凸，但 $h(g(x)) = x^4$ 的凸性取决于具体形式 - 正确条件需要单调性：$h$ 凸且不减 + $g$ 凸，或 $h$ 凸且不增 + $g$ 凹

练习¶

利用保凸运算证明 $f(x) = \|Ax - b\|_2$ 是凸函数（不用计算 Hessian）。
证明矩阵的最大特征值函数 $\lambda_{\max}(X)$ 是凸函数。（提示：写成 sup 形式。）
利用透视变换证明相对熵 $f(x,t) = x\log(x/t)$（$x, t > 0$）关于 $(x,t)$ 联合凸。

1.7 闭凸函数与下半连续性 ⭐⭐⭐¶

动机¶

为什么需要"闭"凸函数？因为对偶理论的核心定理——$f^{**} = f$（双共轭等于自身）——只对**闭凸函数**（proper + lower semicontinuous + convex）成立。如果函数不"闭"，共轭运算会丢失信息。

下半连续性¶

定义 1.7.1：$f$ 在 $x_0$ 处下半连续（lsc），如果 $\liminf_{x \to x_0} f(x) \geq f(x_0)$。

直觉：函数可以"向上跳"，但不能"向下跳"。即函数在每一点的值不会比极限值小。

等价条件：$f$ 是 lsc $\Leftrightarrow$ 所有下水平集 $\{x \mid f(x) \leq \alpha\}$ 是闭集 $\Leftrightarrow$ $\text{epi}(f)$ 是闭集。

闭凸函数¶

定义 1.7.2：$f$ 是闭凸函数，如果 $f$ 是 proper（不恒为 $+\infty$，且不取 $-\infty$）、凸、且下半连续的。

为什么叫"闭"：因为它等价于 epigraph 是闭集。

关键定理：$f^{**} = f$ 当且仅当 $f$ 是闭凸函数。

如果 $f$ 不是闭凸的，$f^{**}$ 只是 $f$ 的"闭凸包"（最大的不超过 $f$ 的闭凸函数）。

反事实推理：如果不要求闭凸，对偶理论会出什么问题？考虑 $f(x) = \begin{cases} x^2 & x > 0 \\ 1 & x = 0 \end{cases}$。这个函数凸但不 lsc（在 $x=0$ 有向下的跳跃）。它的共轭的共轭 $f^{**}(x) = x^2$（$x \geq 0$），$= 0$（$x = 0$），即 $f^{**}$ 把那个不连续点"补"上了。对偶理论给出的不是原函数，而是"修补后的版本"。

凸函数的连续性 ⭐⭐¶

定理 1.7.3：有限维空间中的凸函数在其定义域的相对内部上自动连续。

这是一个深刻的结果：凸性这个"代数"性质蕴含了连续性这个"分析"性质。直觉上，如果凸函数在某点"断裂"，那么 epigraph 就会出现"裂缝"，违反凸性。

但注意：在定义域边界上不一定连续。指示函数 $\delta_C$ 在 $C$ 的边界上就不连续。

⚠️ 常见陷阱¶

💡 概念误区：忽略"闭"条件对对偶的影响 - 非闭凸函数的共轭运算可能丢失信息：$f^{**} \neq f$ - 在使用 Fenchel-Moreau 定理（$f^{**} = f$）之前，必须验证 $f$ 是 proper + lsc + convex - 实际优化中大多数常见函数（范数、指示函数、二次函数等）都是闭凸的，但自定义函数需要检查

练习¶

证明 $f(x) = \|x\|_1$ 是闭凸函数（验证 proper、convex、lsc 三个条件）。
给出一个凸但不闭的函数例子，并计算其 $f^{**}$。
利用"下水平集是闭集"这一等价条件，证明连续凸函数是闭凸的。

1.8 次梯度理论 ⭐⭐¶

动机¶

梯度是光滑优化的基本工具。但机器人优化中充满非光滑函数： - $\ell_1$ 范数 $\|x\|_1$（稀疏优化、LASSO） - 指示函数 $\delta_C(x)$（硬约束） - $\max$ 函数（minimax 问题） - hinge loss $\max(0, 1-x)$（SVM）

这些函数在某些点不可微，梯度不存在。次梯度把微分工具推广到非光滑凸函数，是 ADMM、proximal gradient 等算法的理论基础。

次梯度的定义与几何 ⭐⭐¶

定义 1.8.1（次梯度）：设 $f$ 是凸函数。向量 $g \in \mathbb{R}^n$ 是 $f$ 在 $x$ 处的次梯度，如果：

\[f(y) \geq f(x) + g^\top(y - x), \quad \forall y \in \text{dom}(f)\]

定义 1.8.2（次微分）：$f$ 在 $x$ 处的次微分是所有次梯度的集合：

\[\partial f(x) = \{g \mid f(y) \geq f(x) + g^\top(y-x), \forall y\}\]

几何直觉：次梯度定义的超平面 $h(y) = f(x) + g^\top(y-x)$ 是 $f$ 在点 $(x, f(x))$ 处的一个**支撑超平面**——它"托住"了整个函数图形。次微分 $\partial f(x)$ 是所有这样的支撑超平面的斜率的集合。

与梯度的关系： - 若 $f$ 在 $x$ 处可微，则 $\partial f(x) = \{\nabla f(x)\}$（次微分退化为单点集） - 若 $f$ 不可微，$\partial f(x)$ 是一个凸集（可能包含多个元素）

跨领域类比：次梯度之于凸函数，就像切线之于光滑曲线。光滑曲线每点只有一条切线（梯度唯一），而凸函数在"棱"上可以有多条支撑线（次梯度不唯一），就像折纸的折痕处可以有多个"切面"。

典型例子的次微分计算¶

例 1：$f(x) = |x|$

在 $x > 0$：$\partial f(x) = \{1\}$（就是导数）在 $x < 0$：$\partial f(x) = \{-1\}$ 在 $x = 0$：$\partial f(0) = [-1, 1]$（区间）

验证：$|y| \geq |0| + g \cdot y = g \cdot y$ 对所有 $y$ 成立，当且仅当 $|g| \leq 1$，即 $g \in [-1, 1]$。

例 2：$f(x) = \|x\|_1$

\[(\partial f(x))_i = \begin{cases} \{1\} & x_i > 0 \\ \{-1\} & x_i < 0 \\ [-1, 1] & x_i = 0 \end{cases}\]

次微分是各分量次微分的笛卡尔积。

例 3：指示函数 $f(x) = \delta_C(x)$

\[\partial \delta_C(x) = N_C(x) = \{g \mid g^\top(y - x) \leq 0, \forall y \in C\}\]

这就是 $C$ 在 $x$ 处的**法锥**（normal cone）——所有"指向 $C$ 外部"的方向的集合。

例 4：$f(x) = \max(x_1, ..., x_n)$

设在 $x$ 处最大值被下标集 $I(x) = \{i \mid x_i = \max_j x_j\}$ 取到，则：

\[\partial f(x) = \text{conv}\{e_i \mid i \in I(x)\}\]

即取到最大值的那些坐标对应的标准基向量的凸包。

次梯度存在性定理 ⭐⭐¶

定理 1.8.3：若 $f$ 是凸函数，则对所有 $x \in \text{ri}(\text{dom}\,f)$，次微分 $\partial f(x)$ 非空。

证明思路：由支撑超平面定理应用于 $\text{epi}(f)$ 在点 $(x, f(x)) \in \partial(\text{epi}(f))$ 处。

Step 1：点 $(x, f(x))$ 在 $\text{epi}(f)$ 的边界上（因为 $(x, f(x) - \epsilon) \notin \text{epi}(f)$）。

Step 2：由支撑超平面定理，存在非零向量 $(a, b)$ 使得对所有 $(y, t) \in \text{epi}(f)$： $$a^\top y + bt \geq a^\top x + bf(x)$$

Step 3：取 $t \to +\infty$，如果 $b > 0$ 则左边趋于 $+\infty$，矛盾？不会，因为 $(y, t)$ 必须在 epi 中。实际上，$b$ 必须 $\leq 0$。当 $x \in \text{ri}(\text{dom}\,f)$ 时可以证明 $b < 0$。

Step 4：令 $g = -a/b$，则从支撑条件推出 $f(y) \geq f(x) + g^\top(y-x)$，即 $g \in \partial f(x)$。

次微分的计算规则 ⭐⭐¶

次微分的计算规则是实际应用中最重要的工具——它让我们能从简单函数的次微分出发，通过组合运算得到复杂函数的次微分。

1. 求和规则：若 $f_1, ..., f_m$ 凸，且满足正则条件（如 $\bigcap_i \text{ri}(\text{dom}\,f_i) \neq \emptyset$），则： $$\partial(f_1 + ... + f_m)(x) = \partial f_1(x) + ... + \partial f_m(x)$$

右边是 Minkowski 和：$A + B = \{a + b \mid a \in A, b \in B\}$。

为什么需要正则条件：考虑 $f_1 = \delta_C$，$f_2 = \delta_D$，$C \cap D = \{x_0\}$。此时 $\partial(f_1+f_2)(x_0) = N_{C \cap D}(x_0)$，但 $N_C(x_0) + N_D(x_0)$ 可能严格小于 $N_{C \cap D}(x_0)$。正则条件排除了这种退化。

2. 标量乘法：$\alpha > 0$ 时，$\partial(\alpha f)(x) = \alpha \partial f(x)$。

证明：$g \in \partial(\alpha f)(x) \Leftrightarrow \alpha f(y) \geq \alpha f(x) + g^\top(y-x) \Leftrightarrow f(y) \geq f(x) + (g/\alpha)^\top(y-x) \Leftrightarrow g/\alpha \in \partial f(x) \Leftrightarrow g \in \alpha \partial f(x)$。

3. 仿射复合：设 $g(x) = f(Ax + b)$。当正则条件满足时： $$\partial g(x) = A^\top \partial f(Ax + b)$$

4. 逐点最大值：若 $f(x) = \max_{i=1,...,m} f_i(x)$，设 $I(x) = \{i \mid f_i(x) = f(x)\}$（active 集），则： $$\partial f(x) = \text{conv}\bigcup_{i \in I(x)} \partial f_i(x)$$

直觉上，只有"贡献了最大值"的那些函数才参与次微分的构成。

5. 复合规则（$h$ 凸不减，$f$ 凸）：$\partial(h \circ f)(x) \supseteq \partial h(f(x)) \cdot \partial f(x)$，等号在正则条件下成立。

次微分规则速查表：

运算	公式	条件
求和	$\partial(f+g) = \partial f + \partial g$	ri(dom f) $\cap$ ri(dom g) $\neq \emptyset$
标量乘	$\partial(\alpha f) = \alpha \partial f$	$\alpha > 0$
仿射复合	$\partial(f \circ A) = A^\top \partial f(A\cdot)$	正则条件
逐点 max	$\partial(\max_i f_i) = \text{conv}\cup_{i \in I} \partial f_i$	$f_i$ 凸
指示函数	$\partial \delta_C(x) = N_C(x)$	$C$ 凸

次微分的几何性质 ⭐⭐⭐¶

定理 1.8.4（次微分是闭凸集）：对凸函数 $f$，在每一点 $x$ 处，$\partial f(x)$ 是闭凸集。

证明：$\partial f(x) = \bigcap_y \{g : g^\top(y-x) \leq f(y) - f(x)\}$，是半空间的交，故闭凸。

定理 1.8.5（次微分的有界性）：若 $x \in \text{int}(\text{dom}\,f)$，则 $\partial f(x)$ 是有界集（从而是紧集）。

定理 1.8.6（次微分的单调性）：$\partial f$ 是单调映射，即对任意 $x, y$ 和 $g_x \in \partial f(x)$，$g_y \in \partial f(y)$： $$\langle g_x - g_y, x - y \rangle \geq 0$$

证明：由次梯度定义：$f(y) \geq f(x) + g_x^\top(y-x)$ 和 $f(x) \geq f(y) + g_y^\top(x-y)$。相加：$0 \geq (g_x - g_y)^\top(y-x)$，即 $\langle g_x - g_y, x-y \rangle \geq 0$。

单调性是 proximal 算子理论的基石——正是因为 $\partial f$ 单调，$\text{prox}_f = (I + \partial f)^{-1}$ 才是 firmly nonexpansive 的。

⚠️ 常见陷阱¶

💡 概念误区：次梯度链式法则的误用 - 对 $h = g \circ f$，**不能**随意写 $\partial h(x) = g'(f(x)) \cdot \partial f(x)$ - 链式法则只在 $g$ 非递减凸 + $f$ 凸时安全 - 反例：$g(t) = -t$（递减），$f(x) = |x|$，$h(x) = -|x|$ 是凹函数，上面的"公式"给出错误结果

⚠️ 编程陷阱：用数值差分"逼近"次梯度 - 在不可微点，左右导数不同，数值差分 $(f(x+h) - f(x-h))/(2h)$ 给出的是某个特定方向的方向导数，不是次梯度集合 - 正确做法：根据函数结构解析计算次微分

练习¶

计算 Huber 函数 $\rho_\delta(x) = \begin{cases} \frac{x^2}{2} & |x| \leq \delta \\ \delta|x| - \frac{\delta^2}{2} & |x| > \delta \end{cases}$ 的次微分（在所有点）。
证明：若 $f$ 凸，$\partial f(x)$ 是闭凸集。
计算核范数 $\|X\|_* = \sum_i \sigma_i(X)$ 在零矩阵处的次微分。

1.9 最优性条件与 Fermat 规则 ⭐⭐¶

动机¶

优化的终极目标是找到最优解。对光滑无约束问题，最优性条件是 $\nabla f(x^*) = 0$。次梯度理论把这个条件推广到非光滑凸函数。

Fermat 规则¶

定理 1.9.1（Fermat 规则 / 凸函数最优性条件）：$x^*$ 是凸函数 $f$ 的全局最小值点 $\Leftrightarrow$ $0 \in \partial f(x^*)$。

证明：

$(\Rightarrow)$：$x^*$ 是最小值点意味着 $f(y) \geq f(x^*)$ 对所有 $y$。即 $f(y) \geq f(x^*) + 0 \cdot (y - x^*)$ 对所有 $y$，这正是 $0 \in \partial f(x^*)$ 的定义。

$(\Leftarrow)$：若 $0 \in \partial f(x^*)$，则 $f(y) \geq f(x^*) + 0 \cdot (y - x^*) = f(x^*)$ 对所有 $y$，即 $x^*$ 是全局最小值点。

本质洞察：Fermat 规则的深刻之处在于——对凸函数，局部最优等价于全局最优，而全局最优等价于 $0 \in \partial f(x^*)$。这三者的等价使得凸优化在理论上"完全可解"。

约束优化的推广¶

对约束问题 $\min f(x)$ s.t. $x \in C$，等价于 $\min f(x) + \delta_C(x)$。

由 Fermat 规则：$x^*$ 最优 $\Leftrightarrow$ $0 \in \partial(f + \delta_C)(x^*)$。

若 $f$ 可微且正则条件满足：$0 \in \nabla f(x^*) + N_C(x^*)$，即 $-\nabla f(x^*) \in N_C(x^*)$。

几何解释：最优解处，目标函数的负梯度方向必须在可行域的法锥内。直觉上：如果负梯度方向不在法锥内，就意味着存在一个可行下降方向，$x^*$ 就不是最优的。

与 KKT 条件的联系 ⭐⭐¶

KKT 条件本质上就是 Fermat 规则在特殊约束结构下的展开形式。让我们详细展开这个联系。

考虑约束优化 $\min f_0(x)$ s.t. $f_i(x) \leq 0$（$i=1,...,m$），$h_j(x) = 0$（$j=1,...,p$）。

Step 1：用指示函数重写：$\min f_0(x) + \sum_i \delta_{(-\infty,0]}(f_i(x)) + \sum_j \delta_{\{0\}}(h_j(x))$。

Step 2：应用 Fermat 规则 $0 \in \partial F(x^*)$，其中 $F$ 是上面的复合函数。

Step 3：用次微分计算规则展开： - $\partial \delta_{(-\infty,0]}(f_i(x))$ 的次微分通过链式法则涉及 $\nabla f_i(x)$ 和法锥 $N_{(-\infty,0]}(f_i(x))$ - 法锥 $N_{(-\infty,0]}(t) = \begin{cases}\{0\} & t < 0 \\ \mathbb{R}_+ & t = 0\end{cases}$

Step 4：将法锥条件翻译为乘子 $\lambda_i \geq 0$，得到： $$0 \in \nabla f_0(x^*) + \sum_i \lambda_i \nabla f_i(x^*) + \sum_j \nu_j \nabla h_j(x^*)$$ $$\lambda_i \geq 0, \quad \lambda_i f_i(x^*) = 0 \quad \text{（互补松弛）}$$

这正是 KKT 条件。从这个推导可以看到：KKT 不是"发明"出来的，而是 Fermat 规则在约束结构下的自然结果。 每个 KKT 条件都有其次微分来源。

Fermat 规则的计算应用 ⭐⭐¶

例 1：LASSO 的稀疏性解释

考虑 $\min F(x) = \frac{1}{2}\|Ax - b\|^2 + \lambda\|x\|_1$。

由 Fermat 规则：$0 \in \partial F(x^*) = A^\top(Ax^* - b) + \lambda \partial\|x^*\|_1$。

逐分量：$0 \in (A^\top(Ax^* - b))_i + \lambda \partial|x_i^*|$。

设 $r = A^\top(Ax^* - b)$（残差梯度）。

若 $|r_i| < \lambda$：则 $0 \in r_i + \lambda[-1,1]$，即 $-r_i/\lambda \in [-1,1]$。唯一使此成立的是 $x_i^* = 0$（因为如果 $x_i^* \neq 0$ 则次微分退化为单点，$r_i = \pm\lambda$）。

结论：$\lambda$ 越大，越多分量被"杀死"为零——这就是 $\ell_1$ 正则化产生稀疏解的数学原因。正则化参数 $\lambda$ 充当了一个"阈值"——残差梯度分量小于 $\lambda$ 的维度被置零。

例 2：投影的最优性条件

$\min \frac{1}{2}\|x - v\|^2$ s.t. $x \in C$ 等价于 $\min \frac{1}{2}\|x-v\|^2 + \delta_C(x)$。

Fermat：$0 \in (x^* - v) + N_C(x^*)$，即 $v - x^* \in N_C(x^*)$。

这就是投影的变分不等式特征化：$\langle v - x^*, y - x^* \rangle \leq 0$ 对所有 $y \in C$。

例 3：saddle-point 问题的最优性

对 minimax $\min_x \max_y L(x, y)$（$L$ 关于 $x$ 凸、关于 $y$ 凹），鞍点 $(x^*, y^*)$ 满足： $$0 \in \partial_x L(x^*, y^*), \quad 0 \in -\partial_y(-L)(x^*, y^*)$$

即"关于 $x$ 求最小的最优性"和"关于 $y$ 求最大的最优性"同时成立。

⚠️ 常见陷阱¶

💡 概念误区：Fermat 规则只适用于无约束问题 - Fermat 规则 $0 \in \partial f(x^*)$ 是最一般的最优性条件——通过把约束写成指示函数，任何约束问题都可以用 Fermat 规则处理 - KKT 条件是 Fermat 规则的特殊形式，不是独立的定理 - 当约束结构不是标准的 $f_i \leq 0$ 形式（如集合约束 $x \in C$）时，直接用 Fermat + 法锥比写 KKT 更自然

🧠 思维陷阱：把 $0 \in \partial f(x^*)$ 中的 $0$ 理解为"梯度为零" - 对光滑函数确实是 $\nabla f(x^*) = 0$ - 但对非光滑函数，$0 \in \partial f(x^*)$ 意味着零向量在次微分集合中——不是说"导数为零"，而是说"存在一个支撑超平面斜率为零" - 在 $x^*$ 不可微的情况下，$\partial f(x^*)$ 包含多个向量，只要其中一个是零就够了

练习¶

用 Fermat 规则求解 $\min \|x\|_1 + \frac{1}{2}\|x - v\|^2$（这就是 proximal operator 的定义，推导出软阈值公式）。
证明：对凸函数 $f$，$x^*$ 是 $\arg\min_{x \in C} f(x)$ 当且仅当 $\langle \nabla f(x^*), y - x^* \rangle \geq 0$ 对所有 $y \in C$（假设 $f$ 可微）。
用次微分条件说明为什么 $\ell_1$ 正则化 $\min \|Ax - b\|^2 + \lambda\|x\|_1$ 会产生稀疏解。具体地，给出"第 $i$ 个分量为零"的充要条件。
对 elastic net 正则化 $\min \|Ax-b\|^2 + \lambda_1\|x\|_1 + \lambda_2\|x\|^2$，写出 Fermat 规则并与纯 LASSO 比较——解释为什么 elastic net 的解更"稳定"。
（跨章综合）回顾线性代数中的最小二乘：$\min \|Ax-b\|^2$ 的正规方程为 $A^\top Ax = A^\top b$。用 Fermat 规则重新推导此结果，并说明当 $A$ 不满秩时，$\partial f(x^*) = \{A^\top(Ax^*-b)\}$，Fermat 规则如何恢复伪逆解。

Fermat 规则的历史补注¶

Fermat 规则的名字来自 Pierre de Fermat (1601-1665)，他在微积分发明之前就提出了"极值点处导数为零"的思想（用的是他自己发明的"充分性方法"——adequality）。现代形式的次微分 Fermat 规则由 Rockafellar (1970) 和 Moreau (1960s) 系统化。

有趣的是，Fermat 的原始工作只处理光滑函数的局部极值，而现代 Fermat 规则通过次梯度把它推广到了非光滑凸函数的**全局**最优性条件。这个从"局部-光滑"到"全局-非光滑"的飞跃，正是凸分析的核心贡献之一。它统一了微积分的极值理论（$\nabla f = 0$）和约束优化的 KKT 理论（$0 \in \nabla f + N_C$），让我们能在一个框架下处理光滑/非光滑、有约束/无约束的所有凸优化问题。

1.10 强凸性与光滑性 ⭐⭐¶

动机¶

凸性保证了"局部最优=全局最优"，但没有告诉我们算法需要多快才能找到最优解。强凸性**和**光滑性（L-smooth）提供了这个定量回答——它们分别给出函数曲率的下界和上界，共同决定了梯度下降的收敛速率。

$\mu$-强凸的三种等价定义 ⭐⭐¶

定义 1.10.1（$\mu$-强凸，三种等价形式）：

(a) 减去二次仍凸（最一般，无需可微）：$f(x) - \frac{\mu}{2}\|x\|^2$ 是凸函数。

(b) 一阶条件（需可微）：$f(y) \geq f(x) + \nabla f(x)^\top(y-x) + \frac{\mu}{2}\|y-x\|^2$。

(c) 二阶条件（需二次可微）：$\nabla^2 f(x) \succeq \mu I$ 对所有 $x$。

直觉：强凸性意味着函数的曲率至少为 $\mu$——函数至少像 $\frac{\mu}{2}\|x\|^2$ 那样"弯曲"。在任何方向上，函数都比切平面至少高出一个二次项。

等价性证明（(a) $\Leftrightarrow$ (b)，当 $f$ 可微时）：

设 $g(x) = f(x) - \frac{\mu}{2}\|x\|^2$。

$g$ 凸 $\Leftrightarrow$ $g(y) \geq g(x) + \nabla g(x)^\top(y-x)$

$\Leftrightarrow$ $f(y) - \frac{\mu}{2}\|y\|^2 \geq f(x) - \frac{\mu}{2}\|x\|^2 + (\nabla f(x) - \mu x)^\top(y-x)$

展开右边 $\frac{\mu}{2}$ 的项：$-\frac{\mu}{2}\|x\|^2 - \mu x^\top(y-x) = -\frac{\mu}{2}\|x\|^2 - \mu x^\top y + \mu\|x\|^2 = \frac{\mu}{2}\|x\|^2 - \mu x^\top y$

左边 $-\frac{\mu}{2}\|y\|^2$ 移到右边：$f(y) \geq f(x) + \nabla f(x)^\top(y-x) + \frac{\mu}{2}(\|y\|^2 - 2x^\top y + \|x\|^2) = f(x) + \nabla f(x)^\top(y-x) + \frac{\mu}{2}\|y-x\|^2$

这正是 (b)。

强凸函数的关键性质¶

性质 1：强凸函数有唯一全局最小值点。

证明：设 $x^*$ 是最小值点。由强凸一阶条件（取 $x = x^*$）： $$f(y) \geq f(x^*) + \nabla f(x^*)^\top(y-x^*) + \frac{\mu}{2}\|y-x^*\|^2$$

由 Fermat 规则 $\nabla f(x^*) = 0$，得 $f(y) \geq f(x^*) + \frac{\mu}{2}\|y-x^*\|^2$。因此 $f(y) > f(x^*)$ 对所有 $y \neq x^*$，最小值点唯一。

性质 2：梯度的强单调性。$\langle \nabla f(x) - \nabla f(y), x - y \rangle \geq \mu\|x-y\|^2$。

$L$-光滑的三种等价定义 ⭐⭐¶

定义 1.10.2（$L$-光滑，三种等价形式）：

(a) 梯度 Lipschitz：$\|\nabla f(x) - \nabla f(y)\| \leq L\|x-y\|$。

(b) 二次上界（descent lemma）：$f(y) \leq f(x) + \nabla f(x)^\top(y-x) + \frac{L}{2}\|y-x\|^2$。

(c) 二阶条件：$\nabla^2 f(x) \preceq LI$ 对所有 $x$。

直觉：$L$-光滑意味着函数的曲率至多为 $L$——函数不会比 $\frac{L}{2}\|x\|^2$ 弯得更厉害。

关键结论：步长选取的理论依据

descent lemma 告诉我们：取 $y = x - \frac{1}{L}\nabla f(x)$（步长 $\eta = 1/L$ 的梯度下降），代入 (b)：

\[f(y) \leq f(x) - \frac{1}{2L}\|\nabla f(x)\|^2\]

这意味着每步至少下降 $\frac{1}{2L}\|\nabla f(x)\|^2$。步长 $\eta = 1/L$ 保证了每步都有充分下降。

条件数与收敛率 ⭐⭐¶

定义 1.10.3：条件数 $\kappa = L/\mu$。

条件数描述了函数的"各向异性"程度——最大曲率与最小曲率的比值。

算法	收敛率	含义
梯度下降	$O\left(\left(\frac{\kappa-1}{\kappa+1}\right)^k\right) = O(e^{-2k/\kappa})$	$\kappa$ 越大越慢
Nesterov 加速	$O\left(\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k\right) = O(e^{-2k/\sqrt{\kappa}})$	加速把 $\kappa$ 变成 $\sqrt{\kappa}$
共轭梯度	$O\left(\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k\right)$	与 Nesterov 同阶

数值示例：若 $\kappa = 100$（温和病态），梯度下降需要约 $50\kappa = 5000$ 步达到 $\epsilon$ 精度，而 Nesterov 加速只需约 $50\sqrt{\kappa} = 500$ 步。

"二次夹逼"直觉：$\mu$-强凸 + $L$-光滑意味着函数被两个二次函数夹住：

\[\frac{\mu}{2}\|x - x^*\|^2 \leq f(x) - f(x^*) \leq \frac{L}{2}\|x - x^*\|^2\]

函数的形状介于"窄碗"（曲率 $\mu$）和"宽碗"（曲率 $L$）之间。条件数 $\kappa$ 衡量的就是这两个碗的"扁平度"之比。

Co-coercivity（共推论）⭐⭐⭐¶

定理 1.10.4（Baillon-Haddad 定理）：若 $f$ 是**凸**且 $L$-光滑的，则：

\[\langle \nabla f(x) - \nabla f(y), x - y \rangle \geq \frac{1}{L}\|\nabla f(x) - \nabla f(y)\|^2\]

注意前提：这个定理需要凸性！仅 $L$-光滑不够。

证明（利用 descent lemma 的对称性）：

定义 $g(x) = f(x) - \frac{1}{2L}\|\nabla f(x)\|^2$... 实际上更简洁的证明如下：

设 $h(x) = f(x) - \frac{1}{2L}\|\nabla f(x)\|^2$。

由 descent lemma 对 $(x, y)$ 和 $(y, x)$ 分别应用： $$f(y) \leq f(x) + \nabla f(x)^\top(y-x) + \frac{L}{2}\|y-x\|^2$$ $$f(x) \leq f(y) + \nabla f(y)^\top(x-y) + \frac{L}{2}\|x-y\|^2$$

相加：$0 \leq (\nabla f(x) - \nabla f(y))^\top(y-x) + L\|y-x\|^2$

即：$\langle \nabla f(x) - \nabla f(y), x-y \rangle \leq L\|x-y\|^2$

这给出了上界。要得到下界 $\geq \frac{1}{L}\|\nabla f(x) - \nabla f(y)\|^2$，需要利用凸性。

对凸 $L$-光滑 $f$，考虑 $\phi(x) = f(x) - \nabla f(y)^\top x$。$\phi$ 也是凸且 $L$-光滑的，最小值在 $\nabla\phi(x) = 0$ 即 $\nabla f(x) = \nabla f(y)$ 处取到（但不一定存在）。

更精确地，取 $z = x - \frac{1}{L}(\nabla f(x) - \nabla f(y))$，利用 descent lemma 对 $f$ 在 $x$ 和 $z$ 处...

（完整证明见 Bauschke-Combettes Thm 18.15，核心思想是利用 Fenchel 共轭的光滑-强凸对偶关系。）

为什么 co-coercivity 重要：它是证明 proximal gradient 和 forward-backward splitting 收敛的关键引理。它说的是：梯度算子不仅是单调的（内积非负），而且是"足够单调的"（有定量下界）。

强凸-光滑性质的完整等价链 ⭐⭐¶

对凸函数 $f$，以下关于 $L$-光滑性的四个条件等价（任何一个都可以作为定义）：

\[\|\nabla f(x) - \nabla f(y)\| \leq L\|x-y\| \quad \text{（Lipschitz 梯度）}$$ $$f(y) \leq f(x) + \nabla f(x)^\top(y-x) + \frac{L}{2}\|y-x\|^2 \quad \text{（二次上界）}$$ $$f(y) \geq f(x) + \nabla f(x)^\top(y-x) + \frac{1}{2L}\|\nabla f(x) - \nabla f(y)\|^2 \quad \text{（co-coercivity）}$$ $$\nabla^2 f(x) \preceq LI \quad \text{（Hessian 上界，需二次可微）}\]

类似地，对 $\mu$-强凸性的四个等价条件：

\[\langle \nabla f(x) - \nabla f(y), x - y \rangle \geq \mu\|x-y\|^2 \quad \text{（强单调性）}$$ $$f(y) \geq f(x) + \nabla f(x)^\top(y-x) + \frac{\mu}{2}\|y-x\|^2 \quad \text{（二次下界）}$$ $$f(x) - \frac{\mu}{2}\|x\|^2 \text{ 是凸函数} \quad \text{（减去二次仍凸）}$$ $$\nabla^2 f(x) \succeq \mu I \quad \text{（Hessian 下界，需二次可微）}\]

跨领域类比：$\mu$-强凸和 $L$-光滑就像函数曲率的"最小值"和"最大值"。如果把凸函数比作一个碗，$\mu$ 是碗底最窄处的曲率（决定了水能流多快——收敛多快），$L$ 是碗壁最陡处的曲率（决定了步长不能太大——否则会"飞出"碗外）。条件数 $\kappa = L/\mu$ 衡量碗的"扁平度"。

Descent Lemma 的完整证明 ⭐⭐¶

定理（Descent Lemma）：若 $\nabla f$ 是 $L$-Lipschitz 连续的，则： $$f(y) \leq f(x) + \nabla f(x)^\top(y-x) + \frac{L}{2}\|y-x\|^2$$

证明：由微积分基本定理： $$f(y) - f(x) = \int_0^1 \nabla f(x + t(y-x))^\top(y-x) \, dt$$

\[= \nabla f(x)^\top(y-x) + \int_0^1 [\nabla f(x+t(y-x)) - \nabla f(x)]^\top(y-x) \, dt\]

对积分项取绝对值并用 Cauchy-Schwarz + Lipschitz： $$\left|\int_0^1 [\nabla f(x+t(y-x)) - \nabla f(x)]^\top(y-x) \, dt\right|$$ $$\leq \int_0^1 \|\nabla f(x+t(y-x)) - \nabla f(x)\| \cdot \|y-x\| \, dt$$ $$\leq \int_0^1 Lt\|y-x\| \cdot \|y-x\| \, dt = \frac{L}{2}\|y-x\|^2$$

因此 $f(y) \leq f(x) + \nabla f(x)^\top(y-x) + \frac{L}{2}\|y-x\|^2$。

反事实推理：如果梯度不是 Lipschitz 的（$L = \infty$），descent lemma 给出的上界变成 $+\infty$——即我们无法保证梯度步一定下降。这就是为什么 $L$-光滑性是梯度下降收敛的前提条件。对非光滑函数（如 $\|x\|_1$），梯度下降根本不适用，必须换用次梯度法或 proximal 方法。

⚠️ 常见陷阱¶

💡 概念误区：混淆严格凸和强凸 - $f(x) = x^4$ 严格凸但不强凸（$\mu = 0$），不保证梯度下降线性收敛 - 强凸 $\Rightarrow$ 严格凸 $\Rightarrow$ 凸，反之不成立 - 实际中，强凸性才是我们真正需要的——它给出定量的收敛保证

🧠 思维陷阱：强凸三种等价定义中忘记可微性前提 - 定义 (a)（减二次仍凸）对**任何**凸函数适用 - 定义 (b)（一阶条件）需要函数可微 - 定义 (c)（Hessian 下界）需要函数二次可微 - 对非光滑强凸函数（如 $\|x\|_1 + \frac{\mu}{2}\|x\|^2$），只能用定义 (a)

⚠️ 编程陷阱：co-coercivity 需要凸性前提 - 仅 $L$-光滑（梯度 Lipschitz）**不足以**保证 co-coercivity - 非凸 $L$-光滑函数只有弱单调性 $\langle \nabla f(x) - \nabla f(y), x-y \rangle \geq -L\|x-y\|^2$ - 在非凸优化的收敛分析中，不能直接套用凸情形的 co-coercivity

练习¶

计算 $f(x) = \frac{1}{2}x^\top A x + b^\top x$（$A$ 对称正定）的 $\mu$ 和 $L$。条件数 $\kappa$ 是什么？
证明：若 $f$ 是 $\mu$-强凸的，则对梯度下降 $x_{k+1} = x_k - \frac{1}{L}\nabla f(x_k)$，有 $f(x_k) - f(x^*) \leq \left(1 - \frac{\mu}{L}\right)^k (f(x_0) - f(x^*))$。
验证 co-coercivity：对 $f(x) = \frac{1}{2}x^\top A x$（$A$ 对称正定），直接计算不等式两边并找出 $L$。

1.11 凸集的拓扑性质 ⭐⭐⭐¶

动机¶

凸集不仅具有代数性质（线性组合封闭），还具有丰富的拓扑性质（关于开闭性、边界结构、维度等）。这些性质在对偶理论的严格证明、约束品性的验证、以及算法收敛性分析中都是不可或缺的。

凸集的内部、闭包与边界¶

定理 1.11.1：设 $C$ 是凸集。则： - (a) $\text{int}(C)$ 是凸集 - (b) $\text{cl}(C)$ 是凸集 - (c) 若 $\text{int}(C) \neq \emptyset$，则 $\text{cl}(\text{int}(C)) = \text{cl}(C)$ 且 $\text{int}(\text{cl}(C)) = \text{int}(C)$

证明 (a)：设 $x, y \in \text{int}(C)$，则存在 $\epsilon > 0$ 使 $B(x, \epsilon) \subset C$ 且 $B(y, \epsilon) \subset C$。对 $\theta \in (0,1)$ 和任意 $\|d\| < \epsilon$： $$\theta(x + d) + (1-\theta)(y + d) = \theta x + (1-\theta)y + d \in C$$

因为 $x + d \in C$，$y + d \in C$，且 $C$ 凸。故 $B(\theta x + (1-\theta)y, \epsilon) \subset C$，即 $\theta x + (1-\theta)y \in \text{int}(C)$。

证明 (b)：设 $x, y \in \text{cl}(C)$，取 $x_k \to x$，$y_k \to y$，$x_k, y_k \in C$。则 $\theta x_k + (1-\theta)y_k \in C$（凸性），且 $\theta x_k + (1-\theta)y_k \to \theta x + (1-\theta)y$。故 $\theta x + (1-\theta)y \in \text{cl}(C)$。

证明 (c) 的核心思想：若 $x \in \text{int}(C)$ 且 $y \in \text{cl}(C)$，则开线段 $(x, y) = \{\theta x + (1-\theta)y : \theta \in (0,1)\}$ 全部在 $\text{int}(C)$ 中。

具体地，设 $B(x, r) \subset C$。对 $z = \theta x + (1-\theta)y$（$\theta \in (0,1)$），对任意 $\|d\| < \theta r$： $$z + d = \theta(x + d/\theta) + (1-\theta)y$$

由 $\|d/\theta\| < r$，得 $x + d/\theta \in B(x, r) \subset C$。取 $y$ 在 $C$ 中的逼近列，由闭包和极限运算的交换，得 $z + d \in C$。故 $B(z, \theta r) \subset C$。

定理 1.11.2（凸集的维度与相对内部）：设 $C$ 是非空凸集，$\text{dim}(C) = \text{dim}(\text{aff}(C))$。则： - $\text{ri}(C) \neq \emptyset$ - $\text{ri}(C)$ 的仿射包等于 $\text{aff}(C)$ - 若 $\text{dim}(C) = n$（全维），则 $\text{ri}(C) = \text{int}(C)$

本质洞察：凸集的"真正内部"是相对内部——它始终非空（只要集合非空）。这个保证是凸分析中许多定理（如 Fenchel-Moreau、分离定理的强版本）能够正确运作的根本原因。普通内部可能为空（如 $\mathbb{R}^3$ 中的线段），但相对内部永远存在。

凸集的 recession cone（回收锥）⭐⭐⭐¶

定义 1.11.3：凸集 $C$ 的 recession cone（回收锥）为： $$0^+ C = \{d \mid x + td \in C, \forall x \in C, \forall t \geq 0\}$$

即沿方向 $d$ 从 $C$ 中任意一点出发，永远留在 $C$ 内的所有方向。

性质： - $0^+ C$ 是闭凸锥 - 若 $C$ 是多面体 $\{x : Ax \leq b\}$，则 $0^+ C = \{d : Ad \leq 0\}$ - $C$ 有界 $\Leftrightarrow$ $0^+ C = \{0\}$

为什么 recession cone 重要：它刻画了凸集的"无穷远方向"。在优化中，如果可行域的 recession cone 不与目标函数的下降方向相交，则最优值有限——这是解存在性的基本判据。

跨领域类比：recession cone 就像河流——它告诉你"水往哪个方向流"。如果可行域像一个无限长的河道，recession cone 就是河道的方向。如果目标函数的梯度不沿河道方向，那么沿河道走下去也不会让目标值无限减小。

凸集的极值点与 Krein-Milman 定理 ⭐⭐⭐¶

定义 1.11.4（极值点）：$x \in C$ 是极值点（extreme point），如果 $x$ 不能写成 $C$ 中两个不同点的严格凸组合：$x = \theta y + (1-\theta)z$（$\theta \in (0,1)$，$y, z \in C$）$\Rightarrow$ $y = z = x$。

定理 1.11.5（Krein-Milman 定理，有限维版本）：紧凸集等于其极值点集的闭凸包。

在优化中的意义：对线性规划 $\min c^\top x$ s.t. $x \in P$（$P$ 是多面体），最优解一定在极值点（顶点）处取到。这是单纯形法的理论基础——它只需搜索有限个顶点，而不是整个可行域。

⚠️ 常见陷阱¶

💡 概念误区：混淆"有界"和"紧" - 有界 + 闭 = 紧（在有限维中） - 开球是有界的但不紧 - 半空间是闭的但不有界（也不紧） - Krein-Milman 需要紧性——如果集合只是闭凸但无界（如半空间），它可能没有极值点

🧠 思维陷阱：忘记 recession cone 在解存在性中的作用 - $\min f(x)$ s.t. $x \in C$ 的解不一定存在（即使 $C$ 闭凸、$f$ 凸） - 反例：$\min e^{-x}$ s.t. $x \geq 0$，下确界为 0 但不被取到 - 解存在的充分条件：$C$ 有界（紧），或 $f$ 是 coercive 的（$f(x) \to +\infty$ 当 $\|x\| \to \infty$） - 用 recession cone：若 $0^+C \cap \{d : \nabla f(x)^\top d \leq 0, \forall x\} = \{0\}$，则解存在

练习¶

证明开凸集的闭包是凸集（已在上面证明，请独立复述关键步骤）。
计算半空间 $\{x : a^\top x \leq b\}$ 的 recession cone。
列出单纯形 $\Delta_3 = \{x \in \mathbb{R}^3 : x \geq 0, x_1+x_2+x_3 = 1\}$ 的所有极值点，并验证 Krein-Milman 定理。

1.12 Jensen 不等式与应用 ⭐¶

动机¶

Jensen 不等式是凸函数定义的直接推论，但它在概率论、信息论和机器学习中有极其广泛的应用。

定理与证明¶

定理 1.12.1（Jensen 不等式）：若 $f$ 凸，$X$ 是随机变量（取值在 $\text{dom}(f)$ 中），则：

\[f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]\]

证明：由凸函数的一阶条件（取 $x = \mathbb{E}[X]$）： $$f(X) \geq f(\mathbb{E}[X]) + \nabla f(\mathbb{E}[X])^\top(X - \mathbb{E}[X])$$

两边取期望： $$\mathbb{E}[f(X)] \geq f(\mathbb{E}[X]) + \nabla f(\mathbb{E}[X])^\top \mathbb{E}[X - \mathbb{E}[X]] = f(\mathbb{E}[X])$$

因为 $\mathbb{E}[X - \mathbb{E}[X]] = 0$。

Jensen 不等式的推广形式¶

条件 Jensen 不等式：若 $f$ 凸，则 $f(\mathbb{E}[X|Y]) \leq \mathbb{E}[f(X)|Y]$ a.s.。

积分形式：对测度空间 $(\Omega, \mu)$，$\mu(\Omega) = 1$： $$f\left(\int_\Omega g(\omega)\,d\mu(\omega)\right) \leq \int_\Omega f(g(\omega))\,d\mu(\omega)$$

机器人学与机器学习中的应用¶

EKF 中的线性化误差分析：非线性函数 $h(x)$ 的线性化（用一阶 Taylor 近似 $\hat{h}$）在凸/凹性下有确定的偏差方向。若 $h$ 凸，则 $\mathbb{E}[h(x)] \geq h(\mathbb{E}[x])$，即 EKF 的线性化均值比真实均值偏低——这是 EKF 一致性问题的数学根源之一
RL 中的 value function 下界：$V(s) = \mathbb{E}[R]$ 通过 Jensen 不等式与 $f(\mathbb{E}[\cdot])$ 关联
ELBO（变分推断）：$\log p(x) = \log \mathbb{E}_q[p(x|z)p(z)/q(z)] \geq \mathbb{E}_q[\log(p(x|z)p(z)/q(z))]$（$\log$ 是凹函数，不等号反向）。这是变分自编码器（VAE）训练目标的理论基础
信息论：KL 散度的非负性 $D_{KL}(p\|q) \geq 0$ 是 $-\log$ 凸性 + Jensen 不等式的直接推论： $$D_{KL}(p\|q) = \mathbb{E}_p[-\log(q/p)] \geq -\log\mathbb{E}_p[q/p] = -\log 1 = 0$$
鲁棒优化：minimax 问题 $\min_x \max_y f(x, y)$ 中，若 $f$ 关于 $y$ 凹，则 $\max_y \mathbb{E}[f(x, Y)] \leq \mathbb{E}[\max_y f(x, Y)]$——worst-case 期望不超过期望的 worst-case

从 Jensen 到其他经典不等式¶

Jensen 不等式是很多经典不等式的统一来源：

不等式	取 $f$ 为	取概率分布为
AM-GM：$\sqrt{ab} \leq \frac{a+b}{2}$	$f(x) = -\log x$（凸）	均匀分布在 $\{a, b\}$
Holder：$\sum	x_i y_i	\leq \|x\|_p\|y\|_q$
幂平均不等式	$f(x) = x^r$（$r \geq 1$ 凸）	加权分布
信息不等式 $D_{KL} \geq 0$	$f(x) = -\log x$	分布 $p$

⚠️ 常见陷阱¶

💡 概念误区：Jensen 不等式的方向 - 凸函数：$f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$（$\leq$） - 凹函数：$f(\mathbb{E}[X]) \geq \mathbb{E}[f(X)]$（$\geq$，方向反转） - 常见错误：写 ELBO 推导时搞反不等号方向 - 记忆方法：凸函数"碗口朝上"，期望的函数值（碗的平均高度）高于函数在期望点的值（碗底附近）

练习¶

用 Jensen 不等式证明 AM-GM 不等式：$\sqrt{ab} \leq \frac{a+b}{2}$（$a, b > 0$）。提示：取 $f(x) = -\log x$。
证明：对凸函数 $f$ 和概率分布 $p$，$f\left(\sum_i p_i x_i\right) \leq \sum_i p_i f(x_i)$（有限形式的 Jensen）。
利用 Jensen 不等式和 $x\log x$ 的凸性，证明 $D_{KL}(p\|q) \geq 0$，等号当且仅当 $p = q$。

1.12.1 预处理与条件数改善 ⭐⭐¶

动机¶

条件数 $\kappa$ 决定了梯度下降的收敛速度。如果 $\kappa$ 很大（问题"病态"），可以通过预处理来减小有效条件数。

对角预处理¶

对 $\min \frac{1}{2}x^\top Ax + b^\top x$，设 $D = \text{diag}(\sqrt{A_{11}}, ..., \sqrt{A_{nn}})$，做变量替换 $y = Dx$：

新问题 $\min \frac{1}{2}y^\top (D^{-1}AD^{-1}) y + (D^{-1}b)^\top y$。

矩阵 $D^{-1}AD^{-1}$ 的对角元全为 1，条件数通常比 $A$ 小得多。

不完全 Cholesky 预处理¶

对 $A \succ 0$，计算不完全 Cholesky 分解 $A \approx LL^\top$（保留稀疏性），然后解 $L^{-1}AL^{-\top}$ 的等效问题。预处理后的条件数接近 1。

自适应步长（避免估计 $L$）¶

如果不知道 $L$，可以用 backtracking line search： 1. 初始步长 $\eta = 1$ 2. 检查 Armijo 条件：$f(x - \eta\nabla f) \leq f(x) - \frac{\eta}{2}\|\nabla f\|^2$ 3. 若不满足，$\eta \leftarrow \eta / 2$，重复

这保证了每步至少有 descent lemma 级别的下降，且不需要预先知道 $L$。

预处理在机器人学中的应用¶

场景	典型条件数	预处理方法	效果
MPC-QP	$10^2 - 10^4$	Ruiz 均衡	OSQP 默认使用
SLAM 后端	$10^4 - 10^8$	不完全 Cholesky / AMG	Ceres 自动预处理
RL value function	$10^1 - 10^3$	Adam 自适应步长	隐式对角预处理

练习¶

对 $A = \text{diag}(1, 100)$，计算梯度下降在有/无对角预处理下的收敛率比。
解释为什么 Adam 优化器可以看作一种自适应对角预处理。
对 SLAM 后端的 Hessian（稀疏块对角占优矩阵），为什么不完全 Cholesky 比对角预处理更有效？

本章常见误解汇总¶

误解	正确理解
"凸集的边界有角就不是凸的"	凸性是代数性质（线性组合封闭），与边界光滑性无关。正方形、多面体都是凸集
"凸函数一定连续"	凸函数在 $\text{ri}(\text{dom}\,f)$ 上自动连续，但在定义域边界上可以不连续（如指示函数 $\delta_C$）
"下水平集凸 $\Rightarrow$ 函数凸"	反例：$f(x) = \sqrt{\\|x\\|}$ 的下水平集是凸的（球），但 $f$ 不凸。下水平集凸只意味着拟凸
"二阶条件是判断凸性的唯一方法"	二阶条件只适用于二次可微函数。$f(x) = \\|x\\|$ 是凸函数但在 $x=0$ 不可微，需用定义式或 epigraph 判断
"凸函数之积仍凸"	反例：$f(x) = x$（凸），$g(x) = -x$（凸），$fg = -x^2$（凹）。凸性不在乘法下封闭
"$\sup$ 和 $\inf$ 对凸性地位相同"	$\sup$ 保凸但 $\inf$ 不一定保凸。$\inf$ 保凸需要联合凸性条件（部分最小化定理）
"相对内部和内部差不多"	低维凸集（如 $\mathbb{R}^3$ 中的线段）的内部为空但相对内部非空。Fenchel-Moreau 定理等关键结论依赖相对内部
"$0 \in \partial f(x^*)$ 表示导数为零"	对非光滑函数，$\partial f(x^)$ 是一个集合。$0 \in \partial f(x^)$ 表示零向量在次微分集中，不是"导数为零"

本章小结¶

符号表¶

符号	含义	首次出现
$C$, $D$	凸集	$\S$1.2
$\text{conv}(S)$	集合 $S$ 的凸包	$\S$1.2
$\text{aff}(C)$	凸集 $C$ 的仿射包	$\S$1.2
$K$, $K^*$	凸锥及其对偶锥（极锥）	$\S$1.2, $\S$1.4
$\mathbb{S}^n_+$	$n \times n$ 半正定矩阵锥	$\S$1.3
$\text{SOC}_n$	$n+1$ 维二阶锥（Lorentz 锥）	$\S$1.3
$\text{ri}(C)$	凸集 $C$ 的相对内部	$\S$1.3
$\text{epi}(f)$	函数 $f$ 的上图（epigraph）	$\S$1.5
$\text{dom}(f)$	函数 $f$ 的有效定义域	$\S$1.5
$\partial f(x)$	$f$ 在 $x$ 处的次微分	$\S$1.8
$N_C(x)$	凸集 $C$ 在 $x$ 处的法锥	$\S$1.8
$\sigma_C(y)$	凸集 $C$ 的支撑函数	$\S$1.4
$\delta_C(x)$	凸集 $C$ 的指示函数	$\S$1.5
$\mu$	强凸参数	$\S$1.10
$L$	光滑（Lipschitz 梯度）常数	$\S$1.10
$\kappa = L/\mu$	条件数	$\S$1.10
$\Pi_C(x)$	$x$ 到凸集 $C$ 的投影	$\S$1.4

概念	核心陈述	难度	关键应用
凸集	连线段在集合内	⭐	可行域描述
凸锥	非负组合封闭	⭐⭐	LP/SOCP/SDP 层级
分离超平面定理	不相交凸集可被超平面分开	⭐⭐	KKT/对偶的几何根源
凸函数	切线是全局下界	⭐	全局最优可局部判定
保凸运算	sup、仿射变换、部分最小化保凸	⭐⭐	DCP 验证规则
次梯度	非光滑函数的广义导数	⭐⭐	ADMM/proximal 理论基础
Fermat 规则	$0 \in \partial f(x^*) \Leftrightarrow$ 全局最优	⭐⭐	所有优化的最优性条件根源
强凸性	曲率有正下界 $\mu$	⭐⭐	线性收敛保证
L-光滑	曲率有上界 $L$	⭐⭐	步长选取 $\eta = 1/L$
条件数 $\kappa$	$L/\mu$	⭐⭐	收敛步数 $\sim \kappa$ 或 $\sim \sqrt{\kappa}$
Co-coercivity	梯度算子的定量单调性	⭐⭐⭐	Proximal gradient 收敛证明
Jensen 不等式	$f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$	⭐	ELBO/信息论
Recession cone	凸集的"无穷远方向"	⭐⭐⭐	解存在性
极值点	不能写成其他两点凸组合	⭐⭐	单纯形法理论基础
PL 不等式	$\\|\nabla f\\|^2 \geq 2\mu(f-f^*)$	⭐⭐	线性收敛证明关键步骤
拟凸	下水平集是凸集	⭐⭐⭐	二分法求解
凸投影 $\Pi_C$	闭凸集最近点，非扩张	⭐⭐	投影梯度法 / ADMM

累积项目：本章新增模块¶

项目：手写凸分析验证工具

本章新增模块： - 实现凸性验证函数：给定函数和随机采样点，通过定义式检验凸性 - 实现次梯度计算：对 $\ell_1$ 范数、max 函数、Huber 函数 - 实现强凸性/L-光滑参数估计：通过随机点对估计 $\mu$ 和 $L$ - 实现常见凸集投影：非负象限、Box、$\ell_2$ 球、单纯形 - 实现梯度下降与 Nesterov 加速，可视化收敛曲线差异

import numpy as np

def check_convexity(f, dim, n_samples=1000, tol=1e-6):
    """通过随机采样验证函数凸性（概率性检验）"""
    for _ in range(n_samples):
        x = np.random.randn(dim)
        y = np.random.randn(dim)
        theta = np.random.uniform(0, 1)
        # 检验 Jensen 不等式
        lhs = f(theta * x + (1 - theta) * y)
        rhs = theta * f(x) + (1 - theta) * f(y)
        if lhs > rhs + tol:
            return False, (x, y, theta)
    return True, None

def subdiff_l1(x):
    """计算 L1 范数在 x 处的次微分（返回一个次梯度）"""
    g = np.sign(x)
    # 在 x_i = 0 处，次梯度可以是 [-1,1] 中的任何值
    # 这里返回 0 作为"最小范数次梯度"
    g[x == 0] = 0.0
    return g

def proj_box(x, l, u):
    """投影到 Box 约束 [l, u]"""
    return np.clip(x, l, u)

def proj_l2_ball(x, r=1.0):
    """投影到 L2 球 {z: ||z|| <= r}"""
    norm_x = np.linalg.norm(x)
    if norm_x <= r:
        return x.copy()
    return r * x / norm_x

def proj_simplex(x):
    """投影到概率单纯形 {z >= 0, sum(z) = 1}"""
    n = len(x)
    u = np.sort(x)[::-1]  # 降序排列
    cssv = np.cumsum(u) - 1
    rho = np.max(np.where(u > cssv / np.arange(1, n+1))[0])
    tau = cssv[rho] / (rho + 1)
    return np.maximum(x - tau, 0)

def gradient_descent(f, grad_f, x0, L, n_iter=100):
    """L-光滑凸函数的梯度下降"""
    x = x0.copy()
    eta = 1.0 / L  # 步长 = 1/L（descent lemma 保证）
    history = [f(x)]
    for _ in range(n_iter):
        x = x - eta * grad_f(x)
        history.append(f(x))
    return x, history

def nesterov_accelerated(f, grad_f, x0, L, mu, n_iter=100):
    """Nesterov 加速梯度法（强凸情形）"""
    kappa = L / mu
    beta = (np.sqrt(kappa) - 1) / (np.sqrt(kappa) + 1)
    x = x0.copy()
    y = x0.copy()
    y_prev = x0.copy()
    history = [f(x)]
    for _ in range(n_iter):
        g = grad_f(x)
        y_new = x - (1.0/L) * g
        x = y_new + beta * (y_new - y_prev)
        y_prev = y_new
        history.append(f(x))
    return x, history

1.13 凸函数的典型例子大全 ⭐¶

常见凸函数速查表¶

函数	定义域	凸/严格/强凸	$L$-光滑？	梯度/次微分
$f(x) = a^\top x + b$	$\mathbb{R}^n$	凸（也凹）	$L=0$	$\nabla f = a$
$f(x) = \frac{1}{2}x^\top Ax + b^\top x$ ($A \succeq 0$)	$\mathbb{R}^n$	凸；$A \succ 0$ 时强凸	$L = \lambda_{\max}(A)$	$\nabla f = Ax + b$
$f(x) = \\|x\\|_2$	$\mathbb{R}^n$	凸（非严格）	非光滑	$\partial f(0) = B(0,1)$
$f(x) = \\|x\\|_1$	$\mathbb{R}^n$	凸	非光滑	逐分量 sign
$f(x) = \\|x\\|_2^2$	$\mathbb{R}^n$	2-强凸	$L = 2$	$\nabla f = 2x$
$f(x) = e^x$	$\mathbb{R}$	严格凸（非强凸）	非全局光滑	$f'(x) = e^x$
$f(x) = -\log x$	$\mathbb{R}_{++}$	严格凸	非全局光滑	$f'(x) = -1/x$
$f(x) = x\log x$	$\mathbb{R}_+$	严格凸	非全局光滑	$f'(x) = 1 + \log x$
$f(x) = \max(x_1,...,x_n)$	$\mathbb{R}^n$	凸	非光滑	$\text{conv}\{e_i : x_i = \max\}$
log-sum-exp	$\mathbb{R}^n$	凸	局部光滑	softmax
$f(X) = -\log\det X$	$\mathbb{S}^n_{++}$	严格凸	非全局光滑	$\nabla f = -X^{-1}$
$f(X) = \text{tr}(X^{-1})$	$\mathbb{S}^n_{++}$	凸	非全局光滑	$\nabla f = -X^{-2}$
$\delta_C(x)$	$C$	凸	非光滑	$N_C(x)$
$\frac{1}{2}\\|Ax-b\\|^2$	$\mathbb{R}^n$	凸；$A$ 满列秩时强凸	$L = \\|A^\top A\\|$	$A^\top(Ax-b)$
Huber$_\delta$	$\mathbb{R}$	凸（全局）	$L = 1$	分段

重要凸函数的详细分析¶

log-sum-exp 的凸性证明：$f(x) = \log\sum_i e^{x_i}$

计算 Hessian： $$(\nabla^2 f)_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j} = \begin{cases} p_i(1 - p_i) & i = j \\ -p_i p_j & i \neq j \end{cases}$$

其中 $p_i = e^{x_i}/\sum_j e^{x_j}$（softmax 输出）。

矩阵形式：$\nabla^2 f = \text{diag}(p) - pp^\top$。

验证 PSD：对任意 $v$，$v^\top(\text{diag}(p) - pp^\top)v = \sum_i p_i v_i^2 - (\sum_i p_i v_i)^2 = \text{Var}_p[v] \geq 0$。

最后的等式用了方差公式 $\text{Var}[X] = E[X^2] - (E[X])^2$。

$-\log\det X$ 的凸性：这个函数在 MPC 和控制中经常出现（如最大化椭球体积 $\Leftrightarrow$ 最大化 $\log\det P$）。

凸性可以通过限制在一条直线上证明：$g(t) = -\log\det(X + tV) = -\log\det X - \sum_i \log(1 + t\lambda_i)$，其中 $\lambda_i$ 是 $X^{-1/2}VX^{-1/2}$ 的特征值。$-\log(1+t\lambda_i)$ 关于 $t$ 凸，故 $g$ 凸。

Hessian 验证：$\nabla f(X) = -X^{-1}$，$\nabla^2 f(X)[V] = X^{-1}VX^{-1}$。对任意对称 $V$： $$\text{tr}(V \cdot \nabla^2 f(X)[V]) = \text{tr}(V X^{-1} V X^{-1}) = \|X^{-1/2}VX^{-1/2}\|_F^2 \geq 0$$

因此 Hessian 半正定，$f$ 凸。

工程应用： - D-最优实验设计：$\max \log\det(A^\top \text{diag}(\lambda) A)$ s.t. $\lambda \in \Delta_n$ - 最大体积椭球内接：$\max \log\det B$ s.t. $\|Ba_i + d\| \leq 1$ - 协方差估计：$\min -\log\det \Sigma + \text{tr}(S\Sigma^{-1})$（最大似然估计）

凸函数的函数空间视角 ⭐⭐⭐¶

凸函数不仅可以在有限维空间 $\mathbb{R}^n$ 上定义，还可以在函数空间上定义。例如：

熵函数 $H(p) = -\sum p_i \log p_i$ 是概率分布空间上的**凹**函数
KL 散度 $D_{KL}(p\|q) = \sum p_i \log(p_i/q_i)$ 是 $p$ 的凸函数（固定 $q$）
Fisher 信息 $I(\theta) = \mathbb{E}_\theta[(\nabla \log p(x|\theta))(\nabla \log p(x|\theta))^\top]$ 定义了参数空间上的 Riemannian 度量

这些无限维的凸性概念在 RL（策略优化）、变分推断（ELBO）、信息几何中都有核心应用。

1.14 凸集典型例子与反例 ⭐¶

动机¶

在学习了大量抽象定理之后，我们需要一个"速查库"来快速识别常见集合的凸性。下面的表格覆盖了机器人学和优化中最常遇到的集合。

凸性判定流程¶

面对一个新集合，判断其凸性的系统流程如下：

直接法：取两点 $x, y$，检查 $\theta x + (1-\theta)y$ 是否在集合中
保凸运算法：看能否把集合写成已知凸集通过保凸运算（交、仿射像/原像、透视）得到
下水平集法：若集合是某凸函数的下水平集 $\{x : f(x) \leq \alpha\}$，直接得凸
反例法：找两个集合中的点，看其中点是否在集合外——若是，集合不凸

本质洞察：保凸运算法是实践中最强大的工具。CVXPY 的 DCP 规则本质就是保凸运算的自动化检查——只要你的表达式能被"分解"为凸原子通过保凸运算组合而成，CVXPY 就能确认凸性。

凸集完整分类表¶

集合	定义	闭？	凸？	极值点
超平面	$\{x : a^\top x = b\}$	是	是	无（除零维）
半空间	$\{x : a^\top x \leq b\}$	是	是	无
多面体	$\{x : Ax \leq b\}$	是	是	顶点
单纯形 $\Delta_n$	$\{x \geq 0 : \mathbf{1}^\top x = 1\}$	是	是	$e_i$
欧氏球	$\{x : \\|x-c\\| \leq r\}$	是	是	球面所有点
椭球	$(x-c)^\top P^{-1}(x-c) \leq 1$	是	是	椭球面所有点
SOC	$\{(x,t) : \\|x\\| \leq t\}$	是	是	原点
$\mathbb{S}^n_+$	$\{X : X \succeq 0\}$	是	是	秩 1 矩阵
正交矩阵 $O(n)$	$\{Q : Q^\top Q = I\}$	是	否	—
旋转矩阵 $SO(3)$	$O(n) \cap \{\det=1\}$	是	否	—

重要反例¶

正交矩阵集不凸：取 $Q_1 = I$ 和 $Q_2 = -I$（都是正交矩阵）。中点 $\frac{1}{2}(I + (-I)) = 0$ 不是正交矩阵（$0^\top 0 = 0 \neq I$）。

这就是为什么旋转同步（SE-Sync）需要凸松弛——正交约束 $R^\top R = I$ 定义的可行域不凸，原问题是非凸 QCQP，必须通过 SDP 松弛到凸问题。

Stiefel 流形不凸：$V_k(\mathbb{R}^n) = \{X \in \mathbb{R}^{n \times k} : X^\top X = I_k\}$。这是 $k$ 个正交列向量的集合。当 $k = n$ 时退化为正交群 $O(n)$。

反例：$X_1 = \begin{pmatrix}1\\0\end{pmatrix}$，$X_2 = \begin{pmatrix}0\\1\end{pmatrix}$（都在 $V_1(\mathbb{R}^2) = S^1$ 上）。中点 $\frac{1}{2}(X_1+X_2) = \begin{pmatrix}1/2\\1/2\end{pmatrix}$，$\|(\frac{1}{2},\frac{1}{2})\| = 1/\sqrt{2} \neq 1$，不在单位圆上。

实际影响：以下常见约束定义的可行域**不凸**——任何涉及这些约束的优化都是非凸的： - 旋转矩阵约束 $R \in SO(3)$ - 单位四元数约束 $\|q\| = 1$ - 正交性约束 $U^\top U = I$ - 秩约束 $\text{rank}(X) \leq r$

凸优化的策略是：通过松弛（如 SDP 松弛、核范数松弛）把这些非凸约束替换为凸约束，用松弛问题的解来逼近原问题。

练习¶

证明 $SO(3) = \{R : R^\top R = I, \det R = 1\}$ 不是凸集（给出两个旋转矩阵，验证其中点不在 $SO(3)$ 中）。
证明秩约束集 $\{X \in \mathbb{R}^{m \times n} : \text{rank}(X) \leq r\}$ 不是凸集。
写出核范数松弛 $\|X\|_* \leq \tau$（$\|X\|_*$ 是奇异值之和）定义的集合，验证它是凸集，并解释它如何"松弛"了秩约束。

1.15 从凸分析到优化算法的桥梁 ⭐⭐¶

梯度下降的收敛性（完整证明）¶

定理 1.14.1：设 $f$ 是 $L$-光滑的凸函数，梯度下降 $x_{k+1} = x_k - \frac{1}{L}\nabla f(x_k)$ 满足：

\[f(x_k) - f(x^*) \leq \frac{L\|x_0 - x^*\|^2}{2k}\]

证明：

Step 1：由 descent lemma（$L$-光滑的推论），取 $y = x_k - \frac{1}{L}\nabla f(x_k) = x_{k+1}$：

\[f(x_{k+1}) \leq f(x_k) - \frac{1}{2L}\|\nabla f(x_k)\|^2\]

Step 2：由凸性一阶条件：$f(x^*) \geq f(x_k) + \nabla f(x_k)^\top(x^* - x_k)$

\[f(x_k) - f(x^*) \leq \nabla f(x_k)^\top(x_k - x^*) \leq \|\nabla f(x_k)\| \cdot \|x_k - x^*\|\]

Step 3：由 Step 1：$\|\nabla f(x_k)\|^2 \leq 2L(f(x_k) - f(x_{k+1}))$

Step 4：定义 $\delta_k = f(x_k) - f(x^*)$。由 Step 2：$\delta_k^2 \leq \|\nabla f(x_k)\|^2 \|x_k - x^*\|^2 \leq 2L\delta_k \cdot R^2$

其中 $R = \|x_0 - x^*\|$（可以证明 $\|x_k - x^*\| \leq \|x_0 - x^*\|$）。

因此 $\delta_k \leq 2LR^2 / k$（通过 telescoping 和 $\sum 1/\delta_k$ 的处理）。

更精确的证明使用 $\sum_{i=0}^{k-1} \frac{1}{2L}\|\nabla f(x_i)\|^2 \leq f(x_0) - f(x^*)$ 和 Cauchy-Schwarz。

强凸情形的线性收敛¶

定理 1.14.2：设 $f$ 是 $\mu$-强凸且 $L$-光滑的，梯度下降 $x_{k+1} = x_k - \frac{1}{L}\nabla f(x_k)$ 满足：

\[f(x_k) - f(x^*) \leq \left(1 - \frac{\mu}{L}\right)^k (f(x_0) - f(x^*))\]

证明：

由 descent lemma：$f(x_{k+1}) \leq f(x_k) - \frac{1}{2L}\|\nabla f(x_k)\|^2$

由强凸性的推论（PL 不等式）：$\|\nabla f(x)\|^2 \geq 2\mu(f(x) - f(x^*))$

代入：$f(x_{k+1}) - f(x^*) \leq (f(x_k) - f(x^*)) - \frac{\mu}{L}(f(x_k) - f(x^*)) = (1 - \mu/L)(f(x_k) - f(x^*))$

递推得 $f(x_k) - f(x^*) \leq (1 - \mu/L)^k (f(x_0) - f(x^*))$。

连接到本章内容：这个证明只用了两个工具——$L$-光滑的 descent lemma 和 $\mu$-强凸的 PL 不等式——两者都在 §1.10 建立。凸分析为算法分析提供了精确的"零件"。

PL 不等式的证明与推广 ⭐⭐¶

上面的收敛证明用到了 PL（Polyak-Lojasiewicz）不等式，这里给出完整证明。

定理（PL 不等式）：若 $f$ 是 $\mu$-强凸的，则： $$\|\nabla f(x)\|^2 \geq 2\mu(f(x) - f(x^*))$$

证明：由强凸一阶条件，对任意 $y$：$f(y) \geq f(x) + \nabla f(x)^\top(y-x) + \frac{\mu}{2}\|y-x\|^2$。

对 $y$ 最小化右边（这是关于 $y$ 的二次函数）：最优 $y^* = x - \frac{1}{\mu}\nabla f(x)$。

代入：$f(y^*) \geq f(x) - \frac{1}{2\mu}\|\nabla f(x)\|^2$。

又 $f(x^*) \leq f(y^*)$（$x^*$ 是全局最小），得：$f(x^*) \geq f(x) - \frac{1}{2\mu}\|\nabla f(x)\|^2$。

移项即得 PL 不等式。

PL 不等式的意义：它建立了"梯度大小"和"函数值与最优值之差"之间的定量关系。梯度越大，离最优越远；梯度为零当且仅当到达最优。这个不等式实际上比强凸性弱——存在非凸函数也满足 PL 条件（称为 PL 函数），它们同样具有梯度下降的线性收敛性质。

Nesterov 加速的直觉¶

Nesterov 加速把收敛率从 $(1-\mu/L)^k$ 改善到 $(1-\sqrt{\mu/L})^k$（即把 $\kappa$ 变成 $\sqrt{\kappa}$）。

直觉：普通梯度下降像"在碗里滚球"——在长轴方向来回振荡，收敛慢。Nesterov 加速加了"动量"——像球有惯性，不会在每步完全改变方向，而是保持之前的运动趋势。这抑制了振荡，加速了沿长轴方向的收敛。

与条件数的关系：$\kappa$ 越大，碗越"扁"（长轴/短轴比大），梯度下降振荡越严重。加速方法通过动量抑制振荡，把有效条件数从 $\kappa$ 降到 $\sqrt{\kappa}$。

Nesterov 加速梯度法的完整形式 ⭐⭐⭐¶

算法（Nesterov 加速，强凸情形）： $$y_{k+1} = x_k - \frac{1}{L}\nabla f(x_k)$$ $$x_{k+1} = y_{k+1} + \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}(y_{k+1} - y_k)$$

第二行的"动量项" $\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}(y_{k+1} - y_k)$ 是 Nesterov 加速的精髓——它利用了前一步的运动方向来"预测"下一步该往哪走，从而减少在窄谷方向的振荡。

收敛率对比：

算法	每步复杂度	凸 $f$ 的收敛率	$\mu$-强凸 $f$ 的收敛率
梯度下降	$O(n)$	$O(L R^2 / k)$	$O((1-\mu/L)^k)$
Nesterov 加速	$O(n)$	$O(L R^2 / k^2)$	$O((1-\sqrt{\mu/L})^k)$
共轭梯度（二次）	$O(n)$	—	$O((1-\sqrt{\mu/L})^k)$
Newton 法	$O(n^3)$	—	二次收敛

Nesterov 加速是最优的：Nesterov (1983) 证明了一个下界——对于一阶方法（只能访问梯度的方法），任何算法在 $L$-光滑凸函数上的收敛率不能比 $O(1/k^2)$ 更快。加速梯度法恰好达到了这个下界，因此是一阶方法中最优的。

本质洞察：加速方法的加速来源不是"更聪明地选方向"，而是"利用历史信息抑制振荡"。它在数学上等价于一个精心设计的二阶线性递推——Nesterov 的原始证明使用了"估计序列"技术，本质是构造一系列越来越紧的二次下界。

收敛率的物理直觉¶

可以用一个物理类比来理解不同收敛率：

梯度下降 $O((1-1/\kappa)^k)$：像一个**无摩擦的球在碗中滚动**，每次碰到碗壁就完全反弹，在窄谷方向来回振荡，沿长轴方向缓慢前进
Nesterov 加速 $O((1-1/\sqrt{\kappa})^k)$：像一个**有惯性的重球**，碰到碗壁后动量减缓了反弹，振荡被阻尼，沿长轴方向更快收敛
Newton 法（二次收敛）：像**直接跳到碗底**——用 Hessian 信息消除了方向选择问题，但计算 Hessian 的代价是 $O(n^3)$

练习¶

对 $f(x) = \frac{1}{2}x^\top \text{diag}(1, 100) x$（$\kappa = 100$），分别运行梯度下降和 Nesterov 加速 50 步，画出 $f(x_k) - f^*$ 的收敛曲线。
验证 Nesterov 下界：构造一个 $L$-光滑凸函数 $f$ 和初始点 $x_0$，使得任何只使用梯度信息的方法在 $k$ 步内的误差 $f(x_k) - f^* \geq \frac{L\|x_0-x^*\|^2}{8(k+1)^2}$。（提示：考虑 Nesterov 的"最坏情况函数" $f(x) = \frac{L}{4}(x_1^2 + \sum_{i=1}^{n-1}(x_{i+1}-x_i)^2)$。）

1.16 凸性在机器人优化中的具体应用 ⭐⭐¶

MPC 中的凸性¶

模型预测控制（MPC）每个周期解一个有限 horizon 优化问题：

\[\min_{x, u} \sum_{k=0}^{N-1} [\frac{1}{2}x_k^\top Q x_k + \frac{1}{2}u_k^\top R u_k] + \frac{1}{2}x_N^\top Q_f x_N$$ $$\text{s.t. } x_{k+1} = A x_k + B u_k, \quad x_k \in \mathcal{X}, \quad u_k \in \mathcal{U}\]

凸性分析： - 目标函数：$Q, R, Q_f \succeq 0$ 时是凸的（二次函数，Hessian PSD） - 等式约束：仿射的（线性系统动力学） - 不等式约束：若 $\mathcal{X}, \mathcal{U}$ 是凸集（如多面体、椭球），则约束凸

因此标准线性 MPC 是**凸 QP**，保证全局最优且可高效求解。

SLAM 中的非凸性与凸松弛¶

SLAM 后端优化问题（pose graph optimization）：

\[\min_R \sum_{(i,j)} \|R_i - R_{ij}R_j\|_F^2 \quad \text{s.t. } R_i \in SO(3)\]

这是**非凸**的（$SO(3)$ 不是凸集）。但通过 Shor 松弛（用矩阵 $X \succeq 0$ 替代 $RR^\top$），可以得到 SDP 松弛——一个凸问题。

凸松弛的意义：它给出原非凸问题最优值的下界。如果松弛是"tight"的（松弛最优解恰好满足原约束），则找到了全局最优。

轨迹优化中的凸化¶

SpaceX 的火箭着陆轨迹优化原本是非凸的（推力大小约束 $T_{\min} \leq \|u\| \leq T_{\max}$ 不凸）。

Acikmese-Ploen (2007) 的 lossless convexification 把它变成 SOCP：通过引入 slack 变量和放松，把非凸推力约束变成 SOC 约束 $\|u\| \leq \sigma$（$\sigma$ 是新变量）。

关键定理：松弛后的 SOCP 最优解恰好满足原约束（lossless），即不损失最优性。这使得火箭可以在飞行中**实时**求解轨迹优化（SOCP 有多项式时间算法）。

凸投影算子及其性质 ⭐⭐¶

凸投影是凸分析中最基本的运算之一，也是很多算法（投影梯度法、ADMM）的核心步骤。

定义：对闭凸集 $C$，投影算子 $\Pi_C: \mathbb{R}^n \to C$： $$\Pi_C(x) = \arg\min_{y \in C} \|y - x\|^2$$

由前面的分离定理证明中已知，$\Pi_C(x)$ 存在且唯一。

投影的变分不等式特征化：$p = \Pi_C(x)$ 当且仅当： $$\langle x - p, y - p \rangle \leq 0, \quad \forall y \in C$$

投影的关键性质：

非扩张性（Nonexpansive）：$\|\Pi_C(x) - \Pi_C(y)\| \leq \|x - y\|$

证明：设 $p = \Pi_C(x)$，$q = \Pi_C(y)$。由变分不等式： $$\langle x - p, q - p \rangle \leq 0, \quad \langle y - q, p - q \rangle \leq 0$$

相加：$\langle (x-p) - (y-q), q-p \rangle \leq 0$，即 $\langle x-y, q-p \rangle - \|p-q\|^2 \leq 0$。

由 Cauchy-Schwarz：$\|p-q\|^2 \leq \langle x-y, q-p \rangle \leq \|x-y\|\|p-q\|$，故 $\|p-q\| \leq \|x-y\|$。

幂等性：$\Pi_C(\Pi_C(x)) = \Pi_C(x)$
与法锥的关系：$p = \Pi_C(x) \Leftrightarrow x - p \in N_C(p)$

常见凸集的投影公式：

凸集 $C$	投影 $\Pi_C(x)$	复杂度
半空间 $\{z: a^\top z \leq b\}$	$x - \frac{(a^\top x - b)_+}{\\|a\\|^2}a$	$O(n)$
非负象限 $\mathbb{R}^n_+$	$\max(x, 0)$	$O(n)$
Box $[l, u]$	$\min(\max(x, l), u)$	$O(n)$
$\ell_2$ 球 $\{\\|z\\| \leq r\}$	$r \cdot x / \max(\\|x\\|, r)$	$O(n)$
仿射集 $\{z: Az = b\}$	$x - A^\top(AA^\top)^{-1}(Ax - b)$	$O(n^2)$ 预分解
单纯形 $\Delta_n$	排序 + 阈值	$O(n\log n)$
$\ell_1$ 球 $\{\\|z\\|_1 \leq r\}$	软阈值 + 缩放	$O(n\log n)$
半正定锥 $\mathbb{S}^n_+$	特征分解，截取负特征值	$O(n^3)$

半正定锥投影的推导：设 $X = U\text{diag}(\lambda_i)U^\top$（特征分解），则 $\Pi_{\mathbb{S}^n_+}(X) = U\text{diag}(\max(\lambda_i, 0))U^\top$。

证明：需最小化 $\|Y - X\|_F^2$ s.t. $Y \succeq 0$。由 von Neumann trace inequality，最优 $Y$ 与 $X$ 有相同特征向量，只需对特征值做非负投影。

投影与优化的深层联系¶

投影梯度法（projected gradient descent）的每步迭代是： $$x_{k+1} = \Pi_C(x_k - \eta \nabla f(x_k))$$

先沿负梯度走一步（无约束步），再投影回可行域。这等价于： $$x_{k+1} = \arg\min_{x \in C} \left[\nabla f(x_k)^\top(x - x_k) + \frac{1}{2\eta}\|x - x_k\|^2\right]$$

这正是 proximal 算子的特殊情形——当正则项是指示函数 $\delta_C$ 时。投影梯度法的收敛率与无约束梯度下降相同（$O(1/k)$ for convex，linear for strongly convex），前提是投影步能高效计算。

练习¶

推导对仿射集 $\{x : Ax = b\}$ 的投影公式。（提示：用 KKT 条件。）
证明半正定锥的投影确实是"截取负特征值"。（提示：用 Frobenius 范数的酉不变性。）
证明投影梯度法 $x_{k+1} = \Pi_C(x_k - \eta\nabla f(x_k))$ 等价于 proximal gradient with $g = \delta_C$。

1.17 拟凸与伪凸函数 ⭐⭐⭐¶

动机¶

有些优化问题的目标函数不是凸的，但具有比一般非凸函数更好的结构——下水平集是凸的。这就是拟凸函数。

定义¶

定义 1.16.1（拟凸函数）：$f$ 是拟凸的，如果所有下水平集 $S_\alpha = \{x \mid f(x) \leq \alpha\}$ 都是凸集。

等价条件：$f(\theta x + (1-\theta)y) \leq \max(f(x), f(y))$。

凸 vs 拟凸 vs 伪凸¶

函数类别	定义	关键性质	举例
凸	$f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$	局部最优 = 全局最优	$x^2$, $\\|x\\|$
严格拟凸	$f(\theta x + (1-\theta)y) < \max(f(x), f(y))$	下水平集严格凸	$\sqrt{
拟凸	下水平集是凸集	可用二分法求解	$\lceil x \rceil$（取整）
伪凸	$\nabla f(x)^\top(y-x) \geq 0 \Rightarrow f(y) \geq f(x)$	KKT 充分（比凸弱）	某些分式函数

凸 $\Rightarrow$ 拟凸（凸函数的下水平集一定凸）
拟凸 $\not\Rightarrow$ 凸（反例：$f(x) = \sqrt{|x|}$，下水平集是对称区间（凸），但函数本身在 $x=0$ 附近不凸）
伪凸介于凸和拟凸之间——它保证了"梯度为零 $\Rightarrow$ 全局最优"，但不要求凸性的完整定义

为什么拟凸有用¶

对拟凸问题，可以通过二分法求解：检查 $\{f(x) \leq t\}$ 是否可行（凸可行性问题），对 $t$ 做二分
很多工程问题天然是拟凸的（如信噪比、某些比值优化）
分式规划（$\min f(x)/g(x)$）中，若 $f$ 凸、$g$ 凹且 $g > 0$，则目标是拟凸的——可以通过 Dinkelbach 变换转化为凸问题序列

二分法求解拟凸优化的流程：

设 $p^* = \min f_0(x)$ s.t. $f_i(x) \leq 0$，$f_0$ 拟凸。

设 f_0 的值域的上下界为 [l, u]
while u - l > epsilon:
    t = (l + u) / 2
    解凸可行性问题: 是否存在 x 使得 f_0(x) <= t 且 f_i(x) <= 0?
    if 可行:
        u = t    # 最优值 <= t
    else:
        l = t    # 最优值 > t
输出 p* ≈ u

每个子问题是凸可行性检查（$\{f_0 \leq t\}$ 是凸集），因此高效可解。总迭代次数 $O(\log((u-l)/\epsilon))$。

⚠️ 常见陷阱¶

💡 概念误区：拟凸被误以为是凸 - 拟凸函数的下水平集是凸的，但函数本身不一定凸 - $f$ 拟凸 $\not\Rightarrow$ $f$ 凸 - 拟凸函数可以有非全局的局部极小（与凸函数不同！），但所有严格局部极小都是全局极小

🧠 思维陷阱：对拟凸函数直接用梯度下降 - 梯度下降的收敛保证（如 descent lemma）需要凸性或强凸性，不适用于一般拟凸函数 - 拟凸问题应该用二分法 + 凸可行性检查，或者 Dinkelbach 方法 - 在实践中，如果能把拟凸问题转化为等价凸问题（如通过变量替换），那是最好的策略

练习¶

证明 $f(x) = x_1/x_2$（$x_2 > 0$）是拟凸但不凸的。
用二分法求解 $\min \|Ax - b\|_\infty / \|x\|_2$ s.t. $\|x\| \geq 1$（信号处理中的最小化相对误差问题）。描述每个二分步骤中需要解的凸可行性问题。

1.18 历史脉络与知识演进 ⭐¶

凸分析的发展历程¶

年代	里程碑	贡献者
1911	凸集的基本性质	Minkowski
1935	分离定理的现代形式	Mazur, Eidelheit
1951	凸规划的对偶理论	Fenchel
1958	Legendre-Fenchel 变换系统化	Fenchel
1962	近端映射（proximal mapping）	Moreau
1970	《Convex Analysis》出版	Rockafellar
1976	Proximal point algorithm	Rockafellar
1984	内点法多项式时间	Karmarkar
2004	《Convex Optimization》出版	Boyd & Vandenberghe
2009	FISTA	Beck & Teboulle
2011	ADMM 工程综述	Boyd, Parikh et al.
2014	Proximal Algorithms 综述	Parikh & Boyd
2016	SE-Sync: 凸松弛用于 SLAM	Rosen & Carlone

历史启示：凸分析从纯数学（Minkowski 的几何）到工程应用（Boyd 的教材）经历了近一个世纪。关键转折点是 1970 年代 Rockafellar 的系统化和 2000 年代 Boyd 的工程化——后者让"凸优化"从数学家的工具变成工程师的日常。

两大学派的对比：

维度	Rockafellar 学派	Boyd 学派
核心追求	数学完备性、最弱条件	工程可用性、直觉建立
代表作	《Convex Analysis》(1970)	《Convex Optimization》(2004)
强调的工具	共轭、recession cone、相对内部	DCP、求解器、建模技巧
定理风格	"当且仅当"精确条件	充分条件，强调"如何用"
对工程师的意义	理解"为什么这样做是对的"	知道"怎么做"并快速上手

两个学派互补：Boyd 让工程师能用凸优化解决问题，Rockafellar 让研究者知道这些方法的数学边界在哪里。本教程的目标是把两者结合——用 Boyd 的直觉引入，用 Rockafellar 的严格性证明。

凸分析核心定理依赖图 ⭐⭐¶

理解定理之间的逻辑依赖关系，有助于构建知识树的骨架：

凸集定义
├── 分离超平面定理 ← 投影定理（闭凸集的唯一最近点）
│   ├── 支撑超平面定理
│   │   └── 次梯度存在性
│   ├── Farkas 引理
│   │   └── KKT 条件（第三章）
│   └── 强对偶定理（第三章）
├── 保凸运算
│   └── DCP 规则
└── 凸函数定义
    ├── 一阶条件 → 最优性条件 $0 \in \partial f(x^*)$
    ├── 二阶条件 → 强凸性/光滑性
    │   ├── Descent Lemma → 梯度下降收敛
    │   ├── PL 不等式 → 线性收敛
    │   └── Co-coercivity → Proximal gradient 收敛
    ├── Fenchel-Moreau ($f^{**}=f$) ← 闭凸函数 + 分离定理
    └── Jensen 不等式 → ELBO / 信息论

每个箭头 $A \to B$ 表示"$B$ 的证明依赖 $A$"。可以看到，分离超平面定理是整个凸分析的"枢纽"——几乎所有重要定理都直接或间接依赖它。

跨章综合练习¶

📝 综合练习（需要本章 + 前置线性代数知识）

SVD 与凸优化：证明矩阵的最大奇异值 $\sigma_{\max}(A) = \|A\|_2 = \max_{\|x\|=1} \|Ax\|$ 是 $A$ 的凸函数（作为矩阵空间中的函数）。利用这个结论解释为什么核范数最小化可以用凸优化求解。
特征值与半正定锥：设 $A$ 是对称矩阵。证明 $\lambda_{\max}(A)$ 是凸函数，$\lambda_{\min}(A)$ 是凹函数。利用这个结论解释 Lyapunov 不等式 $A^\top P + PA \prec 0$ 为什么定义了 $P$ 空间中的凸集。
从凸分析到 SLAM：考虑简化的 2D pose graph（3 个节点，2 条边）。写出目标函数，分析其凸性，说明为什么 Gauss-Newton 可能陷入局部最优，以及 SDP 松弛如何提供全局最优性证书。

凸性的计算验证工具 ⭐⭐¶

为什么需要计算验证¶

理论上判断凸性可以通过 Hessian 半正定来完成，但在实际问题中： - 函数可能没有解析的 Hessian（如黑箱函数、仿真目标） - Hessian 的计算代价可能很高（维度 $n$ 很大时 $O(n^2)$） - 有时我们只需要"大概率确认"凸性，而不需要严格证明

基于采样的凸性验证¶

方法 1：随机采样 Jensen 检验。取 $N$ 对随机点 $(x_i, y_i)$ 和随机 $\theta_i \in [0,1]$，检查： $$f(\theta_i x_i + (1-\theta_i)y_i) \leq \theta_i f(x_i) + (1-\theta_i)f(y_i) + \epsilon$$

若所有检查通过，函数"大概率"凸。若任何一个失败，函数确定不凸。

方法 2：随机采样 Hessian 特征值。在随机点 $x_i$ 处计算 $\nabla^2 f(x_i)$ 的最小特征值，若全部 $\geq 0$，函数可能凸。

方法 3：使用 SymPy 进行符号计算。对于有解析表达式的函数，可以符号计算 Hessian 并验证半正定性。

import sympy as sp

def verify_convexity_symbolic(f_expr, vars):
    """用 SymPy 符号验证凸性（计算 Hessian 并检查半正定）"""
    H = sp.hessian(f_expr, vars)
    # 检查所有主子式非负（Sylvester 判据）
    n = len(vars)
    for k in range(1, n+1):
        minor = H[:k, :k].det()
        result = sp.simplify(minor)
        print(f"  {k}阶主子式 = {result}")
    # 或直接检查特征值
    eigenvals = H.eigenvals()
    print(f"  特征值: {eigenvals}")
    return H

# 示例：验证 f(x,y) = x^2 + xy + y^2 的凸性
x, y = sp.symbols('x y')
f = x**2 + x*y + y**2
H = verify_convexity_symbolic(f, [x, y])

CVXPY 的 DCP 验证¶

CVXPY 提供了自动的凸性验证——如果你的表达式通过 DCP 检查，就保证了凸性：

import cvxpy as cp

x = cp.Variable(3)
# DCP 可以验证的凸表达式
expr1 = cp.norm(x)          # 凸
expr2 = cp.quad_form(x, P)  # 凸（P psd）
expr3 = cp.log_sum_exp(x)   # 凸

# DCP 无法验证的（可能凸但不满足 DCP 规则）
# expr4 = cp.sqrt(cp.quad_form(x, P))  # DCP 拒绝
# 等价的 DCP 写法：cp.norm(P_sqrt @ x)

何时 DCP 不够用：自定义非线性函数、含有条件分支的函数、需要 Schur 互补变换的函数。此时需要手动验证凸性，或使用 DQCP（Disciplined Quasiconvex Programming）框架。

向后指向：从凸分析到后续章节¶

本章建立的凸分析基础将在后续章节中反复使用。以下是关键联系：

本章概念	后续章节	如何使用
次梯度 $\partial f$	Ch2 共轭与 proximal	proximal 算子 = 次微分 resolvent
分离超平面定理	Ch3 对偶理论	Slater → 强对偶的证明核心步骤
强凸性 $\mu$	Ch2 强凸-光滑对偶	$f$ $\mu$-强凸 $\Leftrightarrow$ $f^*$ $1/\mu$-光滑
$L$-光滑 + descent lemma	Ch3 KKT + 求解器	OSQP 终止条件基于 KKT 残差
凸集投影	Ch2 proximal 算子	$\text{prox}_{\delta_C} = \Pi_C$
法锥 $N_C(x)$	Ch3 KKT 条件	互补松弛 = 法锥条件
条件数 $\kappa = L/\mu$	优化算法	决定梯度法 / Nesterov 的收敛步数
半正定锥 $\mathbb{S}^n_+$	Ch3 SDP 对偶	Certifiable SLAM 的对偶证书

延伸阅读¶

资源	难度	说明
Boyd & Vandenberghe《Convex Optimization》Ch 2-3	⭐⭐	最友好的工程入门，免费PDF
Rockafellar《Convex Analysis》§1-§13, §23-§27	⭐⭐⭐⭐	凸分析圣经，查阅用
Bubeck《Convex Optimization: Algorithms and Complexity》§1-§3	⭐⭐⭐	130 页精炼总结，证明极简洁
Bauschke & Combettes《Convex Analysis and Monotone Operator Theory》Ch 3-4, 8-9, 16	⭐⭐⭐⭐	Hilbert 空间框架，最严格
Nesterov《Lectures on Convex Optimization》Ch 2.1	⭐⭐⭐	强凸/光滑的标准定义出处
Beck《First-Order Methods in Optimization》Ch 2-3	⭐⭐⭐	面向算法的实用参考
Hiriart-Urruty & Lemaréchal《Fundamentals of Convex Analysis》	⭐⭐⭐	Rockafellar 的可读版本
Bertsekas《Convex Optimization Theory》	⭐⭐⭐⭐	几何直觉极强，Min Common/Max Crossing 视角独特
Stanford EE364a 视频课程（Boyd 2023版）	⭐⭐	免费，清晰幽默，最佳入门视频
文再文《最优化：建模、算法与理论》	⭐⭐⭐	最现代中文教材，覆盖非凸优化
Sra & Vishnoi "Optimization for Machine Learning"	⭐⭐⭐	机器学习视角的凸分析

🔧 故障排查手册¶

症状	可能原因	排查步骤	相关章节
CVXPY 报错 "DCP violation"	目标或约束不满足 DCP 合成规则	1. 检查每个 atom 的 curvature 和 sign 2. 用等价变换改写（如 norm 代替 sqrt(quad_form)）3. 查 CVXPY DCP 规则表	§1.6 保凸运算
优化器返回多个局部最优	问题实际上不凸	1. 验证目标函数凸性（计算 Hessian 检查 PSD）2. 验证约束集凸性 3. 如果非凸，考虑凸松弛	§1.5 凸函数定义
梯度下降收敛极慢	条件数 $\kappa$ 很大	1. 估计 $L$ 和 $\mu$ 2. 如果 $\kappa \gg 1$，使用预处理或 Nesterov 加速 3. 考虑 L-BFGS 等拟牛顿法	§1.10 条件数
次梯度法不收敛	步长设置不当	1. 次梯度法需要递减步长（如 $\eta_k = 1/\sqrt{k}$）2. 不能用固定步长 3. 检查是否误用了梯度下降的步长策略	§1.8 次梯度
投影到凸集计算出错	集合描述有误或算法实现有bug	1. 验证集合确实是凸的 2. 对简单集合用解析投影公式 3. 对复杂集合用 CVXPY 求解投影子问题	§1.4 分离定理
法锥计算结果为空	点不在集合边界上	1. 检查点是否真的在 $\partial C$ 上 2. 内部点的法锥是 $\{0\}$（不是空集）3. 集合外部点的法锥未定义	§1.8 次梯度
凸性验证与 DCP 矛盾	DCP 比保凸运算更严格	1. 检查是否用了 DCP 不支持的复合 2. 尝试手动做等价变换（如 Schur 互补）3. 使用 DQCP 框架处理拟凸	§1.6 保凸运算
强凸参数 $\mu$ 估计不准	非二次函数的 $\mu$ 依赖定义域	1. 在有界域上用 Hessian 最小特征值估计 2. 加 $\ell_2$ 正则 $\frac{\mu}{2}\\|x\\|^2$ 可控制 $\mu$ 3. 用自适应步长避免依赖 $\mu$	§1.10 强凸性
Nesterov 加速"不加速"	动量参数 $\beta$ 设错	1. 检查 $\beta = (\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)$ 是否用了正确的 $\kappa$ 2. 一般凸（非强凸）情形 $\beta = (k-1)/(k+2)$（与迭代步相关）3. 验证步长 $\eta = 1/L$	§1.15 收敛性
半正定锥投影后矩阵不对称	数值精度或输入矩阵不对称	1. 先对称化 $X \leftarrow (X+X^\top)/2$ 2. 特征分解后截取负特征值 3. 检查截取后 $\lambda_{\min} \geq -\epsilon$	§1.3 半正定锥

故障排查的一般策略¶

面对优化算法的异常行为，推荐以下排查顺序：

先检查问题本身：凸性是否成立？约束是否相容？Slater 条件是否满足？
再检查算法参数：步长是否 $\leq 1/L$？强凸参数 $\mu$ 是否准确？动量参数是否正确？
然后检查实现：梯度计算是否正确？（用数值差分验证）投影是否正确？prox 公式是否对应正确的 $\lambda$ 位置？
最后检查数值：是否有 NaN/Inf？条件数是否过大？精度是否足够？

本质洞察：大多数优化算法的 bug 不是算法本身的问题，而是问题建模的问题（不凸、约束不相容）或参数设置的问题（步长太大）。先确认问题是"结构良好的"，再去调试算法。

运算	条件	结论
\(f(x) = h(g(x))\)	\(h\) 凸不减，\(g\) 凸	\(f\) 凸
\(f(x) = h(g(x))\)	\(h\) 凸不增，\(g\) 凹	\(f\) 凸
非负加权和	\(w_i \geq 0\)，\(f_i\) 凸	\(\sum w_i f_i\) 凸
仿射复合	\(f\) 凸	\(f(Ax+b)\) 凸
逐点 sup	\(f_\alpha\) 凸	\(\sup_\alpha f_\alpha\) 凸
部分最小化	\(f(x,y)\) 联合凸	\(\inf_y f(x,y)\) 凸

不等式	取 \(f\) 为	取概率分布为
AM-GM：\(\sqrt{ab} \leq \frac{a+b}{2}\)	\(f(x) = -\log x\)（凸）	均匀分布在 \(\{a, b\}\)
Holder：$\sum	x_i y_i	\leq \|x\|_p\|y\|_q$
幂平均不等式	\(f(x) = x^r\)（\(r \geq 1\) 凸）	加权分布
信息不等式 \(D_{KL} \geq 0\)	\(f(x) = -\log x\)	分布 \(p\)

误解	正确理解
"凸集的边界有角就不是凸的"	凸性是代数性质（线性组合封闭），与边界光滑性无关。正方形、多面体都是凸集
"凸函数一定连续"	凸函数在 \(\text{ri}(\text{dom}\,f)\) 上自动连续，但在定义域边界上可以不连续（如指示函数 \(\delta_C\)）
"下水平集凸 \(\Rightarrow\) 函数凸"	反例：\(f(x) = \sqrt{\\|x\\|}\) 的下水平集是凸的（球），但 \(f\) 不凸。下水平集凸只意味着拟凸
"二阶条件是判断凸性的唯一方法"	二阶条件只适用于二次可微函数。\(f(x) = \\|x\\|\) 是凸函数但在 \(x=0\) 不可微，需用定义式或 epigraph 判断
"凸函数之积仍凸"	反例：\(f(x) = x\)（凸），\(g(x) = -x\)（凸），\(fg = -x^2\)（凹）。凸性不在乘法下封闭
"\(\sup\) 和 \(\inf\) 对凸性地位相同"	\(\sup\) 保凸但 \(\inf\) 不一定保凸。\(\inf\) 保凸需要联合凸性条件（部分最小化定理）
"相对内部和内部差不多"	低维凸集（如 \(\mathbb{R}^3\) 中的线段）的内部为空但相对内部非空。Fenchel-Moreau 定理等关键结论依赖相对内部
"\(0 \in \partial f(x^*)\) 表示导数为零"	对非光滑函数，\(\partial f(x^)\) 是一个集合。\(0 \in \partial f(x^)\) 表示零向量在次微分集中，不是"导数为零"

符号	含义	首次出现
\(C\), \(D\)	凸集	\(\S\)1.2
\(\text{conv}(S)\)	集合 \(S\) 的凸包	\(\S\)1.2
\(\text{aff}(C)\)	凸集 \(C\) 的仿射包	\(\S\)1.2
\(K\), \(K^*\)	凸锥及其对偶锥（极锥）	\(\S\)1.2, \(\S\)1.4
\(\mathbb{S}^n_+\)	\(n \times n\) 半正定矩阵锥	\(\S\)1.3
\(\text{SOC}_n\)	\(n+1\) 维二阶锥（Lorentz 锥）	\(\S\)1.3
\(\text{ri}(C)\)	凸集 \(C\) 的相对内部	\(\S\)1.3
\(\text{epi}(f)\)	函数 \(f\) 的上图（epigraph）	\(\S\)1.5
\(\text{dom}(f)\)	函数 \(f\) 的有效定义域	\(\S\)1.5
\(\partial f(x)\)	\(f\) 在 \(x\) 处的次微分	\(\S\)1.8
\(N_C(x)\)	凸集 \(C\) 在 \(x\) 处的法锥	\(\S\)1.8
\(\sigma_C(y)\)	凸集 \(C\) 的支撑函数	\(\S\)1.4
\(\delta_C(x)\)	凸集 \(C\) 的指示函数	\(\S\)1.5
\(\mu\)	强凸参数	\(\S\)1.10
\(L\)	光滑（Lipschitz 梯度）常数	\(\S\)1.10
\(\kappa = L/\mu\)	条件数	\(\S\)1.10
\(\Pi_C(x)\)	\(x\) 到凸集 \(C\) 的投影	\(\S\)1.4

函数	定义域	凸/严格/强凸	\(L\)-光滑？	梯度/次微分
\(f(x) = a^\top x + b\)	\(\mathbb{R}^n\)	凸（也凹）	\(L=0\)	\(\nabla f = a\)
\(f(x) = \frac{1}{2}x^\top Ax + b^\top x\) (\(A \succeq 0\))	\(\mathbb{R}^n\)	凸；\(A \succ 0\) 时强凸	\(L = \lambda_{\max}(A)\)	\(\nabla f = Ax + b\)
\(f(x) = \\|x\\|_2\)	\(\mathbb{R}^n\)	凸（非严格）	非光滑	\(\partial f(0) = B(0,1)\)
\(f(x) = \\|x\\|_1\)	\(\mathbb{R}^n\)	凸	非光滑	逐分量 sign
\(f(x) = \\|x\\|_2^2\)	\(\mathbb{R}^n\)	2-强凸	\(L = 2\)	\(\nabla f = 2x\)
\(f(x) = e^x\)	\(\mathbb{R}\)	严格凸（非强凸）	非全局光滑	\(f'(x) = e^x\)
\(f(x) = -\log x\)	\(\mathbb{R}_{++}\)	严格凸	非全局光滑	\(f'(x) = -1/x\)
\(f(x) = x\log x\)	\(\mathbb{R}_+\)	严格凸	非全局光滑	\(f'(x) = 1 + \log x\)
\(f(x) = \max(x_1,...,x_n)\)	\(\mathbb{R}^n\)	凸	非光滑	\(\text{conv}\{e_i : x_i = \max\}\)
log-sum-exp	\(\mathbb{R}^n\)	凸	局部光滑	softmax
\(f(X) = -\log\det X\)	\(\mathbb{S}^n_{++}\)	严格凸	非全局光滑	\(\nabla f = -X^{-1}\)
\(f(X) = \text{tr}(X^{-1})\)	\(\mathbb{S}^n_{++}\)	凸	非全局光滑	\(\nabla f = -X^{-2}\)
\(\delta_C(x)\)	\(C\)	凸	非光滑	\(N_C(x)\)
\(\frac{1}{2}\\|Ax-b\\|^2\)	\(\mathbb{R}^n\)	凸；\(A\) 满列秩时强凸	\(L = \\|A^\top A\\|\)	\(A^\top(Ax-b)\)
Huber\(_\delta\)	\(\mathbb{R}\)	凸（全局）	\(L = 1\)	分段

分离类型	条件	结论	适用场景
弱分离	\(C \cap D = \emptyset\)，\(C\)、\(D\) 凸	\(a^\top x \leq b \leq a^\top y\)	一般不相交凸集
严格分离	至少一个闭、另一个紧	\(a^\top x < b < a^\top y\)	闭凸集与外部点
强分离	\(\text{dist}(C, D) > 0\)	\(a^\top x \leq b - \epsilon \leq b + \epsilon \leq a^\top y\)	闭凸集之间有正距离

运算	为什么不保凸	反例
凸函数之积	\(f \cdot g\) 可以不凸	\(f(x) = x\)，\(g(x) = x\)，\(fg = x^2\)（碰巧凸）；\(f = x\)，\(g = -x\)，\(fg = -x^2\)（凹）
凸函数之差	\(f - g\) 可以不凸	\(f = x^2\)，\(g = 2x^2\)，\(f-g = -x^2\)（凹）
\(\inf\) 的 \(\inf\)	嵌套 inf 不一定保凸	需要联合凸性条件
凸函数的复合（无单调性）	\(h(g(x))\)，\(h\) 凸 \(g\) 凸不够	\(h(t)=t^2\)，\(g(x)=-x^2+1\)：\(h(g(x))=(1-x^2)^2\) 非凸

运算	公式	条件
求和	\(\partial(f+g) = \partial f + \partial g\)	ri(dom f) \(\cap\) ri(dom g) \(\neq \emptyset\)
标量乘	\(\partial(\alpha f) = \alpha \partial f\)	\(\alpha > 0\)
仿射复合	\(\partial(f \circ A) = A^\top \partial f(A\cdot)\)	正则条件
逐点 max	\(\partial(\max_i f_i) = \text{conv}\cup_{i \in I} \partial f_i\)	\(f_i\) 凸
指示函数	\(\partial \delta_C(x) = N_C(x)\)	\(C\) 凸

算法	收敛率	含义
梯度下降	\(O\left(\left(\frac{\kappa-1}{\kappa+1}\right)^k\right) = O(e^{-2k/\kappa})\)	\(\kappa\) 越大越慢
Nesterov 加速	\(O\left(\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k\right) = O(e^{-2k/\sqrt{\kappa}})\)	加速把 \(\kappa\) 变成 \(\sqrt{\kappa}\)
共轭梯度	\(O\left(\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k\right)\)	与 Nesterov 同阶

场景	典型条件数	预处理方法	效果
MPC-QP	\(10^2 - 10^4\)	Ruiz 均衡	OSQP 默认使用
SLAM 后端	\(10^4 - 10^8\)	不完全 Cholesky / AMG	Ceres 自动预处理
RL value function	\(10^1 - 10^3\)	Adam 自适应步长	隐式对角预处理

集合	定义	闭？	凸？	极值点
超平面	\(\{x : a^\top x = b\}\)	是	是	无（除零维）
半空间	\(\{x : a^\top x \leq b\}\)	是	是	无
多面体	\(\{x : Ax \leq b\}\)	是	是	顶点
单纯形 \(\Delta_n\)	\(\{x \geq 0 : \mathbf{1}^\top x = 1\}\)	是	是	\(e_i\)
欧氏球	\(\{x : \\|x-c\\| \leq r\}\)	是	是	球面所有点
椭球	\((x-c)^\top P^{-1}(x-c) \leq 1\)	是	是	椭球面所有点
SOC	\(\{(x,t) : \\|x\\| \leq t\}\)	是	是	原点
\(\mathbb{S}^n_+\)	\(\{X : X \succeq 0\}\)	是	是	秩 1 矩阵
正交矩阵 \(O(n)\)	\(\{Q : Q^\top Q = I\}\)	是	否	—
旋转矩阵 \(SO(3)\)	\(O(n) \cap \{\det=1\}\)	是	否	—

算法	每步复杂度	凸 \(f\) 的收敛率	\(\mu\)-强凸 \(f\) 的收敛率
梯度下降	\(O(n)\)	\(O(L R^2 / k)\)	\(O((1-\mu/L)^k)\)
Nesterov 加速	\(O(n)\)	\(O(L R^2 / k^2)\)	\(O((1-\sqrt{\mu/L})^k)\)
共轭梯度（二次）	\(O(n)\)	—	\(O((1-\sqrt{\mu/L})^k)\)
Newton 法	\(O(n^3)\)	—	二次收敛

凸集 \(C\)	投影 \(\Pi_C(x)\)	复杂度
半空间 \(\{z: a^\top z \leq b\}\)	\(x - \frac{(a^\top x - b)_+}{\\|a\\|^2}a\)	\(O(n)\)
非负象限 \(\mathbb{R}^n_+\)	\(\max(x, 0)\)	\(O(n)\)
Box \([l, u]\)	\(\min(\max(x, l), u)\)	\(O(n)\)
\(\ell_2\) 球 \(\{\\|z\\| \leq r\}\)	\(r \cdot x / \max(\\|x\\|, r)\)	\(O(n)\)
仿射集 \(\{z: Az = b\}\)	\(x - A^\top(AA^\top)^{-1}(Ax - b)\)	\(O(n^2)\) 预分解
单纯形 \(\Delta_n\)	排序 + 阈值	\(O(n\log n)\)
\(\ell_1\) 球 \(\{\\|z\\|_1 \leq r\}\)	软阈值 + 缩放	\(O(n\log n)\)
半正定锥 \(\mathbb{S}^n_+\)	特征分解，截取负特征值	\(O(n^3)\)

函数类别	定义	关键性质	举例
凸	\(f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)\)	局部最优 = 全局最优	\(x^2\), \(\\|x\\|\)
严格拟凸	\(f(\theta x + (1-\theta)y) < \max(f(x), f(y))\)	下水平集严格凸	$\sqrt{
拟凸	下水平集是凸集	可用二分法求解	\(\lceil x \rceil\)（取整）
伪凸	\(\nabla f(x)^\top(y-x) \geq 0 \Rightarrow f(y) \geq f(x)\)	KKT 充分（比凸弱）	某些分式函数

本章概念	后续章节	如何使用
次梯度 \(\partial f\)	Ch2 共轭与 proximal	proximal 算子 = 次微分 resolvent
分离超平面定理	Ch3 对偶理论	Slater → 强对偶的证明核心步骤
强凸性 \(\mu\)	Ch2 强凸-光滑对偶	\(f\) \(\mu\)-强凸 \(\Leftrightarrow\) \(f^*\) \(1/\mu\)-光滑
\(L\)-光滑 + descent lemma	Ch3 KKT + 求解器	OSQP 终止条件基于 KKT 残差
凸集投影	Ch2 proximal 算子	\(\text{prox}_{\delta_C} = \Pi_C\)
法锥 \(N_C(x)\)	Ch3 KKT 条件	互补松弛 = 法锥条件
条件数 \(\kappa = L/\mu\)	优化算法	决定梯度法 / Nesterov 的收敛步数
半正定锥 \(\mathbb{S}^n_+\)	Ch3 SDP 对偶	Certifiable SLAM 的对偶证书

工具	用途	示例
`np.linalg.eigvalsh(H)`	检查 Hessian 半正定	最小特征值 \(< 0\) → 非凸
`scipy.optimize.check_grad`	验证梯度实现	解析梯度 vs 数值差分
CVXPY `.is_dcp()`	DCP 规则检查	表达式是否满足 DCP
OSQP `.dual_inf_cert`	对偶不可行证书	原问题是否无界

凸分析基础¶

前置自测¶

本章目标¶

1.1 为什么凸分析是优化理论的绝对地基 ⭐¶

动机¶

如果不学凸分析会怎样¶

凸分析在机器人学中的角色¶

本章知识地图¶

1.2 凸集的定义与直觉 ⭐¶

动机¶

严格定义¶

凸组合与凸包¶

仿射集与仿射包¶

锥与凸锥¶

⚠️ 常见陷阱¶

练习¶

1.3 重要凸集家族 ⭐⭐¶

动机¶

超平面与半空间¶

多面体¶

欧氏球与椭球¶

二阶锥（SOC / Lorentz 锥） ⭐⭐¶

半正定锥 \(\mathbb{S}^n_+\) ⭐⭐⭐¶

相对内部（relative interior）⭐⭐⭐¶

⚠️ 常见陷阱¶

练习¶

1.4 保凸运算与分离超平面定理 ⭐⭐¶

动机¶

保凸运算大全¶

分离超平面定理 ⭐⭐¶

分离定理的推论与应用 ⭐⭐¶

支撑函数 ⭐⭐⭐¶

极锥 ⭐⭐⭐¶

⚠️ 常见陷阱¶

练习¶

1.5 凸函数的四种等价定义 ⭐¶

动机¶

定义式¶

Epigraph 定义¶

一阶条件（需可微）⭐⭐¶

二阶条件（需二次可微）⭐⭐¶

四种定义的关系总结¶

严格凸与强凸的区分 ⭐⭐¶

⚠️ 常见陷阱¶

练习¶

1.6 凸函数的保凸运算 ⭐⭐¶

动机¶

非负加权和¶

仿射复合¶

逐点上确界 ⭐⭐¶

部分最小化 ⭐⭐⭐¶

透视变换 ⭐⭐⭐¶

保凸运算的反面——非保凸运算¶

复合规则总结¶

⚠️ 常见陷阱¶

练习¶

1.7 闭凸函数与下半连续性 ⭐⭐⭐¶

动机¶

下半连续性¶

闭凸函数¶

凸函数的连续性 ⭐⭐¶

⚠️ 常见陷阱¶

练习¶

1.8 次梯度理论 ⭐⭐¶

动机¶

次梯度的定义与几何 ⭐⭐¶

典型例子的次微分计算¶

次梯度存在性定理 ⭐⭐¶

次微分的计算规则 ⭐⭐¶

次微分的几何性质 ⭐⭐⭐¶

⚠️ 常见陷阱¶

练习¶

1.9 最优性条件与 Fermat 规则 ⭐⭐¶

动机¶

Fermat 规则¶

约束优化的推广¶

与 KKT 条件的联系 ⭐⭐¶

Fermat 规则的计算应用 ⭐⭐¶

⚠️ 常见陷阱¶

练习¶