拟 Newton 法与 DFP 更新

Views: --

Newton 法快，却要计算和分解 Hessian。拟 Newton 法只用相邻点的梯度变化，逐步学习一个曲率矩阵。

割线方程

记

sk=xk+1−xk,yk=gk+1−gk.s_k=x_{k+1}-x_k,\qquad y_k=g_{k+1}-g_k.

若 Hessian 在这一步附近近似不变，Taylor 展开给

yk≈∇2f(xk+1)sk.y_k\approx \nabla^2f(x_{k+1})s_k.

若 Bk+1B_{k+1} 近似 Hessian，应满足

Bk+1sk=yk.B_{k+1}s_k=y_k.

若 Hk+1H_{k+1} 近似逆 Hessian，则割线条件为

Hk+1yk=sk.H_{k+1}y_k=s_k.

一个向量方程不足以唯一确定矩阵，所以还要要求对称、尽量接近旧矩阵，并保持正定。

DFP 更新

DFP 直接更新逆 Hessian 近似：

Hk+1=Hk+skskTskTyk−HkykykTHkykTHkyk.H_{k+1}=H_k+\frac{s_ks_k^T}{s_k^Ty_k} -\frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k}.

把 yky_k 乘进去：第二项给 sks_k，第三项抵消 HkykH_ky_k，所以确实满足 Hk+1yk=skH_{k+1}y_k=s_k。

搜索方向为

dk=−Hkgk,d_k=-H_kg_k,

再配合一维搜索计算 xk+1x_{k+1}。

正定性

若 Hk≻0H_k\succ0 且

skTyk>0,s_k^Ty_k>0,

则 DFP 更新保持正定，因而 dkd_k 是下降方向：

gkTdk=−gkTHkgk<0.g_k^Td_k=-g_k^TH_kg_k<0.

对强凸函数，满足 Wolfe 曲率条件的线搜索可保证 skTyk>0s_k^Ty_k>0。若这个内积过小或为负，直接更新会数值不稳，应跳过或阻尼修正。

与 BFGS 的关系

课程重点是 DFP，但应知道 BFGS 是更常用的兄弟方法。DFP 更新逆 Hessian；BFGS 可视为在对偶意义下更新 Hessian，其数值鲁棒性通常更好。两者在正定二次函数配合精确搜索时会产生共轭方向。

一个一维直觉

一维时 HH 只是一个数，割线条件直接给

Hk+1=skyk,H_{k+1}=\frac{s_k}{y_k},

即用“位置变化 / 梯度变化”估计逆曲率。多维 DFP 正是在保持对称正定的前提下推广这个想法。

算法步骤

  1. 给定 x0x_0 和 H0=IH_0=I；
  2. dk=−Hkgkd_k=-H_kg_k；
  3. 一维搜索得 αk\alpha_k，更新 xk+1x_{k+1}；
  4. 计算 sk,yks_k,y_k，检查 skTyks_k^Ty_k；
  5. 用 DFP 公式更新，直到梯度足够小。

考试要点

  • sks_k 是点差，yky_k 是梯度差，别写反。
  • 会验证 DFP 满足割线条件。
  • 正定保持的关键是 skTyk>0s_k^Ty_k>0。
  • 拟 Newton 避免显式 Hessian，但仍需要梯度；它不是“无导数直接法”。

评论