本页目录
优化 II · 无约束优化：从梯度下降到 Newton 法
无约束问题 \(\min_x f(x)\) 的算法全景。主线三问：往哪走（下降方向）、走多远（步长）、多快到（收敛速率）。收敛速率一节是本页核心——条件数给出一阶方法最重要的定量尺度，但不替代具体谱形、初始方向和步长的分析，也是理解深度学习各种优化器为何存在的理论底座。
学习层：同一个步长，为什么有人下山、有人原地打转？
1. 具体谜题：旋转的椭圆碗上，下一步到底会怎样？
把损失想成一个二维的椭圆碗。碗的两条主轴已经旋转了 \(30^\circ\)，沿一条轴的曲率是 \(\mu=1\)，沿另一条轴的曲率是 \(L=10\)。从单位圆上的
出发，只用固定步长梯度下降。现在只改学习率：
前者在陡轴上的一步因子是 \(1-0.18\times10=-0.8\)，后者是 \(1-0.22\times10=-1.2\)。你先猜：哪一种会在陡轴上变号？哪一种会把目标值降下来？哪一种最终会失控？ 注意，图上的坐标轴不是碗的主轴；只看 \(x_1,x_2\) 的左右摆动，很容易把“变号”误读成“发散”。
2. 先预测：在打开结果前写下三个判断
先不要点击“核对预测”，对当前预设写下：
- \(\alpha\) 是低于 \(1/L\)、介于 \(1/L\) 与 \(2/L\)，还是达到/越过 \(2/L\)？
- 在主轴坐标中，\(r_\mu=1-\alpha\mu\) 与 \(r_L=1-\alpha L\) 的符号和绝对值分别是什么？
- 你预测轨迹属于“不换号收敛”“换号但收敛”“有界但不趋零”还是“增长发散”？目标值、坐标分量和到原点的距离，分别会怎样变化？
预测不是猜图形，而是先读两个一维因子：\(|r_i|<1\) 才会在第 \(i\) 个特征方向上衰减；\(r_i<0\) 只说明该模态交替换号。
3. 最小精确模型：把二维问题拆成两个一维因子
令 \(Q(\theta)\) 的列是旋转后的正交主轴，
其中 \(0<\mu\le L\)。实验只研究这个精确二维、对称正定二次型：
换到主轴坐标 \(z=Q^\mathsf T x\) 后，梯度下降
就是
这给出一张可逐行核对的稳定性账本：条件数 \(\kappa=L/\mu\)；对所有初始方向都稳定收敛的固定步长范围是
这不是说超过边界的每条轨迹都发散。若初始快轴分量恰为零，它会一直为零；此时只需检查慢轴。实验同时显示
前者是整个迭代矩阵的谱半径，后者才针对当前初值。对活跃模态：最大模小于 \(1\) 时趋零，等于 \(1\) 时有界但不趋零，大于 \(1\) 时增长发散；负乘子表示换号。边界 \(\alpha=2/L\) 的快轴因子为 \(-1\)，因此要把等幅振荡与增长分开。
目标值与距离也要分开推理。 对这个 SPD 二次型，所有活跃乘子的模不超过 \(1\) 时，
都不增。原坐标的某一分量却可以增大：取 \(\theta=30^\circ,\mu=1,L=10,x_0=(1,0),\alpha=0.1\)，一步得到 \(x_1=(0.675,0.225\sqrt3)\)；第二坐标从零增大，距离仍缩短。
下降的步长保证还可以超出二次型。若 \(f\) 的梯度在整段更新路径上是 \(L\)-Lipschitz，下降引理给出
所以 \(0<\alpha<2/L\) 且 \(g\ne0\) 时目标严格下降；\(\alpha\le1/L\) 是便于写出标准速率的常用选择。再加上全空间上的凸性和最小点存在，由余强单调性 \(\langle g,x-x^*\rangle\ge\|g\|^2/L\) 可得
因此 \(0<\alpha\le2/L\) 时到任意最小点的距离不增；这仍不保证边界步长下趋于该点，也不保证每个原坐标分量不增。非凸问题则不能沿用这个距离结论。
以所有初始方向中最坏的误差二范数收缩为标准，最优常数步长为
右边是这个精确二次模型中误差二范数的最坏特征方向收缩因子；它不是每条轨迹、每个初始方向的实际步数承诺。
4. 可操作实验：先选判断，再揭开轨迹和账本
下面的实验固定 \(\mu=1\) 和单位长度初点，用 \(\kappa=L\) 决定另一条主轴曲率，并把步长改写成无量纲油门 \(\beta=\alpha L\)。先选预设，再调 \(\kappa\)、\(\beta\)、主轴旋转角、初始方向角和迭代次数，最后预测“不换号收敛 / 换号但收敛 / 有界但不趋零 / 增长发散”。核对前，轨迹、图表、指标和迭代表保持隐藏。
无 JavaScript 时的静态读法：初点长度为 \(1\)；\(\theta\) 是主轴旋转角，\(\varphi\) 是初始方向角。“换号收敛”表示某个活跃主轴因子为负且模小于 \(1\)；边界等幅不归为增长发散。
| 预设 | \(\kappa=L/\mu\) | \((\theta,\varphi)\) | \(\beta=\alpha L\) | 快轴乘子 \(1-\beta\) | 预测 |
|---|---|---|---|---|---|
| 良态 | \(4\) | \((35^\circ,20^\circ)\) | \(0.80\) | \(0.20\) | 不换号收敛 |
| 病态 | \(25\) | \((-35^\circ,25^\circ)\) | \(1.00\) | \(0\) | 快轴一步消失，慢轴很慢 |
| 保守 | \(10\) | \((25^\circ,40^\circ)\) | \(0.50\) | \(0.50\) | 不换号收敛 |
| 近极限 | \(10\) | \((28^\circ,-20^\circ)\) | \(1.85\) | \(-0.85\) | 换号但收敛 |
| 边界 | \(10\) | \((28^\circ,-20^\circ)\) | \(2.00\) | \(-1\) | 有界但不趋零 |
| 发散 | \(10\) | \((28^\circ,-20^\circ)\) | \(2.20\) | \(-1.20\) | 增长发散 |
| 纯慢轴 | \(10\) | \(z_0=(1,0)\) | \(2.40\) | \(-1.40\)（未激活） | 慢轴乘子 \(0.76\)，收敛 |
| 微小快轴 | \(10\) | \(z_0=(\sqrt{1-10^{-28}},10^{-14})\) | \(2.40\) | \(-1.40\) | 先下降、后增长 |
实验的等高线使用同一个 \(H\)，蓝色轨迹在横纵单位长度相同的原坐标中走，虚线标出旋转后的两个特征方向；第二幅图把 \(\|x_k\|_2/\|x_0\|_2\) 与 \(f(x_k)/f(x_0)\) 放到对数纵轴上。逐步账本会同时列出 \(x_k\)、主轴坐标 \(z_k\)、目标值和误差，便于定位“哪一个模态先出问题”。这是 SPD 二次型的双精度模拟，不能替非凸函数宣称任意的鞍点或局部极小行为。完整视野容纳全部轨迹；固定初始视野仅裁切窗外部分，不把数据压到边框。对数图不设误差地板，浮点零另列。几乎纯慢轴的微小分量绝不按容差删去；若乘子或迭代值发生舍入、下溢，则须回到解析公式判断。
5. 误区与边界：每一句保证都要带上条件
- “步长小于 \(2/L\) 就每个坐标都不变号”是错的。 只要 \(1/L<\alpha<2/L\)，\(L\) 模态因子就可能为负；变号本身不等于发散。
- “坐标增大就是离解更远”是错的。 本模型的模态平方和给出距离；旋转后的某个坐标可增大，而距离和目标同时减小。一般凸光滑问题的距离不增结论另需上述条件。
- “边界有界就等于收敛到最小点”是错的。 边界的活跃 \(L\) 模态等幅翻转；纯慢轴却可能趋零。对所有初值趋零的区间才是 \(0<\alpha<2/L\)。
- “条件数决定每一条轨迹”是错的。 \(\kappa\) 控制经典最坏情形尺度，但初始方向、实际谱形、步长和停止准则都会改变观察到的步数。
- “Newton 永远一步到位”是错的。 对本页的精确二次型，若 Hessian 和线性方程组都精确，Newton 确实一步到 \(x^*=0\)；一般非线性函数只在适当正则性和足够近的起点下才有局部二次收敛，而且 Hessian 不正定时方向还可能不是下降方向。
6. 迁移问题：模型变了，哪些结论要重写？
如果把 \(H\) 换成一个只“近似”已知的 Hessian，或把更新改成带动量的二阶递推，你会如何从特征方向重新写稳定多项式？如果 \(H\) 不再正定，\(f\) 可能有鞍点或无下界；此时“\(0<\alpha<2/L\) 就收敛到全局最小”还剩下哪一部分？请分别指出需要的凸性、光滑性、谱界和线性求解假设，而不要把这个二维椭圆碗的图像当作任意非凸地形的定理。
迁移题参考答案
用 \(\gamma\) 表示动量系数，避免与实验的 \(\beta=\alpha L\) 混淆。对 heavy-ball 更新 \(x_{k+1}=x_k-\alpha Hx_k+\gamma(x_k-x_{k-1})\)，沿 \(H\) 的特征向量、特征值 \(\lambda\) 投影后有 \(z_{k+1}=(1+\gamma-\alpha\lambda)z_k-\gamma z_{k-1}\)，故特征多项式是 \(r^2-(1+\gamma-\alpha\lambda)r+\gamma=0\)。稳定要对谱中的每个 \(\lambda\) 检查两个根都严格落在单位圆内；只检查一个平均曲率不够。若使用近似 Hessian 或近似线性求解，还要把谱误差和求解残差纳入收缩界。
若 \(H\) 不定，正特征值方向仍可在 \(0<\alpha<2/L\) 下受控，但负特征值方向的梯度下降因子 \(1-\alpha\lambda>1\)，会离开驻点；这可能帮助逃离严格鞍点，却既不证明目标有下界，也不证明轨迹会到全局最小。全局最小保证需要凸性（常配合 \(L\)-光滑）；线性速率还通常需要强凸下界 \(\mu I\preceq H\)。一般非凸问题最多在额外条件下谈收敛到驻点。
1. 最优性条件（回收数分 V）
设 \(x^*\) 是定义域的内点。\(f\) 在附近可微时，局部极小的一阶必要条件是 \(\nabla f(x^*)=0\)；若 \(f\in C^2\)，还必须有 \(\nabla^2f(x^*)\succeq0\)。反向的充分条件是 \(\nabla f(x^*)=0\) 且 \(\nabla^2f(x^*)\succ0\)，此时为严格局部极小。半正定本身不充分，例如 \(-x^4\) 在零点。
在开凸域上的可微凸问题中，驻点就是全局最小点；非凸问题中，小梯度只表示近似驻点，可能靠近鞍点甚至局部极大点。算法的停止条件必须说明检验了什么，不能把“梯度小”称为“找到好解”。
2. 下降法框架
先找下降方向，再决定步长。精确线搜索沿射线求最小值，但最小值不一定取得，求它也有代价；实践中常用充分下降测试。
Armijo 回溯：选 \(c\in(0,1)\)、缩减比 \(\tau\in(0,1)\) 和初始步长 \(\bar\alpha>0\)，反复令 \(\alpha\leftarrow\tau\alpha\)，直到新点在定义域内且
为什么足够小的步长会通过？可微性给出 \(f(x+\alpha d)=f(x)+\alpha g^\mathsf Td+o(\alpha)\)；因为 \((1-c)g^\mathsf Td<0\)，高阶余项最终压不住这个负项。内点处的下降方向因此会使回溯有限次结束。这是一次步长搜索的保证，还不是整个算法到达全局最小点的保证。
3. 梯度下降及其收敛速率（本页核心）
在欧氏单位球 \(\|d\|_2=1\) 上，Cauchy–Schwarz 给出 \(g^\mathsf Td\ge-\|g\|_2\)，等号在 \(d=-g/\|g\|_2\) 取得。因此 \(d_k=-\nabla f(x_k)\) 是欧氏意义的最速下降方向；若用 \(\|d\|_M^2=d^\mathsf TMd\)、\(M\succ0\) 衡量步长，对应未归一化方向改为 \(-M^{-1}g\)。收敛速率取决于函数的"弯曲程度"假设：
假设语言：\(L\)-光滑（梯度 Lipschitz：\(\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|\)，曲率上界）；\(\mu\)-强凸（曲率下界，优化 I）。条件数 \(\kappa = L/\mu\)。
这里假设 \(f:\mathbb R^n\to\mathbb R\) 可微，最小点 \(x^*\) 存在，\(L>0\)，表中 \(k\ge1\)；凸行的 \(\varepsilon\) 是目标差的绝对精度，强凸行是相对精度。若 \(\mu=L\)，步长 \(1/L\) 一步到解，单独处理这个退化边界。
| 函数类 | 固定步长 \(\alpha = 1/L\) 的速率 | 达到 \(\varepsilon\) 精度需要 |
|---|---|---|
| \(L\)-光滑 + 凸 | \(f(x_k) - f^* \leq \dfrac{L\|x_0 - x^*\|^2}{2k}\) | \(O(1/\varepsilon)\) 步（次线性） |
| \(L\)-光滑 + \(\mu\)-强凸 | \(f(x_k)-f^*\le(1-\mu/L)^k(f(x_0)-f^*)\) | 相对初始目标差达到 \(\varepsilon\)：\(O(\kappa\ln(1/\varepsilon))\) 步（线性收敛） |
凸行为什么是 \(1/k\)？ 光滑下降与凸性合起来给出
从 \(j=0\) 加到 \(k-1\)，距离项望远镜消去；再用目标差不增，将左边下界为 \(k(f(x_k)-f^*)\)，即得表中结果。
强凸情形的证明骨架：由 \(L\)-光滑的下降引理 \(f(x_{k+1}) \leq f(x_k) - \frac{1}{2L}\|\nabla f\|^2\)，再用强凸的 PL 不等式 \(\|\nabla f\|^2 \geq 2\mu(f - f^*)\)，代入得 \(f(x_{k+1}) - f^* \leq (1 - \frac{\mu}{L})(f(x_k) - f^*)\)。
几何读法（比公式重要）：等高线是圆（\(\kappa = 1\)）且取 \(\alpha=1/L\) 时一步到底；等高线是细长椭圆（\(\kappa\) 大）时，梯度方向常偏离指向圆心的方向，轨迹可能在谷壁间锯齿。对表中 \(\alpha=1/L\) 的标准强凸上界，达到给定精度的迭代数按 \(O(\kappa\log(1/\varepsilon))\) 缩放；具体轨迹仍取决于谱、步长与初始方向。
🔗 AI 衔接：在标准光滑强凸模型中，适当的加速梯度法可把复杂度对 \(\kappa\) 的依赖由 \(\kappa\) 改善到 \(\sqrt\kappa\)。RMSProp/Adam 的逐坐标缩放有预条件直觉，但在一般非凸随机问题上，不能据此自动推出条件数变小或训练更快；SGD 则用有噪但更便宜的梯度估计替代全梯度（ai 课 04 讲）。
4. Newton 法：先确认二次近似确实是碗
二阶局部模型是 \(m(d)=f(x)+g^\mathsf Td+\tfrac12d^\mathsf THd\)。若 \(H\succ0\)，其唯一最小点满足
写成 \(d=-H^{-1}g\) 便于推导，计算时应解线性方程组，通常不显式形成逆矩阵。此时 \(g^\mathsf Td=-g^\mathsf TH^{-1}g<0\)（\(g\ne0\)），所以它是下降方向。对 Hessian 恒定的 SPD 二次型，精确求解后一步到最小点。
一般函数为什么只在附近快？ 设 \(x^*\) 为驻点，在它的某个凸邻域内 \(H(x)\succeq mI\)、\(m>0\)，且 Hessian 是 \(M\)-Lipschitz。起点足够近、采用精确全步 Newton 时，积分 Taylor 余项给出
取小到能使迭代留在该邻域的初始误差，才能反复应用此界。这是局部二次收敛；线搜索、信赖域或 Hessian 修正用于处理远处的困难，不自动继承每步平方的速度。光有 \(C^2\) 和可逆 Hessian，不足以直接引用上述 Lipschitz 余项界。
仿射不变的含义也要精确。 对可逆变换 \(x=Ty+b\)，精确算术下，匹配初点、全步或相同线搜索规则的 Newton 迭代对应为 \(d_x=Td_y\)。这不意味着数值计算不怕病态：Hessian 的有限精度求解、舍入和依赖坐标的停止范数仍会影响结果。Stanford 无约束优化讲义，Newton 部分。
稠密实现形成 Hessian 需 \(O(n^2)\) 存储、直接分解通常需 \(O(n^3)\) 运算；稀疏结构、Hessian–向量乘积及迭代内层求解可以改变这些成本，不能把稠密代价当作所有 Newton 方法的下界。参见线性方程组与预条件。
BFGS：割线信息什么时候能保住正定性？
记 \(s_k=x_{k+1}-x_k\)、\(y_k=g_{k+1}-g_k\)，以 \(B_k\) 近似 Hessian。BFGS 的割线条件是 \(B_{k+1}s_k=y_k\)，其更新为
\(B_k\succ0\) 且 \(s_k^\mathsf Ty_k>0\) 时才有标准的保正定结论。Wolfe 曲率条件 \(g_{k+1}^\mathsf Td_k\ge c_2g_k^\mathsf Td_k\)（\(0<c_2<1\)，\(g_k^\mathsf Td_k<0\)，\(\alpha_k>0\)）给出
Armijo 单独只检查函数下降，不能替代这个曲率条件。若曲率失败，可采用有说明的阻尼或跳过更新策略。L-BFGS 用最近 \(m\) 对向量近似应用逆 Hessian，存储 \(O(mn)\)，适用于能较稳定地评价目标及梯度的光滑问题；它并非所有中等规模任务的统一首选。CMU 拟 Newton 讲义。
线性 CG 的准确边界：对 SPD 系统，在精确算术下至多 \(n\) 步求解（更细可由不同特征值个数界定），每步需要矩阵–向量乘法及向量运算。有限精度可能破坏共轭性；不定 Hessian 不能直接套用 SPD 保证。Newton-CG 可用 Hessian–向量乘积进行内层求解，并额外处理负曲率。
5. 方法选型：先问能可靠得到什么
| 已知条件与成本 | 可考虑的方法 | 还要核对 |
|---|---|---|
| 光滑，Hessian 或其乘积可得，要高精度 | Newton、信赖域、Newton-CG | 曲率、内层残差、离解多远 |
| 光滑，全梯度较可靠，存储受限 | L-BFGS | 线搜索与曲率条件 |
| 大规模和式，单样本梯度便宜 | SGD 及自适应一阶方法 | 噪声、批量、学习率与实际验证 |
| 光滑项加可处理的非光滑项 | 近端梯度 | 是否能有效计算近端映射 |
这个表给出候选方法，不能代替同等精度和计算预算下的比较。AI 课程中的随机优化有自己的假设与实验，不由本页二次型直接裁定。
6. 手算与反例：把“快”和“安全”落实为数值
例 1：同一句“误差乘 0.96”，究竟指什么？
设 \(f(x)=\tfrac12(x_1^2+100x_2^2)\)，\(x_0=(100,1)\)。精确线搜索梯度下降中
令 \(q=99/101\)，归纳得 \(\alpha_k=2/101\)、\(x_k=q^k(100,(-1)^k)\)。因此
距离每步乘约 \(0.980198\)，目标差及距离平方每步乘约 \(0.960788\)。要将目标差压到初始值的 \(1\%\)，须 \(k\ge\lceil\log(0.01)/(2\log q)\rceil=116\)；精确 Newton 对同一二次型一步到零。对比时还须计算每步成本。
例 2：从驻点到唯一最小点
对 \(f=x_1^2+2x_2^2-2x_1x_2-4x_2\)， \(\nabla f=(2x_1-2x_2,4x_2-2x_1-4)^\mathsf T\)，解得 \(x^*=(2,2)\)。常 Hessian \(\begin{pmatrix}2&-2\\-2&4\end{pmatrix}\) 的顺序主子式为 \(2,4>0\)，所以函数严格凸，驻点为唯一全局最小点，\(f(x^*)=-4\)。
例 3：Newton 也会奔向极大点
对 \(f(x)=x^4/4-x^2/2\)，从 \(x_0=1/5\) 出发。先判断 Newton 全步是上山还是下山，再打开答案。
展开计算：负曲率让二次模型不是碗
\(f'(x)=x^3-x\)、\(f''(x)=3x^2-1\)。在 \(x_0=1/5\)， \(g_0=-24/125\)、\(H_0=-22/25\)，故 \(d_0=-12/55\)，\(x_1=-1/55\)。 \(g_0d_0>0\)，它是上升方向；\(f(x_0)=-49/2500=-0.0196\)，而 \(f(x_1)\approx-0.000165262\) 更大。靠近零的 Newton 递推 \(x_{\rm new}=2x^3/(3x^2-1)\) 会趋向局部极大点零。求解驻点方程的快速收敛，不等于最小化成功。
例 4：充分下降能代替 BFGS 的曲率检查吗？
取 \(f(x)=-x^2\)，\(x=1\)，下降方向 \(d=2\)，步长 \(\alpha=1/4\)、Armijo 参数 \(c=1/2\)。计算 \(s\,y\) 的符号。
展开计算：下降通过，曲率失败
\(x_{\rm new}=3/2\)，\(f(x_{\rm new})=-9/4\le-1+(1/2)(1/4)(-2)(2)=-3/2\)，所以 Armijo 通过。可是 \(s=1/2\)、\(y=-3-(-2)=-1\)，故 \(sy=-1/2<0\)。任何一维正数 \(B_{\rm new}\) 都不可能满足 \(B_{\rm new}s=y\)，标准 BFGS 的保正定前提已经失败。此反例的目标无下界，也说明一次下降不等于存在可求的最小点。
再检查一个步长边界：对 \(f=x^2\)、\(L=2\)、\(\alpha=1.1\)，\(x_{k+1}=-1.2x_k\)；非零初值增长振荡。\(\alpha=1\) 时改为等幅翻转，\(\alpha=1/2\) 时则一步到零。三个现象来自同一个乘子。
下一页：Lagrange 对偶与 KKT 条件。