无约束优化的最优性条件

本页回答最优化中最基本的问题：给定一个点，如何判断它是不是（局部）极小点？ 答案是一组以梯度和黑塞矩阵表达的最优性条件——一阶/二阶必要条件用来"排除不可能是极小点的点"，二阶充分条件用来"确认严格局部极小点"。它们是后面所有迭代算法（一维搜索、梯度方法、牛顿法）的理论出发点：算法的本质就是寻找满足这些条件的点。

核心结论速览

考虑问题 \(\min f(\boldsymbol{x}),\ \text{s.t.}\ \boldsymbol{x} \in \Omega\)，\(\boldsymbol{x}^*\) 为局部极小点，\(\boldsymbol{F}\) 为黑塞矩阵：

条件	适用场景	内容	性质
FONC（一阶必要）	一般约束集	任意可行方向 \(\boldsymbol{d}\)：\(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) \ge 0\)	必要
FONC（内点）	\(\boldsymbol{x}^*\) 是内点 / 无约束	\(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\)	必要
SONC（二阶必要）	一般约束集	可行方向 \(\boldsymbol{d}\) 满足 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) = 0\) 时：\(\boldsymbol{d}^\top \boldsymbol{F}(\boldsymbol{x}^*) \boldsymbol{d} \ge 0\)	必要
SONC（内点）	\(\boldsymbol{x}^*\) 是内点 / 无约束	\(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\) 且 \(\boldsymbol{F}(\boldsymbol{x}^*) \succeq 0\)（半正定）	必要
SOSC（二阶充分）	\(\boldsymbol{x}^*\) 是内点	\(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\) 且 \(\boldsymbol{F}(\boldsymbol{x}^*) \succ 0\)（正定）\(\Rightarrow\) 严格局部极小	充分

必要条件不充分（反例 \(f(x)=x^3\)、鞍点 \(f=x_1^2-x_2^2\)），充分条件不必要（反例 \(f(x)=x^4\)）。

优化问题与局部极小点

本课程研究的优化问题统一写成如下一般形式：

\[ \begin{aligned} \min\ & f(\boldsymbol{x}) \\ \text{s.t.}\ & \boldsymbol{x} \in \Omega \end{aligned} \]

• \(f:\mathbb{R}^n \to \mathbb{R}\) 是目标函数（或价值函数）；
• \(\boldsymbol{x} = (x_1, x_2, \dots, x_n)^\top \in \mathbb{R}^n\) 是决策变量；
• \(\Omega \subset \mathbb{R}^n\) 是约束集（可行集）。\(\boldsymbol{x} \in \Omega\) 这种写法称为集合约束；若约束集由函数刻画，即 \(\Omega = \{\boldsymbol{x} : \boldsymbol{h}(\boldsymbol{x}) = \boldsymbol{0},\ \boldsymbol{g}(\boldsymbol{x}) \le \boldsymbol{0}\}\)，则称为函数约束；
• 当 \(\Omega = \mathbb{R}^n\) 时，问题就是无约束优化问题。

求极大可以统一转化为求极小：\(\max f(\boldsymbol{x}) \iff \min\,(-f(\boldsymbol{x}))\)，因此一切结论只需对极小化叙述。

定义（局部极小点与全局极小点）

设 \(f:\mathbb{R}^n \to \mathbb{R}\) 定义在 \(\Omega \subset \mathbb{R}^n\) 上，\(\boldsymbol{x}^* \in \Omega\)。

1. 若存在 \(\varepsilon > 0\)，使得对所有满足 \(\lVert \boldsymbol{x} - \boldsymbol{x}^* \rVert < \varepsilon\) 的 \(\boldsymbol{x} \in \Omega \setminus \{\boldsymbol{x}^*\}\) 都有 \(f(\boldsymbol{x}) \ge f(\boldsymbol{x}^*)\)，则称 \(\boldsymbol{x}^*\) 是 \(f\) 在 \(\Omega\) 上的局部极小点；
2. 若对所有 \(\boldsymbol{x} \in \Omega \setminus \{\boldsymbol{x}^*\}\) 都有 \(f(\boldsymbol{x}) \ge f(\boldsymbol{x}^*)\)，则称 \(\boldsymbol{x}^*\) 是全局极小点。

把 \(\ge\) 换成 \(>\)，就得到严格局部 / 全局极小点。

直观地说：局部极小点只要求"在自己附近的可行点中最小"，全局极小点要求"在整个可行集中最小"。一条一维曲线上可以同时存在严格全局极小点、严格局部极小点，以及一段平坦谷底上的（非严格）局部极小点。

