数值优化扩展：用图理解梯度、步长与收敛

从 x = 0 出发，怎样一步步走到函数的最低点 x = 3？同一条曲线，步长不同，结果可能是收敛、来回振荡或越走越远。本篇先画出实际迭代，再用几行公式解释它，最后把梯度下降、牛顿法和常见优化方法放回各自适用的问题中。

专题目录 · 学习路线

这篇是“数据结构与算法”的数值优化扩展。基础主线讨论数组、链表、查找和排序；这里处理的是连续变量的迭代更新。先读懂循环、复杂度与不变量，再学习这篇，会更容易把“每次更新做了什么”和“为什么能停下来”对应起来。

1. 先看一个可以手算的问题

假设希望把参数 x 调到 3，用与目标的平方距离表示代价：

$f(x)=\frac{1}{2}(x-3)^2$

函数值越小，表示参数越接近目标。因为平方非负，在 x = 3 时函数值为 0，这就是唯一的全局最小值。这次我们故意不直接写答案，而是从 x = 0 开始，用迭代方法逐步找它。

同一二次函数的梯度下降：步长0.5逐渐收敛，步长2振荡，步长2.2发散

图中浅色曲线是目标函数，彩色圆点是实际算出来的迭代结果，虚线只把相邻结果连接起来。它不是连续时间运动轨迹。三个面板的坐标范围不同，应结合各自的数值序列阅读。

下面先只看第一块图：0 → 1.5 → 2.25 → 2.625。为什么下一步会是这些数？

2. 梯度告诉方向，步长控制一次走多少

一维情况下，梯度就是导数：

$g(x)=f'(x)=x-3$

在起点 x = 0，梯度是 −3。这表示在这个点附近，向右增加 x 可以降低函数值。因此沿负梯度走，参数应该向右移动。

梯度下降的更新规则是：

$x_{k+1}=x_k-\eta g(x_k)$

这里 k 是迭代次数，η 是步长。取 η = 0.5，把每一步都展开：

当前步骤	当前参数 `x`	梯度 `x − 3`	更新 `x − 0.5 × 梯度`	更新后的函数值
第 1 步	0	−3	1.5	1.125
第 2 步	1.5	−1.5	2.25	0.28125
第 3 步	2.25	−0.75	2.625	0.0703125
第 4 步	2.625	−0.375	2.8125	0.017578125

每一轮距离 3 都缩小一半。数值序列、图上不断靠近谷底的点，以及代码中的一行更新，是同一件事情的三个表示。

double x = 0.0;
const double eta = 0.5;
for (int k = 0; k < 4; ++k) {
    const double gradient = x - 3.0;
    x = x - eta * gradient;
}
// x = 2.8125

多维情况下，梯度由各个偏导数组成。在欧氏距离度量下，负梯度是局部一阶变化最快的下降方向。但这句话只描述足够小的邻域，不能推出沿这个方向跨任意大的步子都下降。

3. 步长为什么会改变结果

把本例的梯度代回更新式，得到：

$x_{k+1}-3=(1-\eta)(x_k-3)$

把 x − 3 看成误差，这个等式说：每一步都把误差乘以 1 − η。于是无需猜测，就能判断图里的三个结果。

步长	误差每轮乘以	从 0 开始的序列	行为
`η = 0.5`	`0.5`	`0 → 1.5 → 2.25 → 2.625`	从同一侧逐渐接近 3
`η = 1`	`0`	`0 → 3 → 3`	本例中一步到达
`η = 1.5`	`−0.5`	`0 → 4.5 → 2.25 → 3.375`	跨过 3，但距离逐渐缩小
`η = 2`	`−1`	`0 → 6 → 0 → 6`	永远来回振荡
`η = 2.2`	`−1.2`	`0 → 6.6 → −1.32 → 8.184`	跨过 3，距离逐渐增大

本例收敛要求 |1 − η| < 1，也就是 0 < η < 2。这个区间来自本例二阶导数为 1，不是所有函数通用的学习率范围。如果改成 f(x) = 5(x − 3)²，梯度放大了 10 倍，稳定步长范围就相应缩小为 0 < η < 0.2。

实际优化器通常还会采用线搜索或信赖域策略控制更新。例如回溯线搜索先尝试一步，检查是否得到足够下降；不满足就缩短步长。它比“随便挑一个固定步长并希望收敛”有更明确的依据，但也有适用条件和额外函数求值成本。Boyd 与 Vandenberghe《Convex Optimization》第 9 章

