1. 最优性条件 (Optimality Condition)

1.1. 优化问题

任何一个优化问题，无论是在机器学习、金融、还是工程领域，我们都可以用三个核心组件来描述它：

目标函数 (Objective Function) $f:\mathbb{R}^n\mapsto\mathbb{R}$ 这是我们希望最小化（或最大化）的那个函数。在机器学习中，这通常是损失函数 (Loss Function)，比如衡量模型预测值与真实值差距的均方误差。
优化变量 (Optimization Variable) $x\in\mathbb{R}^n$ 这是我们可以调整和控制的变量，以期改变目标函数的值。在机器学习中，$x$ 通常是模型的参数或权重 (weights)。我们训练模型的过程，就是在寻找一组最优的权重 $x$ 来让损失函数 $f(x)$ 最小。
约束 (Constraints) 这些是优化变量 $x$ 必须满足的规则或限制。它们分为两种：
- 不等式约束 (Inequality constraints) $g_i(x)≤0$：规定了变量的取值范围。比如，某个模型参数必须是正数，就可以写成 $−x_j≤0$。
- 等式约束 (Equality constraints) $h_j(x)=0$：规定了变量必须满足的精确关系。比如，在投资组合优化中，所有投资权重之和必须恰好等于1，即 $∑x_i−1=0$。

优化问题的两大类别

线性规划 (Linear Programming, LP)

线性规划的数学形式： $$\begin{aligned}\min_{x}&c^\top x\\mathrm{s.t.}&Gx\leq h\&Ax=b\end{aligned}$$ 目标函数 ($c^⊤x$) 和所有约束函数 ($Gx≤h,Ax=b$) 都是关于变量 $x$ 的线性函数（或者叫仿射函数）。这意味着函数图像是直线、平面或超平面，没有任何弯曲。

一般（连续）优化 (General Optimization)

更通用的形式： $$\begin{aligned}\underset{x}{\operatorname*{\operatorname*{\min}}}&f(x)\s.t.&g_i(x)\leq0,\quad i=1,\ldots,m\&h_j(x)=0,\quad j=1,\ldots,p\end{aligned}$$ 这里的目标函数 $f(x)$ 和约束函数 $g_i(x),h_j(x)$ 可以是任何连续函数，比如二次函数、指数函数、或者神经网络那样极其复杂的非线性函数。

这里我们引入可行域和问题分类的概念：

可行域 (Feasible Region) $Ω$

所有能够同时满足所有约束条件的点的集合，被称为可行域。我们可以把它想象成变量 x 的“合法活动范围”。它的数学定义是： $$\Omega={x\in\mathbb{R}^n:g_i(x)\leq0,h_j(x)=0,\forall i=1,\ldots,m,j=1,\ldots,p}$$ 有了可行域的概念，任何优化问题都可以被简洁地写成： $$\min_{x\in\Omega}f(x)$$ 根据可行域 $Ω$ 的形态，我们可以将优化问题分为两类：

无约束优化 (Unconstrained Optimization) 当问题没有任何约束时，可行域就是整个 $n$ 维空间，即 $\Omega=\mathbb{R}^n$。这意味着 $x$ 可以取任何值。比如，最简单的线性回归就是无约束优化问题。我们后面课程学到的梯度下降法等，首先就是为了解决这类问题而设计的。
约束优化 (Constrained Optimization) 当问题存在至少一个约束时，可行域 $Ω$ 就是 $\mathbb{R}^n$ 的一个子集。最优解必须在这个子集内部或边界上寻找。这类问题通常更复杂，需要用到拉格朗日乘子法等更高级的技巧来求解。

1.2. 全局最优与局部最优

假设我们要在一个可行域 $Ω$ 中寻找最优解 $x^∗$。

全局最小值点 (Global Minimum Point)

$x^∗$ 是一个全局最小值点，如果满足： $$f(x)\geq f(x^*)\quad\forall x\in\Omega$$

局部最小值点 (Local Minimum Point)

$x^∗$ 是一个局部最小值点，如果存在一个 $ϵ>0$，使得： $$f(\mathbf{x})\geq f(\mathbf{x}^{})\quad\forall\mathbf{x}\in\Omega,|\mathbf{x}-\mathbf{x}^{}|\leq\epsilon.$$

严格局部最小值点 (Strict Local Minimum Point) $x^∗$ 是一个严格局部最小值点，如果存在一个 $ϵ>0$，使得： $$f(\mathbf{x})>f(\mathbf{x}^{})\quad\forall\mathbf{x}\in\Omega,|\mathbf{x}-\mathbf{x}^{}|\leq\epsilon.$$

1.3. 梯度

对于一个输入为 $n$ 维向量 $x$，输出为一个标量（单个数值）的多元函数 $f:\mathbb{R}^n\mapsto\mathbb{R}$，它在点 $x$ 处的梯度写作 $∇_xf(x)$，是一个包含了所有偏导数的 $n$ 维向量： $$\nabla_xf(x)=\begin{pmatrix}\frac{\partial f(x)}{\partial x_1}\\vdots\\frac{\partial f(x)}{\partial x_n}\end{pmatrix}$$ 向量中的每一个分量 $\frac{\partial f(x)}{\partial x_i}$ 是函数 f 对其中一个变量 xi 的偏导数。它衡量的是，在点 $x$ 处，如果我们只让 $x_i$ 发生微小的变动，函数值 $f(x)$ 会变化多快。

知道了函数在一点的变化趋势后，我们就可以用一个简单的线性函数去近似一个复杂的非线性函数。

一阶泰勒展开： $$f(x^{\prime})\approx f(x)+\nabla_xf(x)^\top(x^{\prime}-x)$$ 对于一维函数，这个一阶近似就是函数曲线在 $x$ 点的切线。复杂的曲线和其简单的切线近似之间，存在一个误差： $$f(x^{\prime})-(f(x)+\nabla_xf(x)^\top(x^{\prime}-x))$$

当 $x′$ 离 $x$ 越远，这个差距就越大，说明我们的线性近似就越不准确。
当 $x′$ 无限逼近 $x$ 时，这个差距会趋向于零。这保证了在足够小的局部范围内，这种线性近似是非常精确的。

线性函数的梯度 (Gradient of a Linear function)

线性函数形式为： $$f(x)=a^\top x$$ 其中，$a$ 和 $x$ 都是 $d$ 维向量。这个函数本质上是向量 $a$ 和 $x$ 的点积，即 $f(x)=a_1x_1+a_2x_2+\cdots+a_dx_d$。这个函数的梯度就是向量 $a$ 本身： $$\nabla(a^\top x)=a$$ 2. 二次函数的梯度 (Gradient of a Quadratic Function)

二次函数一般形式为： $$f(x)=\frac{1}{2}x^\top Ax+b^\top x$$ 其中，$x$ 和 $b$ 是 $n$ 维向量，$A$ 是一个 $n×n$ 的矩阵。梯度公式是： $$\nabla f(x)=\frac{1}{2}(A+A^\top)x+b$$ 在绝大多数机器学习和优化问题中，我们遇到的矩阵 A 都是对称的（Symmetric Matrix），即 $A=A^⊤$。当 $A$ 是对称矩阵时，$A+A^⊤=A+A=2A$。此时，梯度公式可以大大简化： $$\nabla f(x) = \frac{1}{2}(2A)x + b = Ax + b \quad (当 A 是对称矩阵时)$$

1.4. 海森矩阵 (Hessian Matrix)

