拟牛顿法

牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息, 而计算Hesse矩阵工作量大, 并且有的目标函数的Hesse矩阵很难计算, 甚至不好求出来, 这就导致仅用目标函数的一阶导数的方法, 拟牛顿法就是利用目标函数值和一阶导数信息, 构造出目标函数的曲率近似, 而不需要明显形成Hesse矩阵, 同时具有收敛速度快的优点.

一: 拟牛顿法条件
目标函数\(f\)在\({x_{k + 1}}\)附近的二次近似为:
\[f(x) \approx f({x_{k + 1}}) + g_{k + 1}^T(x - {x_{k + 1}}) + \frac{1}{2}{(x - {x_{k + 1}})^T}{G_{k + 1}}(x - {x_{k + 1}})\]
对上面的式子两边求导, 有\(g(x) \approx {g_{k + 1}} + {G_{k + 1}}(x – {x_{k + 1}})\). 令\(x = {x_k},{s_k} = {x_{k + 1}} – {x_k},{y_k} = {g_{k + 1}} – {g_k}\),得\(G_{k + 1}^{ – 1}{y_k} \approx {s_k}\).对于二次函数, 此式精确成立. 现在我们想在牛顿法中构造出的Hesse逆近似\({H_{k + 1}}\)满足这种关系. 即:
\[H_{k + 1}^{}{y_k} = {s_k}\]
上式是关于Hesse逆近似的拟牛顿条件.类似地, 也可以考虑用\({B_k}\)来直接逼近Hesse矩阵, 这时, 相应的拟牛顿条件为, \(B_{k + 1}^{}{s_k} = {y_k}\).
拟牛顿法(Hesse逆近似)的主要步骤为:
1). 令\({d_k} = – H_k^{}{g_k}\);
2). 沿方向\({d_k}\)作线性搜索, 得到\({x_{k + 1}} = {x_k} + {\alpha _k}{d_k}\);
3). 校正\({H_k}\)产生\({H_{k + 1}}\).
与牛顿法相比, 拟牛顿法有下列优点:
1). 仅需要一阶导数; (牛顿法需要二阶导数)
2). \({H_k}\)保持正定, 使得方法具有下降性质; (在牛顿法中, \(G_k^{}\)可能不定)
3). 每次迭代需\({\rm O}({n^2})\)次乘法. (牛顿法需\({\rm O}({n^3})\)次乘法)

二: DFP校正(Davidon-Fletcher-Powell)
利用Hesse逆近似方法构造\(H_{k + 1}^{}\)进行校正的思路是这样的, 假设每一步迭代中矩阵\(H_{k + 1}^{}\)是由\(H_k^{}\)加上两个附加项构成的, 即\(H_{k + 1}^{}{\rm{ = }}H_k^{}{\rm{ + }}{P_k}{\rm{ + }}{Q_k}\), 其中\({P_k},{Q_k}\)是待定矩阵, 这时\(H_{k + 1}^{}{{\rm{y}}_k}{\rm{ = }}H_k^{}{{\rm{y}}_k}{\rm{ + }}{P_k}{{\rm{y}}_k}{\rm{ + }}{Q_k}{{\rm{y}}_k}\). 为使\(H_{k + 1}^{}\)满足拟牛顿条件, 得到DFP校正迭代公式为: \[H_{k + 1}^{}{\rm{ = }}H_k^{} + \frac{{{s_k}s_k^T}}{{s_k^T{y_k}}} - \frac{{{H_k}{y_k}y_k^T{H_k}}}{{y_k^T{H_k}{y_k}}}\]
DFP方法是一个实际上广为采用的方法, 它在理论分析和实际应用中都起了很大作用. 但是, 进一步的研究发现, DFP方法具有数值不稳定性, 有时产生数值上奇异的Hesse近似. 而BFGS校正克服了DFP校正的缺陷.

三: BFGS校正(Broyden-Fletcher-Goldfarb-Shanno)
利用Hesse近似方法构造\(B_{k + 1}^{}\)进行校正. 思路和上面类似. 可以得到BFGS校正迭代公式: \[B_{k + 1}^{}{\rm{ = }}B_k^{} + \frac{{{y_k}y_k^T}}{{y_k^T{s_k}}} - \frac{{{B_k}{s_k}s_k^T{B_k}}}{{s_k^T{B_k}{s_k}}}\]
BFGS校正是迄今最好的拟牛顿公式. 它具有DFP校正所具有的各种性质. 此外, 当采用不精确线性搜索时, BFGS公式还具有总体收敛性质, 这个性质对于DFP公式还没有证明. 在数值执行中, BFGS公式也优于DFP公式, 尤其是它常常能与低精度线性搜索方法一起连用.

[参考] 1. <最优化理论与方法>.袁亚湘院士著.
2.<统计学习方法>.李航著

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>