跳转至

数学预备知识

本页把课件中的数学回顾部分（约 190 页）压缩为速查式整理：只保留后续章节真正用到的定义、结论与公式，基本不展开证明。建议初学时通读一遍建立索引，之后在学习最优性条件及各算法时按需回查。

核心工具速览

后续章节出场频率最高的五件工具：

工具 用在哪里
二次型正定性判定（特征值 / 西尔维斯特准则） 最优性条件中黑塞矩阵的分类
瑞利不等式 \(\lambda_{\min} \lVert \boldsymbol{x} \rVert^2 \le \boldsymbol{x}^\top \boldsymbol{P} \boldsymbol{x} \le \lambda_{\max} \lVert \boldsymbol{x} \rVert^2\) SOSC 的证明、梯度方法收敛性分析
泰勒展开（一元 / 多元二阶） 一切最优性条件与算法收敛性的推导起点
矩阵微分公式 \(D(\boldsymbol{x}^\top \boldsymbol{Q} \boldsymbol{x}) = 2\boldsymbol{x}^\top \boldsymbol{Q}\) 二次型目标函数求梯度
梯度正交于水平集、指向最速上升方向 最速下降法的几何依据

记法与证明方法

  • 集合用大括号表示，如 \(\{x \in \mathbb{R} : x > 5\}\)；\(X \setminus Y\) 表示属于 \(X\) 但不属于 \(Y\) 的元素全体。
  • \(f: X \to Y\) 表示"\(f\) 是从集合 \(X\) 到集合 \(Y\) 的函数"。
  • \(:=\) 表示赋值；\(\triangleq\) 表示"定义为相等"。
  • 证明"\(A \Rightarrow B\)"的四种方法：直接法；对位证明法（证等价命题 \(\lnot B \Rightarrow \lnot A\)）；反证法（证 \(A \wedge \lnot B\) 导出矛盾）；归纳法（验证第 1 项 + 第 \(n\) 项成立推出第 \(n+1\) 项成立）。

向量与矩阵

线性无关与基：向量组 \(\{\boldsymbol{a}_1, \dots, \boldsymbol{a}_k\}\) 线性无关 \(\iff\) \(\alpha_1 \boldsymbol{a}_1 + \cdots + \alpha_k \boldsymbol{a}_k = \boldsymbol{0}\) 只有零解；线性相关 \(\iff\) 其中某个向量可写成其余向量的线性组合。所有线性组合的集合记为 \(\operatorname{span}[\boldsymbol{a}_1, \dots, \boldsymbol{a}_k]\)，是 \(\mathbb{R}^n\) 的子空间。子空间的一组线性无关生成元称为基，基的元素个数（维数 \(\dim \mathcal{V}\)）与基的选取无关，且任意向量在给定基下的表示唯一。

秩：\(\operatorname{rank} \boldsymbol{A}\) = 线性无关列的最大数目 = 列张成子空间的维数 = 非零子式的最高阶数。列乘非零标量、交换列、某列加上其他列的线性组合，都不改变秩。方阵 \(\boldsymbol{A}\) 可逆（非奇异）\(\iff \det \boldsymbol{A} \ne 0 \iff\) 存在 \(\boldsymbol{B}\) 使 \(\boldsymbol{A}\boldsymbol{B} = \boldsymbol{B}\boldsymbol{A} = \boldsymbol{I}_n\)。

线性方程组 \(\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}\)（\(\boldsymbol{A} \in \mathbb{R}^{m \times n}\)）：

解的存在性与唯一性

  • 有解 \(\iff \operatorname{rank} \boldsymbol{A} = \operatorname{rank} [\boldsymbol{A}, \boldsymbol{b}]\)（\(\boldsymbol{b}\) 落在 \(\boldsymbol{A}\) 各列张成的子空间内）；
  • 唯一解 \(\iff \operatorname{rank} \boldsymbol{A} = \operatorname{rank} [\boldsymbol{A}, \boldsymbol{b}] = n\)；
  • 若 \(\operatorname{rank} \boldsymbol{A} = m\)（行满秩），可给 \(n - m\) 个未知数赋任意值、解出其余 \(m\) 个——这正是线性规划中"基本解"的来源。