对于一个输入为 $n$ 维向量，输出为一个标量的函数 $f:\mathbb{R}^n\mapsto\mathbb{R}$，它的海森矩阵是一个 $n×n$ 的方阵，包含了函数所有的二阶偏导数。它的符号是 $\nabla^2f(x)$ $$\nabla^2f(x)=\begin{pmatrix}\frac{\partial^2f(x)}{\partial x_1^2}&\frac{\partial^2f(x)}{\partial x_1\partial x_2}&\cdots&\frac{\partial^2f(x)}{\partial x_1\partial x_n}\\frac{\partial^2f(x)}{\partial x_2\partial x_1}&\frac{\partial^2f(x)}{\partial x_2^2}&\cdots&\frac{\partial^2f(x)}{\partial x_2\partial x_n}\\vdots&\vdots&\ddots&\vdots\\frac{\partial^2f(x)}{\partial x_n\partial x_1}&\frac{\partial^2f(x)}{\partial x_n\partial x_2}&\cdots&\frac{\partial^2f(x)}{\partial x_n^2}\end{pmatrix}\in\mathbb{R}^{n\times n}$$

对角线元素 ($\frac{\partial^2f(x)}{\partial x_i^2}$): 这是函数对某个单一变量 xi 的二阶导数。它衡量的是，如果只沿着 $x_i$ 轴方向移动，函数图像是向上弯曲（像碗底，$f′′(x)>0$）还是向下弯曲（像山顶，$f′′(x)<0$）。
非对角线元素 ($\frac{\partial^2f(x)}{\partial x_i\partial x_j}$): 这是混合偏导数。它衡量的是，当我们在 $x_j$ 方向上移动时，$f(x)$ 在 $x_i$ 方向上的“坡度”是如何变化的。这捕捉了函数曲面的“扭曲”程度。
一个关键性质：对于绝大多数在机器学习中遇到的函数，求导的顺序不影响结果，即 $\frac{\partial^2f(x)}{\partial x_i\partial x_j}=\frac{\partial^2f(x)}{\partial x_j\partial x_i}$。这意味着海森矩阵永远是一个对称矩阵 。

海森矩阵描述了函数在某一点附近的局部几何形状，尤其是在我们找到了一个“平坦”点（即梯度为零的点）之后，用来区分这个点到底是什么：

如果海森矩阵是正定的 (Positive Definite)：说明函数在该点向所有方向都向上弯曲。这个点是一个局部最小值点（碗底）。
如果海森矩阵是负定的 (Negative Definite)：说明函数在该点向所有方向都向下弯曲。这个点是一个局部最大值点（山顶）。
如果海森矩阵是不定的 (Indefinite)：说明函数在该点在某些方向向上弯曲，在另一些方向向下弯曲。这个点是一个鞍点 (Saddle Point)（像马鞍的中心）。

二次函数的海森矩阵。函数形式为： $$f(x)=\frac{1}{2}x^\top Ax+b^\top x$$ 其海森矩阵为： $$\nabla^2f(x)=\frac{1}{2}(A+A^\top)$$ 如同梯度一样，在机器学习中我们遇到的矩阵 $A$ 绝大多数都是对称的 ($A=A^⊤$)。在这种情况下，海森矩阵的公式就简化为： $$\nabla^2f(x)=\frac{1}{2}(A+A)=A\quad(\text{当 }A\text{ 是对称矩阵时})$$ 因此对于一个由对称矩阵 $A$ 定义的二次函数，其曲率就完全由矩阵 $A$ 本身来定义。如果矩阵 $A$ 是正定的，那么这个函数就是一个向上开口的、凸的碗形。

1.5. 方向导数 (Directional Derivative)

我们已经知道，梯度 $∇f(x)$ 指向了上山最快的方向。但是，在很多实际情况中，我们不一定能或者想朝着这个方向走。

如果我站在山坡上的 $x$ 点，不朝着最陡峭的方向，而是朝着我任意指定的一个方向 $d$（比如正东方向）走，那么我脚下的坡度是多少？

我们定义一个辅助函数： $$g(\alpha)=f(x+\alpha d),\quad\forall\alpha\in\mathbb{R}$$

$x$ 是我们固定的起点。
$d$ 是我们选择的方向（一个向量）。
$α$ 是一个标量，代表我们沿着方向 d 行进的距离。
所以，$g(α)$ 的含义是：从点 $x$ 出发，沿着方向 $d$ 走 $α$ 那么远之后，我们所处位置的海拔高度。它相当于从多元函数 $f$ 上“切”下来了一个一维的剖面。

我们想知道在起点（即 $α=0$ 时）的瞬时坡度，这其实就是在求一元函数 $g(α)$ 在 $α=0$ 处的导数，即 $g′(0)$。

结论： $$g^{\prime}(0)=\nabla f(x)^\top d$$ 我们不需要为了计算每一个方向的导数而重新进行复杂的求导。一个函数在某一点 $x$ 处所有的方向导数信息，已经全部被浓缩在梯度 ∇f(x) 这一个向量中。

一个更通用的结论： $$g^{\prime}(\alpha)=\nabla f(x+\alpha d)^\top d$$ 这说明，在剖面函数 $g(α)$ 上的任意一点 $α$，其切线斜率等于多元函数 f 在对应点 $x+αd$ 处的梯度与方向 $d$ 的点积。

1.6. 曲率

我们定义了函数 $g(α)=f(x+αd)$，它代表从点 $x$ 沿着方向 $d$ 行走的“海拔剖面图”。我们已经知道，它的一阶导数 $g′(0)$ 代表了在这个方向上的初始坡度。

现在，我们自然会问下一个问题：

在这个方向 d 上，函数是向上弯曲（像走进一个碗里），还是向下弯曲（像走过一个山丘）？

这个问题，本质上是在问这个一维剖面函数 $g(α)$ 的曲率，也就是它的二阶导数 $g′′(0)$。

假设 $f$ 的梯度可微（即 $f$ 二阶可微），定义 $g(α)=f(x+αd)$。那么： $$g^{\prime\prime}(0)=d^\top\nabla^2f(x)d$$

$g′′(0)$：是在 $x$ 点，沿着方向 $d$ 的曲率。
$d^⊤∇^2f(x)d$：是一个所谓的二次型 (Quadratic Form)。它把海森矩阵 $∇^2f(x)$ “夹在”了方向向量 d 的转置 $d^⊤$和它自身 $d$ 之间。

这个定理是二阶优化条件的理论基础。判断一个梯度为零的点 $x^∗$ 是否为局部最小值的二阶必要条件是：它的海森矩阵 $∇^2f(x^∗)$ 是半正定的。

一个矩阵是半正定的，定义就是对于任意非零向量 $d$，都满足 $d^⊤∇^2f(x^∗)d≥0$。即： $$g''(0) = d^\top \nabla^2 f(x^*) d \geq 0 \text{ （对于任意方向 } d \text{）}$$ 因此这个判别的意思是：在一个点 $x^∗$ 是局部最小值的必要条件是，从这个点出发，无论你朝哪个方向走，路径的初始曲率都必须是向上弯曲的（或者至少是平的）。

1.7. 二阶泰勒近似 (Second-order Taylor Approximation)

二阶泰勒近似的公式： $$f(x)\approx f(x^0)+\nabla_xf(x^0)^\top(x-x^0)+\frac{1}{2}(x-x^0)^\top\nabla^2f(x^0)(x-x^0)$$

第零项: $f(x^0)$ 这是基准值或锚点。它保证了我们的近似函数在点 $x_0$ 处的函数值与原函数完全一致。
第一项: $\nabla_xf(x^0)^\top(x-x^0)$ 这是线性修正项。它利用 $x_0$ 点的梯度（坡度）信息，保证了我们的近似函数在 $x_0$ 点的切线与原函数完全一致。
第二项: $\frac{1}{2}(x-x^0)^\top\nabla^2f(x^0)(x-x^0)$ 这是新增的二次修正项。它利用 $x_0$ 点的海森矩阵（曲率）信息，保证了我们的近似函数在 $x_0$ 点的弯曲程度与原函数完全一致。