全局极小点常用 \(\operatorname{argmin}\) 记号表示：

\[ f(\boldsymbol{x}^*) = \min_{\boldsymbol{x} \in \Omega} f(\boldsymbol{x}), \qquad \boldsymbol{x}^* = \operatorname*{argmin}_{\boldsymbol{x} \in \Omega} f(\boldsymbol{x}) \]

即 \(\min\) 取的是最小的函数值，\(\operatorname{argmin}\) 取的是达到该值的自变量（若不唯一，任取其一即可）。

求全局极小点一般非常困难，本课程的理论与算法主要围绕局部极小点展开。

预备：梯度、黑塞矩阵与方向导数

最优性条件全部用 \(f\) 的一、二阶导数信息表达，先固定记号。\(n\) 元实值函数 \(f:\mathbb{R}^n \to \mathbb{R}\) 的一阶导数（行向量）为

\[ Df(\boldsymbol{x}) \triangleq \left[ \frac{\partial f}{\partial x_1}(\boldsymbol{x}),\ \frac{\partial f}{\partial x_2}(\boldsymbol{x}),\ \dots,\ \frac{\partial f}{\partial x_n}(\boldsymbol{x}) \right] \]

梯度是它的转置：\(\nabla f(\boldsymbol{x}) = Df(\boldsymbol{x})^\top\)（列向量）。二阶导数即黑塞矩阵（Hessian）：

\[ \boldsymbol{F}(\boldsymbol{x}) = D^2 f(\boldsymbol{x}) \triangleq \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \cdots & \dfrac{\partial^2 f}{\partial x_n \partial x_1} \\ \vdots & \ddots & \vdots \\ \dfrac{\partial^2 f}{\partial x_1 \partial x_n} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix} \]

当 \(f\) 二阶连续可微（\(f \in \mathcal{C}^2\)）时，混合偏导相等，黑塞矩阵是对称矩阵。

例：求一、二阶导数

求 \(f(x_1, x_2) = 5x_1 + 8x_2 + x_1 x_2 - x_1^2 - 2x_2^2\) 的一、二阶导数。

解答

\[ Df(x_1, x_2) = [\,5 + x_2 - 2x_1,\ \ 8 + x_1 - 4x_2\,], \qquad D^2 f(x_1, x_2) = \begin{bmatrix} -2 & 1 \\ 1 & -4 \end{bmatrix} \]

可行方向

有约束时不能朝任意方向移动，需要刻画"哪些方向走一小步仍留在 \(\Omega\) 内"：

定义（可行方向）

对 \(\boldsymbol{d} \in \mathbb{R}^n\)（\(\boldsymbol{d} \ne \boldsymbol{0}\)）和 \(\boldsymbol{x} \in \Omega\)，若存在 \(\alpha_0 > 0\)，使得对所有 \(\alpha \in [0, \alpha_0]\) 都有 \(\boldsymbol{x} + \alpha \boldsymbol{d} \in \Omega\)，则称 \(\boldsymbol{d}\) 是 \(\boldsymbol{x}\) 处的可行方向。

直观图像：站在 \(\boldsymbol{x}\) 处朝 \(\boldsymbol{d}\) 方向迈出一小段直线，脚不出界，这个方向就可行。两个极端情形值得记住：

• \(\boldsymbol{x}\) 是 \(\Omega\) 的内点（特别地，无约束时所有点都是内点）：任意方向都是可行方向；
• \(\Omega\) 是曲面（如单位圆周 \(x_1^2 + x_2^2 = 1\)）：任何直线方向都会离开曲面，不存在可行方向——这正是该定义的局限，见下文例（圆周约束）。

线性等式约束下的可行方向有一个干净的刻画，后面讲约束优化时会反复用到：

命题（线性等式约束的可行方向）

设 \(\Omega = \{\boldsymbol{x} \in \mathbb{R}^n : \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}\}\)，则 \(\boldsymbol{d}\) 是 \(\boldsymbol{x} \in \Omega\) 处的可行方向 \(\iff \boldsymbol{A}\boldsymbol{d} = \boldsymbol{0}\)。

证明

必要性：\(\boldsymbol{d}\) 可行，则存在 \(\alpha > 0\) 使 \(\boldsymbol{x} + \alpha\boldsymbol{d} \in \Omega\)，即 \(\boldsymbol{A}\boldsymbol{x} + \alpha \boldsymbol{A}\boldsymbol{d} = \boldsymbol{b}\)；又 \(\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}\)，故 \(\alpha \boldsymbol{A}\boldsymbol{d} = \boldsymbol{0}\)，即 \(\boldsymbol{A}\boldsymbol{d} = \boldsymbol{0}\)。