内积与范数：欧氏内积 \(\langle \boldsymbol{x}, \boldsymbol{y} \rangle = \boldsymbol{x}^\top \boldsymbol{y}\)，满足非负性、对称性、可加性、齐次性；\(\langle \boldsymbol{x}, \boldsymbol{y} \rangle = 0\) 称 \(\boldsymbol{x}, \boldsymbol{y}\) 正交。欧氏范数 \(\lVert \boldsymbol{x} \rVert = \sqrt{\boldsymbol{x}^\top \boldsymbol{x}}\) 满足非负性、齐次性与三角不等式 \(\lVert \boldsymbol{x} + \boldsymbol{y} \rVert \le \lVert \boldsymbol{x} \rVert + \lVert \boldsymbol{y} \rVert\)。

柯西–施瓦茨不等式

\[ |\langle \boldsymbol{x}, \boldsymbol{y} \rangle| \le \lVert \boldsymbol{x} \rVert\, \lVert \boldsymbol{y} \rVert \]

等号成立 \(\iff \boldsymbol{x} = \alpha \boldsymbol{y}\)（共线）。它是"梯度方向是增长最快方向"的全部数学内容。

常用范数家族：

范数 定义
1-范数（曼哈顿） \(\lVert \boldsymbol{x} \rVert_1 = \lvert x_1 \rvert + \cdots + \lvert x_n \rvert\)
2-范数（欧氏） \(\lVert \boldsymbol{x} \rVert_2 = \big( x_1^2 + \cdots + x_n^2 \big)^{1/2}\)
\(p\)-范数 \(\lVert \boldsymbol{x} \rVert_p = \big( \lvert x_1 \rvert^p + \cdots + \lvert x_n \rvert^p \big)^{1/p}\)，\(1 \le p < \infty\)
\(\infty\)-范数 \(\lVert \boldsymbol{x} \rVert_\infty = \max_i \lvert x_i \rvert\)
0-"范数" 非零分量个数（不满足齐次性，并非真正的范数）

特征值、对称矩阵与正交投影

特征值与特征向量：\(\boldsymbol{A}\boldsymbol{v} = \lambda \boldsymbol{v}\)（\(\boldsymbol{v} \ne \boldsymbol{0}\)）\(\iff \det(\lambda \boldsymbol{I} - \boldsymbol{A}) = 0\)（特征方程，\(n\) 次多项式，必有 \(n\) 个根，可重可复）。若 \(n\) 个特征值互异，则对应特征向量线性无关，\(\boldsymbol{A}\) 可相似对角化 \(\boldsymbol{T} \boldsymbol{A} \boldsymbol{T}^{-1} = \operatorname{diag}(\lambda_1, \dots, \lambda_n)\)。

实对称矩阵的谱性质（黑塞矩阵分析的基础）

设 \(\boldsymbol{A} = \boldsymbol{A}^\top\) 为实对称矩阵，则：

  1. 所有特征值都是实数；
  2. 不同特征值对应的特征向量相互正交；
  3. 可取规范正交特征向量拼成正交矩阵 \(\boldsymbol{T}\)（\(\boldsymbol{T}^\top = \boldsymbol{T}^{-1}\)），实现正交对角化 \(\boldsymbol{T}^\top \boldsymbol{A} \boldsymbol{T} = \operatorname{diag}(\lambda_1, \dots, \lambda_n)\)。

