优化 I · 凸分析基础

优化理论的第一课不是算法而是几何：什么样的问题天生"好解"？答案常常是凸问题——凸性给出局部最优即全局最优；在适当约束资格（经典凸规划中如 Slater 条件）下才可推出强对偶/零对偶间隙；在步长、光滑性、强凸性或单调性等算法假设满足时，才有相应的收敛保证。凸与非凸是优化世界的"可靠/探险"分界线，深度学习属于后者，但它的一切算法语言仍是在凸世界里锻造的。

0. 读定理前，先给四个词具体含义

本页在有限维空间 \(\mathbb R^n\) 中讨论。允许 \(f(x)=+\infty\) 表示“这个点不允许”，但不允许 \(-\infty\)。

• 有效域 \(\operatorname{dom}f=\{x:f(x)<+\infty\}\)；proper（真函数）意味着这个域非空，即至少有一个有限值。
• 上图集 \(\operatorname{epi}f=\{(x,t):t\ge f(x)\}\)，是在函数图像上方的全部点。\(f\) 凸等价于它的上图集凸；这把“函数的弦”变成“集合里的线段”。
• 下半连续：\(f(x)\le\liminf_{y\to x}f(y)\)。函数在极限点不能突然向上跳；上图集是闭集与此等价。凸分析里“闭函数”指这个性质，不是说有效域必须闭。例如 \(-\log x\) 在 \(x>0\) 有限，域外为 \(+\infty\)，有效域开放，但它仍是闭凸函数。
• 相对内部 \(\operatorname{ri}C\)：在集合的仿射包里取内部。一条线段在平面里没有普通内点，在自身所在直线中却有相对内点。次梯度存在性与 Slater 条件经常需要这个区别。

把集合约束写成指标函数 \(\delta_C(x)=0\)（\(x\in C\)）与 \(+\infty\)（域外），便可将 \(\min_{x\in C}f(x)\) 写成无约束的 \(\min_x[f(x)+\delta_C(x)]\)。\(\delta_C\) 凸当且仅当 \(C\) 凸；\(C\) 闭时它下半连续。

1. 凸集

定义 \(C\) 凸 \(\iff \forall x, y \in C,\ \lambda \in [0,1]:\ \lambda x + (1-\lambda)y \in C\)（任两点连线段不出集合）。

基本例子：超平面 \(\{a^\top x = b\}\) 与半空间 \(\{a^\top x \leq b\}\)；球；多面体（有限个半空间之交——线性规划的可行域，优化 IV）；半正定矩阵锥（高代 VI 的半正定判据给出的集合）。

保凸运算：任意多个凸集的交仍凸（并一般不凸）；仿射映射的像与原像。

分离与支撑，要问有没有正间隔。 对两个非空、不相交的凸集 \(C,D\subset\mathbb R^n\)，弱分离给出非零 \(a\) 和实数 \(b\)，使

这不保证两侧留有正间隔。例如 \(C=(-\infty,0)\)、\(D=(0,\infty)\) 虽不相交，但距离为零。若进一步一集紧、另一集闭，仍不相交，则可得到正间隔的强分离。SVM 的正间隔不能仅由“不相交”三个字推出。

对非空凸集 \(C\) 的边界点 \(x_0\)，有限维支撑定理给出某个 \(a\ne0\)，使 \(\langle a,x-x_0\rangle\le0\) 对所有 \(x\in C\) 成立。即使 \(x_0\) 不属于 \(C\)，这条边界支撑关系仍有意义；而上图集的支撑面可能竖直，不能据此保证每个边界点都有有限次梯度。

2. 凸函数

定义 \(f\) 凸 \(\iff\) 定义域凸且 \(f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)\)（弦在图像上方）。严格凸：对不同的有限域点 \(x\ne y\)、\(0<\lambda<1\)，不等号严格；\(\mu\)-强凸（\(\mu>0\)）：\(f - \frac{\mu}{2}\|x\|^2\) 仍凸（碗至少弯到二次程度——收敛速率的关键参数，优化 II）。

三级判据：以下一、二阶等价判据放在开凸域上讨论，可微性逐级增强；若有效域在低维仿射空间中，应改用相对坐标。

一阶条件是三者中最常被引用的：它说凸函数的局部线性信息（梯度）携带全局下界——这就是为什么梯度方法在凸世界有全局保证。

常见凸函数清单：仿射（唯一既凸又凹）、\(e^{ax}\)、\(-\ln x\)、范数、\(\max(x_1,\dots,x_n)\)、log-sum-exp \(\ln\sum e^{x_i}\)（softmax 的势函数；对 logits 的凸性不能直接推到网络参数）、二次型 \(x^\top A x\)（对称 \(A\succeq0\) 时；一般 \(A\) 只由对称部分决定）。

