第一章：基础理论

1.1.1 有约束与无约束#

最直观的划分是按有无约束分类：

• 有约束优化：$\Omega$ 包含等式或不等式约束；
• 无约束优化：$\Omega = \mathbb{R}^n$，不对 $x$ 施加任何限制。

无约束问题更易求解，因此将有约束问题转化为无约束问题是一个基本策略。一个关键工具是指示函数（indicator function）：

指示函数的值只有两种可能：要么为零，要么为正无穷。它的作用是用”无穷大惩罚”来编码约束：当 $x$ 落在可行域内时，$\iota_\Omega(x) = 0$，不影响目标函数；当 $x$ 越界时，$\iota_\Omega(x) = +\infty$，使目标值趋于正无穷，自然被最小化过程排除。利用指示函数，约束优化问题等价转化为：

这个等价变换看似简单，却有深远的理论意义。指示函数将在 1.4 节的零包含形式中再次出现——它的次微分恰好给出法锥的概念，从而将约束信息编码进算子语言。指示函数本身不可微（在边界处有跳跃），但它是凸函数（当 $\Omega$ 为凸集时），因此可以在非光滑凸优化的框架下处理。

1.1.2 广义实值函数与适当函数#

指示函数的值域包含 $+\infty$，这提示我们需要在更广的框架下讨论函数。定义广义实数空间 $\bar{\mathbb{R}} = \mathbb{R} \cup \{-\infty, +\infty\}$，从 $\mathbb{R}^n$ 到 $\bar{\mathbb{R}}$ 的映射称为广义实值函数。

并非所有广义实值函数都适合做优化：若函数恒取 $+\infty$ 则无法求最小值，若在某点取 $-\infty$ 则最小值不存在。适当函数（proper function）排除了这两种病态情形：

设 $f: \mathbb{R}^n \to \bar{\mathbb{R}}$，$\mathcal{X}$ 为非空集合。若 $\exists\, x \in \mathcal{X}$ 使得 $f(x) < +\infty$，且 $\forall\, x \in \mathcal{X}$ 均有 $f(x) > -\infty$，则称 $f$ 关于 $\mathcal{X}$ 是适当的。

第一个条件保证函数在某处有有限值（有地方可以”站”），第二个条件排除负无穷（最小值不会掉到无底洞里）。函数的有效定义域为 $\text{dom}\,f := \{x \in \mathbb{R}^n \mid f(x) < +\infty\}$，即去掉函数值为 $+\infty$ 的那些点后的定义域。后续讨论中，除非特别说明，所有函数均假定满足适当性条件。

1.1.3 优化问题的分类体系#

优化问题的分类维度很多，以下是最常用的几种，它们从不同角度刻画问题的结构和求解难度。

按变量类型：

• 连续优化：决策变量取连续值，可行域是 $\mathbb{R}^n$ 的连续子集。
• 离散优化：决策变量取离散值，如 0-1 规划、整数规划。
• 混合优化：既有连续变量又有离散变量。

连续优化中，目标函数和约束函数的连续性使得我们可以从一个点的局部信息（梯度、Hessian）来推断邻域的行为，从而指导搜索方向。离散优化不具备这种性质，通常比连续优化更难求解。本书主要讨论连续优化问题。

按目标函数与约束的线性性：

• 线性规划（Linear Programming）：目标函数和所有约束条件均为线性的。模型简单，求解成熟（如单纯形法、内点法）。
• 非线性规划：目标函数或约束中至少有一个是非线性的。其中二次规划（Quadratic Programming, QP）是重要的特例——目标函数为二次型 $\frac{1}{2}x^\top A x + b^\top x$，约束条件为线性，SVM 的对偶问题就是一个典型的二次规划。

按光滑性：

• 光滑优化：目标函数和约束条件都连续可导（通常要求至少一阶连续可微）。
• 非光滑优化：至少有一个不可导。$\ell_1$ 正则化中的绝对值函数、ReLU 激活函数在原点处不可导，都属于非光滑问题。非光滑问题的梯度不存在，需要次梯度等替代工具，第五章将详细讨论。

按凸性（最核心的分类）：

• 凸优化：目标函数 $f$ 是凸函数，且可行域 $\Omega$ 是凸集。
• 非凸优化：上述两个条件至少有一个不满足。

