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

  数学 数值计算 最优化    浏览次数: 1073
13

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

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

请求指点!

谢谢!


 

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



   2个回答 
16

牛顿法是用来求根的。

比如说要求$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$。

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


高代兄   2017-09-21 11:10

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

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

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

sasa   2017-09-21 09:16

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


  相关主题

Adam优化算法   1回答

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

最速下降法与梯度下降法   1回答

RMSProp的直白解释   1回答

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

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

梯度上升算法是什么?   2回答

线性回归有精确的解析解为什么还要用梯度下降得到数值解?   4回答

什么是Hessian矩阵和Jacobian矩阵   1回答

python里用来做数值优化的库?   2回答

关于随机梯度下降法(SGD)的问题   1回答

怎么用牛顿法近似求解根号2?   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!