牛顿法和高斯牛顿法

看代码的过程中遇到了高斯-牛顿法，感慨于自己作为调包侠，对各种最优化方法知之甚少，于是学习了一下这个算法。费曼技巧推崇以教促学，遂在此写一个简单的教程，希望整理思路以备复习的同时，也能帮助到和我一样的初学者。

本文所涉算法的研究目标是寻找多元二阶可微函数的极小值点，即:

本文首先介绍牛顿法（也称作 Newton-Raphson 方法），然后介绍高斯-牛顿法。

牛顿法

牛顿法的推导基于二阶可微函数的泰勒展开，以一维函数为例:

(2) 式是对f(x)在xn处的二阶近似。如下图所示：

蓝色曲线代表原函数f(x)，绿色圆点代表当前点xn，橘黄色的抛物线就是原函数在xn附近的泰勒展开。不难发现，在xn附近，抛物线和原函数曲线基本重合。也就是说，可以用抛物线方程代替原函数方程，而抛物线导函数的零点即为xn+1：

解得：

(4) 即为一维函数的牛顿法迭代公式。

对于高维函数，推导过程基于多元函数的泰勒展开：

(5) 是用高维二次曲面在xn处逼近原函数，如下图所示：

令 (5) 对x的导函数为 0：

解得：

牛顿法的优点是收敛速度快，缺点是需要求矩阵的逆，计算量比较大。此外，如果矩阵非正定（在一维情况下表现为泰勒展开的二阶导数小于0），极值点为极大值，而非极小值。如果初始位置离最优点太远，也会导致迭代过程中目标函数不严格递减的情况。

高斯-牛顿法

高斯-牛顿法是牛顿法的特例，用于解非线性最小二乘问题。

假设观测到 N 个数据点 {(x1,y1),(x2,y2),…(xn,yn)}，希望找到包含 M 个参数的非线性函数 f(x,a1,a2,…am)，拟合上述N个数据点。 为了方便书写，记: f1(a) = f(x1,a1,…am)。则最小二乘的目标函数为：

我们需要找到 a = [a1,a2,..am]T，使得 (8) 的值最小。

将 (8) 对aj求导：

令：

(9) 可以写成向量形式：

接下来求海森矩阵第 k 行 j 列的元素：

由 (11) 可知：

其中：

把 (10) 和 (12) 带入 (7) 得：

很多时候 (13) 中的S可以忽略，最终高斯-牛顿法的迭代公式为：

除了借助牛顿法之外，高斯牛顿法还可以直接通过多元函数的一阶泰勒展开推导：

我们希望找到 an+1使得 (10) 为 0 。

根据多元函数的一阶泰勒展开：

，(10) 可以变为（注意 (15) 的第一行括号外的 JT仍然用 J(an)T近似）：

即：

(16) 与 (14) 相同。