1. 牛顿法
牛顿法(Newton's method)是一种近似求解方程的方法，它使用函数$f(x)$的泰勒级数的前面几项来寻找方程$f(x)=0$的根，后来由于最优化研究兴起后，将其应用在了最优化领域。
牛顿法和梯度下降法的目标一样，都是通过迭代法寻找导数为0的点，核心思想是在迭代点用二次函数（泰勒级数）来逼近目标函数，得到导数为0的方程，求解该方程，得到下一个迭代点，就这样不断迭代，直到到达导数为0的点处。
2. 牛顿法的代数方法理解
我们同样先用易懂的代数方法进行描述，然后再理解矩阵方法的描述
如有有同学不太了解泰勒级数，可以先看维基百科-泰勒级数对其有个大致的了解就可以了。
假设目标函数$f(x)$, 我们对其在$x_0$处做泰勒展开，其公式如下：
$$
f(x) = f(x_0) + f’(x_0)(x-x_0) + \frac{1}{2} f’’(x_0)(x-x_0)^2 + \ldots + \frac{1}{n!}f^{(n)}(x_0)(x-x_0)^n
$$
我们忽略那些高阶无穷小的项，在这里也就是二次以上的项，也就是
$$
f(x) = f(x_0) + f’(x_0)(x-x_0) + \frac{1}{2} f’’(x_0)(x-x_0)^2
$$
现在再对等式两边其进行求导，并令其为0，即
$$
\begin{split}
f’(x) &= 0 + f’(x_0) + \frac{1}{2} f’’(x_0) * (2(x-x_0)) \\\
&= f’(x_0) + f’’(x_0)(x-x_0)
\end{split}
$$
令左式为0，即得
$$
0 = f’(x_0) + f’’(x_0)(x-x_0)
$$
可得
$$
x = x_0 - \frac{f’(x_0)}{f’’(x_0)}
$$
这样我们就得倒了下一个迭代点，只要重复这个过程直到是导数为0的点，这样我们就有了代数方法的牛顿迭代公式，如下
$$
x_{i+1} \leftarrow x_i - \frac{f’(x_i)}{f’’(x_i)}
$$
2.2 牛顿法的矩阵方法理解
在实际应用中我们主要面对向量和矩阵的情况。便于理解，在矩阵方法中会需要矩阵微分的基础知识，网上有很多相关资料，推荐wikipedia-Matrix_calculus
2.2.1 泰勒展开
首先我们先看二元函数在点$x^0即(x^0_1, x^0_2)$处的泰勒展开(只展开到二级)：
$$
\begin{split}
f(x_1, x_2) = &f(x^0_1, x^0_2) \\\
&+(x_1-x^0_1)f’_{x_1}(x^0_1, x^0_2) + (x_2-x^0_2)f’_{x_2}(x^0_1, x^0_2) \\\
&+\frac{1}{2!}(x_1-x^0_1)^2f’’_{x_1x_1}(x^0_1, x^0_2) + \frac{1}{2!}(x_1-x^0_1)(x_2-x^0_2)f’’_{x_1x_2}(x^0_1, x^0_2) \\\
&+\frac{1}{2!}(x_2-x^0_2)(x_1-x^0_1)f’’_{x_2x_1}(x^0_1, x^0_2) + \frac{1}{2!}(x_2-x^0_2)^2f’’_{x_2x_2}(x^0_1, x^0_2)\\\
&+o^n
\end{split}
$$
下面对N元函数在$x^0即(x^0_1, x^0_2, \ldots, x^0_n)$处进行展开，也只展开到二级，如下：
$$
\begin{split}
f(x_1, x_2, \ldots, x_n) = &f(x^0_1, x^0_2, \ldots, x^0_n) \\\
& + \sum_{i=1}^{n} (x_i - x^0_i)f’_{x_i}(x^0_1, x^0_2, \ldots, x^0_n) \\\
& + \frac{1}{2!}\sum_{i,j=1}^{n}(x_i-x^0_i)(x_j-x^0_j)f’’_{x_ix_j}(x^0_1, x^0_2, \ldots, x^0_n) \\\
& + o^n
\end{split}
$$
好了，现在我们将其写成矩阵形式，在$\mathbf{x}^0$处展开，其中$\mathbf{x}^0=[x^0_1, x^0_2, \ldots, x^0_n]^T$，即为：
$$
\begin{split}
f(\mathbf{x})=f(\mathbf{x}^0) + [\nabla f(\mathbf{x}^0)]^T(\mathbf{x}-\mathbf{x}^0) + \frac{1}{2!}[\mathbf{x}-\mathbf{x}^0]^T\nabla^2f(\mathbf{x}^0)(\mathbf{x}-\mathbf{x}^0) + o^n
\end{split}
$$
其中：
$$
\nabla^2f(\mathbf{x}^0) =
\begin{bmatrix}
\frac{\partial^2f(\mathbf{x}^0)}{(\partial x_1)^2} & \frac{\partial^2f(\mathbf{x}^0)}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2f(\mathbf{x}^0)}{\partial x_1 \partial x_n} \\\
\frac{\partial^2f(\mathbf{x}^0)}{\partial x_2 \partial x_1} & \frac{\partial^2f(\mathbf{x}^0)}{(\partial x_2)^2} & \cdots & \frac{\partial^2f(\mathbf{x}^0)}{\partial x_2 \partial x_n} \\\
\vdots & \vdots & \ddots & \vdots \\\
\frac{\partial^2f(\mathbf{x}^0)}{\partial x_n \partial x_1} & \frac{\partial^2f(\mathbf{x}^0)}{\partial x_n \partial x_1} & \cdots & \frac{\partial^2f(\mathbf{x}^0)}{(\partial x_n)^2} \\\
\end{bmatrix}
$$
这种矩阵也称之为Hessian 矩阵,wikipedia-Hessian_matrix
如果对上面还有不太理解的，可以先用二元自己尝试转换成矩阵形式来类推N元。
2.2.2 迭代求解
我们对矩阵形式的泰勒展开忽略二次以上的项，即为：
$$
\begin{split}
f(\mathbf{x})=f(\mathbf{x}^0) + [\nabla f(\mathbf{x}^0)]^T(\mathbf{x}-\mathbf{x}^0) + \frac{1}{2!}[\mathbf{x}-\mathbf{x}^0]^T\nabla^2f(\mathbf{x}^0)(\mathbf{x}-\mathbf{x}^0)
\end{split}
$$
对其两边同时求梯度，我们可以得到：
$$
\nabla f(\mathbf{x})= \nabla f(\mathbf{x}^0) + \nabla^2f(\mathbf{x}^0)(\mathbf{x}-\mathbf{x}^0)
$$
其中 $\nabla^2f(\mathbf{x}^0)$ 为Hessian 矩阵, 我们将其写为$\mathbf{H}$, 令函数的梯度为0，则有：
$$
\begin{split}
0 &= \nabla f(\mathbf{x}^0) + \nabla^2f(\mathbf{x}^0)(\mathbf{x}-\mathbf{x}^0) \\\
\Rightarrow \mathbf{x} &= \mathbf{x}^0 - [\nabla^2f(\mathbf{x}^0)]^{-1} \nabla f(\mathbf{x}^0) \\\
&= \mathbf{x}^0 - \mathbf{H}^{-1} \nabla f(\mathbf{x}^0)
\end{split}
$$
从$\mathbf{x}^0$处开始，反复计算函数在处的Hessian矩阵和梯度向量，然后用下述公式进行迭代：
$$
\mathbf{x}^{i+1} \leftarrow \mathbf{x}^i - \mathbf{H}_i^{-1} \nabla f(\mathbf{x}^i)
$$
最终会达到最优的点，其中$- \mathbf{H}_i^{-1} \nabla f(\mathbf{x}^i)$ 称之为牛顿方向，迭代终止的条件是梯度的模接近于0，或者函数值下降小于指定阈值。
3. 优缺点
| 主题 | 内容 |
|---|---|
| 优点 | 1. 充分接近极小点时，牛顿法具有二阶收敛速度 |
| 缺点 | 1. 和梯度下降法相比，在使用牛顿迭代法进行优化的时候，需要求Hessien矩阵的逆矩阵，这个开销是很大的。 2. 牛顿法不是整体收敛的。 |