4. 把判断写成可执行实验

下载 optimization.cpp。它不依赖额外数学库，用 C++17 运行同一组更新，并检查：

η = 0.5 的前三步与表格一致，50 步后接近 3，函数值不增加。
η = 2 在 0 与 6 之间交替，函数值始终为 4.5。
η = 2.2 的误差绝对值逐步增大。
下一节二维二次函数的牛顿方向为 (3, −1)。

在已有 GCC／Clang 的 Linux 或 Docker 环境中运行；本仓库的原生编译统一放在 Docker 中：

c++ -std=c++17 -O1 -g -Wall -Wextra -Wpedantic \
  -fsanitize=address,undefined -fno-omit-frame-pointer \
  optimization.cpp -o optimization
./optimization

这个教学测试使用 assert，编译时不要定义 NDEBUG；程序也会检查这一点，避免关闭断言后把空跑当成测试通过。预期看到：

eta=0.500000: 0.000000 1.500000 2.250000 2.625000
eta=2.000000: 0.000000 6.000000 0.000000 6.000000
eta=2.200000: 0.000000 6.600000 -1.320000 8.184000
PASS convergence, oscillation, divergence and Newton solve

这里用有限次计算观察发散趋势；“这个序列会一直发散”的结论来自上一节的误差递推式，而不是只看几步图形就作出判断。

5. 牛顿法：用曲率调整方向

梯度下降用一阶信息告诉我们朝哪走，牛顿法还使用二阶信息描述各方向的曲率。考虑二维问题：

$F(x,y)=\frac{1}{2}(x-3)^2+2(y+1)^2$

最低点是 (3, −1)。y 方向的曲率比 x 方向大，因此把两个方向都用同样大小的梯度步更新，可能在陡的方向上跨得太远。

在起点 (0, 0)，梯度与 Hessian 矩阵为：

$g=\begin{bmatrix}-3\\4\end{bmatrix},\qquad H=\begin{bmatrix}1&0\\0&4\end{bmatrix}$

牛顿方向 p 通过求解线性方程得到：

$Hp=-g$

这次可以逐行手算：pₓ = 3，4pᵧ = −4，所以 p = (3, −1)。取完整的一步 (x, y) ← (x, y) + p，恰好到达最低点。

当前位置        线性系统给出的方向       更新后
(0, 0)      +       (3, −1)       =   (3, −1)
F = 6.5                                  F = 0

代码中的 newton_direction() 用一个 2 × 2 Cholesky 分解和前后代入求解 Hp = −g。工程实现通常调用适合矩阵结构的线性求解器，不显式计算 Hessian 的逆矩阵。遇到大型稀疏矩阵，还可以利用稀疏分解或在满足条件时使用迭代线性求解器。

“一步到达”依赖这个目标恰好是正定二次函数。一般非线性函数的 Hessian 会随位置变化；非凸问题的 Hessian 还可能不正定，直接使用牛顿方向可能没有下降效果。阻尼、正则化、线搜索或信赖域，都是工程求解器需要考虑的部分。牛顿法的局部快速收敛也有初始点、光滑性和非退化性等前提，不能无条件写成“总比梯度下降快”。

求函数零点和求最小值也应分清：一维求根针对方程 h(x) = 0，优化中的牛顿法则对驻点条件 f′(x) = 0 进行处理；找到驻点后还要判断它是什么点。

6. 什么时候停：不能只看曲线变平

连续优化通常不会精确命中答案，而是在误差或预算达到条件时停止。无约束光滑问题常检查梯度范数是否小于容差，同时记录目标值、步长和迭代次数。

信号	可以说明什么	单独使用的局限
梯度范数很小	接近一阶驻点	非凸问题中可能是鞍点或局部极大点
相邻参数变化很小	最近一次移动很少	也可能只是步长过小
相邻目标值变化很小	最近一次代价变化很少	平台区、尺度或数值精度都可能造成
达到最大迭代数／时间	预算已经用完	不是已经收敛的证明
出现 `NaN`／`Inf`	数值计算异常	应中止并排查，不应继续输出“最优解”

对于本例，|g(x)| = |x − 3|，梯度容差直接对应参数误差；其他问题一般没有这么简单的对应关系。容差也应结合变量单位和函数尺度设置，不能把同一阈值不加区分地用于米、弧度与大额成本。

约束问题还要检查可行性和相应的最优性条件。例如要求 0 ≤ x ≤ 2 时，本例最优解是 x = 2，但梯度等于 −1。它已经不能继续沿负梯度方向移动，因为再向右就违反约束；所以约束最优点不必满足普通梯度为零。