正交投影（线性方程组与最小二乘的几何语言）：子空间 \(\mathcal{V}\) 的正交补 \(\mathcal{V}^\perp = \{\boldsymbol{x} : \boldsymbol{v}^\top \boldsymbol{x} = 0,\ \forall \boldsymbol{v} \in \mathcal{V}\}\)；任意 \(\boldsymbol{x} \in \mathbb{R}^n\) 可唯一分解为 \(\boldsymbol{x} = \boldsymbol{x}_1 + \boldsymbol{x}_2\)（\(\boldsymbol{x}_1 \in \mathcal{V}\)，\(\boldsymbol{x}_2 \in \mathcal{V}^\perp\)）。矩阵 \(\boldsymbol{A}\) 的值域 \(\mathcal{R}(\boldsymbol{A}) = \{\boldsymbol{A}\boldsymbol{x}\}\) 与零空间 \(\mathcal{N}(\boldsymbol{A}) = \{\boldsymbol{x} : \boldsymbol{A}\boldsymbol{x} = \boldsymbol{0}\}\) 满足

\[ \mathcal{R}(\boldsymbol{A})^\perp = \mathcal{N}(\boldsymbol{A}^\top), \qquad \mathcal{N}(\boldsymbol{A})^\perp = \mathcal{R}(\boldsymbol{A}^\top) \]

\(\boldsymbol{P}\) 是 \(\mathcal{V} = \mathcal{R}(\boldsymbol{P})\) 上的正交投影算子 \(\iff \boldsymbol{P}^2 = \boldsymbol{P} = \boldsymbol{P}^\top\)。

二次型与正定性

二次型 \(f(\boldsymbol{x}) = \boldsymbol{x}^\top \boldsymbol{Q} \boldsymbol{x}\)。总可以假定 \(\boldsymbol{Q}\) 对称：若不对称，用 \(\boldsymbol{Q}_0 = \frac{1}{2}(\boldsymbol{Q} + \boldsymbol{Q}^\top)\) 替换，二次型的值不变。

类别 定义 记号
正定 \(\boldsymbol{x}^\top \boldsymbol{Q} \boldsymbol{x} > 0\)，\(\forall \boldsymbol{x} \ne \boldsymbol{0}\) \(\boldsymbol{Q} \succ 0\)
半正定 \(\boldsymbol{x}^\top \boldsymbol{Q} \boldsymbol{x} \ge 0\)，\(\forall \boldsymbol{x}\) \(\boldsymbol{Q} \succeq 0\)
负定 / 半负定 反号同理 \(\boldsymbol{Q} \prec 0\) / \(\boldsymbol{Q} \preceq 0\)
不定 既非半正定也非半负定 —

两种实用判定方法（\(\boldsymbol{Q}\) 必须对称）：

判定一：特征值判据

\(\boldsymbol{Q} \succ 0 \iff\) 所有特征值 \(> 0\)；\(\boldsymbol{Q} \succeq 0 \iff\) 所有特征值 \(\ge 0\)（负定/半负定反号同理；有正有负 \(\iff\) 不定）。

依据：正交对角化后 \(\boldsymbol{x}^\top \boldsymbol{Q} \boldsymbol{x} = \sum_{i=1}^n \lambda_i y_i^2\)，二次型的符号完全由特征值符号决定。

判定二：西尔维斯特准则（顺序主子式）

记 \(\Delta_k\) 为 \(\boldsymbol{Q}\) 的 \(k\) 阶顺序主子式（左上角 \(k \times k\) 块的行列式），则

\[ \boldsymbol{Q} \succ 0 \iff \Delta_1 > 0,\ \Delta_2 > 0,\ \dots,\ \Delta_n > 0 \]

易错点：半正定不能只看顺序主子式

  • 顺序主子式全 \(\ge 0\) 只是半正定的必要条件，不充分（反例：\(\operatorname{diag}(0, -1)\) 的顺序主子式为 \(0, 0\)，却是半负定）。半正定的充要条件是所有主子式（任取同标号行列的子式）全 \(\ge 0\)；实践中判半定通常直接算特征值。
  • \(\boldsymbol{Q}\) 不对称时西尔维斯特准则失效，必须先对称化。
  • 判负定可对 \(-\boldsymbol{Q}\) 用正定判据；等价地，顺序主子式负正交错（\(\Delta_1 < 0, \Delta_2 > 0, \dots\)）。

