海森矩阵与牛顿法

2020-03-21 本文已影响0人努力学习的CC

之前在看求解优化问题的时候一直出现的两个概念，今天来记录一下

泰勒展开式

$f(x) = \sum_{n=1}^N \frac {f^n(x_0)}{n!} (x-x_0)^n$

牛顿法

牛顿法主要用用在

1. 求解方程式

目标是求解：f（x）=0

当我们要求接的方程式求解起来很困难，我们可以试试用牛顿法来迭代求解，其原理就是对求解的函数使用一阶泰勒展开，那我们在x0处：

$f(x)=f(x_0)+(x-x_0)*f$

已知f(x)=0,则

$x = x_0-\frac {f(x_0)}{f^{`}(x_0)}$ ,很明显只根据这一次迭代我们很难直接得到关于x的准确估测，因此我们需要多次迭代直到收敛 $x_k = x_{k-1}-\frac {f(x_{k-1})}{f^{`}(x_{k-1})}$

2. 求解最优化问题

目标是求解 $f^{`}(x)$ =0

针对这个问题，我们对f(x)进行二阶泰勒公式展开：

$f(x) \approx f(x_0)+f^{`}(x_0)*(x-x_0)+\frac {1}{2}*f^{``}(x_0)*(x-x_0)^2$

我们对上面的式子求导，并令其导数等于0

$f^{`}(x_0) + f^{``}(x_0)*(x-x_0)=0$

$x = x_0-\frac {f^{`}(x_0)}{f^{``}(x_0)}$ 将其推广到 $x_k = x_{k-1}-\frac {f^{`}(x_{k-1})}{f^{``}(x_{k-1})}$

那么对于高纬函数，牛顿公式可以推广为：

$x_k=x_{k-1}-H^{-1}_{k-1}g_{k-1},g_{k-1}=\nabla f(x_{k-1})$

其中 $H^{-1}_{k-1}$ 为海森矩阵， $H_{k-1}=H(x_{k-1})=\frac {\partial^2f(x_{k-1})}{\partial x_i \partial x_j}$

这里比较一下梯度下降：

$x_k = x_{k-1}-\eta {f^{`}(x_{k-1})}$

梯度下降通过调整学习率来调整学习的速度，而牛顿法利用了函数曲线本身的性质，所以更容易收敛，但是牛顿法也有缺点，引入海森矩阵，增加了复杂性，当维度很高的时候，带来很大的计算压力，另外如果海森矩阵非正定会导致函数不一定下降，从而不会收敛，如果H为负定矩阵，则函数在f(x)在x0处为凸函数，会得到函数的极大值而不是极小值，如果H不定，则其逆矩阵可能不存在，导致 $-\frac {f^{`}(x_{k-1})}{f^{``}(x_{k-1})}$ 这一现无法给出有效的信息

参考1

参考2

海森矩阵与牛顿法

泰勒展开式

牛顿法

1. 求解方程式

2. 求解最优化问题

猜你喜欢

热点阅读