凸优化的核心性质是局部最优点就是全局最优点（定理的严格陈述见 1.3 节）。这意味着只要找到任何一个局部最优解，就已经是全局最优的——不必担心陷在某个局部最小值里。深度学习中的训练问题几乎都是非凸的，局部最优不保证全局最优，但实践中发现局部最优往往已经足够好。对非凸问题的收敛性分析，一个常用的理论工具是 KL 条件（Kurdyka-Lojasiewicz condition），它为一大类非凸问题提供了收敛性保证。

凸性是上述分类中最关键的结构性概念。下面系统建立凸集与凸函数的理论。

1.2.1 凸集#

1.2.2 凸函数的定义#

设 $f$ 为适当函数且 $\text{dom}\,f$ 为凸集。若对任意 $x, y \in \text{dom}\,f$ 和 $\theta \in [0, 1]$：

则称 $f$ 为凸函数。这个不等式的几何含义是：函数图像上任意两点的连线段（即 $f$ 在这两点的线性插值）总位于曲线的上方。函数”弓起来”，而不是”塌下去”。

用定义判定凸性在低维时可行，但对高维函数往往难以操作——需要验证所有可能的 $x, y$ 和 $\theta$。以下定理将凸性判定降维为一维问题，极大地简化了验证过程。

定理（限制在直线上）. $f$ 是凸函数，当且仅当对任意 $x \in \text{dom}\,f$ 和任意方向 $v \in \mathbb{R}^n$，一元函数 $g(t) = f(x + tv)$（定义在 $\{t \mid x + tv \in \text{dom}\,f\}$ 上）是凸函数。

几何上，$x + tv$ 表示过点 $x$、沿方向 $v$ 的直线。定理说的是：$f$ 在整个定义域上是凸的，等价于 $f$ 限制在任意一条直线上都是凸的。高维的凸性判定因此被归结为一族一维凸性判定。

证明. 必要性：取 $t_1, t_2 \in \text{dom}\,g$，由 $x + t_1 v, x + t_2 v \in \text{dom}\,f$ 且 $\text{dom}\,f$ 凸，其凸组合 $x + (\theta t_1 + (1-\theta)t_2)v \in \text{dom}\,f$，故 $\text{dom}\,g$ 是凸集。凸函数不等式直接由 $f$ 的凸性得到：$g(\theta t_1 + (1-\theta)t_2) = f(\theta(x+t_1 v) + (1-\theta)(x+t_2 v)) \leq \theta f(x+t_1 v) + (1-\theta)f(x+t_2 v) = \theta g(t_1) + (1-\theta)g(t_2)$。

充分性：令 $t_1 = 0$，$t_2 = 1$，$v = y - x$，则 $g(t) = f(x + t(y-x))$。由 $g$ 的凸性得 $g(1-\theta) \leq \theta g(0) + (1-\theta)g(1) = \theta f(x) + (1-\theta)f(y)$，而 $g(1-\theta) = f(\theta x + (1-\theta)y)$，即得凸函数定义。$\square$

常见凸函数的判定实例。 以下函数的凸性可以通过限制到直线上来验证，也可以直接计算 Hessian（见 1.2.3 节的二阶条件）。对其中两个给出完整验证过程，以示方法。

• $f(x) = \|x\|_p$（$p \geq 1$）：所有 $p \geq 1$ 的范数都是凸函数。特别地，$\ell_1$ 范数 $\|x\|_1 = \sum_i |x_i|$ 和 $\ell_2$ 范数 $\|x\|_2$ 均凸。

  $\ell_1$ 范数的凸性验证。 每个分量函数 $|x_i|$ 是凸函数（由三角不等式 $|\theta a + (1-\theta)b| \leq \theta|a| + (1-\theta)|b|$ 直接验证），而凸函数的非负线性组合仍是凸函数（系数全为 1），因此 $\|x\|_1 = \sum_i |x_i|$ 是凸函数。也可以从三角不等式的角度理解：$\|\theta x + (1-\theta)y\|_1 = \sum_i |\theta x_i + (1-\theta)y_i| \leq \sum_i [\theta|x_i| + (1-\theta)|y_i|] = \theta\|x\|_1 + (1-\theta)\|y\|_1$，恰好是凸函数的定义。

