Welcome To My Blog
牛顿法和拟牛顿法是求解无约束最优化问题的常用方法,优点是收敛速度快.
牛顿法是迭代算法,每一步需要求解目标函数的Hessian矩阵的逆矩阵,矩阵的逆运算很耗时.
拟牛顿法通过正定矩阵近似Hessian矩阵的逆矩阵或Hessian矩阵,简化Hessian矩阵的求逆计算过程
采用线搜索框架
搜索方向由牛顿法或拟牛顿法给出,步长可以通过精确线搜索或非精确线搜索获得
关于步长,之前的文章有提过:Line search and Step length线搜索与步长
牛顿法
- 假设f(x)具有二阶连续偏导数.要求解的无约束最优化问题是min f(x),x*标识目标函数f(x)的极小点.
- 若第k次迭代值为x^(k),则可将f(x)在x^(k)附近进行二阶泰勒展开(Taylor expansion):
- 函数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类
参考:
李航,统计学习方法