半正定矩阵存在对称半正定平方根 \(\boldsymbol{Q}^{1/2} = \boldsymbol{T} \operatorname{diag}(\lambda_1^{1/2}, \dots, \lambda_n^{1/2}) \boldsymbol{T}^\top\)，满足 \(\boldsymbol{Q}^{1/2} \boldsymbol{Q}^{1/2} = \boldsymbol{Q}\)，于是 \(\boldsymbol{x}^\top \boldsymbol{Q} \boldsymbol{x} = \lVert \boldsymbol{Q}^{1/2} \boldsymbol{x} \rVert^2\)。

瑞利（Rayleigh）不等式

若 \(\boldsymbol{P}\) 为 \(n \times n\) 实对称正定矩阵，则对任意 \(\boldsymbol{x}\)：

\[ \lambda_{\min}(\boldsymbol{P})\, \lVert \boldsymbol{x} \rVert^2 \le \boldsymbol{x}^\top \boldsymbol{P} \boldsymbol{x} \le \lambda_{\max}(\boldsymbol{P})\, \lVert \boldsymbol{x} \rVert^2 \]

它把二次型"夹"在两个特征值之间，是 SOSC 证明与梯度方法收敛速度分析的关键不等式。

矩阵范数

矩阵范数除满足向量范数三公理（非负、齐次、三角不等式）外，本课程还要求次可乘性 \(\lVert \boldsymbol{A}\boldsymbol{B} \rVert \le \lVert \boldsymbol{A} \rVert \lVert \boldsymbol{B} \rVert\)。

  • Frobenius 范数：\(\lVert \boldsymbol{A} \rVert_F = \big( \sum_{i,j} a_{ij}^2 \big)^{1/2}\)，即把矩阵摊平成 \(mn\) 维向量取欧氏范数。
  • 导出范数（由向量范数诱导）：\(\lVert \boldsymbol{A} \rVert = \max_{\lVert \boldsymbol{x} \rVert = 1} \lVert \boldsymbol{A}\boldsymbol{x} \rVert\)，自动满足兼容性 \(\lVert \boldsymbol{A}\boldsymbol{x} \rVert \le \lVert \boldsymbol{A} \rVert \lVert \boldsymbol{x} \rVert\)。

谱范数

由欧氏向量范数导出的矩阵范数为

\[ \lVert \boldsymbol{A} \rVert = \sqrt{\lambda_{\max}(\boldsymbol{A}^\top \boldsymbol{A})} \]

特别地，\(\boldsymbol{A}\) 对称时 \(\lVert \boldsymbol{A} \rVert = \max_i |\lambda_i(\boldsymbol{A})|\)。

几何概念

线段与凸组合：\(\boldsymbol{x}, \boldsymbol{y}\) 之间的线段为 \(\{\alpha \boldsymbol{x} + (1 - \alpha) \boldsymbol{y} : \alpha \in [0, 1]\}\)，其中的点称为 \(\boldsymbol{x}, \boldsymbol{y}\) 的凸组合。

超平面与半空间：\(H = \{\boldsymbol{x} : \boldsymbol{u}^\top \boldsymbol{x} = v\}\)（\(\boldsymbol{u} \ne \boldsymbol{0}\)）是 \(n-1\) 维的；\(\boldsymbol{u}\) 是 \(H\) 的法向量（与 \(H\) 内任意 \(\boldsymbol{x} - \boldsymbol{a}\) 正交）。超平面把空间分成正负两个半空间 \(H_+ = \{\boldsymbol{x} : \boldsymbol{u}^\top \boldsymbol{x} \ge v\}\)、\(H_- = \{\boldsymbol{x} : \boldsymbol{u}^\top \boldsymbol{x} \le v\}\)。线性簇 \(\{\boldsymbol{x} : \boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}\}\) 是有限个超平面的交，维数为 \(\dim \mathcal{N}(\boldsymbol{A})\)；仅当 \(\boldsymbol{b} = \boldsymbol{0}\) 时是子空间。