保凸运算：非负加权和；与仿射复合 \(f(Ax + b)\)；逐点上确界 \(\sup_\alpha f_\alpha(x)\)（凸函数族的包络仍凸——对偶函数凹性的来源，优化 III）；复合规则（外凸内仿射，或外凸不减内凸）。

Jensen 不等式：例如 \(f\) 为 proper、下半连续凸函数，\(X\) 可积且 \(f(X)\) 绝对可积时，\(f(EX)\le E[f(X)]\)。有限加权平均的版本直接反复使用凸性定义；期望版还要确保各项有意义，不能在不存在的期望上套公式。

严格凸不等于强凸。 \(x^4\) 在 \(\mathbb R\) 上严格凸，但 \(f''(0)=0\)，不存在全局正的强凸常数；它也说明 Hessian 处处正定是严格凸的充分条件，非必要条件。强凸保证的是统一的二次下界，不只是“图像没有直线段”。

log-sum-exp 的凸性可直接验算。 设 \(p_i=e^{z_i}/\sum_j e^{z_j}\)，其 Hessian 为 \(\operatorname{diag}(p)-pp^\top\)。任意向量 \(v\) 都满足

右边是加权方差。沿全一向量曲率为零，因此它在整个 logits 空间也不是强凸函数。交叉熵 \(\log\sum_i e^{z_i}-z_k\) 对 \(z\) 凸；若 \(z\) 是参数的非线性函数，复合规则未必保凸。

3. 凸优化问题

定义 \(\min f(x)\) s.t. \(g_i(x) \leq 0,\ Ax = b\)，其中 \(f, g_i\) 凸。这是标准凸规划的一种保证凸性的表示形式：等式约束写成仿射。不能反推“任何非仿射等式的可行域都不凸”；例如 \(x^2=0\) 的可行集就是凸集 \(\{0\}\)。

定理（局部即全局） 凸问题的任何局部极小点都是全局极小点。 证明（三行，值得记住）：设 \(x^*\) 局部极小而 \(y\) 更优（\(f(y) < f(x^*)\)）。沿线段 \(z_\lambda = (1-\lambda)x^* + \lambda y\)，凸性给 \(f(z_\lambda) \leq (1-\lambda)f(x^*) + \lambda f(y) < f(x^*)\) 对一切 \(\lambda \in (0,1]\) 成立——\(x^*\) 的任意小邻域内都有更优点，与局部极小矛盾。\(\blacksquare\)

（在无约束、可微凸问题且 \(x^*\) 位于适当定义域内点时，\(\nabla f(x^*) = 0 \iff\) \(x^*\) 是全局最优；有约束问题要改用 KKT/法锥条件，边界点也不能直接套这句。）

最优点是否存在，要另查。 严格凸只保证最优点至多一个，不能保证存在；\(e^x\) 的下确界为零，却在 \(\mathbb R\) 上从不取到。甚至 \(x^2\) 限制在 \((0,\infty)\) 上仍强凸，但也没有最小点。一个实用的充分条件是：proper、下半连续目标存在非空紧的次水平集 \(\{x:f(x)\le\alpha\}\)；此时可用紧性取得最小值，再用严格凸性取得唯一性。闭的可行域、无穷远的增长控制与凸性，各管一件事。

4. 次梯度：不可微时怎么办

凸函数可以有折点（\(|x|\)、hinge 损失、标量 ReLU）。次梯度 \(g\) 定义为满足一阶条件的向量：

全体次梯度构成次微分 \(\partial f(x)\)（它总是凸集；对有限维 proper 凸函数，在 \(\operatorname{ri}(\operatorname{dom}f)\) 非空，但定义域边界可能为空；可微内点处退化为 \(\{\nabla f\}\)）。例：\(f = |x|\) 在 0 处 \(\partial f(0) = [-1, 1]\)。无约束全局最优性恰为 \(0\in\partial f(x^*)\)。对闭凸约束 \(C\)，若 \(f\) 在其邻域可微凸，可以改写成

例如在 \([0,\infty)\) 上最小化 \(f(x)=x\)，最优点 \(x^*=0\) 的梯度是 \(1\)，但法锥 \(N_C(0)=(-\infty,0]\) 含有 \(-1\)，恰好抵消。若目标也不可微，直接使用 \(\partial(f+\delta_C)\) 最稳妥；把它拆成 \(\partial f+N_C\) 还需要相应求和资格条件。

定义域边界无次梯度的例子是 \(f(x)=-\sqrt{x}\)（\(x\ge0\)），域外 \(+\infty\)。在零点若有有限次梯度 \(g\)，就应有 \(-\sqrt y\ge gy\) 对每个 \(y>0\) 成立，即 \(g\le-1/\sqrt y\)；令 \(y\downarrow0\) 不可能。这是闭凸函数，缺少的是该点的相对内点条件。

