（不全）深度学习基础之二阶优化算法

二阶优化问题

前面说的算法都是使用梯度 $\mathit{g}$，属于一阶方法。二阶方法则需要求海森矩阵（或部分二阶偏导）。

牛顿法

给出一个函数 $f$，用二阶泰勒展开来近似 ${\mathit{x}}^{(0)}$ 附近的 $f(\mathit{x})$：

$$\begin{gathered} f(\mathit{x})\approx f({\mathit{x}}^{(0)}) \\ +(\mathit{x}-{\mathit{x}}^{(0)}{)}^{\mathrm{\top }}{\mathrm{\nabla }}_{\mathit{x}}f({\mathit{x}}^{(0)}) \\ +\frac{1}{2}(\mathit{x}-{\mathit{x}}^{(0)}{)}^{\mathrm{\top }}(\mathit{H}(f)({\mathit{x}}^{(0)}))(\mathit{x}-{\mathit{x}}^{(0)}) \end{gathered}$$

得到临界点：

$${\mathit{x}}^{\ast }={\mathit{x}}^{(0)}-\mathit{H}(f)({\mathit{x}}^{(0)}{)}^{-1}{\mathrm{\nabla }}_{\mathit{x}}f(x^{(0)})$$

如果目标函数 $f$ 是有最小值的二次函数，牛顿法可以直接跑到最小值点，如果不是，牛顿法反复迭代多次可以很快接近附近的临界点。如果附近的临界点不是最小点牛顿法不适用。

牛顿法每次迭代计算量很大：参数数量设为 $n$，需要在内存中储存 $n\times n$ 的海森矩阵，还要算它的逆矩阵（速度是 $O(n^3)$）。所以深度学习一般不直接使用牛顿法。

共轭梯度法

待补充！

线性共轭梯度

最初，共轭梯度法用于求解 $N$ 维线性方程 $\mathit{A}\mathit{x}=\mathit{b}$。

构造目标函数 $\varphi (\mathit{x})=\frac{1}{2}{\mathit{x}}^{\mathrm{\top }}\mathit{A}\mathit{x}-{\mathit{b}}^{\mathrm{\top }}\mathit{x}$（二次型），$\mathrm{\nabla }\varphi (\mathit{x})=\mathbf{0}$ 等价于 $\mathit{A}\mathit{x}-\mathit{b}=\mathbf{0}$。

我们只考虑 $A$ 对称正定的情况，这样 $\varphi$ 有唯一最小值。

给出 $N$ 个向量 ${\mathit{p}}_1,\dots ,{\mathit{p}}_N$，如果其中任意两个向量都有 ${\mathit{p}}_i^{\mathrm{\top }}\mathit{A}{\mathit{p}}_j$（$i≠j$），则称这组向量与 $\mathit{A}$ 共轭。

可以证明，依次沿着这些向量优化，可以在 $N$ 次迭代后到达最小值。