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

  数学 数值计算 最优化
12

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

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

请求指点!

谢谢!


 

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



   2个回答 
13

牛顿法是用来求根的。

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

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

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

sasa   2017-09-21 09:16

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


相关问题

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

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

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

Adam优化算法   1回答

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

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

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

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

神经网络里的batch size和sgd里的batch size是一回事嘛?   1回答

PCA和SVD是一回事吗?   1回答

凸优化中局部最优解就是全局最优解吗?   2回答

什么样的优化问题算是凸优化?   1回答



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

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

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

我们谢绝答非所问。

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

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