• $f(x) = \max(x_1, \ldots, x_n)$：逐点最大值函数是凸的。对任意一条直线 $g(t) = \max_i (a_i + b_i t)$，是分段线性函数，因此凸。

• $f(X) = -\log\det X$（$X \succ 0$）：定义在正定矩阵集上，是严格凸函数。该函数作为 log-det 正则项出现在稀疏逆协方差估计（graphical lasso）中。

• $f(x) = e^{a^\top x}$：仿射函数的指数，限制到任意直线上是 $e^{ct+d}$（指数函数），凸。

• $f(x) = \log(\sum_i e^{x_i})$（log-sum-exp）：这是 softmax 的”前身”，是凸函数，且是 $\max$ 函数的光滑近似。

  log-sum-exp 的凸性验证。 通过验证 Hessian 半正定来证明。记 $p_i = e^{x_i}/\sum_j e^{x_j}$（即 softmax 输出，满足 $p_i > 0$ 且 $\sum_i p_i = 1$），则梯度为 $[\nabla f(x)]_i = p_i$，Hessian 为 $\nabla^2 f(x) = \text{diag}(p) - pp^\top$。对任意向量 $v$，

右端恰好是随机变量 $V$（取值 $v_i$，概率 $p_i$）的方差 $\text{Var}(V) = \mathbb{E}[V^2] - (\mathbb{E}[V])^2$，由方差的非负性（或 Cauchy-Schwarz 不等式 $(\sum_i p_i v_i)^2 \leq \sum_i p_i \cdot \sum_i p_i v_i^2 = \sum_i p_i v_i^2$）知 $v^\top \nabla^2 f(x)\,v \geq 0$。因此 Hessian 处处半正定，$f$ 是凸函数。

1.2.3 凸函数的三个等价条件#

对可微凸函数 $f: \mathbb{R}^n \to \mathbb{R}$，以下三个条件两两等价，分别用零阶、一阶和二阶信息来刻画凸性。

一阶条件（最常用）：

右端 $f(x) + \nabla f(x)^\top(y - x)$ 是 $f$ 在 $x$ 处的一阶 Taylor 近似，几何上对应过点 $(x, f(x))$ 的切超平面。一阶条件说的是：凸函数在任意一点的切超平面总位于函数图像的下方，切平面从下方”支撑”整个函数。这意味着一阶 Taylor 展开始终是凸函数的全局下估计——这个性质在后续章节中被反复利用，例如梯度下降法每一步实际上就是在最小化一个切平面加二次惩罚项的组合。

梯度单调性：

即 $\nabla f$ 是单调映射：沿任意方向移动时，梯度在该方向上的分量不会减小。直观地说，凸函数越往右走坡越陡（或至少不变），不会出现”先上坡再下坡再上坡”的振荡行为。

二阶条件：

即 Hessian 矩阵处处半正定。Hessian 的特征值反映了函数在各方向上的曲率，半正定意味着所有方向的曲率都非负——函数在任何方向上都不会”向下弯”。

证明概要.

一阶条件的充分性：令 $z = \theta x + (1-\theta)y$，对 $x$ 和 $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$ 后相加，右端 $\nabla f(z)^\top$ 的系数恰好为零（$\theta(x-z) + (1-\theta)(y-z) = 0$），得 $\theta f(x) + (1-\theta)f(y) \geq f(z)$。构造之所以奏效，是因为 $z$ 恰好是 $x$ 和 $y$ 的凸组合，使得梯度项在加权平均后消去。

一阶条件的必要性：由凸性得 $f(x + t(y-x)) \leq f(x) + t(f(y) - f(x))$，移项除以 $t$ 后令 $t \to 0^+$，利用极限的保号性和方向导数定义，得 $f(y) - f(x) \geq \nabla f(x)^\top(y-x)$。

梯度单调性：由一阶条件对 $(x, y)$ 和 $(y, x)$ 分别写出不等式后相加即得。充分性的证明如下。令 $g(t) = f(x + t(y-x))$，则 $g'(t) = \nabla f(x + t(y-x))^\top(y-x)$。由梯度单调性可知 $g'(t)$ 关于 $t$ 单调不减：对 $0 \leq s \leq t \leq 1$，取 $u = x + s(y-x)$，$w = x + t(y-x)$，则 $w - u = (t-s)(y-x)$，梯度单调性给出

