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

采用线搜索框架

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

牛顿法

1. 假设f(x)具有二阶连续偏导数.要求解的无约束最优化问题是min f(x),x*标识目标函数f(x)的极小点.
2. 若第k次迭代值为x^(k),则可将f(x)在x^(k)附近进行二阶泰勒展开(Taylor expansion):
   
3. 
   
   • 函数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))求梯度得:
     
   • 将x^(k+1)带入上面的梯度公式:
     

算法流程

拟牛顿法

牛顿法算法流程的步骤(4)涉及Hessian矩阵的求逆,计算复杂,所以有其它改进的方法,比如

先看牛顿法迭代中Hessian矩阵H_k满足的条件,进而引出拟牛顿条件.

下面说明如果H_k正定,则牛顿法的搜索方向是下降方向

拟牛顿法是用一个n阶矩阵G_k去近似Hessian矩阵的逆,所以矩阵G_k需要满足Hessian矩阵满足的条件

每次迭代时需要更新G_k矩阵,更新方法有多种类选择,主要介绍下Broyden类拟牛顿法

DFP算法

DFP(Davidon-Flectcher-Powell)算法选择G_(k+1)的方法是:

进一步,关于P_k,Q_k

P_k,Q_k如上取值的可行性证明:

DFP算法流程

BFGS算法

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

BFGS算法流程

DFP和BFGS的迭代公式很像

Broyden类算法

Sherman-Morrison公式

Broyden类

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