【优化】一篇入门之-高斯-牛顿算法

牛顿法大家都知道了，今天我们来说说高斯牛顿法，它是一种常用于目标优化函数为MSE(均方误差)时的二次优化算法，它是一种二次优化算法，但相比牛顿法，它可以不用求Hession矩阵，所以会更容易落地许多。下面我们就一起来看看高斯牛顿法的强大与巧妙吧~！

一、高斯牛顿法

前言

我们都知道，二次优化算法的思想就是在当前迭代点用二次曲面来近似目标函数，然后再把迭代点迭代到二次曲面的极值点处，如下：

其中牛顿法就是二次优化算法的开山鼻祖，但是，牛顿法要用到Hession矩阵，也就是二阶导，这使得比较难以落地，因此，就提出了各种其它二次优化算法，核心就是既要能得到二次曲面，又能避开Hession矩阵。

高斯牛顿法是为目标函数为平方和形式时，量身订造的一种二次优化算法，它利用了误差函数是误差的平方这一特性，用一阶的平方来近似获取二阶信息，从而避开Hession矩阵的计算，下面赶快让我们来看看这到底是怎么一回事。

1.1. 高斯牛顿法-初识

为了容易理解思想，这里我们以一元函数举例，假设，我们的优化目标函数是一系列函数的平方和，如下：

那么，按照牛顿法的做法，就是把它的二阶泰勒展开，来作为近似曲面，如下：

可见，项的系数就是二阶导，多元函数时也就是要求Hession矩阵了，难搞！那怎么才能不去算这个平方项前的二阶导呢？高斯牛顿法是个善于观察的孩子，他竟然发现，目标函数里就有"平方"了！这岂不是直接挪过来用就可以了？我们看看它怎么挪来用的，如下：

上面是啥意思呢，其实它就是用来近似，然后利用平方，展开后就得到了二次项了。

1.2. 高斯牛顿法-迭代公式

好了，在这里我们先展示高斯牛顿法的迭代公式，下面再来推导公式的由来。

高斯-牛顿迭代法，是一种目标函数为多个函数的平方和时的优化算法，即目标函数形式如下：

高斯-牛顿迭代法的思想与牛顿法一样，每次迭代时，将  迭代到在当前的二次近似曲面的极值处，与牛顿法不同的是，它的迭代公式不需计算二阶导(Hession矩阵)， 高斯-牛顿法的迭代公式如下

 其中，是函数向量：

  是雅克比矩阵:

二、高斯牛顿法-推导过程

好了，下面我们一起来推导一下高斯牛顿法的公式是怎么推导出来的。

2.1. 高斯牛顿法-目标函数

我们先来看看高斯牛顿法所优化的目标函数，并用向量形式来表示它。

高斯牛顿法只优化平方和形式的目标函数，即：

用向量形式来表示，则是：

  其中

  备注：和都是列向量

2.2. 高斯牛顿法-二次曲面

好了，下面我们来看看高斯牛顿法所采用的二次曲面是什么。

与牛顿法的思想一样，现在希望求得在处的二次近似曲面，为了避开Hession矩阵，高斯牛顿法取  一阶近似，如下：

其中是雅克比矩阵:

那么

 从而在处的二阶近似(即二次近似曲面)为

2.3. 高斯牛顿法-迭代公式

好了，最后，我们来看看高斯牛顿法的迭代公式是什么。

高斯牛顿法每次迭代都是将x迭代到二阶近似曲面的驻点，要求二阶近似曲面的驻点，只需令二阶近似曲面的偏导数为0， 如下：

所以，可求得二阶近似曲面的极值处为：

所以，高斯-牛顿法的迭代公式为：

以上就是高斯牛顿法的迭代公式推导了。

三、高斯牛顿法-相关证明  

3.1.的意义

高斯牛顿法中的迭代量为，其中的实际就是梯度。

证明如下

3.2. 高斯-牛顿法下降的证明

下面证明h能够使F下降，如下：

所以，当是正定时，，从而 也大于0，可得小于0，说明 h 是个下降的方向。

总结

好了，这节我们学习了高斯牛顿法，其实它的巧妙之处就是，利用目标函数中的平方项，来获得二次曲面中的平方项，从而避开Hession矩阵的计算。这里就不带大家写代码了，大概了解它是个什么东西，以及它的公式就好了，其余的，其实和牛顿法都比较相似。