【优化】一篇入门之-拟牛顿法-介绍

拟牛顿法是牛顿法的改进版本，它围绕牛顿法“用二次曲面来近似当前迭代点”的思路，然后降低二次曲面的精度，从而避免使用Hession矩阵H，降低算法的实现难度以及计算量，大大提高了可实现性，DFP和BFGS法都属于拟牛顿法，下面就一步一步来看看拟牛顿法到底是怎么干的吧！

一、初识-拟牛顿法

我刚开始学拟牛顿法时，他们直接就把拟牛顿法的公式砸我脸上来了，学得我云里雾里，所以这里我们放慢一点速度，一步一步来，先说说拟牛顿法到底想干什么，再根据它的思想，来整理出它的公式，好了，开干！

1.1. 拟牛顿法-背景-牛顿法

大家都知道二次优化算法就是用二次曲面来近似当前迭代点，从而将x迭代到二次曲面的极值点处：

而牛顿法作为二次优化算法的老祖，使用泰勒二次展开来获得二次曲面：

从而得到迭代公式：

虽然牛顿法用泰勒二次展开的方法获得的二次曲面是最理想的，但这样就导致最终牛顿法的迭代公式要求Hession矩阵H，往往很难落地，那怎么才能避开Hession矩阵呢？于是，各种拟牛顿法就登场了。

1.2. 拟牛顿法-思想

我们都知道，拟牛顿法仍然用的是牛顿法那一套，而它们要干的就是如何避开Hession矩阵，那它们是怎么干的呢？它们的做法是，降低二次曲面的近似精度，如下：

如图所示，拟牛顿法并不要求二次曲面在点附近完全的近似目标函数

而是只要求： 

（1）在点与目标函数相切

这很好理解，既然是点的近似，肯定要在点相切，这样可以保持二次曲面与目标函数在点的一阶导是一致的。

（2）在点与目标函数一阶导数一致(即曲率一致) 

这样进一步限制了曲面的曲率，使它更加迫近目标函数。

（3）二次曲面取得的是极小值

这个条件当作是补丁就行了，因为满足(1)(2)的曲面，可能会开口向下，这就尴尬了。

实际就是限制二次曲面的切点、开口宽度、开口方向

可以注意到，拟牛顿法并没有改变牛顿法中的切点，因此它们所用的二次曲面的常数项、一次项是一致的，所以从数学的角度来理解，也可以认为拟牛顿法是找另一个矩阵来替代牛顿法中的Hession矩阵或：

总的来说，拟牛顿法除了获取二次曲面的方法与牛顿法略为不同之外，其余地方与牛顿法一致。

二、拟牛顿法-迭代公式与推导

好了，既然我们知道拟牛顿法到底想干什么了，那下面我们就用数学来描述整个要干的事情，然后进一步就可以推导出拟牛顿法的数学表述，马上开干！

上面说到了，拟牛顿算法的核心就是如何找出符合以下三个要求的二次曲面：

要求1：在点与目标函数相切

要求2：在点与目标函数一阶导数一致(即曲率一致) 

要求3：二次曲面取得的是极小值

那么，根据上述条件，我们就开始一步一步来推导吧！

2.1. 拟牛顿法-迭代公式

在处与相切的二次曲面可以表示为：

它的导数为：

令它的导数为0，即：

通过上式可求得它的最小解取值为：

因此，第k次的迭代量为：

其中，就是梯度，而呢，我们还不知道，那下面我们再具体来看看它需要满足什么数学条件，才能使上面的"要求2、要求3"成立。

2.2. 拟牛顿法-条件

先来看看要求2，它要求二次曲面在处的一阶导数与目标函数一致，即：

简化一下就可以得到，需要满足：

---------------我是分割线-------------------

再来看看要求3，它要求二次曲面取得的是极小值，事实上这等同于要求迭代量是一个下降量。而要保证迭代量是一个下降量，只需要是正定矩阵就可以了。

为什么B为正定矩阵时，h就一定是一个下降量呢？

不妨将 简记为，则有：

当B是正定矩阵时，也是正定，由可得， 这说明h与G方向不同，而梯度G是上升方向，所以自然就是一个下降方向了。

2.3. 拟牛顿法-公式总结

上面推导了这么多，我们来总结一下拟牛顿法的公式。

首先，拟牛顿法的迭代公式如下：

其中，是目标函数在处的梯度

然后，需满足如下条件：

(1) 满足拟牛顿条件：

其中，，即第次的迭代量                           

，即第次迭代后梯度的增量

(2) 是正定矩阵

      要求是正定矩阵，是为了保障迭代量一定是下降量

值得注意的是，拟牛顿法还有另一种表示形式，它将上述公式中的替换为，此时拟牛顿法就相当于用替代牛顿法中的Hession矩阵。

三、拟牛顿法-各种实现

3.1. 拟牛顿法-具体算法

从上面的公式可知，拟牛顿法的只有条件要求，而具体的取值方法不是固定的，所以拟牛顿法是一类型的算法的总称，不同的取值方法，就是不同的拟牛顿算法.

 常见的拟牛顿算法有：DFP算法，BFGS算法，L-BFGS算法，等等。

其中，BFGS算法是最常用的拟牛顿算法。L-BFGS算法则可认为是BFGS的"节省内存版本" 。

3.2. 拟牛顿法-迭代步长

拟牛顿法虽然提供了迭代点，但这更多时候仅仅作为一个迭代方向。

就牛顿法而言，它的迭代点未必是下降的，而拟牛顿算法的二次曲面更加的不准确，它的迭代点更加不可信，且拟牛顿法的二次曲面依赖于上一个迭代点，当迭代步长过大时，往往会使得曲面更加不准确。

因此，拟牛顿法一般会配以步长搜索算法，来确保拟牛顿法的稳定性，由于拟牛顿算法的迭代方向h是一个下降方向，即步长足够小时，朝该方向一定会下降。因此，拟牛顿法在配合步长搜索算法后，可以保障每次迭代都是下降的，也就确定了算法的稳定性。

 常用的步长搜索算法有：线性搜索算法、可信域搜索算法等等。

四、拟牛顿法-算法流程

最后的最后，我们来展示一下拟牛顿算法的算法流程图，它与牛顿法是差不多的，具体如下：

不同的拟牛顿算法在计算B时会略有不同，所以算法流程也会有所差异，但整体上是差不多的。

总结

总的来说，拟牛顿法就是牛顿法的改进，它牺牲了二次曲面的精度，用矩阵B来替代Hession矩阵，矩阵B只要满足正定、且满足拟牛顿条件就可以了，不同的拟牛顿算法就有不同的构造B的方法，常见的有DFP算法，BFGS算法，L-BFGS算法等等。