因此 $g'(t) \geq g'(0)$ 对所有 $t \in [0, 1]$ 成立。由 Newton-Leibniz 公式：

这就还原了一阶条件。

二阶条件：必要性用反证法——若 $\nabla^2 f(x^*)$ 存在负特征值 $\lambda$ 对应特征向量 $d$，则 Taylor 展开在 $t$ 充分小时给出 $f(x^* + td) < f(x^*)$，与一阶条件矛盾。充分性由 Taylor 展开加 Hessian 半正定得到非负余项，从而推出一阶条件。$\square$

优化中常用的三种 Taylor 展开形式： (1) Hessian 余项形式：$f(x + p) = f(x) + \nabla f(x)^\top p + \frac{1}{2}p^\top \nabla^2 f(x + tp)\,p$，$t \in (0, 1)$；(2) 一阶余项形式：$f(x + p) = f(x) + \nabla f(x + tp)^\top p$，$t \in (0, 1)$；(3) 积分形式：$\nabla f(x + p) = \nabla f(x) + \int_0^1 \nabla^2 f(x + tp)\,p\,dt$。这三种形式在后续各章的收敛性证明中反复使用。

1.2.4 凸函数的分类#

凸函数按”凸的程度”可分为四类，从弱到强依次为弱凸、凸、严格凸和强凸。它们的差异主要体现在最优解的唯一性和优化算法的收敛速度上。

凸函数（Convex）. 基本定义如上。一阶条件：$f(y) \geq f(x) + \nabla f(x)^\top(y - x)$。

严格凸函数（Strictly Convex）. 在凸函数定义的基础上将不等号取严格：对任意 $x \neq y \in \text{dom}\,f$，

等价的严格单调性：$(\nabla f(y) - \nabla f(x))^\top(y - x) > 0$，$\forall\, x \neq y$。严格凸函数的切平面严格位于函数下方（除了切点本身），因此如果最优解存在，则必然唯一——否则两个不同的最优解之间的凸组合会给出更小的函数值。

Hessian 正定是严格凸的充分条件，但非必要。反例：$f(x_1, x_2) = x_1^4 + x_2^4$ 是严格凸的，但在原点处 $\nabla^2 f(0) = 0$（零矩阵），不正定。

强凸函数（Strongly Convex）. 强凸性比严格凸性更强，它给出了函数图像与切平面之间间距的定量下界：

其中 $\mu$ 称为强凸参数（或强凸系数）。这个不等式称为二次下界：函数不仅在切平面上方，还至少高出一个开口大小为 $\mu$ 的二次函数。$\mu$ 越大，函数在最小值点附近弯曲得越厉害。

强凸函数有一个等价的定义形式，有时更便于验证：$f$ 是 $\mu$-强凸函数当且仅当 $g(x) = f(x) - \frac{\mu}{2}\|x\|^2$ 是凸函数。直观地说，从 $f$ 中减去一个开口为 $\mu$ 的抛物线之后仍然是凸的，说明 $f$ 本身至少有 $\mu$ 的曲率。

等价性证明. 我们证明一个方向（另一个方向类似）。设 $f$ 是 $\mu$-强凸的，验证 $g(x) = f(x) - \frac{\mu}{2}\|x\|^2$ 满足凸性定义。由凸组合形式的强凸定义（见下方），

另一方面，利用范数平方的凸组合恒等式：

将两式代入 $g$ 的定义：

右端的 $-\frac{\mu}{2}\theta(1-\theta)\|x-y\|^2$ 项恰好与 $+\frac{\mu}{2}\theta(1-\theta)\|x-y\|^2$ 项相消，得到

即 $g$ 是凸函数。$\square$

还有一个直接从凸组合角度出发的等价定义：对任意 $x, y \in \text{dom}\,f$ 和 $\theta \in (0, 1)$，

这个形式在证明最优解唯一性时特别方便。

等价的强单调性：$(\nabla f(y) - \nabla f(x))^\top(y - x) \geq \mu\|y - x\|^2$。二阶条件：$\nabla^2 f(x) \succeq \mu I \succ 0$。

强凸函数的重要性质可以概括为两点。

第一，最优解唯一。

命题. 若 $f$ 是 $\mu$-强凸函数且存在最小值，则最小值点唯一。