直接最小化一个复杂的函数 $f(x)$ 可能非常困难。但是，最小化一个二次函数却非常简单（对于一个碗状的二次函数，我们甚至可以直接用公式解出它的最低点）。

这启发了一种非常强大的优化算法牛顿法 (Newton's Method)：

建模 (Model)：在当前点 $x_k$，我们对真实但复杂的目标函数 $f(x)$ 建立一个二阶泰勒近似，得到一个简单的二次函数模型 $m(x)$。
求解 (Solve)：我们直接求解这个二次函数模型 $m(x)$ 的最小值点。
更新 (Update)：将我们找到的这个最小值点作为下一个迭代点 $x_{k+1}$。
重复：回到第一步，在新的点 $x_{k+1}$ 重新建立模型并求解。

牛顿法通常比梯度下降收敛得快得多。它的缺点是计算海森矩阵并求解线性方程组的计算量巨大，尤其是在高维问题中（比如深度学习），这使得它的直接应用受到了限制。

1.8. 一阶必要条件 (First-Order Necessary Conditions, FONC)

1.8.1. 可行方向

可行方向的定义，通俗地讲，就是在不立即“撞墙”或“穿墙而出”的前提下，你能够迈出第一步的所有方向。

设 $x∈Ω$。一个非零向量 $d$ 被称为在 $x$ 点的一个可行方向，如果存在一个很小的正数 $δ>0$，使得对于任何步长 $α$（其中 $0<α≤δ$），点 $x+αd$ 都仍然在可行域 $Ω$ 内。

![[Pasted image 20250930144644.png]]

1.8.2. FONC

我们定义约束问题下的最小值点。

思想：如果你正站在花园里的真正最低点 $x^∗$，那么必然会出现一个现象：无论你沿着任何一个“可行的”方向迈出一步，你的海拔（函数值）要么增加，要么保持不变，但绝不可能降低。如果存在任何一个可行的方向能让你海拔降低，那说明你现在所处的位置就不是最低点。

设 $f$ 是在可行域 $Ω$ 上的可微函数。如果 $x^∗$ 是 $f$ 在 $Ω$ 上的一个局部最小值点，那么对于在 $x^∗$ 点的每一个可行方向 $d$，都必须满足： $$\nabla f(x^*)^\top d\geq0$$ 需要注意的是，无约束的规则是约束规则的一个特例。

当 $x^∗$ 是一个内部点时：想象一下你正站在花园的正中央，而不是边界上。这时，四面八方任何一个方向都是可行方向。
根据本页的定理，对于任何方向 $d$，都必须满足 $\nabla f(x^*)^\top d\geq0$。
但如果对于向量 d 成立，那么对于它的反方向 −d 也必须成立，即 $\nabla f(x^)^\top {-d}\geq0$，也就是 $-\nabla f(x^)^\top d\geq0$。
一个数值（这里是 $∇f(x^∗)^⊤d$）既要大于等于0，又要小于等于0，那么它只可能等于0。
由于这个结论对所有方向 $d$ 都成立，那么唯一可能就是梯度向量本身为零向量，即 $∇f(x^∗)=0$。

下面我们考虑内部点的情况，首先我们定义内部点：

一个点 $x$ 是可行域 $Ω$ 的一个内部点，如果存在一个很小的正数 $δ>0$，使得所有与 $x$ 的距离不超过 $δ$ 的点 $x′$，都仍然在 $Ω$ 内部。

这个时候实际上等于无约束的情况，$f$ 是在 $Ω$ 上的可微函数。如果 $x^∗$ 是一个局部最小值点，并且它还是一个内部点，那么它的梯度必须为零： $$\nabla f(x^*)=0$$

需要注意的是，FONC只是一个必要条件，而不是充分条件。

在优化中，“如果 $x^∗$ 是一个局部最小值点，那么它的一阶导数（梯度）必然为零”。这个是我们已经知道的 FONC。它能帮我们筛选候选人。但是 FONC ($∇f(x)=0$) 只关心“平不平”，不关心“凹凸性”。一个点的切线是水平的，它可能是在一个碗的底部（局部最小）、一个山丘的顶部（局部最大），或者是一个马鞍的中心（鞍点）。FONC会把所有这些点都找出来，无法区分它们。

1.9. 二阶必要条件 (Second-Order Necessary Conditions, SONC)

设函数 $f$ 是二次连续可微的。如果 $x^∗$ 是一个局部最小值点，那么对于任何一个可行方向 $d$，以下两条都必须成立：

$\nabla f(x^*)^\top d\geq0$
如果 $\nabla f(x^)^\top d=0$，那么 $d^\top\nabla^2f(x^)d\geq0$。

第二点的证明如下：

前提：我们只关注那些“可疑”的方向 $d$，即坡度为零的方向，满足 $\nabla f(x^*)^\top d=0$。
构造剖面函数：和之前一样，我们构造一维剖面函数 $g(\alpha)=f(x^+\alpha d)$。根据已知定理，我们知道它的初始坡度 $g^{\prime}(0)=\nabla f(x^)^\top d=0$，初始曲率 $g^{\prime\prime}(0)=d^\top\nabla^2f(x^*)d$。
利用最优性：因为 $x^∗$ 是局部最小值，所以沿着 $d$ 方向走一小步，函数值不能减小，即 $g(α)≥g(0)$。
利用泰勒展开：根据泰勒展开（也是二阶导数的定义），我们知道：$g^{\prime\prime}(0)=\lim_{\alpha\to0^+}\frac{g(\alpha)-g(0)-g^{\prime}(0)\alpha}{\alpha^2/2}$
代入并推导：
- 因为我们已经知道 $g′(0)=0$，上式简化为 $\lim\frac{g(\alpha)-g(0)}{\alpha^2/2}$。
- 又因为 $g(α)−g(0)≥0$，而分母 $α^2/2$ 显然为正，所以整个极限值必然大于等于零。
- 因此我们得到 $g′′(0)≥0$。
得出结论：将 $g′′(0)$ 的公式代入，我们最终证明了 $d^\top\nabla^2f(x^*)d\geq0$。

当问题是无约束的，或者我们正在考察一个可行域的内部点 (interior point) 时，这个条件可以被简化和加强。

设函数 $f$ 是二次连续可微的。如果 $x^∗$ 是一个内部的局部最小值点，那么：

$\nabla f(x^*)=0$
$d^\top\nabla^2f(x^*)d\geq0,\forall d\in\mathbb{R}^n$，也就是说，海森矩阵 $∇^2f(x^∗)$ 是半正定的 (positive semi-definite)。

注意，SONC依然是一个必要条件，必要条件是用来做“排除法”的。它们是否决工具。

驻点 (Stationary Point)：任何满足 $∇f(x)=0$ 的点，我们称之为驻点或临界点。
SONC的作用：我们可以用二阶必要条件来审查这个名单。如果某个驻点 $x^∗$ 的海森矩阵不是半正定的（比如它有负的特征值），我们就可以百分之百地确定，这个点绝对不是一个局部最小值，可以直接从名单中划掉。

1.10.二阶充分条件 (Second-Order Sufficient Conditions, SOSC)

设函数 $f$ 是二次连续可微的，且 $x^∗$ 是一个内部点。如果 $x^∗$ 同时满足以下两个条件：

$∇f(x^∗)=0$ （它是一个驻点）
$∇^2f(x^∗)$ 是正定的 (positive definite) 那么，$x^∗$ 必定是一个严格的局部最小值点。

因此，对于无约束优化问题。对于任何一个给定的函数，标准的解题流程是：

第一步：寻找候选点
- 解方程 $∇f(x)=0$，找出所有的驻点。
第二步：审查候选点
- 对每一个驻点 $x^∗$，计算其海森矩阵 $∇^2f(x^∗)$。
- 计算海森矩阵的特征值。
  - 如果所有特征值都严格大于 0 ⟹ 正定矩阵 ⟹ $x^∗$ 是一个严格局部最小值点 (SOSC)。
  - 如果所有特征值都严格小于 0 ⟹ 负定矩阵 ⟹ $x^∗$ 是一个严格局部最大值点。
  - 如果特征值中有正有负 ⟹ 不定矩阵 ⟹ $x^∗$ 是一个鞍点。
  - 如果有特征值为0，其余同号 ⟹ 半正定/半负定 ⟹ 测试无结论，需要用其他更高阶的方法分析。

1.11. 最大化问题

整个最大化问题简要来说就是对最小化问题的反转：

一阶必要条件 (FONC for Maximization)

如果 $x^∗$ 是一个局部内部最大值点，那么它的梯度必须为零： $$\nabla f(x^*)=0$$ 2. 二阶必要条件 (SONC for Maximization)

如果 $x^∗$ 是一个局部内部最大值点，那么它的梯度必须为零，并且它的海森矩阵必须是负半定的： $$\nabla^2f(x^*)\text{ is negative semidefinite}$$ 3. 二阶充分条件 (SOSC for Maximization)

如果一个点 $x^∗$ 的梯度为零，并且它的海森矩阵是负定的，那么它必定是一个严格的局部最大值点。 $$\nabla f(x^)=0\mathrm{~and~}\nabla^2f(x^)\text{ is negative definite}$$

1.12. 补充推论

如果一个问题只有一个驻点，并且我们能确定该问题一定存在一个最优解，那么这个唯一的驻点就必然是全局最优点。
对于凸函数，任何局部最小值都必定是全局最小值。对于凹函数，任何局部最大值必定是全局最大值。

1.13. 鞍点 (Saddle Points)

驻点 (Stationary Point)：任何满足梯度为零 $∇f(x)=0$ 的点。这是我们之前所有分析的起点，包含了所有“平坦”的点。
鞍点 (Saddle Point)：一个驻点，如果它既不是局部最小值点，也不是局部最大值点，那么它就是一个鞍点。

假设 $x^∗$ 是一个驻点，并且它的海森矩阵 $∇^2f(x^∗)$ 是不定的，那么 $x^∗$ 就是一个鞍点。这意味着在某些方向上曲率 > 0（向上弯曲），同时在另一些方向上曲率 < 0（向下弯曲）。

一个对称矩阵是不定的，一个充分必要条件是它既有正的特征值，也有负的特征值。

2. 凸优化 (Convex Optimization)

2.1. 凸函数

一个函数是凸的，最直观的特征就是它的图像是“碗”形的。

这个“碗”形有一个非常明确的几何性质：

在函数图像上任意取两个点，然后用一条直线（我们称之为弦 (chord)）将它们连接起来。那么，位于这两点之间的那段函数图像，必须完全位于这条弦的下方（或恰好在弦上）。

数学定义：

一个函数 $f:\mathbb{R}^n\mapsto\mathbb{R}$ 被称为凸函数，如果对于其定义域中的任意两点 $x,y$ 和任意一个在 [0,1] 区间内的数 $θ$，都满足以下不等式： $$f(\theta x+(1-\theta)y)\leq\theta f(x)+(1-\theta)f(y)$$

相似的，一个函数 $f$ 是凹的，如果 $−f$ 是凸的。

另外，一个函数是仿射的，如果它既是凸的又是凹的。仿射函数就是我们通常所说的线性函数，它的标准形式是： $$f(x)=a^\top x+b$$

![[Pasted image 20250930153948.png]]

2.2. 严格凸性 (Strict Convexity)

严格凸性的数学定义，就是将之前凸函数定义中的不等号“≤”换成严格的“<”，从图像上来说，就是不允许有任何平坦的部分，整个图像必须严格向下弯曲。

一个函数 $f:\Omega\mapsto\mathbb{R}$ 被称为严格凸函数，当且仅当对于任意两个不同的点 $x_1\neq x_2\in\Omega$ 以及任意一个在 (0,1) 开区间内的数 $α$，都满足以下不等式： $$f(\alpha x_1+(1-\alpha)x_2)<\alpha f(x_1)+(1-\alpha)f(x_2)$$ 严格凸性核心影响在于最优解的唯一性。

对于一个凸函数（可能有平坦区域）：
- 如果它存在一个最小值，那么这个最小值是唯一的。
- 但是，达到这个最小值的点（即最优解 $x^∗$）可能不唯一。
对于一个严格凸函数：
- 如果它存在一个最小值，那么这个最小值是唯一的，并且达到这个最小值的点也是唯一的。
- 严格凸性保证了最优解的唯一性。

![[Pasted image 20250930154435.png]]

2.3. 一阶条件 (First-order Condition)

对于一个凸函数，如果你在任意一点画一条切线，那么整条函数曲线都将位于这条切线的上方（或恰好在切线上）。

换句话说，凸函数的任何一条切线，都是对整个函数的“全局下估计”。

数学定义：一个可微的函数 $f:\mathbb{R}^n\mapsto\mathbb{R}$ 是凸函数，当且仅当 (if and only if) 对于其定义域中的任意两点 $x,y$，都满足： $$f(y)\geq f(x)+\nabla f(x)^\top(y-x)$$ 下面进行证明：

2.3.1. 原始定义 ⟹ 一阶条件

我们假设 f 是凸函数，因此它必须满足“弦在图之下”的原始定义（为了方便，这里把 $θ$ 换成了 $t$）： $$f((1-t)x + ty) \le (1-t)f(x) + tf(y), \quad \forall t \in (0,1)$$为了方便分析从点 $x$ 开始的变化，引入方向向量 $d=y−x$，并将中间点 $(1−t)x+ty$ 等价地写为 $x+td$。于是，原始定义就变成了： $$f(x+td)\leq(1-t)f(x)+tf(y)$$ 代数变形，最终得到： $$\frac{f(x+td)-f(x)}{t}\leq f(y)-f(x)$$

左边：这是连接点 $(x,f(x))$ 和中间点 $(x+td,f(x+td))$ 的小割线的斜率。可以想象成图中连接 $x$ 和 $x+td$ 两点的那段绿色直线的斜率。
右边：为了方便比较，我们可以认为这是连接点 $(x,f(x))$ 和终点 $(y,f(y))$ 的大割线的斜率（假设 $x$ 和 $y$ 的水平距离为1）。可以想象成图中连接 $x$ 和 $y$ 两点的那段更长的绿色直线的斜率。

整个不等式的含义：对于一个凸函数（碗状），从一个固定点出发，割线的斜率是单调递增的。也就是说，连接起点和一个很近的点的割线，要比连接起点和一个很远的点的割线更平缓。这个代数不等式，其实是在描述凸函数“斜率越来越陡”的性质。

我们对不等式 $\frac{f(x+td)-f(x)}{t}\leq f(y)-f(x)$ 两边同时取极限：

右边 $f(y)−f(x)$ 与 $t$ 无关，所以不变。
左边 $\lim_{t\to0}\frac{f(x+td)-f(x)}{t}$：
- 这正是方向导数的定义。它表示函数 $f$ 在点 $x$ 处，沿着方向 $d$ 的瞬时变化率。
- 我们已经知道，这个方向导数就等于梯度和方向向量的点积：$\nabla f(x)^\top d$。
- 几何上，当 $t→0$ 时，不断变短的割线（绿色），其极限位置就是点 $x$ 处的切线（红色）。因此，割线斜率的极限，就是切线的斜率。

![[Pasted image 20250930155252.png]]

因为在取极限之前，不等式 $≤$ 对于所有 $t>0$ 都成立，那么在极限状态下它也必然成立。于是我们得到： $$\nabla f(x)^\top d \le f(y) - f(x)

$$最后，我们把 $d = y-x$ 代回去：$$

\nabla f(x)^\top (y-x) \le f(y) - f(x)$$稍作整理，就得到了我们想要证明的一阶条件： $$f(y)\geq f(x)+\nabla f(x)^\top(y-x)$$

2.3.2. 一阶条件 ⟹ 原始定义

们假设“切线在图之下”的规则（一阶条件）是成立的。即对于任意两点 $x,y$： $$f(y)\geq f(x)+\nabla f(x)^\top(y-x)$$ 我们将点 $z = \theta x + (1-\theta)y$ 作为切点，画一条切线。根据我们的假设，这条切线必须位于整个函数图像的下方。

从 $z$ 看向 $x$：
- 函数在 $x$ 点的真实值 $f(x)$，必须大于或等于 $z$ 点的切线在 $x$ 处的高度。
- 数学上，这意味着：$f(x)≥f(z)+∇f(z)^⊤(x−z)$。
从 $z$ 看向 $y$：
- 同样，函数在 $y$ 点的真实值 $f(y)$，也必须大于或等于 $z$ 点的切线在 $y$ 处的高度。
- 数学上，这意味着：$f(y)≥f(z)+∇f(z)^⊤(y−z)$。

我们给第一个不等式（关于 $f(x)$ 的）乘以权重 $θ$。
我们给第二个不等式（关于 $f(y)$ 的）乘以权重 $(1−θ)$。

相加后的结果：

左边： $\theta f(x)+(1-\theta)f(y)$
右边：$\theta\left(f(z)+\nabla f(z)^\top(x-z)\right)+(1-\theta)\left(f(z)+\nabla f(z)^\top(y-z)\right)$

经过化简，我们得到结果： $$\theta f(x) + (1-\theta)f(y) \ge f(z)$$ 将 $z = \theta x + (1-\theta)y$ 代回去，得到“弦在图之上”的原始定义。 $$\theta f(x) + (1-\theta)f(y) \ge f(\theta x + (1-\theta)y) $$

2.4. 二阶条件 (Second-Order Characterization)

一个“当且仅当”的等价条件，设：

$f$ 是在一个凸集 $Ω$ 上二次连续可微的函数。那么，$f$ 在 $Ω$ 上是凸函数，当且仅当 (if and only if) 它的海森矩阵 $∇^2f(x)$ 在 $Ω$ 上处处是半正定的 。

在单变量微积分中，我们判断一个函数 $f(x)$ 是否为凸函数，是看它的二阶导数是否满足 $f′′(x)≥0$。
在多维空间中，海森矩阵 $∇^2f(x)$ 扮演了二阶导数的角色，而“半正定” 这个矩阵性质，对应了“大于等于零 $≥0$” 这个概念。

海森矩阵半正定，意味着函数在每一点、沿每一个方向的曲率都是非负的（向上弯曲或平坦） 。一个处处都向上弯曲或平坦的函数，其整体形状必然是一个“碗”形。

海森矩阵半正定（曲率 ≥0）允许了曲率等于零的情况，这对应于函数图像上出现平坦的部分 。如果我们想得到更强的严格凸性，就需要一个更强的条件：海森矩阵处处正定 。

实践中，要验证一个函数是否为凸函数，计算它的海森矩阵并判断其正定性，往往是最直接和有效的方法。

一个小型证明如下，这里的目标是证明一个二次函数是凸的，等价于其对应的矩阵是半正定的：

我们分析的是一个带有对称矩阵A的通用二次函数： $$f(x)=\frac{1}{2}x^\top Ax+b^\top x$$ 我们将使用一阶凸性条件来作为判别标准。这个条件的内容是：

函数 $f$ 是凸的 $⟺$ $f(y)\geq f(x)+\nabla f(x)^\top(y-x)$ 对所有 $x,y$ 成立。

为了方便代数推导，我们通常令 $y=x+d$，于是这个条件就等价地写为：

函数 $f$ 是凸的 $⟺$ $f(x+d)\geq f(x)+\nabla f(x)^\top d$ 对所有 $x,d$ 成立。

我们的策略是，将 $f(x+d)$ 和 $f(x)+∇f(x)^⊤d$ 这两项都用包含 $A,b,x,d$ 的表达式写出来，然后比较它们的大小。

展开 $f(x+d)$ $$\begin{aligned}f(x+d)&=\frac{1}{2}(x+d)^\top A(x+d)+b^\top(x+d)\&=\frac{1}{2}(x^\top Ax+x^\top Ad+d^\top Ax+d^\top Ad)+b^\top x+b^\top d\end{aligned}$$ 因为 $x^⊤Ad$ 是一个标量，它的转置等于它自身。所以 $(x^\top Ad)^\top=d^\top A^\top x$。又因为我们假设了 $A$ 是对称矩阵（$A=A^⊤$），所以 $d^\top A^\top x=d^\top Ax$。因此，交叉项 $x^\top Ad\text{ 和 }d^\top Ax$ 是相等的。于是，上式可以整理为： $$f(x+d)=\left(\frac{1}{2}x^\top Ax+b^\top x\right)+(d^\top Ax + b^\top d)+\left(\frac{1}{2}d^\top Ad\right)$$
第一项 $(\frac{1}{2}x^\top Ax+b^\top x)$ 正是原始函数 $f(x)$。
我们之前已经知道，对于对称矩阵 $A$，该二次函数的梯度是 $∇f(x)=Ax+b$。那么 $\nabla f(x)^\top d=(Ax+b)^\top d=(x^\top A^\top+b^\top)d=(x^\top A+ b^\top)d=x^\top Ad+b^\top d$

因此，我们得到了一个关于 $f(x+d)$ 的精确等式： $$f(x+d)=f(x)+\nabla f(x)^\top d+\frac{1}{2}d^\top Ad$$ 现在，我们将这个等式代入我们的判别式 $f(x+d)≥f(x)+∇f(x)^⊤d$ 中： $$f(x)+\nabla f(x)^\top d+\frac{1}{2}d^\top Ad\geq f(x)+\nabla f(x)^\top d$$ 两边的 $f(x)$ 和 $∇f(x)^⊤d$ 项完全相同，可以直接消去。最终得到： $$\frac{1}{2}d^\top Ad\geq0\quad\Longleftrightarrow\quad d^\top Ad\geq0,\quad\forall d\in\mathbb{R}^n$$

2.5. 凸性定理

设 $f$ 是一个定义在凸集 $Ω$ 上的凸函数。如果点 $x^∗∈Ω$ 是 $f$ 的一个局部最小值，那么它也必定是一个全局最小值。

反证法：

假设：$x^∗$ 是一个局部最小值，但它不是一个全局最小值。

如果 $x^∗$ 不是全局最小，那意味着在可行域 $Ω$ 中，必然存在另一个点 $y$，它的函数值比 $f(x^∗)$ 还要低，即 $f(y)<f(x^∗)$。
现在，我们考察连接 $x^∗$ 和这个更低的点 $y$ 之间的任意一个中间点 $x_\theta=\theta x^*+(1-\theta)y$。

因为 $f$ 是一个凸函数，它必须满足“弦在图之下”的性质： $$f(x_\theta)\leq\theta f(x^)+(1-\theta)f(y)$$ 把假设 $f(y)<f(x^∗)$ 代入上面的不等式： $$f(x_\theta)\leq\theta f(x^)+(1-\theta)f(y)<\theta f(x^)+(1-\theta)f(x^)=f(x^*)$$ 推导，我们得出：$f(x_θ)<f(x^∗)$。这意味着，在 $x^∗$ 和 $y$ 之间的任何一个点，其函数值都比 $f(x^∗)$ 要低。这与 $x^∗$ 是一个局部最小值相矛盾。证毕。

注意：这个定理不保证全局最小值的存在性。这个定理只承诺“如果你找到了一个局部最小值，那它就是全局的”。但它不保证你一定能找到一个最小值。

2.6. 凸优化问题

设 $f$ 是一个在凸集 $Ω$ 上可微的凸函数。如果在 $Ω$ 中存在一个点 $x^∗$，它满足： $$\nabla f(x^)^\top(x-x^)\geq0\quad\forall x\in\Omega$$ 那么，$x^∗$ 就是一个全局最小值点。只要函数是凸函数，那么FONC就从必要条件升级成了充分条件。

证明：

一阶凸性条件： $$f(x)\geq f(x^)+\nabla f(x^)^\top(x-x^)$$ 最优性条件： $$\nabla f(x^)^\top(x-x^)\geq0$$ 所以有 $$f(x)\geq f(x^),\quad\forall x\in\Omega$$ 所以 $x^*$ 是全局最小值。

如果 $x^*$ 是内部点，那么这个条件可以在简化成：

如果 $f$ 是凸函数，且 $x^∗$ 是一个内部点，那么 $x^∗$ 是全局最小值当且仅当 $∇f(x^∗)=0$。

2.7. 凸性的保持

以下四种操作可以保证经过操作后的函数依然是凸的。

1. 非负数乘 (Non-negative scaling): $h(x)=αf(x) for α≥0$。

直观理解：你有一个“碗”($f(x)$)。用一个正数 $α$ 去乘以它，相当于在垂直方向上把它拉伸或压缩。一个碗被拉高或压扁了，它依然是一个碗。但如果你乘以一个负数，碗就倒过来了，变成了“圆顶”（凹函数）。

2. 求和 (Sum): $h(x)=f(x)+g(x)$。

直观理解：把一个碗 ($f(x)$) 叠在另一个碗 ($g(x)$) 上，得到的总形状还是一个碗。两个凸函数的和一定是凸的。

3. 取最大值 (Maximum): $h(x)=max{f(x),g(x)}$。

直观理解：想象两条凸的曲线（比如两个抛物线）的图像。取它们在每一点的最大值，相当于描绘出这两条曲线的“上包络线”。这个上包络线的形状依然是“碗”形的，所以也是凸的。
补充应用：这个性质非常有用。例如，在支持向量机（SVM）中著名的Hinge Loss损失函数 $L(y)=max(0,1−y)$，就是两个凸函数（$f_1=0$ 和 f$_2=1−y$）取最大值，因此它是一个凸函数。

4. 与仿射函数复合 (Composition with affine map): $h(x)=f(Ax+b)$。

直观理解：仿射函数 $Ax+b$ 本质上是对输入变量 $x$ 进行线性变换（旋转、缩放）和平移。这个操作的含义是，在将你的输入 $x$ 放入“碗”($f$) 之前，先对它进行一番变换。这并不会改变 $f$ 本身的“碗”形性质，只是可能让这个碗在坐标系里被移动、被拉伸或者被旋转了而已。

注意：两个凸函数的复合 $f(g(x))$，通常不一定是凸的。

2.8. 支持向量机 (SVM)

SVM（带有L2正则化）的目标函数： $$f(x)=\underbrace{\frac{1}{n}\sum_{i=1}^n\max{0,1-y_ix^\top s_i}}{\text{第一项:Hinge Loss (经验风险)}}+\underbrace{\frac{\lambda}{2}|x|^2}{\text{第二项:L2 Regularization (结构风险)}}$$

$x$：是我们需要学习的模型参数（权重）。
第一项 (Hinge Loss)：这是损失项，用来衡量模型在训练数据上的表现。$max{0,…}$ 的意思是，如果一个样本被正确分类且与决策边界的间隔足够大，那么它的损失就是 0；否则，就会产生一个线性的惩罚。
第二项 (L2 Regularization)：这是正则化项，用来防止模型过拟合。它通过惩罚过大的模型参数值，来鼓励模型学习到更简单、更平滑的决策边界。$λ$ 是一个超参数，用来平衡“模型在训练集上的表现”和“模型的简洁度”。

证明目标：这个函数 $f(x)$ 对于变量 $x$ 来说，是一个凸函数。

分析第二项：$\frac{\lambda}{2}|x|^2$

这个比较简单，分两步：

基础函数：$|x|^2$ (范数的平方) 是一个凸函数。
- 补充：因为它本质上是一个二次函数 $x^⊤Ix$，而单位矩阵 $I$ 是正定的。
非负数乘：我们用一个非负常数 $\frac{\lambda}{2}$ (因为 $λ≥0$) 去乘以它。根据“非负数乘保持凸性”的法则，整个第二项是凸的。

分析第一项：$\frac{1}{n}\sum_{i=1}^n\max{0,1-y_ix^\top s_i}$

这个稍微复杂，我们从最里面开始分析：

最核心的部分：$1-y_ix^\top s_i$。对于变量 x 来说，这是一个仿射函数（$Ax+b$ 的形式），我们知道仿射函数是凸的。
取最大值：$\max{0,1-y_ix^\top s_i}$。这是在两个凸函数（常数函数 $g_1(x)=0$ 和我们上一步的仿射函数 $g_2(x)$）之间取最大值。根据“取最大值保持凸性”的法则，这一整块 $max{…}$ 是凸的。
求和：$\sum_{i=1}^n(\ldots)$。这是将 $n$ 个凸函数（每个样本对应一个）相加。根据“求和保持凸性”的法则，这个求和项是凸的。
非负数乘：最后，我们乘以一个非负常数 $\frac{1}{n}$。根据“非负数乘保持凸性”的法则，整个第一项是凸的。

2.9. 最小二乘问题

最小二乘的目标函数： $$f(x)=\frac{1}{2}|Sx-y|^2$$ 展开成二次函数形式： $$f(x)=\frac{1}{2}x^\top S^\top Sx-x^\top S^\top y+\frac{1}{2}y^\top y$$ 最小二乘问题本质上是一个二次优化问题，所以能给出一次性的解析解。

证明：

我们应用二阶条件。对于上面展开的二次函数，我们可以直接套用公式得到它的梯度和海森矩阵：

梯度: $\nabla f(x)=S^\top Sx-S^\top y$
海森矩阵: $\nabla^2f(x)=S^\top S$

我们的任务现在简化为：证明矩阵 $S^⊤S$ 是一个半正定矩阵。

要证明一个矩阵 $A$ 是半正定的，我们需要证明对于任意非零向量 $v$，都满足 $v^\top Av\geq0$。

我们来看 $v^\top(S^\top S)v$：
1. 利用矩阵转置的性质 $(AB)^\top=B^\top A^\top$，我们可以把 $v^\top S^\top$ 写成 $(Sv)^\top$。于是：$v^\top S^\top Sv=(Sv)^\top(Sv)$
2. 一个向量与自身的转置相乘（点积），等于这个向量的L2范数的平方。令 $z=Sv$，那么上式就等于：$|Sv|^2$
3. 任何向量的范数平方（可以理解为“长度”的平方）必然是大于等于零的。

因此，海森矩阵 $S^⊤S$ 是半正定的，这意味着最小二乘的目标函数是一个凸函数。这个问题的全局最小值可以通过令梯度等于零来找到。 $$\nabla f(x^)=S^\top Sx^-S^\top y=0$$ 将含 $x^∗$ 的项移到一边，我们就得到了机器学习中的正规方程： $$S^\top Sx^=S^\top y$$ 如果矩阵 $S^⊤S$ 是可逆的（通常在特征不共线且样本数足够多的情况下成立），我们就可以两边同乘以它的逆，从而得到一个一步到位的解析解： $$x^=(S^\top S)^{-1}S^\top y$$

3. 一般性优化

3.1. 迭代算法 (Iterative Algorithms)

对于一些非常简单的优化问题（比如我们之前看到的二次函数），我们或许能通过令梯度为零，直接解方程得到一个完美的解析解。但是，对于绝大多数现实世界中的复杂问题，尤其是机器学习中的非凸、高维问题（比如训练一个深度神经网络），想通过解方程一步到位地求出最优解是不可能的。

迭代更新法则： $$x^{k+1}=x^k+\eta_kd^k,\quad k=0,1,\ldots$$ 这个公式的每一部分：

$x^k$: 代表我们在第 $k$ 步时所处的位置。
$x^{k+1}$: 代表我们走完这一步后，将要到达的下一个位置。
$d^k$: 这是一个向量，代表在当前位置 $x^k$ 时，我们决定要朝哪个方向 (direction) 走。
$η^k$: 这是一个标量（一个数），代表我们决定沿着选定的方向 $d^k$ 走多远，也就是步长。在机器学习中，我们更常称之为学习率。

如果我们想找到最小值（山谷底部），那么在每一步最合乎逻辑的选择，当然是往下走。在数学上，我们就称这种能让函数值下降的方向为下降方向。

对于一个可微函数 $f$，在点 $x$ 处，一个非零向量 $d$ 被称为下降方向，如果 $f$ 在该点的方向导数 $f′(x;d)$ 为负值。

数学表达式为： $$f^{\prime}(x;d):=\nabla f(x)^\top d<0$$ 引理：

设 $f$ 是一个连续可微的函数。如果在点 $x$ 处，$d$ 是一个下降方向，那么必然存在一个很小的正数 $ϵ$，使得只要你沿着方向 $d$ 走的步长 $α$ 在 $(0,ϵ]$ 这个区间内，你的新位置的函数值就一定会比当前位置的函数值要低。 $$f(x+\alpha d)<f(x)\quad\forall\alpha\in(0,\epsilon]$$

3.2. 利用局部信息

在任何一个点 $x$，你拥有的“工具”可以帮你测量三类信息：

函数值 $f(x)$：你的海拔高度计，告诉你“我现在有多高？”
梯度 $∇f(x)$：你的坡度计，告诉你“哪个方向是上坡最陡的，以及有多陡？”
海森矩阵 $∇^2f(x)$：一个高级地形扫描仪，告诉你“我脚下的地面是向上弯曲（碗状），还是向下弯曲（山顶状）？”

3.2.1. 一阶算法 (First-order algorithms)

使用的信息：只使用函数值 $f$ 和梯度 $∇f$。
登山者比喻：你只有一个海拔高度计和坡度计。你知道自己有多高，也知道往哪走是下山最快的方向，但你对地面的形状一无所知。你不知道你是在一个宽阔的U形山谷里，还是在一个狭窄的V形峡谷里。
策略：非常“贪心”和直接。既然坡度计告诉了我最陡的下山方向（即梯度的反方向 $−∇f(x)$），那我就朝这个方向走一小步。
代表算法：梯度下降法 (Gradient Descent) 及其各种变体（如Adam, RMSprop, Momentum等）。这是目前深度学习等大规模机器学习领域绝对的主流。
优缺点：
- 优点：每一步的计算成本非常低。只需要计算梯度即可，这对于有数百万参数的模型来说是可行的。
- 缺点：收敛可能较慢。因为它不了解地形的曲率，在狭窄的“峡谷”中可能会来回“之字形”震荡，在平坦区域则会移动缓慢。

3.2.2. 二阶算法 (Second-order algorithms)

使用的信息：使用函数值 $f$、梯度 $∇f$ 和海森矩阵 $∇^2f$。
策略：非常“聪明”和“有远见”。它不再是盲目地沿着最陡的方向走，而是会自问：“根据我建立的这个局部碗状模型，这个碗的最低点在哪里？” 然后，它会直接一步跳到那个预测的最低点。
代表算法：牛顿法 (Newton's Method)。
优缺点：
- 优点：收敛速度极快（在最优点附近是二次收敛），比一阶算法快得多。它走的每一步都更有“规划”，能直接指向目标。
- 缺点：每一步的计算成本极其昂贵。
  - 补充：对于一个有 $n$ 个参数的模型：
    1. 你需要计算海森矩阵，它有 $n×n$ 个元素。
    2. 你需要求这个 $n×n$ 矩阵的逆，这个操作的计算复杂度大约是 $O(n^3)$。
  - 当 n 很大时（比如一个有100万个参数的神经网络），存储和求逆一个 100万×100万的矩阵是完全不可想象的。

在参数维度极高的现代深度学习中，研究者们主要致力于改进和优化一阶算法，而不是直接使用纯粹的二阶算法。

3.3. 下降迭代算法步骤

初始化 (Initialization): pick x⁰ ∈ ℝⁿ arbitrarily。
- 含义：在开始下山之前，先把机器人随机空投到山上的某个位置 $x^0$。

接下来，机器人进入一个无限循环的“通用步骤 (General step)”：

第①步: pick a descent direction dᵏ。
- 含义：在当前位置，机器人环顾四周（通过计算），确定一个可以“往下走”的下降方向 $d^k$。
第②步: find a stepsize ηₖ satisfying f(xᵏ + ηₖdᵏ) < f(xᵏ)。
- 含义：确定了方向后，机器人需要决定朝这个方向走多远（步长 ηk）。这里的唯一要求是，走完这一步后，新的位置必须比当前位置的海拔更低。
第③步: Set xᵏ⁺¹ = xᵏ + ηₖdᵏ。
- 含义：机器人执行移动，从当前位置 $x^k$ 到达新的位置 $x^{k+1}$。
第④步: if a stopping criteria is satisfied, then STOP。
- 含义：到达新位置后，机器人检查一下是否已经“到达山底”。如果满足了停止条件，任务结束，报告当前位置；否则，回到第①步，开始新一轮的决策和移动。

一个算法的“灵魂”就在于它如何回答以下四个问题。

1. 如何选择起始点 (Starting point)？

随机初始化：在很多机器学习应用（尤其是神经网络）中，参数会被随机初始化，以打破对称性，避免所有神经元学习到同样的东西。
零初始化：对于一些简单的模型（如逻辑回归），有时会直接将所有参数初始化为0。
预训练/热启动 (Warm Start)：如果我们已经有了一个训练好的相似模型，可以拿它的参数作为新模型的起始点，这能大大加快训练速度。

2. 如何选择下降方向 (Descent direction)？

这是区分不同算法的最核心部分。
最速下降方向 (Steepest Descent)：选择当前位置“最陡”的下坡方向，即梯度的反方向 $d^k=−∇f(x^k)$。这就是梯度下降法。
牛顿方向 (Newton's Direction)：利用二阶信息（曲率），找到一个指向局部二次近似模型最低点的方向 $d^k=-[\nabla^2f(x^k)]^{-1}\nabla f(x^k)$。这就是牛顿法，通常收敛更快但计算更昂贵。
坐标下降方向 (Coordinate Descent)：一种非常简单的方法，每次只沿着一个坐标轴的方向进行优化。

3. 如何选择步长 (Stepsize)？

固定步长/学习率：选择一个固定的、比较小的数值（例如 $η^k=0.01$）。这是最简单的方法，但选择过大可能导致算法不收敛，过小则收敛太慢。
精确线搜索 (Exact Line Search)：在确定方向后，精确计算出能使函数值下降最多的那个最优步长。这种方法计算代价很高，很少使用。
回溯线搜索 (Backtracking Line Search)：一种近似方法。先尝试一个较大的步长，如果不满足某个“充分下降”条件，就按比例缩小步长，直到满足条件为止。
自适应步长 (Adaptive Stepsize)：现代优化算法（如 Adam, AdaGrad, RMSprop）的核心思想。它们能够根据历史梯度信息，在训练过程中自动地为每个参数调整步长。

4. 如何设定停止条件 (Stopping criteria)？

达到最大迭代次数：最简单粗暴，也是最常用的方法。比如“训练100个epoch后停止”。
梯度范数足够小：在最优点附近，地势平坦，梯度接近于零。所以可以设定当梯度的长度 $|\nabla f(x^k)|$ 小于一个很小的阈值时停止。
函数值不再下降：如果连续几次迭代，函数值的下降非常微小（例如 $f(x^k)-f(x^{k+1})<\epsilon$），可以认为已经收敛。
参数变化足够小：如果参数本身在迭代中不再有明显变化（$|x^{k+1}-x^k|<\epsilon$），也可以认为已经收敛。在实践中，通常会组合使用这些条件。

3.4. 精确线搜索 (Exact Line Search)

在迭代的每一步，我们已经选好了一个下降方向 dk（比如梯度反方向）。现在的问题是，沿着这个方向走多远（$η^k$）才是最好的？

一个非常自然和“贪心”的想法是：

沿着这个方向一直走，直到函数值达到该方向上的最低点再停下来。多走一步，函数值可能就要回升了。

这个想法在数学上，就表达为一个关于步长 $η$ 的一维最小化问题： $$\eta_k=\arg\min_{\eta\geq0}f(x^k+\eta d^k)$$ 当我们能够精确地解出这个一维优化问题，找到那个最优的步长 $η^k$ 时，我们就称这种方法为精确线搜索 (Exact Line Search)。对于绝大多数复杂的函数，上面那个一维最小化问题本身就很难解，甚至没有解析解。

但是假设我们的目标函数是一个由正定矩阵 $A$ 定义的二次函数： $$f(x)=\frac{1}{2}x^\top Ax+b^\top x$$

构建一维函数：我们想最小化 $g(\eta)=f(x^k+\eta d^k)$。将 $x^k+\eta d^k$ 代入 $f(x)$ 并展开，经过一系列代数运算，$g(η)$ 是一个关于变量 $η$ 的一维二次函数（即一条抛物线）： $$g(\eta)=\left(\frac{1}{2}(d^k)^\top Ad^k\right)\eta^2+\left((x^k)^\top Ad^k+b^\top d^k\right)\eta+f(x^k)$$
对于一个形如 $g(\eta)=a\eta^2+b\eta+c$ 的抛物线，它的最低点在哪里？我们可以通过令其导数 $g^{\prime}(\eta)=2a\eta+b$ 等于0来求解，得到 $\eta=-b/(2a)$。
- $a=\frac{1}{2}(d^k)^\top Ad^k$
- $b=(x^k)^\top Ad^k+b^\top d^k$

代入 $\eta=-b/(2a)$，我们就得到了最优步长公式： $$\eta_k=-\frac{(x^k)^\top Ad^k+b^\top d^k}{(d^k)^\top Ad^k}$$ 这个公式还可以写成更简洁的形式。我们知道 $Ax^k+b=\nabla f(x^k)$，所以分子可以写成 $(Ax^k+b)^\top d^k=\nabla f(x^k)^\top d^k$ ，因此： $$\eta_k=-\frac{\nabla f(x^k)^\top d^k}{(d^k)^\top Ad^k}$$ 于二次函数，我们能得到解析解。但对于神经网络这种极其复杂的非线性函数，求解 $\arg\min f(x^k+\eta d^k)$ 这个子问题本身就非常困难，甚至没有闭式解。

3.5. 回溯线搜索

3.5.1. 思路

它的思想非常直观，可以比作一个“谨慎的下山者”：

大胆尝试：在确定了下山方向后，先尝试迈出一大步（比如，设置一个初始的、较大的步长 $η$）。
评估效果：看看迈出这一大步后，新位置的海拔是否“足够低”。
不满意则后退：如果发现这一步迈得太大（比如越过了谷底，跑到了对面的山坡上），导致下降效果不理想，就撤销这一步，然后尝试一个短一点的步子（比如，将步长 η 乘以一个折扣因子 $β<1$）。
重复：不断地“后退”并缩短步长，直到找到一个令人满意的、能带来“足够”下降的步长为止。

如何用数学语言来定义什么叫“足够好”或者“下降效果理想”，我们提出可接受区域 (Acceptable region) 的概念。一个步长 $η$ 被认为是“可接受的”，如果它满足下面的不等式（也被称为 Armijo 条件）： $$f(x^k+\eta d^k)\leq f(x^k)+\sigma\eta\nabla f(x^k)^\top d^k$$

左边: $f(x^k+\eta d^k)$ 。这是迈出步长为 $η$ 的一步后，实际到达的新位置的海拔。
右边: $f(x^k)+\sigma\eta\nabla f(x^k)^\top d^k$
- 含义：这是一个期望达到的目标海拔，如果你没能比这个目标更低，就说明这一步走得不好。我们再把它拆开看：
- $f(x^k)$: 出发时的海拔。
- $\nabla f(x^k)^\top d^k$: 你出发时，脚下在 dk 方向的坡度（这是一个负数）。
- $\eta\nabla f(x^k)^\top d^k$: 如果山坡是一条完美的直线（即切线），你走 η 这么远预期会下降的高度。
- $σ$: 一个介于0和1之间的小常数（比如 $σ=0.1$）。它扮演了一个“折扣”或“容忍度”的角色。

3.5.2. 算法

第一步：设定参数

在开始搜索前，我们需要设定两个“超参数”：

$σ∈(0,0.5)$: 称为Armijo条件参数或“下降率折扣”。它控制了我们对“下降得是否足够”的判断标准有多宽松。一个典型的值是 $σ=0.01$ 或 $σ=0.3$。它越小，要求就越宽松。
$β∈(0,1)$: 称为回溯缩减因子。它控制了当我们发现步长太大时，“后退”的幅度有多大。一个典型的值是 $β=0.5$（步长减半）或 $β=0.8$（步长变为原来的80%）。

第二步：循环搜索

算法的核心是一个 while 循环： 初始化：从一个比较大的初始步长 η 开始（比如 η=1）。

循环条件： while $f(x^k+\eta d^k)>f(x^k)+\sigma\eta\nabla f(x^k)^\top d^k$ do

当 “实际达到的新海拔” 高于 “我们设定的‘足够好’的目标海拔” 时，就执行循环体。

循环体： $η←η⋅β$

直观翻译：将当前的步长 $η$ 乘以缩减因子 $β$，让它变短一点。

退出循环：当 while 循环的条件不再满足时（即实际新海拔低于或等于目标海拔），循环结束。此时的 $η$ 就是我们最终采纳的“足够好”的步长。

![[Pasted image 20250930211156.png]]

Class 5 - Unconstrained Case

beautifulremi