牛顿法到底是一阶优化算法还是二阶优化算法?

  数学 数值计算 最优化    浏览次数:12634        分享
14

我知道牛顿法是利用一阶导数来求根的。这个例子也是用的一阶导数。

但是我最近又听很多人说牛顿法是二阶算法,所以我就混乱了。

请求指点!

谢谢!


 

七号信仰   2017-09-20 22:57



   3个回答 
30

牛顿法是用来求根的。

比如说要求$f(x)=0$的解,先随机选个初始点$x_0$,然后开始迭代。迭代公式为

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_{n})}$$

当$|x_{n+1}-x_n|<\epsilon$时($\epsilon$为你设置的容忍误差),迭代结束,$x_{n+1}$就是$f(x)=0$的近似数值解。

可以清楚地看到,在迭代公式中我们使用了一阶导数$f'(x)$。所以此处牛顿法是一阶算法。


但是,当我们将牛顿法用作优化算法的时候,它就是二阶的。

假设我们有一个凸优化问题

$$\min_{x} f(x)$$

也就是说我们要找一个$x$来最小化$f(x)$。对于凸优化问题,$f(x)$的最小值点就是$f(x)$的极值点,也就是导数为0的点。那么我们上面的优化问题就转换为了如下的求根问题

$$f'(x)=0.$$

利用牛顿法求解上面的式子,我们先选取初始点$x_0$,然后进行如下迭代

$$x_{n+1}=x_n-\frac{f'(x_n)}{f''(x_n)}$$

直到$|x_{n+1}-x_n|<\epsilon$。

综上,牛顿法求根是一阶算法,我们将优化问题转为求根问题需要一阶导数,所以用牛顿法进行最优化是二阶算法。


SofaSofa数据科学社区DS面试题库 DS面经

高代兄   2017-09-21 11:10

茅塞顿开! - 七号信仰   2017-09-22 13:09
17

当我们用牛顿法来求根,牛顿法是基于一阶导数的。

当我们用牛顿法来优化,牛顿法就是基于二阶导数的。

SofaSofa数据科学社区DS面试题库 DS面经

sasa   2017-09-21 09:16

谢谢! - 七号信仰   2017-09-22 13:09
-1

马什么梅,什么冬梅,马东什么?

SofaSofa数据科学社区DS面试题库 DS面经

wangzhongruo   2020-01-14 02:55



  相关讨论

Newton–Raphson和牛顿法区别?

随机平均梯度法(Stochasitc Average Gradient)和随机梯度下降(SGD)有什么区别

nesterov’s momentum和momentum的区别?

梯度上升算法是什么?

对于小批量随机剃度下降法(mini-batch SGD),如何选择每批样本的数量?

最速下降法与梯度下降法

随机梯度下降(sgd)的收敛问题

Adam优化算法

为什么梯度的反方向是函数下降最快的方向?

用SGD时陷入局部最优解的解决方法

  随便看看

numpy里矩阵乘法matmul,@和dot的区别?

软聚类,硬聚类?

修正R方(adjusted R square)是什么?

python里怎么计算曼哈顿距离?

pandas DataFrame中经常出现SettingWithCopyWarning