证明. 反证法。设 $x \neq y$ 都是 $f$ 的最小值点，即 $f(x) = f(y) = f^*$。取 $\theta \in (0, 1)$，由凸组合等价定义：

最后的严格不等号成立是因为 $x \neq y$ 且 $\mu > 0$。但这与 $f^*$ 是最小值矛盾。$\square$

需要注意的是，$f$ 存在最小值是前提。强凸函数的全局最小点不一定存在，例如 $f(x) = x^2$ 定义在开区间 $(1, 2)$ 上，$f$ 是强凸的，但最小值在 $x = 1$ 处取到，而 $x = 1$ 不在定义域内。

第二，强凸函数上的优化算法通常有更快的收敛速度——第三章将证明梯度下降法在强凸问题上达到线性收敛率，而在一般凸问题上只有次线性收敛率（1.5 节将给出具体对比）。在机器学习中，$\ell_2$ 正则化项 $\frac{\lambda}{2}\|w\|^2$ 的一个重要作用就是为目标函数引入强凸性：原始损失函数可能只是凸的，加上 $\ell_2$ 正则化后变成 $\lambda$-强凸的。岭回归（ridge regression）$\min_x \frac{1}{2}\|Ax - b\|^2 + \frac{\lambda}{2}\|x\|^2$ 的目标函数就是强凸的，正则项不仅防止过拟合，还改善了优化问题的条件数。

性质. 凸函数 $+$ 强凸函数 $=$ 强凸函数。更一般地，若 $f$ 是 $\mu$-强凸的，$g$ 是凸的，则 $f + g$ 是 $\mu$-强凸的。

例. $f(x) = \frac{1}{2}x^\top A x + b^\top x$，其中 $A$ 对称正定，最小特征值为 $\lambda_{\min}(A) > 0$。则 $\nabla^2 f(x) = A \succeq \lambda_{\min}(A)\,I$，因此 $f$ 是 $\lambda_{\min}(A)$-强凸的。

弱凸函数（Weakly Convex）. 如果 $f$ 本身可能不凸，但加上足够强的二次项后能变成凸函数：

则称 $f$ 是 $\rho$-弱凸函数。弱凸函数本身不一定是凸的——它只是”偏离凸性”不太远，通过添加二次正则项就能”修复”为凸。非凸损失函数中有不少满足弱凸性，这使得近端梯度法等凸优化算法经过适当修改后仍然可用。

四类凸函数的蕴含关系：强凸 $\Rightarrow$ 严格凸 $\Rightarrow$ 凸。弱凸与前三者不构成蕴含关系——弱凸函数可能根本不是凸函数。在实际使用中，凸函数、严格凸函数和强凸函数最为常用。

1.2.5 $L$-光滑性#

强凸性给出了函数曲率的下界（至少弯曲 $\mu$），与之对偶的概念是 $L$-光滑性，它给出了曲率的上界（至多弯曲 $L$）。两者合在一起为函数提供了一个”曲率范围” $[\mu, L]$，这个范围直接决定了梯度下降法的收敛速度。

定义. 可微函数 $f$ 称为梯度 $L$-Lipschitz 连续的（简称 $L$-光滑的），如果存在 $L > 0$，使得对任意 $x, y \in \text{dom}\,f$：

这个条件控制了梯度变化的剧烈程度：当自变量移动 $\|x - y\|$ 时，梯度的变化不超过 $L\|x - y\|$。$L$ 越大，函数越”颠簸”；$L$ 越小，函数越”平缓”。对于二阶可微的函数，$L$-光滑性等价于 $\nabla^2 f(x) \preceq LI$，即 Hessian 的所有特征值不超过 $L$。

$L$-光滑性的核心推论是二次上界：

引理（二次上界）. 设可微函数 $f$ 的定义域 $\text{dom}\,f = \mathbb{R}^n$，且为梯度 $L$-Lipschitz 连续的，则

证明. 构造辅助函数 $g(t) = f(x + t(y - x))$，$t \in [0, 1]$。则 $g(0) = f(x)$，$g(1) = f(y)$，$g'(t) = \nabla f(x + t(y-x))^\top(y - x)$。由 Newton-Leibniz 公式：

对被积函数用 Cauchy-Schwarz 不等式和梯度 Lipschitz 条件：

