美文网首页
海森矩阵和牛顿法

海森矩阵和牛顿法

作者: 雨住多一横 | 来源:发表于2019-05-18 11:12 被阅读0次

    这个概念和方法的引入是为了求解凸优化问题
    海森矩阵:函数的二阶导数是海森矩阵,海森矩阵经常用于牛顿法优化方法中,牛顿法是一种迭代求解方法,有一阶和二阶方法,主要应用在两个方面: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等。

    相关文章

      网友评论

          本文标题:海森矩阵和牛顿法

          本文链接:https://www.haomeiwen.com/subject/ijuzaqtx.html