充分性：若 \(\boldsymbol{A}\boldsymbol{d} = \boldsymbol{0}\)，则对任意 \(\alpha \ge 0\)，\(\boldsymbol{A}(\boldsymbol{x} + \alpha\boldsymbol{d}) = \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}\)，即 \(\boldsymbol{x} + \alpha\boldsymbol{d} \in \Omega\) 恒成立。\(\blacksquare\)

方向导数

设 \(\boldsymbol{d}\) 是 \(\boldsymbol{x}\) 处的可行方向，\(f\) 沿 \(\boldsymbol{d}\) 的方向导数定义为

\[ \frac{\partial f}{\partial \boldsymbol{d}}(\boldsymbol{x}) = \lim_{\alpha \to 0} \frac{f(\boldsymbol{x} + \alpha \boldsymbol{d}) - f(\boldsymbol{x})}{\alpha} \]

固定 \(\boldsymbol{x}, \boldsymbol{d}\) 后，\(f(\boldsymbol{x} + \alpha\boldsymbol{d})\) 是关于 \(\alpha\) 的一元函数，于是方向导数就是它在 \(\alpha = 0\) 处的导数。用链式法则展开：

\[ \frac{\partial f}{\partial \boldsymbol{d}}(\boldsymbol{x}) = \left. \frac{\mathrm{d}}{\mathrm{d}\alpha} f(\boldsymbol{x} + \alpha \boldsymbol{d}) \right|_{\alpha = 0} = Df(\boldsymbol{x})\, \boldsymbol{d} = \nabla f(\boldsymbol{x})^\top \boldsymbol{d} = \boldsymbol{d}^\top \nabla f(\boldsymbol{x}) \]

当 \(\lVert \boldsymbol{d} \rVert = 1\) 时，\(\boldsymbol{d}^\top \nabla f(\boldsymbol{x})\) 就是 \(f\) 在 \(\boldsymbol{x}\) 处沿 \(\boldsymbol{d}\) 的增长率。由柯西–施瓦茨不等式，增长率在 \(\boldsymbol{d}\) 取梯度方向 \(\nabla f / \lVert \nabla f \rVert\) 时最大——"梯度是函数增长最快的方向"，这是后面梯度方法的全部出发点。

例：求方向导数

\(f(\boldsymbol{x}) = x_1 x_2 x_3\)，方向 \(\boldsymbol{d} = \left( \frac{1}{2}, \frac{1}{2}, \frac{1}{\sqrt{2}} \right)^\top\)，求 \(f\) 沿 \(\boldsymbol{d}\) 的方向导数。

解答

\(\lVert \boldsymbol{d} \rVert = 1\)，故

\[ \frac{\partial f}{\partial \boldsymbol{d}}(\boldsymbol{x}) = \nabla f(\boldsymbol{x})^\top \boldsymbol{d} = [\,x_2 x_3,\ x_1 x_3,\ x_1 x_2\,] \begin{bmatrix} 1/2 \\ 1/2 \\ 1/\sqrt{2} \end{bmatrix} = \frac{x_2 x_3}{2} + \frac{x_1 x_3}{2} + \frac{x_1 x_2}{\sqrt{2}} \]

一阶必要条件（FONC）

定理（一阶必要条件，FONC）

设 \(f \in \mathcal{C}^1\)，\(\Omega \subset \mathbb{R}^n\)。若 \(\boldsymbol{x}^*\) 是 \(f\) 在 \(\Omega\) 上的局部极小点，则对 \(\boldsymbol{x}^*\) 处的任意可行方向 \(\boldsymbol{d}\)，都有

\[ \boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) \ge 0 \]

证明

取可行方向 \(\boldsymbol{d}\)，令 \(\boldsymbol{x}(\alpha) = \boldsymbol{x}^* + \alpha \boldsymbol{d} \in \Omega\)，定义一元函数 \(\phi(\alpha) = f(\boldsymbol{x}(\alpha))\)。由泰勒定理，对 \(\alpha \ge 0\)：

\[ f(\boldsymbol{x}(\alpha)) - f(\boldsymbol{x}^*) = \phi(\alpha) - \phi(0) = \phi'(0)\,\alpha + o(\alpha) = \alpha\, \boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) + o(\alpha) \]

\(\boldsymbol{x}^*\) 是局部极小点，故 \(\alpha\) 足够小时左边 \(\ge 0\)；两边除以 \(\alpha > 0\) 并令 \(\alpha \to 0\)（\(o(\alpha)/\alpha \to 0\)），得 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) \ge 0\)。\(\blacksquare\)