凸集：\(\Theta\) 是凸集 \(\iff\) 任意两点的连线段都落在 \(\Theta\) 内，即 \(\alpha \boldsymbol{u} + (1-\alpha)\boldsymbol{v} \in \Theta\)，\(\forall \boldsymbol{u}, \boldsymbol{v} \in \Theta,\ \alpha \in [0,1]\)。空集、单点、线段、子空间、超平面、线性簇、半空间、\(\mathbb{R}^n\)、范数球 \(\{\lVert \boldsymbol{x} \rVert \le r\}\) 都是凸集。保凸运算：数乘 \(\beta\Theta\)、和集 \(\Theta_1 + \Theta_2\)、任意多个凸集的交。凸集中不能表示为两个不同点的凸组合的点称为极点。

拓扑概念：点 \(\boldsymbol{x}\) 的 \(\varepsilon\)-邻域为 \(\{\boldsymbol{y} : \lVert \boldsymbol{y} - \boldsymbol{x} \rVert < \varepsilon\}\)。集合含某点的整个邻域 → 该点是内点；每个邻域都同时含集合内外的点 → 边界点。全是内点 → 开集；包含全部边界 → 闭集；能装进有限半径的球 → 有界；闭 + 有界 → 紧集。

魏尔斯特拉斯定理（解的存在性）

连续函数 \(f: \Omega \to \mathbb{R}\) 在紧集 \(\Omega\) 上必能取得极小值（存在 \(\boldsymbol{x}_0 \in \Omega\) 使 \(f(\boldsymbol{x}_0) \le f(\boldsymbol{x})\)，\(\forall \boldsymbol{x} \in \Omega\)）。

这是优化问题"最优解存在"的最常用判据：可行集闭且有界、目标连续，解就一定存在。

多面体与多胞形：有限个半空间的交称为多面体；非空有界的多面体称为多胞形。多面体的 0 维面叫顶点，1 维面叫棱——线性规划单纯形法"沿棱走、在顶点停"的几何舞台就是它。

序列与极限

  • \(\boldsymbol{x}^{(k)} \to \boldsymbol{x}^*\)：\(\forall \varepsilon > 0\)，存在 \(K\) 使 \(k > K\) 时 \(\lVert \boldsymbol{x}^{(k)} - \boldsymbol{x}^* \rVert < \varepsilon\)。收敛序列的极限唯一，且收敛序列必有界。
  • \(\mathbb{R}\) 中单调有界序列必收敛（收敛到上/下确界）。
  • 收敛序列的任意子序列收敛到同一极限；反之，任意有界序列必含收敛子序列（波尔查诺–魏尔斯特拉斯定理）——算法收敛性证明中"先抽收敛子列"的惯用伎俩。
  • \(\boldsymbol{f}\) 在 \(\boldsymbol{x}_0\) 连续 \(\iff\) 对任意 \(\boldsymbol{x}^{(k)} \to \boldsymbol{x}_0\) 都有 \(\boldsymbol{f}(\boldsymbol{x}^{(k)}) \to \boldsymbol{f}(\boldsymbol{x}_0)\)。

矩阵序列的两个结论（迭代算法稳定性的源头）：

  • \(\boldsymbol{A}^k \to \boldsymbol{O} \iff\) \(\boldsymbol{A}\) 的所有特征值满足 \(|\lambda_i(\boldsymbol{A})| < 1\)；
  • 几何级数 \(\boldsymbol{I} + \boldsymbol{A} + \boldsymbol{A}^2 + \cdots\) 收敛 \(\iff \boldsymbol{A}^k \to \boldsymbol{O}\)，此时和为 \((\boldsymbol{I} - \boldsymbol{A})^{-1}\)。

