3个回答
牛顿法是用来求根的。
比如说要求$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-22 13:09
当我们用牛顿法来求根,牛顿法是基于一阶导数的。
当我们用牛顿法来优化,牛顿法就是基于二阶导数的。
SofaSofa数据科学社区DS面试题库 DS面经
谢谢!
-
七号信仰
2017-09-22 13:09