在前⾯的两讲内容⾥，我们所介绍的梯度下降法和最速下降法都只⽤到了⽬标函数的⼀阶导数（也就是梯度）来确定每⼀次 迭代的搜索⽅向，因此也可以被称作为是⼀阶⽅法。
而另⼀种算法的优化思路是这样的：在迭代⽅法中引⼊⾼阶导数，其迭代效率可能会优于最速下降法，而⽜顿法就是其中的 典型代表，它的核⼼是同时使⽤⼀阶导（梯度）和⼆阶导（⿊塞矩阵）来确定搜索⽅向，效率上要优于⼀阶的⽅法。
向量微分基础
函数的分类
我们看看三种函数，标量函数、向量函数和矩阵函数：
对于标量函数$f$，它的⾃变量可以是标量$x$ ，向量$x$，和矩阵$X$，然而函数的结果只能是标量，也就是说⽆论是标量、向量还是矩阵，经过标量函数的映射，得到的最终都是标量。
类似地，对于向量函数$f$和矩阵函数$F$，它的⾃变量同样可以是标量$x$ ，向量 x 或者矩阵 X，但是通过向量函数 f 的映射，最终得到的结果都是向量，而通过矩阵函数 F 的映射，最终得到的结果都是矩阵。
而我们这⼏讲⾥所重点讨论的⼀元函数$f(x)$和多元函数$f(x_1, x_2, …, x_n)$属于什么类型？由于它们最终得到的结果值都是⼀个标量，因此我们所讨论的范畴依然还只是标量函数，而⼀元函数$f(x)$中 的⾃变量也是标量，而多元函数$f(x_1, x_2, …, x_n)$的⾃变量是向量。
进⼀步的，梯度表达式$\nabla f$最终得到的是⼀个梯度向量，因此它是⼀个向量函数，而求取⿊塞矩阵的函数$F(p)$则是⼀个矩阵函数。
包含矩阵与向量的函数求导
第⼀个常⻅的例⼦是$f(x) = x^T A x$，其中$x$是列向量变量，而 A 是⼀个常数矩阵，函数的最终结果是⼀个标量，因此这是⼀个⾃变量为向量的标量函数。对这个多元函数$f(x)$进⾏⼀阶求导， 得到的应该是⼀个梯度向量，它的表达式是：
\[\nabla f = \frac{df}{fx} = (A + A^T)x\]第二个常⻅的例⼦是$f(x) = a^T x$或者$f(x) = x^T a$，其中$x$是列向量变量，$a$是常数列向量，函数的最终结果也是⼀个标量，因此这同样是⼀个⾃变量为向量的标量函数。它的⼀阶导也是梯度向量，表达式为：
\[\nabla = \frac{df}{dx} = a\]⽜顿法的原理
当⽬标函数，也就是多元函数$f(p)$⼆阶连续可微时，可以考虑使⽤⽜顿法。我们以⼆元函数$f(x,y)$为例，当⽬前的迭代取值 点为时$p_k$，迭代到下⼀步的过程如下。
首先我们按照前面学习过的内容，将函数$f$在点$p_k = \begin{bmatrix}x_k & y_k\end{bmatrix}^T$处进行二阶泰勒近似， 略去高阶无穷小量后的展开式如下：
\[f(x, y) \approx f(x_k, y_k) + \begin{bmatrix}x - x_k & y - y_k\end{bmatrix} \begin{bmatrix}\frac{\partial f}{\partial x}(x_k, y_k) \\ \frac{\partial f}{\partial y}(x_k, y_k)\end{bmatrix} + \frac{1}{2} \begin{bmatrix}x - x_k, y - y_k \end{bmatrix}\begin{bmatrix}\frac{\partial^2 f}{\partial x^2}(x_k, y_k) & \frac{\partial^2 f}{\partial x \partial y}(x_k, y_k) \\ \frac{\partial^2 f}{\partial y \partial x}(x_k, y_k) & \frac{\partial^2 f}{\partial y^2}(x_k, y_k)\end{bmatrix}\begin{bmatrix}x - x_k \\ y - y_k\end{bmatrix}\]为了简化⼆阶泰勒展开式，我们按照下⾯的形式将迭代点、梯度和⿊塞矩阵分别替换成相对应的符号。
迭代点： $p$和$p_k$
梯度：
\[\nabla f(p_k) = \begin{bmatrix}\frac{\partial f}{\partial x}(x_k, y_k) \\ \frac{\partial f}{\partial y}(x_k, y_k)\end{bmatrix}\]黑塞矩阵：
\[F(p_k) = \begin{bmatrix}\frac{\partial^2 f}{\partial x^2}(x_k, y_k) & \frac{\partial^2 f}{\partial x \partial y}(x_k, y_k) \\ \frac{\partial^2 f}{\partial y \partial x}(x_k, y_k) & \frac{\partial^2 f}{\partial y^2}(x_k, y_k)\end{bmatrix}\]由此，⼆阶展开式最终表⽰成：
\[f(p) \approx f(p_k) + (p - p_k)^T \nabla f(p_k) + \frac{1}{2}(p - p_k)^TF(p_k)(p - p_k)\]⽜顿法的思想其实很直接，它不像梯度下降法那样⼀步⼀步的下⼭，而是在最速下降法的思维基础上更激进了⼀步，最速下 降法是每次在搜索⽅向上⼀步跨到极小值点，而⽜顿法则利⽤⼆阶泰勒展开式作为⽬标函数的近似，想的是直接⼀步跨到当 前这个⼆阶泰勒展开式的极小值点，以近似作为整个⽬标函数的极小值点。
如果⽬标函数本⾝就只能展开为⼆阶泰勒展开式，那么实际上⼀步就完成了极小值的寻找。否则的话，这⼀轮找到的 极小值点就作为下⼀轮迭代的起始点，经过多轮的迭代，最终达到阈值后停⽌迭代。
⽜顿法的公式推导
在点$p_k$处对函数进行二阶泰勒展开后， 我们通过寻找使得二阶泰勒展开式
\[Q(p) = f(p_k) + (p - p_k)^T \nabla f(p_k) + \frac{1}{2}(p - p_k)^T F(p_k)(p - p_k)\]取得极小值的$p$值，来作为下⼀轮的迭代点$p_{k+1}$。那么按照极小值点存在所需要满⾜的必要条件，我们有：$\frac{d Q(p)}{dp} = 0$。
此时，我们发现表达式$Q(p)$ 当中，有向量、有矩阵，导数该怎么求？这就要⽤到我们前⾯刚刚铺垫过的知识点。
$(p - p_k)^T \nabla f(p_k)$中， $\nabla f(p_k)$是一个常数向量， 这就形如$f(x) = x^T a$的形式， 因此：
\[\frac{d}{dp}(p - p_k)^T \nabla f(p_k) = \nabla f(p_k)\]$\frac{1}{2}(p - p_k)^TF(p_k)(p - p_k)$中， 黑塞矩阵$F(p_k)$是常数矩阵， 这就形如$x^T A x$的形式， 因此
\[\frac{d}{dp}(\frac{1}{2}(p - p_k)^T F(p_k)(p - p_k)) = \frac{1}{2}(F(p_k) + F(p_k)^T)(p - p_k)\]由于黑塞矩阵是一个对称矩阵， 因此最终有：
\[\frac{d}{dp}(\frac{1}{2}(p - p_k)^T F(p_k)(p - p_k)) = F(p_k)(p - p_k)\]合并起来就有：
\[\frac{dQ(p)}{dp} = \nabla f(p_k) + F(p_k)(p - p_k) = 0\]解方程得到$p_{k+1}$的迭代公式：
\[p_{k+1} = p_k - F(p_k)^{-1} \nabla f(p_k)\]关于最优算法的延伸讨论
⽜顿法似乎⾮常强⼤，但是实际上它有诸多限制，从迭代公式$p_{k+1} = p_k - F(p_k)^{-1}\nabla f(p_k)$可知，它必须计算⿊塞矩阵的逆矩阵，⼀⽅⾯计算量巨⼤，另⼀⽅⾯可能矩阵是奇异矩阵，因此就有算法去设计⼀个⿊塞矩 阵逆矩阵的近似矩阵来代替它，这就是拟⽜顿法的基本思想。
而另⼀种改进的算法叫共轭梯度法，它也不需要计算⿊塞矩阵，同样是最优化⼯程实践中的⼀种选择。
-
Previous
【机器学习】045--多元函数的极值（中）：最速下降法 -
Next
【深度学习】Learning to Compose Dynamic Tree Structures for Visual Contexts
