首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

最优化理论与方法-牛顿迭代法后续

目录:

(1)牛顿迭代法在数学中求解方程的根。

(2)最优化理论与方法中牛顿迭代法应用。

(3)对Hessian矩阵的深入讨论。

(4)牛顿法与梯度下降法的区别。

(一)牛顿迭代法在数学中求解方程的根

(1)数学中牛顿迭代法和最优化理论与方法中牛顿迭代法的区别?

(2)最优化理论与方法中,牛顿迭代法为什么要计算海森矩阵?

(二)最优化理论与方法中牛顿迭代法应用

首先,在我的上一篇文章《最优化理论与方法-牛顿迭代法》中,我们推出了牛顿迭代法的基本公式:

上面(1)式是为了求解f(x)=0的时候,x的值。但是在最优化理论与方法中,我们用的不是上面(1)式。

在机器学习的最优化理论与方法中,求解最优化问题时,我们一般是为了求解minf(x),即f’(x)=0,极值点x的值。也就是实际迭代中,我们用到的是(2)式。

我们有了在机器学习中最优化理论与方法的牛顿迭代法的迭代公式(2)式。那么,我们再来思考一下,(2)式的由来。我们是求f’(x)=0的根。把f(x)泰勒展开,展开到2阶形式。

这个(3)式是成立的,当且仅当无限趋近于0时。此时,(3)式中:

我们对求导,为什么对求导呢?因为对求导可以得到的表达式。得到下面公式(5):

求解得:

得到迭代公式(2)。从公式(2)中,我们可以看出,与之间的差距就是:

注意:这就是最优化理论与方法中,牛顿法是要求二阶导数的,并且还要讨论二阶收敛性。经过上面的解释,大家对牛顿迭代法二阶收敛应该有比较直观的理解吧!

(三)对Hessian矩阵的深入讨论

对于高维函数,用牛顿法求极值也是(2)式这个形式,只不过这里的f’(x)和f’’(x)都变成了向量和矩阵。而且我们可以想象一下,高维函数二阶导数有多个,如下:

假设:f(X)是关于x1、x2、x3、… …、xn的高维函数映射,那么f’(x)如公式(7)所示:

那么,f’’(x)就是Hessian矩阵,定义如公式(8)所示:

高维情况下,迭代公式如下:

高维情况依然可以用牛顿迭代求解,但是问题是Hessian矩阵引入的复杂性,使得牛顿迭代求解的难度大大增加,但是已经有了解决这个问题的办法就是拟牛顿法(Quasi-Newton method),拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷,它使用正定矩阵来近似Hessian矩阵的逆,从而简化了运算的复杂度。感兴趣的同学,可以接着了解一下拟牛顿法。

(1) Hessian矩阵的对称性

如果函数f在D区域内二阶连续可导,那么f的Hessian矩阵在D内为对称矩阵。

原因:如果函数f的二阶偏导数连续,则二阶偏导数的求导顺序没有区别,即

则对于矩阵,有,所以为对称矩阵。

(2) 利用海森矩阵判定多元函数的极值

(四)牛顿法和梯度下降法的区别

1.牛顿法优点:

在最优化问题中,牛顿法比梯度下降法求解需要的迭代次数更少。

原因:牛顿法是二阶收敛,梯度下降是一阶收敛,所以牛顿法就更快。如果更通俗地说的话,比如你想找一条最短的路径走到一个盆地的最底部,梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步,牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。所以牛顿法比梯度下降法看得更远一点,能更快地走到最底部。根据wiki上的解释如图1所示,从几何上说,牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面,而梯度下降法是用一个平面去拟合当前的局部曲面,通常情况下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最优下降路径。红色是牛顿法的迭代路径,绿色的是梯度下降法的迭代路径。

图1:牛顿法与梯度下降法的区别

2.牛顿法缺点:

(1)对目标函数有严格的要求,必须有连续的一、二阶偏导数,海森矩阵必须是正定的。

(2)计算量大,除计算梯度外,还需要计算二阶偏导矩阵及其逆矩阵。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180406G1A0RK00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券