用方向导数的语言说就是：在局部极小点处，沿任何可行方向的增长率都非负——如果存在某个可行方向使函数值下降，那这个点显然还能更优，不可能是极小点。FONC 就是把这句大白话写成数学。

当 \(\boldsymbol{x}^*\) 是内点时，所有方向都可行，条件大幅简化：

推论（内点的 FONC）

在定理条件下，若 \(\boldsymbol{x}^*\) 还是 \(\Omega\) 的内点（特别地，无约束问题中的任意点），则

\[ \nabla f(\boldsymbol{x}^*) = \boldsymbol{0} \]

证明

内点处任意 \(\boldsymbol{d} \in \mathbb{R}^n\) 都是可行方向，于是 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) \ge 0\) 与 \((-\boldsymbol{d})^\top \nabla f(\boldsymbol{x}^*) \ge 0\) 同时成立，故对一切 \(\boldsymbol{d}\) 有 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) = 0\)，即 \(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\)。\(\blacksquare\)

满足 \(\nabla f(\boldsymbol{x}) = \boldsymbol{0}\) 的点称为驻点（平稳点）。求无约束极小点的第一步永远是解方程 \(\nabla f(\boldsymbol{x}) = \boldsymbol{0}\) 筛出全部驻点。

易错点：边界点的梯度不必为零

\(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\) 只对内点成立。当极小点落在约束集边界上时，梯度完全可以非零，此时只能用一般形式 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) \ge 0\) 逐个检查可行方向（见下例）。

例：检验边界点与内点的 FONC

考虑问题

\[ \begin{aligned} \min\ & x_1^2 + 0.5 x_2^2 + 3 x_2 + 4.5 \\ \text{s.t.}\ & x_1, x_2 \ge 0 \end{aligned} \]

判断以下各点是否满足局部极小点的一阶必要条件： (a) \(\boldsymbol{x}^1 = (1, 3)^\top\)；(b) \(\boldsymbol{x}^2 = (0, 3)^\top\)；(c) \(\boldsymbol{x}^3 = (1, 0)^\top\)；(d) \(\boldsymbol{x}^4 = (0, 0)^\top\)。

解答

梯度为 \(\nabla f(\boldsymbol{x}) = (2x_1,\ x_2 + 3)^\top\)。

(a) \(\boldsymbol{x}^1 = (1,3)^\top\) 是内点，但 \(\nabla f(\boldsymbol{x}^1) = (2, 6)^\top \ne \boldsymbol{0}\)，不满足。

(b) \(\boldsymbol{x}^2 = (0,3)^\top\) 在边界 \(x_1 = 0\) 上，\(\nabla f(\boldsymbol{x}^2) = (0, 6)^\top\)。取可行方向 \(\boldsymbol{d} = (0, -1)^\top\)（沿边界向下走仍可行），\(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^2) = -6 < 0\)，不满足。

(c) \(\boldsymbol{x}^3 = (1,0)^\top\) 在边界 \(x_2 = 0\) 上，\(\nabla f(\boldsymbol{x}^3) = (2, 3)^\top\)。取可行方向 \(\boldsymbol{d} = (-1, 0)^\top\)，\(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^3) = -2 < 0\)，不满足。

(d) \(\boldsymbol{x}^4 = (0,0)^\top\) 是角点，\(\nabla f(\boldsymbol{x}^4) = (0, 3)^\top\)。该点处全部可行方向为 \(\boldsymbol{d} = (a, b)^\top\)，\(a, b \ge 0\)，于是 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^4) = 3b \ge 0\) 恒成立，满足 FONC。

例：移动通信中的最优位置（信噪比最大化）

移动用户位于两座基站（相距 2，主基站在原点）连线上的位置 \(x\) 处，接收功率与距离平方成反比（含常数 1 防奇异）。信噪比为

\[ f(x) = \frac{P(1 + x^2)^{-1}}{P(1 + (2 - x)^2)^{-1}} = \frac{1 + (2 - x)^2}{1 + x^2} \]

求使信噪比最大的位置 \(x^*\)。

解答

转化为内点上的驻点问题（\(\Omega = \mathbb{R}\)，所有点都是内点）。求导：

