牛顿法原理推导

牛顿法是用迭代的方法，来求解方程的根和最优化

预备知识
1.Hessian矩阵
2.多元泰勒展开

用牛顿法求解方程的根
用牛顿法求解导数为0 的点

---

1.Hessian矩阵

相当于一元函数的二阶导数，所有元素由函数的二阶偏导数构成。

由于高阶导数一般和求导次序无关，所以Hessian矩阵往往是对称矩阵

$$f(x_1,x_2,...x_n)$$
H ( f ) = ( ∂ 2 f ∂ x 1 ∂ x 1 ∂ 2 f ∂ x 1 ∂ x 2 ∂ 2 f ∂ x 1 ∂ x 3 ∂ 2 f ∂ x 2 ∂ x 1 ∂ 2 f ∂ x 2 ∂ x 2 ∂ 2 f ∂ x 2 ∂ x 3 ∂ 2 f ∂ x 3 ∂ x 1 ∂ 2 f ∂ x 3 ∂ x 2 ∂ 2 f ∂ x 3 ∂ x 3 ) H(f)=

$$\begin{pmatrix} \frac{\partial^2 f}{\partial x_1\partial x_1} & \frac{ \partial^2 f}{\partial x_1\partial x_2} & \frac{ \partial^2 f}{\partial x_1\partial x_3 }\\ \frac{\partial^2 f}{\partial x_2\partial x_1} & \frac{ \partial^2 f}{\partial x_2\partial x_2} & \frac{ \partial^2 f}{\partial x_2\partial x_3 }\\ \frac{\partial^2 f}{\partial x_3\partial x_1} & \frac{ \partial^2 f}{\partial x_3\partial x_2} & \frac{ \partial^2 f}{\partial x_3\partial x_3 }\\ \end{pmatrix}$$ H(f)=⎝⎜⎛​∂x1​∂x1​∂2f​∂x2​∂x1​∂2f​∂x3​∂x1​∂2f​​∂x1​∂x2​∂2f​∂x2​∂x2​∂2f​∂x3​∂x2​∂2f​​∂x1​∂x3​∂2f​∂x2​∂x3​∂2f​∂x3​∂x3​∂2f​​⎠⎟⎞​

举个例子:
$f(x,y,z)=2x^2-xy+y^2-3z^2$
故Hessian矩阵为
( 4 − 1 0 − 1 2 0 0 0 − 6 )

$$\begin{pmatrix} 4&-1&0\\-1&2&0\\0&0&-6 \end{pmatrix}$$ ⎝⎛​4−10​−120​00−6​⎠⎞​

Hessian矩阵的作用：
与多元函数的凹凸性由密切的关系。
如果Hessian矩阵正定，则f(x,y,z)是凸函数
如果Hessian矩阵负定，则f(x,y,z)是凹函数

极值判别法：
一元函数的极值判别法：

• f’(x)=0 f’’(x)>0 极小值
• f’(x)=0 f’’(x)<0 极大值
• f’(x)=0 f’’(x)=0 无法判断

多元函数的极值判别法

• $\nabla f=0$,Hessian矩阵正定，极小值点
• $\nabla f=0$,Hessian矩阵负定，极大值点
• $\nabla f=0$,Hessian矩阵不定，还需要看更高阶的导数

---

2.多元函数的泰勒展开

一元函数的泰勒展开
$$f(x^{k+1})=f(x^k)+f^{\prime }(x^k)(x^{k+1}-x^k)+\frac{1}{2}{f}^{\prime \prime }(x^k)(x^{(k+1)}-x^k{)}^2+...+\frac{1}{n!}{f}^{(n)}(x^k)(x^{k+1}-x^k{)}^n+\frac{1}{n+1!}{f}^{(n+1)}(ϵ)(x^{k+1}-x^k{)}^{n+1}$$
其中$ϵ$是介于$x^k$与$x^{k+1}$的数

推广到多元函数的泰勒展开
$$f(x)=f(x_0)+(\nabla f(x_0){)}^T(x-x_0)+\frac{1}{2}(x-x_0{)}^{T}H(x_0)(x-x_0)+O(||x-x_0|{|}^2)$$

---

用牛顿法求解方程的根

一元函数的情形：
$f(x^{k+1})$在$x=x^k$一阶展开
$$f(x^{k+1})=f(x^k)+f^{\prime }(x^k)(x^{k+1}-x^k)+O$$
因为我们要找到的是$f(x^{k+1})=0$的位置
故$$f(x^k)+f^{\prime }(x^k)(x^{k+1}-x^k)=0$$
化简的
$$x^{k+1}=x^k-\frac{f(x^k)}{f^{\prime }(x^k)}$$

---

用牛顿法求解导数为0 的点

一元函数的情形：
$f(x^{k+1})$在$x=x^k$二阶展开
$$f(x^{k+1})=f(x^k)+f^{\prime }(x^k)(x^{k+1}-x^k)+\frac{1}{2}{f}^{\prime \prime }(x^k)(x^{(k+1)}-x^k{)}^2+O$$
因为我们要找的$f(x^{k+1})$的导数为0
故函数左右两端同时对$x^{k+1}$求导=0
得
$$\begin{gathered} x^{k+1}=x^k-\frac{f^{\prime }(x^k)}{f^{\prime \prime }(x^k)} \\ =x^k-f^{\prime \prime }(x^k{)}^{-1}{f}^{\prime }(x^k) \end{gathered}$$
由此可以推测，若求n阶导为0的点
则迭代公式为:
$$x^{k+1}=x^k-\frac{f^n(x^k)}{f^{n+1}(x^k)}$$

推广到多元
$f(x^{k+1})$在$x=x^k$二阶展开
$$f(x^{k+1})=f(x^k)+\nabla f(x^k{)}^T(x^{k+1}-x^k)+\frac{1}{2}(x^{k+1}-x^k{)}^{T}H(x^k)(x^{k+1}-x^k)+O(||x-x_0|{|}^2)$$
因为我们要找的$\nabla f(x^{k+1})$为0的坐标
故函数左右两端同时对$x^{k+1}$求梯度，并令其为0
得
$$x^{k+1}=x^k-H(x_k{)}^{-1}\nabla f(x_k)$$
为了保证确实可以忽略高阶无穷小
则
$$x^{k+1}=x^k-H(x_k{)}^{-1}\nabla f(x_k)\ast \gamma$$
其中
$$-H(x_k{)}^{-1}\nabla f(x_k)\ast \gamma$$
为搜索方向

牛顿法无法保证每次迭代后，函数值会更小，所以$\gamma$的选取非常有技巧，往往采用线性搜索(line search)
即gamma的取值在0.01，0.001，0.0001,0.00001这几个选项中，选择令函数值下降最快的步长。

牛顿法的终止条件：
设置迭代停止条件：

1） 最大迭代次数T，迭代次数大于T时停止迭代

2） 停止搜索条件$||\nabla f||<ϵ$，满足条件时停止

牛顿法与梯度下降法的联系：
牛顿法与梯度下降法是非常相似的，只是牛顿法多乘Hessian矩阵的逆矩阵。
梯度下降法是用线性函数来近似代替目标函数，而牛顿法是用二次函数来代替目标函数，故牛顿法的收敛速度是更快的。
尤其是当函数的三阶导为0时，只需要迭代一次，即可得到最终的结果。

牛顿法的局限：

1. Hessian矩阵不一定可逆
2. 当Hessian矩阵规模很大时，变量很多时，解Hessian矩阵的逆矩阵非常耗时，由此出现改进算法（拟牛顿法）