可微性与导数矩阵

可微的本质是仿射近似：\(\boldsymbol{f}: \Omega \to \mathbb{R}^m\) 在 \(\boldsymbol{x}_0\) 可微，指存在线性函数 \(\mathcal{L}\) 使

\[ \lim_{\boldsymbol{x} \to \boldsymbol{x}_0} \frac{\lVert \boldsymbol{f}(\boldsymbol{x}) - \big( \mathcal{L}(\boldsymbol{x} - \boldsymbol{x}_0) + \boldsymbol{f}(\boldsymbol{x}_0) \big) \rVert}{\lVert \boldsymbol{x} - \boldsymbol{x}_0 \rVert} = 0 \]

即 \(\boldsymbol{f}\) 在 \(\boldsymbol{x}_0\) 附近能被仿射函数 \(\mathcal{A}(\boldsymbol{x}) = \boldsymbol{f}(\boldsymbol{x}_0) + D\boldsymbol{f}(\boldsymbol{x}_0)(\boldsymbol{x} - \boldsymbol{x}_0)\) 一阶逼近（一元情形就是切线）。

导数矩阵（雅可比矩阵）：\(D\boldsymbol{f}(\boldsymbol{x}_0) \in \mathbb{R}^{m \times n}\)，第 \((i,j)\) 元为 \(\partial f_i / \partial x_j\)。实值函数（\(m = 1\)）的梯度是行向量导数的转置：\(\nabla f = (Df)^\top\)。梯度的导数是黑塞矩阵 \(\boldsymbol{F}(\boldsymbol{x}) = D^2 f(\boldsymbol{x})\)。

光滑性记号：各分量有 \(p\) 阶连续偏导记为 \(f \in \mathcal{C}^p\)。\(f \in \mathcal{C}^2\) 时黑塞矩阵对称（克莱罗/施瓦茨定理）；二阶偏导不连续时对称性可能失效（课件例 5.1 给出 \(\boldsymbol{F}(\boldsymbol{0}) = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}\) 的经典反例）。

微分法则与常用公式

链式法则（最常用的形态）

\(g: \mathbb{R}^n \to \mathbb{R}\) 与 \(\boldsymbol{f}: \mathbb{R} \to \mathbb{R}^n\) 复合成 \(h(t) = g(\boldsymbol{f}(t))\)，则

\[ h'(t) = Dg(\boldsymbol{f}(t))\, D\boldsymbol{f}(t) = \nabla g(\boldsymbol{f}(t))^\top \boldsymbol{f}'(t) \]