\[ f'(x) = \frac{4(x^2 - 2x - 1)}{(1 + x^2)^2} \]

令 \(f'(x^*) = 0\)，解得 \(x^* = 1 \pm \sqrt{2}\)。比较两点的函数值：\(f(1 - \sqrt{2}) \approx 5.83\)，\(f(1 + \sqrt{2}) \approx 0.17\)，故最优位置为 \(x^* = 1 - \sqrt{2}\)（在主基站背向邻基站一侧）。

这也演示了 FONC 的用法：它只给出候选点，最终还要比较函数值（或用二阶条件）定夺。

例：圆周约束——FONC 失效与参数化

考虑 \(\min f(\boldsymbol{x})\)，s.t. \(\boldsymbol{x} \in \Omega = \{(x_1, x_2)^\top : x_1^2 + x_2^2 = 1\}\)。

(a) 求 \(\boldsymbol{x}^* \in \Omega\) 处的全部可行方向；(b) FONC 能筛掉哪些点？(c) 通过参数化把问题化为无约束问题，导出真正有用的必要条件。

解答

(a) 圆周上任何点沿任何直线方向走都会离开圆周，故不存在可行方向。

(b) 没有可行方向意味着 FONC 对所有点都自动成立——它筛不掉任何点，对这类等式约束问题完全失效。

(c) 用极坐标参数化 \(\boldsymbol{x} = \boldsymbol{g}(\theta) = (\cos\theta, \sin\theta)^\top\)，问题变为关于 \(\theta \in \mathbb{R}\) 的无约束问题 \(\min h(\theta) = f(\boldsymbol{g}(\theta))\)。由链式法则

\[ h'(\theta) = Df(\boldsymbol{g}(\theta))\, D\boldsymbol{g}(\theta) = D\boldsymbol{g}(\theta)^\top \nabla f(\boldsymbol{x}), \qquad D\boldsymbol{g}(\theta) = (-\sin\theta, \cos\theta)^\top \]

若 \(\boldsymbol{x}^* = \boldsymbol{g}(\theta^*)\) 是局部极小点，则 \(\theta^*\) 是 \(h\) 的局部极小点（内点），故 \(h'(\theta^*) = 0\)，即：对所有与 \(\boldsymbol{x}^*\) 正交（即与圆周相切）的方向 \(\boldsymbol{d}\)，都有 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) = 0\)。

这就是等式约束优化的雏形："梯度在切方向上的分量为零"，后续约束优化中的拉格朗日条件是它的一般化。

二阶必要条件（SONC）

FONC 只用了一阶信息。在 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) = 0\)（一阶项不提供信息）的方向上，还可以追问二阶项：

定理（二阶必要条件，SONC）

设 \(f \in \mathcal{C}^2\)，\(\Omega \subset \mathbb{R}^n\)。若 \(\boldsymbol{x}^*\) 是 \(f\) 在 \(\Omega\) 上的局部极小点，\(\boldsymbol{d}\) 是 \(\boldsymbol{x}^*\) 处的可行方向且 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) = 0\)，则

\[ \boldsymbol{d}^\top \boldsymbol{F}(\boldsymbol{x}^*)\, \boldsymbol{d} \ge 0 \]

证明（反证法）

假设存在可行方向 \(\boldsymbol{d}\) 满足 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) = 0\) 但 \(\boldsymbol{d}^\top \boldsymbol{F}(\boldsymbol{x}^*) \boldsymbol{d} < 0\)。令 \(\phi(\alpha) = f(\boldsymbol{x}^* + \alpha \boldsymbol{d})\)，二阶泰勒展开：

