专题进阶 · 优化算法推荐总顺序 · 第 125 / 148 课

从二阶近似推导牛顿方向,理解正定曲率、线搜索及求根牛顿法的关系。

先学会这些,再进入本课 梯度下降 高斯消元
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 优化算法

牛顿优化Newton Optimization

解 Hessian 相关线性系统取得更新方向;非正定情况常需要阻尼或信赖域。

建议 50 分钟 · 含手算、代码与三层练习

本课要建立的能力

从二阶近似推导牛顿方向,理解正定曲率、线搜索及求根牛顿法的关系。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

梯度下降只知道坡往哪里低,能否利用弯曲程度直接估计谷底的位置?

02一步步得到方法

把局部目标近似为抛物面

一维二阶近似为 f(x+p)≈f(x)+f′(x)p+½f″(x)p²。若 f″(x)>0,右边是一条开口向上的抛物线,令其对 p 的导数为零,得到 p=−f′(x)/f″(x)。

多维写成 f(x+p)≈f(x)+gᵀp+½pᵀHp,其中 H 是二阶偏导组成的 Hessian。若 H 正定,解线性方程 Hp=−g 得到局部模型的唯一最小点。实际应解方程,通常不显式形成 H⁻¹。

求导数的零点与求最小值

对方程 f′(x)=0 使用求根牛顿法,也会得到相同更新式。但驻点可能是最大值;例如 f(x)=−x² 的 Newton 更新会到 0,而那里是最大值。正曲率条件不能省略。

本课一维实现检查二阶导数为正,否则退回负梯度方向。更复杂的多维算法会使用阻尼、修正 Hessian 或信赖域,让方向具有合理的下降性质。

局部模型也需要试探

即使方向是下降方向,直接取完整步长 1 也可能跨到局部近似失真的区域。Armijo 回溯从 α=1 开始反复减半,直到 f(x+αp)≤f(x)+cαf′(x)p。右侧要求与方向斜率相符的下降量。

适当条件下,靠近非退化最小值的牛顿法具有局部二次收敛;远离解时不能套用这项结论。下面代码明确限制在一维光滑函数,返回迭代轨迹便于观察。

03把一个小例子完全算清楚

f(x)=(x−3)²,x₀=0。

步骤计算与状态为什么这样做
计算局部曲率g=−6,h=2二阶导数为正
求牛顿方向p=−(−6)/2=3抛物线模型的最小点
检验完整步长x₁=3,f(x₁)=0此例局部模型就是原函数

窄屏可左右滑动表格,阅读完整计算与理由。

一次完整牛顿步到达 3;一般非二次函数不具备这个一步到位的性质。

04为什么这个方法成立

  1. 对正曲率的二次模型求导可得唯一极小点 p=−g/h。
  2. h>0 且 g≠0 时 gp=−g²/h<0,所以它是严格下降方向。
  3. 足够小的正步长满足局部下降;回溯寻找可接受步长,失败时应报告而非无条件更新。

05把推导翻译成代码

Python · 一维牛顿最小化与 Armijo 回溯

def newton_minimize_1d(f, derivative, second_derivative, initial,
                       steps=100, tolerance=1e-10):
    x = float(initial)
    trace = [x]
    for _ in range(steps):
        g = derivative(x)
        if abs(g) <= tolerance:
            return x, trace
        h = second_derivative(x)
        direction = -g / h if h > 1e-12 else -g
        alpha = 1.0
        for _ in range(60):
            if f(x + alpha * direction) <= f(x) + 1e-4 * alpha * g * direction:
                break
            alpha *= 0.5
        else:
            raise ArithmeticError("line search failed")
        x += alpha * direction
        trace.append(x)
    return x, trace

print(newton_minimize_1d(lambda x: (x-3)**2,
      lambda x: 2*(x-3), lambda x: 2, 0)[0])

逐个理解关键决定

h > 1e-12
一维中检查正曲率并避免除以极小数;这是教学保护阈值,不是所有问题通用的数值尺度。
1e-4 * alpha * g * direction
Armijo 充分下降条件,其中方向导数 g×direction 应为负。
else:
这里属于 for 循环:用尽回溯次数仍未满足条件,就显式失败。

06时间、空间与实现范围

一维每步成本由导数、二阶导数和回溯中的函数计算次数决定。

多维稠密 Hessian 需 O(d²) 存储,通用直接求解通常 O(d³);稀疏或结构化问题可以显著不同。

07改变条件,检查哪里会出错

Newton 自动找到最小值

求驻点与求最小值不同,负曲率需要专门处理。

总是二次收敛

这是解附近、Hessian 非退化等条件下的局部结论。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

f(x)=5(x−2)²,从 10 出发的 Newton 方向是多少?

需要一点提示

计算 g=10(x−2),h=10。

查看解析与答案

p=−8,完整一步到 2。

练习 2 · 边界与辨析

f(x)=−x² 的 Hessian 为什么不适合最小化?

需要一点提示

看二阶模型的开口。

查看解析与答案

Hessian 为负,局部模型无有限最小点;导数零点 0 反而是最大值。

练习 3 · 变式与迁移

多维实现为何推荐解 Hp=−g?

需要一点提示

想想求逆的额外工作与误差。

查看解析与答案

直接求解可利用矩阵结构,通常比先显式求逆再乘向量更合适。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Boyd 与 Vandenberghe · Convex OptimizationDive into Deep Learning · 优化算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。