因此 $f(y) - f(x) - \nabla f(x)^\top(y-x) \leq \int_0^1 Lt\|y-x\|^2\,dt = \frac{L}{2}\|y-x\|^2$。$\square$

二次上界意味着 $f$ 可以被一个二次函数从上方控制——函数的增长速度不会超过二次。这个性质在梯度下降法中至关重要：取步长 $\eta = 1/L$，在 $y = x - \frac{1}{L}\nabla f(x)$ 处代入二次上界可得 $f(y) \leq f(x) - \frac{1}{2L}\|\nabla f(x)\|^2$，保证每步目标值严格下降。

将二次上界与强凸函数的二次下界放在一起，$\mu$-强凸且 $L$-光滑的函数在每一点附近被夹在两个二次函数之间：

左端是二次下界（来自强凸性），右端是二次上界（来自 $L$-光滑性）。比值 $\kappa = L/\mu$ 称为条件数，度量了函数”最陡方向”与”最平方向”之间曲率的差异。条件数越大，函数的等高线越扁（椭球形），梯度下降法的收敛越慢——这正是第三章将详细分析的现象。

二次上界还有一个重要的推论：若 $f$ 是 $L$-光滑的且存在全局最小点 $x^*$，则

证明只需在二次上界中对 $y$ 取下确界：$f(x^*) \leq \inf_y \{f(x) + \nabla f(x)^\top(y-x) + \frac{L}{2}\|y-x\|^2\}$，右端在 $y = x - \frac{1}{L}\nabla f(x)$ 处取到最小值 $f(x) - \frac{1}{2L}\|\nabla f(x)\|^2$。这个不等式将梯度范数与目标函数的次优性（suboptimality gap）联系起来：梯度越大，离最优越远。它为梯度下降法的收敛性分析提供了关键的中间步骤。

例. $f(x) = \frac{1}{2}x^\top Ax$，$A$ 对称正定，特征值范围 $[\mu, L]$。则 $f$ 同时是 $\mu$-强凸和 $L$-光滑的，条件数 $\kappa = L/\mu$。当 $A$ 的特征值分布很不均匀时（例如 $\mu = 0.01$，$L = 100$，$\kappa = 10^4$），函数的等高面是非常扁的椭球，梯度下降法在”短轴”方向上的进展会被”长轴”方向上的振荡严重拖慢。预处理技术（preconditioning）的本质就是通过变量变换来减小条件数。

1.2.6 凸松弛：从非凸到凸#

理解了凸性的层次之后，一个自然的问题是：遇到非凸问题该怎么办？一个常用策略是凸松弛——用凸函数近似替换非凸部分，将问题转化为可高效求解的凸优化问题。松弛后的问题比原问题更容易求解，代价是可能损失一些精度。

例（压缩感知）. 已知压缩矩阵 $A \in \mathbb{R}^{m \times n}$（$n \gg m$）和观测信号 $b = Ax$，要从 $b$ 恢复稀疏的原始信号 $x$。原始问题为：

其中 $\|x\|_0$ 是 $\ell_0$ 范数（$x$ 中非零元素的个数）。前半部分 $\frac{1}{2}\|Ax - b\|_2^2$ 展开后为 $\frac{1}{2}x^\top A^\top A x - b^\top A x + \frac{1}{2}b^\top b$，二次型加线性项，是凸的。但 $\ell_0$ 范数在 $x = 0$ 处不连续（取值为 0，而在任何非零点取值至少为 1），不连续自然不是凸的。凸加非凸，整体非凸。

用 $\ell_1$ 范数（各分量绝对值之和）替代 $\ell_0$ 范数，得到凸松弛后的问题：

$\ell_1$ 范数是凸的，所以整个问题变成了凸优化。在一定条件下（如矩阵 $A$ 满足 RIP 条件），$\ell_1$ 松弛的解恰好就是原始 $\ell_0$ 问题的解。代价是 $\ell_1$ 范数在 $x_i = 0$ 处不可导，需要非光滑优化工具。类似地，矩阵的秩（非零奇异值个数）是非凸的，其凸松弛是核范数（奇异值之和），广泛用于低秩矩阵恢复。

这体现了优化问题中常见的三难取舍：凸性、光滑性、对原问题的逼近程度，往往不能同时兼得。$\ell_1$ 正则化问题的求解正是第五章邻近算法的核心应用场景。

