海森矩阵和牛顿法

这个概念和方法的引入是为了求解凸优化问题
海森矩阵:函数的二阶导数是海森矩阵,海森矩阵经常用于牛顿法优化方法中,牛顿法是一种迭代求解方法,有一阶和二阶方法,主要应用在两个方面:1、求方程的根,2、最优化方法。

  • 求解方程的根
    当方程没有求根公式,或者求根公式很复杂而导致求解困难时,利用牛顿法可以迭代求解。牛顿法的原理是利用泰勒公式,在x_0处展开且展
    开到一阶,x = x_0 + \delta
    f(x) = f(x_0) + (x - x_0)f^{'}(x_0)
    整理上式可得到
    x = x_0 - f(x_0)/f^{'}(x_0)
    由于以上用到的只是泰勒一阶展开,所以泰勒等式只是近似相等,所以求得的x并不能使f(x) = 0完全成立。此处记这个近似解为x_1,可以认为f(x_1)f(x_0)更加接近f(x) = 0,据此我们可得递推公式:
    x_{k + 1} = x_k - f(x_k) / f^{'}(x_k)
    通过迭代这个式子必然可以在f(x^*) = 0处收敛
  • 二阶优化方法——牛顿法
    牛顿法求解二阶优化问题实际上是求解f^{'}(x) = 0的问题,可以参考二阶泰勒展开公式:
    f(x) = f(x_0) + f^{'}(x_0)(x - x_0) + (1 / 2)f^{''}(x_0)(x - x_0)^2
    此时把f^{'}(x)想象成f(x)然后套用上面的递推公式就可以得到:
    x_{n + 1} = x_n - f^{'}(x_n)/f^{''}(x_n)
    以上公式可以通过二阶泰勒公式推导得到
    对于高维函数,牛顿法通用公式可以写成:
    x_{n + 1} = x_{n} - \left [ Hf\left ( x_{n} \right ) \right ]^{-1}\triangledown f\left ( x_{n} \right ),n\geq 0
    可以比较一下牛顿法递推和梯度下降法递推:
    梯度下降的递推公式为:
    x_{n + 1} = x_{n} -\eta f(x_n)
    可见,相比于梯度下降单纯用学习率来调整学习速度,牛顿法可以利用到曲线本身的信息,所以更容易收敛
    牛顿法仍然适用于多变量问题求解,但由于hessian矩阵的引入增加了其复杂性,特别是当:
    • hessian矩阵非正定,导致了目标函数不一定下降,从而牛顿法不收敛
    • hessian矩阵的维度大带来巨大的计算量。
      针对这个问题,提出了很多改进方法,如拟牛顿法。还有更加深入的DFP、BFGS、L-BFGS等。
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容