7. 先分清问题，再选方法

“凸优化”“线性规划”是问题类别；“梯度下降”“内点法”是求解方法。把这些名字放在同一级清单里，容易混淆它们的关系。可以从数据规模、导数信息和约束开始分类。

你面对的问题	可考虑的方法	每步主要做什么	需要留意
光滑目标，梯度容易计算	梯度下降、带动量的一阶法	梯度与向量更新	步长、变量尺度、病态曲率
目标是大量样本损失的均值	SGD、小批量梯度法	抽取部分样本估计梯度	更新有噪声，单步不保证总损失下降
随机梯度，各参数尺度不同	Adam、RMSprop、Adagrad	维护梯度历史统计并缩放更新	超参数及收敛条件仍然重要
光滑、可求梯度，但完整 Hessian 太贵	BFGS、L-BFGS	用相邻参数与梯度变化近似曲率	L-BFGS 保存有限历史；不等于精确牛顿法
某些坐标的子问题特别容易解	坐标下降	一次更新一个坐标或一组坐标	变量耦合、坐标顺序和子问题代价
对称正定线性系统、大型稀疏二次问题	线性共轭梯度法	矩阵向量乘、共轭方向更新	正定性、条件数与预条件器
线性目标与线性约束	线性规划求解器	单纯形法或内点法等	可行性、无界性及求解精度
光滑非线性目标和约束	SQP、内点法	求解局部子问题或原始对偶系统	约束资格条件、初值、可行性
无可靠导数、混合或黑箱搜索	模拟退火、遗传算法、粒子群等	采样、扰动、选择或群体更新	评估预算很关键，有限运行不保证全局最优

7.1 SGD 与小批量：每一步读多少数据

若有 m 个样本，每个样本有 d 个特征，简单稠密线性回归的一次全量梯度计算通常需要 O(md) 工作；单样本梯度通常为 O(d)，批量大小为 b 时约为 O(bd)。这来自每个样本一次长度为 d 的点积及梯度累加，不是无条件的 O(md²)。

全量：    [样本1 … 样本m] → 一个平均梯度 → 更新一次
小批量：  [选出的 b 个样本] → 一个估计梯度 → 更新一次
单样本：  [一个样本] → 一个估计梯度 → 更新一次

每步便宜，并不自动意味着达到同等精度所需的总时间更短。还要比较迭代次数、数据读取、并行利用率与梯度噪声。Adam 进一步维护梯度的一阶与二阶矩估计，用偏差校正后的统计量缩放各坐标更新；它也不保证每一步损失都下降。Adam 原始论文

7.2 约束：先确认“允许去哪里”

把本例限制在 [0, 2]，一个简单办法是投影更新：先做梯度步，再把越界结果拉回合法区间。例如从 x = 0、η = 1 出发，梯度步给出 3，投影后得到 2。它说明约束会改变最优点，也会改变算法的停止条件。

更一般的等式、不等式约束可以写入拉格朗日函数。KKT 条件包括驻点、原始可行性、对偶可行性和互补条件；拉格朗日乘子是理论与算法工具，并不是“写出一个新函数后就可以随意当无约束问题求最小值”。

SQP 用当前点附近的二次目标近似和线性化约束建立 QP 子问题，再用求得的方向更新；曲率模型通常对应拉格朗日函数的 Hessian 或其近似。内点法则通过障碍函数或原始对偶条件处理不等式约束。它们可以处理很多实际问题，但都不能凭方法名称保证任意非凸约束问题得到全局最优解。

8. 凸和非凸：保证到底到哪一步

凸性有力的结论是：凸优化问题的局部最优解也是全局最优解。但凸性本身不保证最优解一定存在。例如 min exp(x) 的下确界是 0，却没有有限的 x 能取到它。问题还可能不可行或无界。

对于光滑无约束凸问题，梯度为零能证明该点全局最优；对于一般非凸问题，梯度为零只说明驻点。经典例子 f(x) = x³ 在 x = 0 的导数也是零，但这里并没有局部最小值。

约束凸问题在适当条件下可以用 KKT 条件刻画最优性；强对偶与必要性还需要关注相应的正则性条件。实际使用求解器时，应一起查看退出状态、残差、约束违反程度和问题假设，而不是只读取最后一个参数向量。

参考：Boyd 与 Vandenberghe 的凸优化教材及配套资料；Adam 原始论文。

返回数据结构与算法学习路线。