🔗 AI 衔接：hinge 损失（ai 课 02 讲 SVM）、L1 正则的稀疏性可用一维模型精确说明：最小化 \(\frac12(x-a)^2+\tau|x|\)（\(\tau\ge0\)），条件为 \(0\in x-a+\tau\partial|x|\)，从而 \(x^*=\operatorname{sign}(a)\max(|a|-\tau,0)\)。当 \(|a|\le\tau\) 时，一个参数区间都映到同一个零解；目标仍严格凸，最优解是唯一的，并非“有一段最优解”。ReLU 网络整体通常是非凸的；在标量 ReLU 的折点 0，框架可以选取约定导数（例如 relu'(0)=0），也可以把这个值看作从广义梯度/次微分 \([0,1]\) 中选取的一个代表，不能把整个非凸网络的 autodiff 值统称为凸次梯度。

5. Fenchel 共轭与支撑线

设 \(f:\mathbb R^n\to(-\infty,+\infty]\) 是 proper、下半连续、凸函数。它的 Fenchel 共轭定义为

固定 \(s\)，若仿射函数 \(\ell(x)=\langle s,x\rangle-b\) 要满足 \(\ell(x)\le f(x)\) 对所有 \(x\) 成立，则必须有

因此 \(\ell_s(x)=\langle s,x\rangle-f^*(s)\) 是该斜率下最高的全局仿射下界；若 \(f^*(s)=+\infty\)，说明这个斜率根本没有有限的全局下界截距。

直接由上确界定义就得到 Fenchel–Young 不等式（这一不等式本身不要求凸性或闭性）

在上述闭凸条件下，等号链是

对 \(x\in\operatorname{dom}f\)，第一步来自“直线正好接触”，这一步无需闭性：\(s\in\partial f(x)\) 意味着 \(f(y)\ge f(x)+\langle s,y-x\rangle\)，对 \(y\) 取上确界即得等号；反向等号又把这条全局下界还原出来。将 \(x\in\partial f^*(s)\) 反推回原函数的等号，需要 \(f=f^{**}\)（由 proper、下半连续、凸性保证），这正是不能省略闭性假设的地方。

三个一维预设的共轭账本是：

不闭时会发生什么？ 取 \(f=\delta_{(0,\infty)}\)。它 proper 且凸，但在零点不下半连续。其共轭为 \(f^*=\delta_{(-\infty,0]}\)，再取共轭得到 \(f^{**}=\delta_{[0,\infty)}\)。闭包补入了零点：\(0\in\partial f^*(-1)\)，却没有 \(-1\in\partial f(0)\)，因为 \(f(0)=+\infty\)，零点根本不在原有效域中。这是不能省略闭性的具体反例。

6. 典型例题

例 1（二阶判据） 判断 \(f(x, y) = x^2 + xy + y^2 - \ln(xy)\) 在 \(x, y > 0\) 上的凸性。 解：Hessian \(= \begin{pmatrix} 2 + \frac{1}{x^2} & 1 \\ 1 & 2 + \frac{1}{y^2} \end{pmatrix}\)，顺序主子式 \(> 0\)（对角 \(> 2\)、行列式 \(> 4 - 1 > 0\)）——正定，故（严格）凸。

例 2（逐点上确界） 证明矩阵最大特征值 \(\lambda_{\max}(A)\) 是对称矩阵空间上的凸函数。 解：Rayleigh 商表示 \(\lambda_{\max}(A) = \sup_{\|v\|=1} v^\top A v\)——对每个固定 \(v\)，\(A \mapsto v^\top A v\) 是线性（凸）函数，逐点 sup 保凸。\(\blacksquare\)（一行用掉两个工具；这类"变分表示 + 保凸运算"是凸性证明的高级套路。）

例 3（一阶条件应用） \(f\) 在开凸域上可微且凸，\(x^*\) 是该域内点。证明 \(\nabla f(x^*) = 0 \Rightarrow x^*\) 全局最优。 解：一阶条件 \(f(y) \geq f(x^*) + \nabla f(x^*)^\top(y - x^*) = f(x^*)\) 对一切域内 \(y\)。完。——无约束凸世界里"梯度为零"就是终点线；若有约束或 \(x^*\) 在边界，必须改用相应的可行方向/KKT 条件。

7. 迁移练习

8. 阅读与后续连接

• Boyd 与 Vandenberghe《Convex Optimization》作者页：凸集、凸函数、优化问题的标准形式与对偶理论。
• MIT 课程：凸集、分离与支撑：弱分离与更强分离条件。

下一步分别进入无约束优化算法、对偶与 KKT、线性规划与动态规划。先辨认域、闭性和曲率，再选择算法或最优性条件。