今日面试题分享：什么是拟牛顿法（Quasi-Newton Methods）？

今日面试题分享

什么是拟牛顿法（Quasi-Newton Methods）

参考答案：

解析：

拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。 

另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。 

具体步骤： 拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型：

这里Bk是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点：

其中我们要求步长ak 满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hessian矩阵Bk 代替真实的Hessian矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk 的更新。现在假设得到一个新的迭代xk+1，并得到一个新的二次模型：

我们尽可能地利用上一步的信息来选取Bk。具体地，我们要求

从而得到

这个公式被称为割线方程。常用的拟牛顿法有DFP算法和BFGS算法。 本题解析来源：@wtq1993，链接：http://blog.csdn.net/wtq1993/article/details/51607040

题目来源：七月在线官网（www.julyedu.com）——面试题库——面试大题——机器学习

今日学习推荐

【OCR文字识别实战】

开班时间：2019年3月9日（本周六）

国内首套全面公开OCR技术的实战课程

四大应用场景  四大课程特色  六大项目实战

有意的亲们抓紧时间喽

咨询/报名可添加微信客服

julyedukefu_02

扫描下方二维码

了解更多课程详情优惠

长按识别二维码

▼

往期推荐

▼

一文详解机器学习中最好用的提升方法：Boosting 与 AdaBoost

必备收藏！8500+公开代码论文，950多项机器学习任务最优结果汇总

我在GitHub上找到了中科大的计算机课程资源必读！

点

咨询，查看课程，请点击“阅读原文”

给我【好看】

你也越好看！