机器学习优化算法-牛顿法

Love The Way You Lie 2022-09-15 15:47 114阅读 0赞

**目录**

牛顿法的数学理解：

使用牛顿法的原因

谈一下线性逼近

线性逼近的应用>牛顿-拉弗森方法

方法的理解

牛顿-拉弗森方法的代数解法

局限性

最优化中得牛顿法应用

--------------------

# 牛顿法的数学理解： #

## 使用牛顿法的原因 ##

并不是所有的方程都有求根公式，或者求根公式很复杂，导致求解困难，例如五次及以上多项式方程没有根式解（就是没有像二次方程那样的万能公式），这个是被伽罗瓦用群论做出的最著名的结论。我们可以利用牛顿法，迭代逼近最优解达到求解目的。

## 谈一下线性逼近 ##

我们先说一个结论，就是切线是曲线的线性逼近，怎么理解呢？

假设 f(x) = x^2 这个函数，图像如下:

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_15_color_FFFFFF_t_70_g_se_x_16][]

函数 f(x) 上的任意一点 A ,找出对应的切线 q(x), 我们可以说在A点附近 q(x) 近似于 f(x)，且距离A点越近误差越小。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_15_color_FFFFFF_t_70_g_se_x_16 1][]

## 线性逼近的应用>牛顿-拉弗森方法 ##

## 方法的理解 ##

牛顿-拉弗森方法提出来的思路就是利用切线是曲线的线性逼近这个思想，他们发现在很多函数求解的情况下(后边会提到有很多情况是不适用的)，利用线性逼近多次迭代后会越来越接近曲线的根。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_14_color_FFFFFF_t_70_g_se_x_16][]

如上图右侧，f(x) 上找随机点x0找切线 q(x0) ，对 q(x0)的切线根(x1,0)(就是切线与X轴的交点) 做垂线，与f(x)角点再做切线得到 q(x1) ，对 q(x1)的切线根(x2,0)做垂线 ...... 最终找到逼近 f(x)根解的切线。

## 牛顿-拉弗森方法的代数解法 ##

已知曲线函数 f(x)，在任意点 xn处做曲线的切线，切线的根点为(x(n+1),0)

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_15_color_FFFFFF_t_70_g_se_x_16 2][]

可以得到xn点的切线方程为

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16][]

其实就是泰勒公式，要想求x(n+1)相当于求

f(xn) + f'(xn)(x(n+1)-xn)=0

则

x(n+1) - xn = - ( f(xn) / f'(xn) )

最终得

![182fccbcea284fe091d87c4199362cd0.png][]

## 局限性 ##

however，不是所有函数求解都可以利用线性逼近来做，也就是牛顿-拉弗森方法不一定总是收敛，不一定可以求得足够近似的根，是否可以使用这种方法的充分条件是**若f(x) 二阶可导，那么在待求的零点x 周围存在一个区域，只要起始点x0 位于这个邻近区域内，那么牛顿-拉弗森方法必定收敛。**

# 最优化中得牛顿法应用 #

在最优化的问题中，线性最优化至少可以使用单纯行法求解，但对于非线性优化问题，牛顿法提供了一种求解的办法。假设任务是优化一个目标函数f(x)，求函数f的极大极小问题，可以转化为求解函数f的导数f(x)'=0的问题，这样求可以把优化问题看成方程求解问题（f(x)'=0）。剩下的问题就和上边提到的牛顿法求解很相似了。

这次为了求解f(x)'=0的根，把f(x)的泰勒展开，展开到2阶形式：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_11_color_FFFFFF_t_70_g_se_x_16][]

这个式子是成立的，当且仅当 Δ*x* 无线趋近于0。此时上式等价与：

![06585e64c25645d7b607839c68ad24de.png][]

Δ*x* 就是 x(n+1) - xn ,因此得出迭代公式：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_8_color_FFFFFF_t_70_g_se_x_16][]

一般认为牛顿法可以利用到曲线本身的信息，比梯度下降法更容易收敛，如下图看出牛顿法步子会很大，迭代更少次数就可以求得最优解。

![de6922863cb3bf08d71a18dff04b6416.gif][]

在上面讨论的是2维情况，高维情况的牛顿迭代公式是：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16][]

其中H是hessian矩阵，定义为：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16 1][]

高维情况依然可以用牛顿迭代求解，但是问题是Hessian矩阵引入的复杂性，使得牛顿迭代求解的难度大大增加，但是已经有了解决这个问题的办法就是**拟牛顿法Quasi-Newton methond**，不再直接计算hessian矩阵，而是每一步的时候使用梯度向量更新hessian矩阵的近似。

参考：[如何通俗易懂地讲解牛顿迭代法？\_马同学-CSDN博客][-CSDN]

[最优化-牛顿法（Newton）\_michaelhan3的博客-CSDN博客][-_Newton_michaelhan3_-CSDN]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/497be3fd06564679ac575a559b61e726.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_15_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/115cdb20ff744150bda3d80b3e14b8e2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/9a4b62948abe45d4b57d57219d8bb636.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_15_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/5be4275503374cebb4cd8a88683efec8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c76511f96f7f432cba4f8e4d0427ece4.png
[182fccbcea284fe091d87c4199362cd0.png]: /images/20220828/6670aff7bc7d458090004d6da23b0d4c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e33d59b459d5403fb760639fd98da870.png
[06585e64c25645d7b607839c68ad24de.png]: /images/20220828/5e765ea619754336aac63ab34157705a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_8_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a2fe3c559ea54c369156a889117c28b5.png
[de6922863cb3bf08d71a18dff04b6416.gif]: /images/20220828/04e1f12a71e34bef8f128b5e45c6137d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/0968500f23a0425eafe2784605f87938.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/4a9bed2ff9c345899d9187ae0c2bdbc0.png
[-CSDN]: https://blog.csdn.net/ccnt_2012/article/details/81837154?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163410425816780264069985%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163410425816780264069985&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-1-81837154.first_rank_v2_pc_rank_v29&utm_term=%E8%AF%A6%E8%A7%A3%E7%89%9B%E9%A1%BF%E6%B3%95&spm=1018.2226.3001.4187
[-_Newton_michaelhan3_-CSDN]: https://blog.csdn.net/michaelhan3/article/details/82350047?ops_request_misc=&request_id=&biz_id=102&utm_term=%E8%AF%A6%E8%A7%A3%E7%89%9B%E9%A1%BF%E6%B3%95&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-82350047.first_rank_v2_pc_rank_v29&spm=1018.2226.3001.4187