优化理论（一）：凸分析基础
解锁本系列后续内容的几何与分析工具包：凸集、凸函数、共轭（Fenchel）变换、次梯度，以及示性函数/支撑函数对；包含詹森不等式、投影定理及基本范数次微分的完整证明。
本文是本系列其余所有内容的基石。我们后续将证明的几乎所有结论——梯度下降法的收敛速率、拉格朗日对偶性、近端算子（proximal operator），乃至随机优化方法的分析——都依赖于关于凸集与凸函数的一小套基本事实。本文从零开始，逐一推导全部结论。
若你仅记住本文中的三点，请务必牢记以下内容：
- 一个集合是凸集，当且仅当它包含其中任意两点之间的整条线段；一个函数是凸函数，当且仅当它的上镜图（epigraph） 是一个凸集。
- 共轭函数（conjugate） $f^*$ 是广义化的勒让德变换（Legendre transform）：它将逐点不等式转化为线性不等式，是连接原始问题（primal problem）与对偶问题（dual problem）的关键桥梁。
- 次微分（subdifferential） $\partial f(x)$ 是非光滑凸函数在点 $x$ 处“梯度”的恰当推广；只要 $x$ 位于 $\mathrm{dom}(f)$ 的相对内部（relative interior），$\partial f(x)$ 就非空。
我第一次试着自己证明梯度下降的收敛速率时，被一堆看起来很无害的术语挡住了：凸集、上镜图、共轭、次梯度。它们都没什么神秘，但堆在一起像一面墙。
这篇文章是写给那时候的我的。先让你在脑子里有几张图——线段、碗状的曲面、两条切线——再慢慢把名字一个个贴上去。等读到后面证明步长上限或者推导对偶问题时，你就会发现这些工具其实只是反复出现的几种几何动作。
如果只能记住三件事：
- 凸集就是任意两点之间的线段还在里面；凸函数等价于上镜图（函数图像上方的区域）是凸集——所有定义最后都要落到这一句话。
- 共轭 $f^*$ 把“点点都满足”的不等式翻译成线性不等式，是后面所有对偶推导的桥梁。
- 次微分 $\partial f(x)$ 把“梯度”推广到带尖角的凸函数；只要 $x$ 不在边界的奇怪地方，它就非空。
下面我会从最普通的二维图像出发，逐步把这些概念建起来。每一步都尽量先问“这个东西在描述什么直观对象”，再写定义。
你将学到什么#
- 凸集、凸包（convex hull）、投影定理（含严格证明）；
- 凸函数及其四种等价刻画方式（定义、上镜图、一阶条件、二阶条件）；
- 保持凸性的运算：逐点上确界（pointwise sup）、复合（composition）、透视变换（perspective）；
- 共轭函数 $f^*$ 及芬切尔–杨不等式（Fenchel–Young inequality）；
- 次梯度（subgradients）与次微分演算（subdifferential calculus）；
- 具体计算示例：$\partial \|x\|_1$ 、$\partial \|x\|_2$ 、$\partial \max\{0, x\}$ 。
前置知识#
线性代数（内积、范数）、基础实分析（极限、连续性、上确界）、多元微积分（梯度、Hessian 矩阵）。无需任何优化背景。
凸集#
定义与基本例子#
$$ \lambda x + (1 - \lambda) y \in C. $$几何含义：连接 $C$ 中任意两点的线段完全落在 $C$ 内部。
以下例子应熟记于心：
- 仿射子空间 $\{x : Ax = b\}$ 与半空间 $\{x : a^\top x \leq b\}$ ；
- 任意范数下的范数球 $\{x : \|x\| \leq r\}$ ；
- 半正定锥 $\mathbf{S}^n_+ = \{X \in \mathbb{R}^{n \times n} : X = X^\top,\, X \succeq 0\}$ ；
- 概率单形 $\Delta^{n-1} = \{p \in \mathbb{R}^n_+ : \sum_i p_i = 1\}$ 。
一个反直觉的例子：所有可逆矩阵构成的集合不是凸集。取 $X = I$ 与 $Y = -I$ ，其连线中点为零矩阵（不可逆）。
保持凸性的运算#
下列构造若以凸集为输入，则输出仍为凸集。每条均可直接由定义一步验证；你应能不查阅资料即写出证明。
| 运算 | 命题 |
|---|---|
| 交集 | 若每个 $C_i$ 是凸集，则 $\bigcap_{i \in I} C_i$ 是凸集。 |
| 仿射像 | $A C + b = \{Ax + b : x \in C\}$ 是凸集。 |
| 笛卡尔积 | $C_1 \times C_2$ 是凸集。 |
| 和集 | $C_1 + C_2 = \{x + y : x \in C_1,\, y \in C_2\}$ 是凸集。 |
| 仿射原像（逆像） | $\{x : Ax + b \in C\}$ 是凸集。 |
其中交集规则在实践中最为常用——它解释了为何多面体 $\{x : Ax \leq b\}$ 是凸集（它是若干半空间的交），也说明了凸优化问题的可行域必为凸集。
投影定理#
本文反复使用如下重要定理：
$$ \langle y - z,\, x - z \rangle \leq 0 \quad \text{对所有 } x \in C \text{ 成立}。 $$ $$ \|x_k - x_m\|_2^2 = 2 \|x_k - y\|_2^2 + 2 \|x_m - y\|_2^2 - 4 \left\| \tfrac{x_k + x_m}{2} - y \right\|_2^2. $$ $$ \|x_k - x_m\|_2^2 \leq 2 \|x_k - y\|_2^2 + 2 \|x_m - y\|_2^2 - 4 d^2 \to 0, $$投影定理．设 $C \subseteq \mathbb{R}^n$ 是非空闭凸集，$y \in \mathbb{R}^n$ 。则存在唯一一点 $\pi_C(y) \in C$ ，使得 $\|x - y\|_2$ 在 $x \in C$ 上取得最小值。进一步地，$z = \pi_C(y)$ 当且仅当
当 $k,m \to \infty$ 时成立。于是 $\{x_k\}$ 收敛于某点 $z$ ；又因 $C$ 是闭集，故 $z \in C$ ，且满足 $\|z - y\|_2 = d$ 。
$$ \|z_1 - z_2\|_2^2 \leq 2 d^2 + 2 d^2 - 4 d^2 = 0, $$故 $z_1 = z_2$ 。
$$ \|y - z\|_2^2 \leq \|y - z - \lambda (x - z)\|_2^2 = \|y - z\|_2^2 - 2 \lambda \langle y - z,\, x - z \rangle + \lambda^2 \|x - z\|_2^2. $$ $$ 2 \langle y - z,\, x - z \rangle \leq \lambda \|x - z\|_2^2. $$令 $\lambda \to 0^+$ 即得所需不等式。反之，若该不等式对所有 $x \in C$ 成立，展开 $\|x - y\|_2^2 = \|(x - z) - (y - z)\|_2^2 \geq \|y - z\|_2^2$ ，即可推出 $z = \pi_C(y)$ 。$\blacksquare$
投影定理具有优美的几何解释：$\pi_C(y)$ 是 $C$ 中使得线段 $y \to z$ 与 $C$ 内任一方向夹角均不超过 $90^\circ$ 的唯一点。
凸函数#
四种等价刻画#
设 $f : \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ ，其有效定义域为 $\mathrm{dom}(f) = \{x : f(x) < +\infty\}$ ，并假设该集合是凸集。以下四条性质彼此等价，后续本文不加区分地使用它们：
$$ f(\lambda x + (1 - \lambda) y) \leq \lambda f(x) + (1 - \lambda) f(y). \tag{D} $$上镜图刻画：集合 $\mathrm{epi}(f) = \{(x, t) \in \mathbb{R}^{n+1} : f(x) \leq t\}$ 是 $\mathbb{R}^{n+1}$ 中的凸集。
$$ f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle. \tag{F1} $$ $$ \nabla^2 f(x) \succeq 0. \tag{F2} $$(D) 与上镜图刻画的等价性：对任意 $(x, s), (y, t) \in \mathrm{epi}(f)$ ，点 $(\lambda x + (1 - \lambda) y,\, \lambda s + (1 - \lambda) t)$ 属于 $\mathrm{epi}(f)$ 当且仅当不等式 (D) 成立（取 $s = f(x),\, t = f(y)$ 即得）。
$$ \frac{f(x + \lambda (y - x)) - f(x)}{\lambda} \leq f(y) - f(x). $$令 $\lambda \to 0^+$ ，左边趋于方向导数 $\langle \nabla f(x), y - x \rangle$ 。
$$ f(x + tv) \geq f(x) + t \langle \nabla f(x), v \rangle. $$由 Taylor 展开 $f(x + tv) = f(x) + t \langle \nabla f(x), v \rangle + \tfrac{t^2}{2} v^\top \nabla^2 f(x) v + o(t^2)$ ，比较两边可得 $v^\top \nabla^2 f(x) v \geq 0$ 。
$$ g''(\lambda) = (y - x)^\top \nabla^2 f((1 - \lambda) x + \lambda y) (y - x) \geq 0, $$故 $g$ 在 $[0,1]$ 上是凸函数，这正是 (D)。
严格凸性与强凸性#
- 严格凸函数：当 $x \neq y$ 且 $\lambda \in (0,1)$ 时，(D) 中不等式严格成立。
- $\mu$ -强凸函数（$\mu > 0$ ）：函数 $f - \frac{\mu}{2} \|x\|_2^2$ 是凸函数。等价地， $ f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle + \frac{\mu}{2} \|y - x\|_2^2. $ 强凸性之于凸性，正如“一致连续”之于“连续”——它提供了可量化的间隙（quantitative gap），是使优化算法收敛速率具象化的核心条件。本文在第 02 篇文章中深入剖析其含义与作用。
典型例子#
你应能借助二阶条件（或直接验证）确认下列函数的凸性：
| $f(x)$ | 是否凸？ | 理由 |
|---|---|---|
| $\mid x\mid_p$ （$p \geq 1$ ） | 是 | 三角不等式 + 正齐次性。 |
| $\log(1 + e^x)$ （softplus） | 是 | $f''(x) = \dfrac{e^x}{(1 + e^x)^2} > 0$ 。 |
| $-\log \det X$ （定义在 $\mathbf{S}^n_{++}$ 上） | 是 | Hessian 为 $X^{-1} \otimes X^{-1}$ ，半正定。 |
| $x \log x$ （定义在 $\mathbb{R}_+$ 上） | 是 | $f''(x) = 1/x > 0$ 。 |
| $x^4$ | 严格凸 | $f''(x) = 12 x^2 \geq 0$ ，仅在 $x = 0$ 处为零（非强凸）。 |
| $\frac{1}{2} x^\top Q x$ （$Q \succ 0$ ） | $\lambda_{\min}(Q)$ -强凸 | $\nabla^2 f = Q$ 。 |
保持凸性的运算#
| 运算 | 是否保持凸性？ |
|---|---|
| 非负加权和 | 是（$\sum_i w_i f_i$ ，其中 $w_i \geq 0$ ）。 |
| 逐点上确界 | $\sup_{i \in I} f_i$ 是凸函数（其上镜图是各 $f_i$ 上镜图的交集）。 |
| 与仿射映射复合 | $g(x) = f(Ax + b)$ 继承凸性。 |
| 复合函数 $g(x) = h(f(x))$ | 若 $h$ 凸且非减、$f$ 凸，则 $g$ 凸。 |
| 射影变换（Perspective）$g(x, t) = t f(x/t)$ （$t > 0$ ） | 是。 |
| 偏最小化 $g(x) = \inf_y f(x, y)$ | 若 $f$ 关于 $(x,y)$ 联合凸，则 $g$ 凸。 |
逐点上确界法则堪称“秘密武器”：它解释了为何支撑函数 $\sigma_C(y) = \sup_{x \in C} \langle y, x \rangle$ 对任意集合 $C$ 恒为凸函数，也说明了凸函数的最大值仍是凸函数。
共轭函数#
$$ f^*(y) = \sup_{x \in \mathbb{R}^n} \big[ \langle y, x \rangle - f(x) \big]. $$无论 $f$ 是否凸，其共轭 $f^*$ 恒为凸函数——因为它是关于 $y$ 的一族仿射函数的逐点上确界。
几何解释#
对固定斜率 $y$ ，$f^*(y)$ 表示 $\langle y, x \rangle - f(x)$ 关于 $x$ 能取到的最大值。等价地，仿射函数 $x \mapsto \langle y, x \rangle - f^*(y)$ 是斜率为 $y$ 、且位于 $f$ 下方的最高仿射下界（affine minorant）。因此，$f^*$ 刻画了：对每个可能的斜率 $y$ ，对应的支持超平面（supporting hyperplane）距离函数图像下方有多远。
Fenchel–Young 不等式#
$$ f(x) + f^*(y) \geq \langle x, y \rangle. \tag{FY} $$等号成立当且仅当 $y \in \partial f(x)$ （该次梯度概念将在后文引入）。这是凸分析中 AM-GM 不等式与 Young 不等式的统一推广；例如取 $f(x) = \frac{1}{p} |x|^p$ （其中 $p > 1$ ），计算其共轭可精确导出经典 Young 不等式 $\frac{|x|^p}{p} + \frac{|y|^q}{q} \geq xy$ ，其中 $\frac{1}{p} + \frac{1}{q} = 1$ 。
常见共轭函数示例#
请熟记以下结果——它们将作为后续各讲中的基本构件反复使用。
| $f(x)$ | $f^*(y)$ |
|---|---|
| $\frac{1}{2} \mid x\mid_2^2$ | $\frac{1}{2} \mid y\mid_2^2$ （自共轭）。 |
| $\frac{1}{2} x^\top Q x$ , $Q \succ 0$ | $\frac{1}{2} y^\top Q^{-1} y$ 。 |
| 指示函数 $\iota_C$ | 支撑函数 $\sigma_C(y) = \sup_{x \in C} \langle y, x \rangle$ 。 |
| $\mid x\mid$ （任一范数） | $\iota_{B^\circ}(y) = \begin{cases} 0 & \mid y\mid_* \leq 1 \\ +\infty & \text{否则} \end{cases}$ ，其中 $\mid\cdot\mid_*$ 为对偶范数。 |
| $e^x$ | $y \log y - y$ （定义域 $y > 0$ ，具熵型结构）。 |
| $\log(1 + e^x)$ | $y \log y + (1 - y) \log(1 - y)$ （定义域 $y \in [0, 1]$ ）。 |
| $-\log x$ （定义在 $x > 0$ 上） | $-1 - \log(-y)$ （定义在 $y < 0$ 上）。 |
范数与其对偶单位球指示函数构成的共轭对，完整解释了我们在第 06 篇文章中展开的 LASSO 对偶性理论。
双共轭及“凸性”即对 $(f^*)^*$ 封闭#
双共轭函数 $f^{**} = (f^*)^*$ 恒满足逐点不等式 $f^{**} \leq f$ 。当且仅当 $f$ 是凸函数且下半连续时，二者相等，即 $f^{**} = f$ 。因此，“取共轭两次”这一运算，恰好给出 $f$ 下方的最小凸闭函数——即 $f$ 的凸包络（convex envelope）。正因如此，人们有时将凸松弛（convex relaxation）直接写作 $f^{**}$ 。
次梯度#
次微分#
$$ \partial f(x) = \{g \in \mathbb{R}^n : f(y) \geq f(x) + \langle g, y - x \rangle \text{ 对所有 } y\}. $$属于 $\partial f(x)$ 的向量 $g$ 称为 $f$ 在 $x$ 处的一个次梯度。与条件 (F1) 对比：当 $f$ 可微时，$\partial f(x) = \{\nabla f(x)\}$ ，即为单点集。
$$ x^\star \in \arg\min f \iff 0 \in \partial f(x^\star). $$存在性与基本微分法则#
定理．若 $f$ 是凸函数，且 $x \in \mathrm{relint}(\mathrm{dom}(f))$ ，则 $\partial f(x)$ 非空。
该结论源于凸集 $\mathrm{epi}(f)$ 在点 $(x, f(x))$ 处存在支撑超平面（支撑超平面定理）。当 $x$ 位于定义域边界时，$\partial f(x)$ 可能为空集——例如，$f(x) = -\sqrt{x}$ 定义在 $[0, \infty)$ 上，则 $\partial f(0) = \emptyset$ 。
以下微分运算法则构成了近端方法（proximal methods）的基石：
| 法则 | 表述 |
|---|---|
| 和法则 | 若 $\mathrm{relint}\,\mathrm{dom}\,f \cap \mathrm{relint}\,\mathrm{dom}\,g \neq \emptyset$ ，则 $\partial(f + g)(x) = \partial f(x) + \partial g(x)$ 。 |
| 仿射复合 | 若 $\mathrm{relint}\,\mathrm{dom}\,f \cap \mathrm{range}(A) \neq \emptyset$ ，则 $\partial(f \circ A)(x) = A^\top \partial f(Ax)$ 。 |
| 逐点最大值 | $\partial \max_i f_i(x) = \mathrm{conv} \bigcup_{i \in I(x)} \partial f_i(x)$ ，其中 $I(x) = \{i : f_i(x) = \max_j f_j(x)\}$ 。 |
| 共轭等价性 | $g \in \partial f(x) \iff x \in \partial f^*(g) \iff f(x) + f^*(g) = \langle x, g \rangle$ 。 |
具体示例#
$$ \partial f(x) = \begin{cases} \{1\} & x > 0 \\ \{-1\} & x < 0 \\ [-1, 1] & x = 0. \end{cases} $$在 $x = 0$ 处，任意斜率介于 $-1$ 与 $1$ 之间的直线均为 $|x|$ 的支撑线，且整体位于其下方。
例 2：$f(x) = \|x\|_1$ 在 $\mathbb{R}^n$ 上。
$$ g_i = \begin{cases} \mathrm{sign}(x_i) & x_i \neq 0 \\ \in [-1, 1] & x_i = 0. \end{cases} $$这正是 ISTA 算法利用以生成稀疏解的结构。
$$ \partial \|\cdot\|_2(x) = \begin{cases} \{x / \|x\|_2\} & x \neq 0 \\ \{g : \|g\|_2 \leq 1\} & x = 0. \end{cases} $$ $$ \partial f(x) = \begin{cases} \{0\} & x > 1 \\ \{-1\} & x < 1 \\ [-1, 0] & x = 1. \end{cases} $$点 $x = 1$ 是“拐点”（kink）——在此间隔边界上，损失函数可被赋予任意斜率 $[-1, 0]$ 中的值，这正是支撑 SVM 对偶理论成立的关键。
最优性：从 $\nabla f = 0$ 到 $0 \in \partial f$ #
$$ x^\star \in \arg\min f \iff 0 \in \partial f(x^\star). $$正向推导直接由次梯度定义 (D) 应用于 $y = x^\star$ 与任意 $x$ 得到；反向推导中，$0 \in \partial f(x^\star)$ 意味着对所有 $y$ 均有 $f(y) \geq f(x^\star)$ 。
$$ 0 \in \partial f(x^\star) + N_C(x^\star), $$其中 $N_C(x^\star) = \{g : \langle g, y - x^\star \rangle \leq 0 \ \forall y \in C\}$ 称为集合 $C$ 在 $x^\star$ 处的法锥（normal cone）。本文在第 08 篇文章中结合 KKT 条件再次深入讨论此式。
综合应用：一个完整求解示例#
$$ \min_x F(x) := \tfrac{1}{2} \|Ax - b\|_2^2 + \lambda \|x\|_1, $$其中 $A \in \mathbb{R}^{m \times n}$ ，$b \in \mathbb{R}^m$ ，$\lambda > 0$ 。
$$ 0 \in A^\top (Ax^\star - b) + \lambda \, \partial \|\cdot\|_1(x^\star). $$ $$ r_i = -\lambda \, \mathrm{sign}(x^\star_i) \quad \text{若 } x^\star_i \neq 0, \qquad r_i \in [-\lambda, \lambda] \quad \text{若 } x^\star_i = 0. $$这正是著名的 LASSO 的 KKT 条件——它表明：对任意坐标 $i$ ，只要 $|r_i| < \lambda$ ，就必有 $x^\star_i = 0$ 。这正是 $\ell_1$ 正则化诱导稀疏性的根本原因。我们在第 06 篇文章中将通过软阈值算子的不动点重新推导该条件。
故事的后续发展#
- 第 02 篇文章在上述基础上引入光滑性与强凸性，并在三种不同设定下证明梯度下降法（GD）的收敛性。
- 第 06 篇文章利用次梯度与共轭函数，系统推导 ISTA、FISTA 与 ADMM 等经典算法。
- 第 08 篇文章将最优性条件 $0 \in \partial f$ 推广至带约束的问题，导出完整的 KKT 系统。
总结#
| 概念 | 它赋予你的能力 |
|---|---|
| 凸集 | 清晰地讨论可行性与投影问题。 |
| 凸函数 | 快速验证凸性：任选四种等价刻画之一即可。 |
| 共轭函数 $f^*$ | 在原始空间与对偶空间之间自由切换；导出 Young 型不等式；构建对偶问题。 |
| 次梯度 | 当 $f$ 不可微时替代 $\nabla f$ ；将最优性条件简洁表述为 $0 \in \partial f$ 。 |
| 法锥（Normal cone） | 在约束定义域上表述最优性；架起通向 KKT 条件的桥梁。 |
下一篇文章将在此基础上引入两个关键假设——Lipschitz 光滑性与强凸性——从而为梯度下降法提供定量的收敛速率保证。
参考文献#
- Boyd & Vandenberghe，《Convex Optimization》，第 2–3 章——关于凸集与凸函数的标准权威参考。
- Rockafellar，《Convex Analysis》——更深入的专著；所有关于次梯度与共轭函数的理论根基尽在于此。
- Bertsekas，《Convex Optimization Theory》，第 1 章——简明扼要、自成体系。
- Nesterov，《Lectures on Convex Optimization》，第 1 章——聚焦现代优化算法视角。