取 \(\boldsymbol{f}(t) = \boldsymbol{x} + t\boldsymbol{d}\)（沿直线运动）就得到最优性条件与一维搜索中反复出现的 \(\phi'(t) = \boldsymbol{d}^\top \nabla g(\boldsymbol{x} + t\boldsymbol{d})\)。

乘积法则：\(h(\boldsymbol{x}) = \boldsymbol{f}(\boldsymbol{x})^\top \boldsymbol{g}(\boldsymbol{x})\) 时 \(Dh = \boldsymbol{f}^\top D\boldsymbol{g} + \boldsymbol{g}^\top D\boldsymbol{f}\)。

矩阵微分公式表（求二次型梯度直接套用）：

函数 导数 \(D(\cdot)\)
\(\boldsymbol{y}^\top \boldsymbol{x}\) \(\boldsymbol{y}^\top\)
\(\boldsymbol{y}^\top \boldsymbol{A} \boldsymbol{x}\) \(\boldsymbol{y}^\top \boldsymbol{A}\)
\(\boldsymbol{x}^\top \boldsymbol{A} \boldsymbol{x}\) \(\boldsymbol{x}^\top (\boldsymbol{A} + \boldsymbol{A}^\top)\)
\(\boldsymbol{x}^\top \boldsymbol{Q} \boldsymbol{x}\)（\(\boldsymbol{Q}\) 对称） \(2 \boldsymbol{x}^\top \boldsymbol{Q}\)，即 \(\nabla(\boldsymbol{x}^\top \boldsymbol{Q} \boldsymbol{x}) = 2\boldsymbol{Q}\boldsymbol{x}\)
\(\boldsymbol{x}^\top \boldsymbol{x}\) \(2 \boldsymbol{x}^\top\)

水平集与梯度

函数 \(f\) 在水平 \(c\) 上的水平集为 \(S = \{\boldsymbol{x} : f(\boldsymbol{x}) = c\}\)（\(\mathbb{R}^2\) 中是等高线）。

梯度的两个几何身份

  1. 梯度正交于水平集：水平集中过 \(\boldsymbol{x}_0\) 的任意光滑曲线，其切向量都与 \(\nabla f(\boldsymbol{x}_0)\) 正交（沿水平集走函数值不变，链式法则立得 \(\nabla f^\top \boldsymbol{v} = 0\)）；
  2. 梯度是最速上升方向：由柯西–施瓦茨不等式，单位方向 \(\boldsymbol{d}\) 上的增长率 \(\nabla f^\top \boldsymbol{d}\) 在 \(\boldsymbol{d} = \nabla f / \lVert \nabla f \rVert\) 时最大。

合起来：增长最快的方向垂直于等高线——这就是梯度方法沿 \(-\nabla f\) 下山的几何依据。

\(f\) 的图像在 \((\boldsymbol{x}_0, f(\boldsymbol{x}_0))\) 处的切平面为 \(z = f(\boldsymbol{x}_0) + Df(\boldsymbol{x}_0)(\boldsymbol{x} - \boldsymbol{x}_0)\)。

课件以 Rosenbrock 函数 \(f(\boldsymbol{x}) = 100(x_2 - x_1^2)^2 + (1 - x_1)^2\) 为水平集示例——它的等高线呈狭长弯曲的"香蕉谷"，是检验优化算法的经典测试函数（谷底平缓，梯度法在其中会剧烈震荡）。

大 O 与小 o 记号

设 \(g\) 在原点邻域内非零（\(\boldsymbol{x} \ne \boldsymbol{0}\) 时 \(g(\boldsymbol{x}) \ne 0\)）：

  • \(\boldsymbol{f}(\boldsymbol{x}) = O(g(\boldsymbol{x}))\)：商 \(\lVert \boldsymbol{f} \rVert / |g|\) 在原点附近有界（同阶或更高阶小），如 \(\sin x = O(x)\)，\(\cos x = O(1)\)；
  • \(\boldsymbol{f}(\boldsymbol{x}) = o(g(\boldsymbol{x}))\)：商趋于 0（严格更高阶小），如 \(x^2 = o(x)\)，\(x^3 = o(x^2)\)；
  • \(o(g) \Rightarrow O(g)\)，反之不成立。

泰勒展开

泰勒定理（一元，带余项）

\(f \in \mathcal{C}^m\) 于 \([a, b]\)，\(h = b - a\)，则

\[ f(b) = f(a) + \frac{h}{1!} f^{(1)}(a) + \frac{h^2}{2!} f^{(2)}(a) + \cdots + \frac{h^{m-1}}{(m-1)!} f^{(m-1)}(a) + R_m \]

拉格朗日型余项 \(R_m = \dfrac{h^m}{m!} f^{(m)}(a + \theta' h)\)，\(\theta' \in (0, 1)\)。用阶记号写：

  • \(f \in \mathcal{C}^m\)：\(f(b) = \displaystyle\sum_{i=0}^{m} \frac{h^i}{i!} f^{(i)}(a) + o(h^m)\)；
  • \(f \in \mathcal{C}^{m+1}\)：\(f(b) = \displaystyle\sum_{i=0}^{m} \frac{h^i}{i!} f^{(i)}(a) + O(h^{m+1})\)。

多元二阶泰勒展开（全课程使用频率最高的公式）

\(f: \mathbb{R}^n \to \mathbb{R}\)，\(f \in \mathcal{C}^2\)，则

\[ f(\boldsymbol{x}) = f(\boldsymbol{x}_0) + \nabla f(\boldsymbol{x}_0)^\top (\boldsymbol{x} - \boldsymbol{x}_0) + \frac{1}{2} (\boldsymbol{x} - \boldsymbol{x}_0)^\top \boldsymbol{F}(\boldsymbol{x}_0) (\boldsymbol{x} - \boldsymbol{x}_0) + o(\lVert \boldsymbol{x} - \boldsymbol{x}_0 \rVert^2) \]

若 \(f \in \mathcal{C}^3\)，余项可加强为 \(O(\lVert \boldsymbol{x} - \boldsymbol{x}_0 \rVert^3)\)。

一阶项决定 FONC，二阶项决定 SONC/SOSC，丢掉余项的二次模型 \(q(\boldsymbol{x})\) 则是牛顿法每步求解的对象——整门课都长在这个公式上。

另外，可微函数 \(\boldsymbol{f}: \Omega \to \mathbb{R}^m\)（\(\Omega\) 为开集）满足中值形式：对任意 \(\boldsymbol{x}, \boldsymbol{y} \in \Omega\)，存在矩阵 \(\boldsymbol{M}\) 使 \(\boldsymbol{f}(\boldsymbol{x}) - \boldsymbol{f}(\boldsymbol{y}) = \boldsymbol{M}(\boldsymbol{x} - \boldsymbol{y})\)。

速查表

结论 内容
方程组有解 \(\operatorname{rank} \boldsymbol{A} = \operatorname{rank}[\boldsymbol{A}, \boldsymbol{b}]\)；唯一解还需 \(= n\)
柯西–施瓦茨 \(\lvert \langle \boldsymbol{x}, \boldsymbol{y} \rangle \rvert \le \lVert \boldsymbol{x} \rVert \lVert \boldsymbol{y} \rVert\)，共线时取等
实对称矩阵 特征值实、特征向量正交、可正交对角化
\(\boldsymbol{Q} \succ 0\) 判定 特征值全正 \(\iff\) 顺序主子式全正（需对称）
半正定判定 特征值全 \(\ge 0\) \(\iff\) 所有主子式 \(\ge 0\)（顺序主子式不够）
瑞利不等式 \(\lambda_{\min} \lVert \boldsymbol{x} \rVert^2 \le \boldsymbol{x}^\top \boldsymbol{P} \boldsymbol{x} \le \lambda_{\max} \lVert \boldsymbol{x} \rVert^2\)
谱范数 \(\lVert \boldsymbol{A} \rVert = \sqrt{\lambda_{\max}(\boldsymbol{A}^\top \boldsymbol{A})}\)
紧集 闭 + 有界；连续函数在紧集上必取得极小（魏尔斯特拉斯）
二次型梯度 \(\nabla (\boldsymbol{x}^\top \boldsymbol{Q} \boldsymbol{x}) = 2 \boldsymbol{Q} \boldsymbol{x}\)（\(\boldsymbol{Q}\) 对称）
梯度几何 正交于水平集，指向最速上升方向
二阶泰勒 \(f(\boldsymbol{x}_0 + \boldsymbol{d}) = f(\boldsymbol{x}_0) + \nabla f^\top \boldsymbol{d} + \frac{1}{2} \boldsymbol{d}^\top \boldsymbol{F} \boldsymbol{d} + o(\lVert \boldsymbol{d} \rVert^2)\)