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为什么这个方法成立
- 对正曲率的二次模型求导可得唯一极小点 p=−g/h。
- h>0 且 g≠0 时 gp=−g²/h<0,所以它是严格下降方向。
- 足够小的正步长满足局部下降;回溯寻找可接受步长,失败时应报告而非无条件更新。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
f(x)=5(x−2)²,从 10 出发的 Newton 方向是多少?
需要一点提示
计算 g=10(x−2),h=10。
查看解析与答案
p=−8,完整一步到 2。
f(x)=−x² 的 Hessian 为什么不适合最小化?
需要一点提示
看二阶模型的开口。
查看解析与答案
Hessian 为负,局部模型无有限最小点;导数零点 0 反而是最大值。
多维实现为何推荐解 Hp=−g?
需要一点提示
想想求逆的额外工作与误差。
查看解析与答案
直接求解可利用矩阵结构,通常比先显式求逆再乘向量更合适。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Boyd 与 Vandenberghe · Convex OptimizationDive into Deep Learning · 优化算法