Newton's method and Quasi Newton method牛顿法与拟牛顿法

牛顿法和拟牛顿法是求解无约束最优化问题的常用方法,优点是收敛速度快.
牛顿法是迭代算法,每一步需要求解目标函数的Hessian矩阵的逆矩阵,矩阵的逆运算很耗时.
拟牛顿法通过正定矩阵近似Hessian矩阵的逆矩阵或Hessian矩阵,简化Hessian矩阵的求逆计算过程

采用线搜索框架

1.png
搜索方向由牛顿法或拟牛顿法给出,步长可以通过精确线搜索或非精确线搜索获得
关于步长,之前的文章有提过:Line search and Step length线搜索与步长

牛顿法

  1. 假设f(x)具有二阶连续偏导数.要求解的无约束最优化问题是min f(x),x*标识目标函数f(x)的极小点.
  2. 若第k次迭代值为x^(k),则可将f(x)在x^(k)附近进行二阶泰勒展开(Taylor expansion):
    2.png
    • 函数f(x)有极值的必要条件是在极值点处一阶导数为0,即梯度向量为0.特别地,当H(x^(k))是正定矩阵时,函数f(x)的极值为极小值.
    • 牛顿法利用极小点的必要条件▽f(x)=0
    • 每次迭代中从点x^(k)开始,求目标函数的极小点,作为第k+1次迭代值x^(k+1).具体地,假设x^(k+1)满足▽f(x^(k+1))=0
    • 由二阶泰勒展开,对f(x)关于(x-x^(k))求梯度得:
      3.png
    • 将x^(k+1)带入上面的梯度公式:
      4.png

      算法流程

      5.png

拟牛顿法

牛顿法算法流程的步骤(4)涉及Hessian矩阵的求逆,计算复杂,所以有其它改进的方法,比如
6.png
先看牛顿法迭代中Hessian矩阵H_k满足的条件,进而引出拟牛顿条件.
7.png
下面说明如果H_k正定,则牛顿法的搜索方向是下降方向
8.png
拟牛顿法是用一个n阶矩阵G_k去近似Hessian矩阵的逆,所以矩阵G_k需要满足Hessian矩阵满足的条件
9.png
每次迭代时需要更新G_k矩阵,更新方法有多种类选择,主要介绍下Broyden类拟牛顿法

DFP算法

DFP(Davidon-Flectcher-Powell)算法选择G_(k+1)的方法是:
10.png
进一步,关于P_k,Q_k
11.png
P_k,Q_k如上取值的可行性证明:
12.jpg

14.png

DFP算法流程

13.png

BFGS算法

BFGS(Broyden-Flectcher-Goldfarb-Shanno)算法是最流行的拟牛顿算法.
15.png

16.png

17.png

BFGS算法流程

18.png

DFP和BFGS的迭代公式很像

19.png

Broyden类算法

Sherman-Morrison公式

20.png

Broyden类

21.png

22.png

参考:
李航,统计学习方法