有了凸集、凸函数及其分类的理论基础，下面讨论如何判断一个点是否是最优解。

1.3.1 解的存在性#

在讨论最优性条件之前，有一个更基本的问题：最优解是否存在？

数学分析中的 Weierstrass 定理给出了经典的回答：定义在紧集（有界闭集）上的连续函数一定存在最大值和最小值。但在很多优化问题中，定义域不是紧集——例如无约束问题的定义域是整个 $\mathbb{R}^n$，它是无界的。此时 Weierstrass 定理不直接适用。

推广后的 Weierstrass 定理将紧性条件替换为更弱的条件：

定理（Weierstrass 定理的推广）. 设 $f: \mathcal{X} \to (-\infty, +\infty]$ 是适当且闭的函数。若下列三个条件中任一成立：

1. $\text{dom}\,f$ 是有界的；
2. 存在 $\bar{\gamma}$ 使得下水平集 $\{x \in \mathcal{X} \mid f(x) \leq \bar{\gamma}\}$ 非空且有界；
3. $f$ 是强制的（coercive），即 $\|x\| \to +\infty$ 时 $f(x) \to +\infty$；

则 $f$ 在 $\mathcal{X}$ 上的最小值点集非空且紧。

三个条件在本质上都是保证函数值不能在”无穷远处”取到最小值，从而可以把搜索范围限制在一个有界区域内。条件 3 最常用：强制性意味着函数”向外走就上升”，所以最小值只能在有限的范围内取到。$f(x) = x^2$ 定义在 $\mathbb{R}$ 上，虽然定义域无界，但由于 $x^2 \to +\infty$（强制），全局最小值 $x^* = 0$ 存在。反例 $f(x) = e^{-x}$ 定义在 $\mathbb{R}$ 上，下确界为 0 但不可达，因为 $f$ 不是强制的（$x \to +\infty$ 时 $f \to 0$，不趋于 $+\infty$）。

对于强凸函数，存在性和唯一性同时得到保证。存在性方面，$\mu$-强凸函数是强制的：由二次下界 $f(y) \geq f(x) + \nabla f(x)^\top(y-x) + \frac{\mu}{2}\|y-x\|^2$，取 $x$ 为定义域中的任意固定点，当 $\|y\| \to \infty$ 时右端以二次速度趋于正无穷，因此 $f$ 满足 Weierstrass 定理的条件 3。唯一性则由 1.2.4 节中强凸函数的反证法证明保证。

定理中”闭函数”这一条件也值得注意。一个函数是闭的当且仅当它的所有下水平集 $\{x \mid f(x) \leq \alpha\}$ 是闭集，对于连续函数这自动成立。闭性的作用是保证下水平集中的极限点仍在下水平集内，从而使下确界可以被取到。

1.3.2 无约束优化的最优性条件#

现在考虑无约束优化问题：

目标是给出 $x^*$ 为局部最小值点的必要条件和充分条件。这些条件将一维微积分中的导数判据推广到 $n$ 维，用梯度和 Hessian 矩阵替代导数和二阶导数。

一阶必要条件.

定理. 若 $x^*$ 是局部最小值点，则 $\nabla f(x^*) = \mathbf{0}$。

满足 $\nabla f(x^*) = \mathbf{0}$ 的点称为驻点（stationary point）或稳定点。驻点是梯度为零的点，在驻点处函数在各个方向上的一阶变化率为零。这个条件的实用价值在于：可以将 $\|\nabla f(x^k)\| < \varepsilon$ 作为优化算法的停止准则——当梯度足够小时，认为已经接近驻点。

证明. 对 $f$ 在 $x^*$ 处做一阶 Taylor 展开：

两边减去 $f(x^*)$ 再除以 $t$：

由于 $x^*$ 是局部最小值点，在其邻域内 $f(x^* + tv) \geq f(x^*)$。令 $t \to 0^+$，左端 $\geq 0$，得 $\nabla f(x^*)^\top v \geq 0$；令 $t \to 0^-$，$t$ 为负但分母也为负，得 $\nabla f(x^*)^\top v \leq 0$。两个不等式结合，对任意方向 $v$ 均有 $\nabla f(x^*)^\top v = 0$，由 $v$ 的任意性推出 $\nabla f(x^*) = \mathbf{0}$。$\square$