\[ \phi(\alpha) = \phi(0) + \phi'(0)\,\alpha + \phi''(0)\,\frac{\alpha^2}{2} + o(\alpha^2) \]

其中 \(\phi'(0) = \boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) = 0\)，\(\phi''(0) = \boldsymbol{d}^\top \boldsymbol{F}(\boldsymbol{x}^*) \boldsymbol{d} < 0\)，于是 \(\alpha\) 足够小时

\[ f(\boldsymbol{x}^* + \alpha\boldsymbol{d}) - f(\boldsymbol{x}^*) = \phi''(0)\,\frac{\alpha^2}{2} + o(\alpha^2) < 0 \]

与 \(\boldsymbol{x}^*\) 是局部极小点矛盾。\(\blacksquare\)

推论（内点的 SONC）

若 \(\boldsymbol{x}^*\) 还是 \(\Omega\) 的内点（或问题无约束），则

\[ \nabla f(\boldsymbol{x}^*) = \boldsymbol{0}, \qquad \boldsymbol{F}(\boldsymbol{x}^*) \succeq 0 \ \text{（半正定）} \]

即对所有 \(\boldsymbol{d} \in \mathbb{R}^n\) 都有 \(\boldsymbol{d}^\top \boldsymbol{F}(\boldsymbol{x}^*) \boldsymbol{d} \ge 0\)。

直觉：极小点处函数局部近似为 \(f(\boldsymbol{x}^* + \boldsymbol{d}) \approx f(\boldsymbol{x}^*) + \frac{1}{2} \boldsymbol{d}^\top \boldsymbol{F}(\boldsymbol{x}^*) \boldsymbol{d}\)（一阶项已为零），要想"周围不比自己低"，二次型至少得非负——曲面在极小点附近必须是"碗口朝上或平的"。

易错点：必要条件不是充分条件

满足 FONC + SONC 的点未必是极小点：

• \(f(x) = x^3\)：\(f'(0) = f''(0) = 0\)，FONC、SONC 全部满足，但 \(x = 0\) 是拐点，不是极小点；
• \(f(\boldsymbol{x}) = x_1^2 - x_2^2\)：驻点 \((0,0)^\top\) 处黑塞矩阵 \(\operatorname{diag}(2, -2)\) 不定，沿 \(x_1\) 方向上凸、沿 \(x_2\) 方向下凹——这是鞍点。该点连 SONC 都不满足，可直接排除；
• 反过来，SONC 满足也可能只是鞍点或极大点的"漏网之鱼"（如 \(f = x_1^2\) 在 \(\mathbb{R}^2\) 上，整条 \(x_2\) 轴都满足必要条件）。

必要条件的正确用法是排除法：不满足者一定不是极小点；满足者只是候选。

二阶充分条件（SOSC）

把 SONC 中的"半正定"加强为"正定"，就从必要条件升级为充分条件：

定理（二阶充分条件，SOSC，内点情形）

设 \(f \in \mathcal{C}^2\)，\(\boldsymbol{x}^*\) 是 \(\Omega\) 的内点。若同时满足

1. \(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\)；
2. \(\boldsymbol{F}(\boldsymbol{x}^*) \succ 0\)（正定），

则 \(\boldsymbol{x}^*\) 是 \(f\) 的严格局部极小点。

证明

\(f \in \mathcal{C}^2\) 故 \(\boldsymbol{F}(\boldsymbol{x}^*)\) 对称。由瑞利（Rayleigh）不等式，对任意 \(\boldsymbol{d} \ne \boldsymbol{0}\)：

\[ \boldsymbol{d}^\top \boldsymbol{F}(\boldsymbol{x}^*)\, \boldsymbol{d} \ge \lambda_{\min}\big(\boldsymbol{F}(\boldsymbol{x}^*)\big)\, \lVert \boldsymbol{d} \rVert^2 > 0 \]

其中 \(\lambda_{\min} > 0\) 是最小特征值。结合泰勒定理与条件 1：

\[ f(\boldsymbol{x}^* + \boldsymbol{d}) - f(\boldsymbol{x}^*) = \frac{1}{2}\, \boldsymbol{d}^\top \boldsymbol{F}(\boldsymbol{x}^*)\, \boldsymbol{d} + o(\lVert \boldsymbol{d} \rVert^2) \ge \frac{\lambda_{\min}}{2} \lVert \boldsymbol{d} \rVert^2 + o(\lVert \boldsymbol{d} \rVert^2) \]

\(\lVert \boldsymbol{d} \rVert\) 足够小时右边为正，即 \(f(\boldsymbol{x}^* + \boldsymbol{d}) > f(\boldsymbol{x}^*)\)。\(\blacksquare\)

例：用 SOSC 确认极小点

考虑 \(f(\boldsymbol{x}) = x_1^2 + x_2^2\)。

解答

\(\nabla f(\boldsymbol{x}) = (2x_1, 2x_2)^\top\)，当且仅当 \(\boldsymbol{x} = (0,0)^\top\) 时为零。黑塞矩阵

\[ \boldsymbol{F}(\boldsymbol{x}) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \succ 0 \]

处处正定。由 SOSC，\((0,0)^\top\) 是严格局部极小点（事实上也是全局极小点）。

易错点：SOSC 不是必要的

\(f(x) = x^4\) 在 \(x = 0\) 处是严格全局极小点，但 \(f''(0) = 0\) 不正定——SOSC 判不出来。所以：

• SOSC 失败 \(\ne\) 不是极小点；
• 黑塞矩阵半定（既不正定也不不定）时，二阶信息不足以下结论，需要更高阶分析（见下方"三阶必要条件"）。

进阶：三阶必要条件（一维情形）

设 \(f \in \mathcal{C}^3\)，\(0\) 是内点且为局部极小点。已知 \(f'(0) = 0\)、\(f''(0) \ge 0\)；若进一步 \(f''(0) = 0\)，由泰勒展开

\[ f(x) - f(0) = \frac{f'''(0)}{6} x^3 + o(x^3) \ge 0 \]

对 \(x > 0\) 和 \(x < 0\) 分别取极限可逼出 \(f'''(0) \ge 0\) 与 \(f'''(0) \le 0\)，故三阶必要条件为：\(f'(0) = f''(0) = 0 \Rightarrow f'''(0) = 0\)。

它同样只是必要的：\(f(x) = x^5\) 在 \(0\) 处满足一、二、三阶必要条件，却不是极小点（\(x < 0\) 时 \(f < 0\)）。但若 \(f\) 是三次多项式 \(ax^3 + bx^2 + cx + d\)，三个必要条件联立可逼出 \(a = c = 0,\ b \ge 0\)，即 \(f = bx^2 + d\)，此时 \(0\) 必为局部极小点——对三次多项式，这组必要条件恰好也是充分的。

典型例题

求极小点 / 极大点的标准流程

无约束（或内点）问题的判定流程是考试主线，模板如下：

1. 求梯度，解 \(\nabla f(\boldsymbol{x}) = \boldsymbol{0}\)，得到全部驻点；
2. 求黑塞矩阵 \(\boldsymbol{F}(\boldsymbol{x})\)，在每个驻点处判定其定性（特征值符号 / 顺序主子式）；
3. 下结论：

\(\boldsymbol{F}(\boldsymbol{x}^*)\)	结论
正定（\(\succ 0\)）	严格局部极小点
负定（\(\prec 0\)）	严格局部极大点
不定	鞍点（既非极小也非极大）
半定（含奇异）	二阶信息不足，需更高阶分析

例：求函数的全部极小点与极大点

求 \(f(x_1, x_2) = \dfrac{1}{3} x_1^3 - 4 x_1 + \dfrac{1}{3} x_2^3 - 16 x_2\) 的极小点和极大点。

解答

第一步：\(\nabla f(\boldsymbol{x}) = (x_1^2 - 4,\ x_2^2 - 16)^\top = \boldsymbol{0}\)，解得 4 个驻点（均为内点）：

\[ \boldsymbol{x}^1 = (-2, -4)^\top,\quad \boldsymbol{x}^2 = (-2, 4)^\top,\quad \boldsymbol{x}^3 = (2, -4)^\top,\quad \boldsymbol{x}^4 = (2, 4)^\top \]

第二步：\(\boldsymbol{F}(\boldsymbol{x}) = \operatorname{diag}(2x_1,\ 2x_2)\)。

第三步：\(\boldsymbol{F}(\boldsymbol{x}^1) = \operatorname{diag}(-4, -8) \prec 0\)，故 \(\boldsymbol{x}^1\) 是严格局部极大点；\(\boldsymbol{F}(\boldsymbol{x}^4) = \operatorname{diag}(4, 8) \succ 0\)，故 \(\boldsymbol{x}^4\) 是严格局部极小点；\(\boldsymbol{F}(\boldsymbol{x}^2)\)、\(\boldsymbol{F}(\boldsymbol{x}^3)\) 不定，对应鞍点。

一维应用题：最佳观赏距离

例：视角最大化

墙上挂着一幅高 \(a\) 英尺的画，画的下缘高出观赏者眼睛 \(b\) 英尺。观赏者距墙 \(x\) 英尺，求使观赏视角 \(\theta\) 最大的距离 \(x\)。

解答

由两角差的正切公式（上缘仰角减下缘仰角）：

\[ f(x) = \tan\theta = \frac{\frac{a+b}{x} - \frac{b}{x}}{1 + \frac{a+b}{x} \cdot \frac{b}{x}} = \frac{ax}{x^2 + c}, \qquad c \triangleq ab + b^2 \]

可行集 \(\Omega = \{x \ge 0\}\)。求导：

\[ f'(x) = \frac{-a x^2 + ac}{(x^2 + c)^2} = \frac{a(c - x^2)}{(x^2 + c)^2} \]

令 \(f'(x) = 0\) 得唯一正驻点 \(x^* = \sqrt{c}\)（内点）。二阶导数

\[ f''(x) = \frac{2ax(x^2 + c)(x^2 - 3c)}{(x^2 + c)^4} \]

在 \(x^* = \sqrt{c}\) 处 \(f''(x^*) < 0\)，是严格局部极大点。故最佳观赏距离为 \(x^* = \sqrt{ab + b^2} = \sqrt{b(a + b)}\)。

用 FONC 锁定线性规划的最优解

例：FONC 在边界上的排除式论证

考虑问题（\(c_1 > c_2 \ge 0\) 为常数）：

\[ \begin{aligned} \max\ & c_1 x_1 + c_2 x_2 \\ \text{s.t.}\ & x_1 + x_2 \le 1, \quad x_1, x_2 \ge 0 \end{aligned} \]

假定最优解 \(\boldsymbol{x}^*\) 存在，试用一阶必要条件证明它唯一，并求出它。

解答

极大化问题的 FONC（对 \(-f\) 用 FONC 即得）：在局部极大点处，任意可行方向 \(\boldsymbol{d}\) 都有 \(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) \le 0\)。本题 \(\nabla f(\boldsymbol{x}) = (c_1, c_2)^\top\) 为非零常向量。

• 内点：\(\nabla f \ne \boldsymbol{0}\)，无内点满足条件；
• 边界 \(x_1 = 0\)（\(0 \le x_2 < 1\)）或 \(x_2 = 0\)（\(0 \le x_1 < 1\)）上的点：\(\boldsymbol{d} = (1, 1)^\top\) 可行（朝可行域内部走），\(\boldsymbol{d}^\top \nabla f = c_1 + c_2 > 0\)，排除；
• 斜边 \(x_1 + x_2 = 1\) 上的内部点及端点 \((0, 1)^\top\)：\(\boldsymbol{d} = (1, -1)^\top\) 可行（沿斜边向 \((1,0)^\top\) 滑动），\(\boldsymbol{d}^\top \nabla f = c_1 - c_2 > 0\)，排除；
• \((1, 0)^\top\)：该点处可行方向需满足 \(d_2 \ge 0\) 且 \(d_1 + d_2 \le 0\)。于是

$$ \boldsymbol{d}^\top \nabla f = c_1 d_1 + c_2 d_2 = c_1 (d_1 + d_2) + (c_2 - c_1) d_2 \le 0 $$

（两项均 \(\le 0\)），满足极大化 FONC。

排除法之下唯一幸存的候选点是 \(\boldsymbol{x}^* = (1, 0)^\top\)；既然最优解存在，它就是唯一最优解（直观验证：\(c_1 > c_2\)，把全部"预算"放在系数大的 \(x_1\) 上，最优值为 \(c_1\)）。

注：原课件此题解答把最优点写为 \((0,1)^\top\)，应为笔误——\(c_1 > c_2\) 时显然应取 \((1,0)^\top\)（目标值 \(c_1 > c_2\)）。

速查表

最优性条件汇总（\(f\) 足够光滑，\(\boldsymbol{F}\) 为黑塞矩阵）：

名称	前提	结论	方向
FONC（一般）	\(\boldsymbol{x}^*\) 局部极小	\(\forall\) 可行 \(\boldsymbol{d}\)：\(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) \ge 0\)	极小 \(\Rightarrow\) 条件
FONC（内点）	\(\boldsymbol{x}^*\) 局部极小且为内点	\(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\)	极小 \(\Rightarrow\) 条件
SONC（一般）	局部极小，且 \(\boldsymbol{d}\) 可行、\(\boldsymbol{d}^\top \nabla f(\boldsymbol{x}^*) = 0\)	\(\boldsymbol{d}^\top \boldsymbol{F}(\boldsymbol{x}^*) \boldsymbol{d} \ge 0\)	极小 \(\Rightarrow\) 条件
SONC（内点）	局部极小且为内点	\(\nabla f = \boldsymbol{0}\) 且 \(\boldsymbol{F} \succeq 0\)	极小 \(\Rightarrow\) 条件
SOSC（内点）	\(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\) 且 \(\boldsymbol{F}(\boldsymbol{x}^*) \succ 0\)	\(\boldsymbol{x}^*\) 严格局部极小	条件 \(\Rightarrow\) 极小

关键反例（考试高频）：

反例	说明
\(f(x) = x^3\)，\(x = 0\)	满足 FONC + SONC 却非极小点 → 必要不充分
\(f = x_1^2 - x_2^2\)，\((0,0)^\top\)	驻点但黑塞不定 → 鞍点，SONC 可排除
\(f(x) = x^4\)，\(x = 0\)	严格极小但 \(f''(0) = 0\) → SOSC 不必要
\(f(x) = x^5\)，\(x = 0\)	一、二、三阶必要条件全满足仍非极小点

记忆主线：

• 必要条件做排除（筛掉非极小点），充分条件做确认（坐实严格极小点）；
• 内点（无约束）三连：\(\nabla f = \boldsymbol{0}\) 找驻点 → \(\boldsymbol{F}\) 定性分类 → 半定时升阶分析；
• 边界点用可行方向版条件，\(\nabla f\) 不必为零；极大化问题全部不等号反向（或对 \(-f\) 套用原条件）。