二阶必要条件.

定理. 若 $x^*$ 是局部最小值点，且 $f$ 在 $x^*$ 附近二阶可导，则：

这个条件在一阶条件的基础上增加了对曲率的要求：Hessian 半正定意味着函数在 $x^*$ 处的各方向曲率均非负。直观地说，局部最小值点必然是”碗形”的，而不能在某个方向上呈”鞍形”（曲率为负）。

证明（反证法）. 假设 $\nabla^2 f(x^*)$ 不是半正定的，则存在负特征值 $\lambda < 0$ 及对应的单位特征向量 $d$。对 $f$ 在 $x^*$ 处做二阶 Taylor 展开：

由一阶必要条件 $\nabla f(x^*) = \mathbf{0}$，中间项消去。利用如下引理：

引理. 设 $S$ 为 $n$ 阶实对称矩阵，则 $d^\top S d \geq \lambda_{\min}(S)\|d\|^2$。

证明：$S$ 正交相似于对角阵 $\Lambda = \text{diag}(\lambda_1, \ldots, \lambda_n)$，即 $S = Q\Lambda Q^\top$。令 $y = Q^\top d$，由正交不变性 $\|y\| = \|d\|$，则 $d^\top S d = y^\top \Lambda y = \sum_i \lambda_i y_i^2 \geq \lambda_{\min}\sum_i y_i^2 = \lambda_{\min}\|d\|^2$。

将 $d$ 取为负特征值对应的特征向量，则 $d^\top \nabla^2 f(x^*) d = \lambda < 0$。令 $\|d\|$ 充分小以忽略高阶项，得 $f(x^* + d) - f(x^*) \approx \frac{1}{2}\lambda\|d\|^2 < 0$，与 $x^*$ 是局部最小值矛盾。$\square$

二阶充分条件.

定理. 若 $\nabla f(x^*) = \mathbf{0}$ 且 $\nabla^2 f(x^*) \succ 0$（正定），则 $x^*$ 是局部最小值点。

正定比半正定更强：正定意味着所有方向的曲率都严格为正，函数在 $x^*$ 处是一个严格的”碗底”。

证明. 二阶 Taylor 展开后，梯度项为零，余项为：

由正定性和上述引理，右端第一项 $\geq \frac{1}{2}\lambda_{\min}(\nabla^2 f(x^*)) > 0$。令 $\|d\|$ 充分小使高阶项可忽略，得 $f(x^* + d) - f(x^*) \geq 0$，故 $x^*$ 是局部最小值点。$\square$

注意半正定与正定的差别：二阶必要条件要求半正定，二阶充分条件要求正定。中间存在一个”间隙”——当 Hessian 半正定但不正定时（即存在零特征值），该点可能是极小值点也可能是鞍点，需要更高阶的信息来判断。

1.3.3 凸函数的全局最优性#

对于凸函数，最优性条件有一个质的飞跃：

定理. 若 $f$ 连续可微且为凸函数，则以下三者等价：

这是凸优化最强大的性质——只要找到一个驻点，就自动是全局最优。非凸问题不具备这一性质：驻点可能是鞍点或局部最小值，不一定是全局最优。这也解释了为什么凸优化在算法设计上比非凸优化简单得多——任何能收敛到驻点的算法都能找到全局最优解。

“局部 $\Rightarrow$ 全局”的关键在于凸函数的一阶条件。假设 $x^*$ 是局部最优但不是全局最优，则存在 $y$ 使得 $f(y) < f(x^*)$。由一阶条件，$f(y) \geq f(x^*) + \nabla f(x^*)^\top(y - x^*) = f(x^*)$（最后一步用了 $\nabla f(x^*) = \mathbf{0}$），矛盾。

对于非凸问题，驻点的类型需要由 Hessian 来判别。在高维空间中，鞍点（部分方向上升、部分方向下降）远比局部极小值常见——对于 $n$ 维问题，一个随机驻点是鞍点的概率随 $n$ 的增大而趋近于 1。深度学习中的损失函数虽然是非凸的，但大量实证和理论工作表明，高维非凸目标中的局部极小值通常与全局极小值的函数值非常接近，真正阻碍优化的主要是鞍点而非局部极小值。

总结. 四个最优性条件的关系如下：