牛顿法被称为牛顿-拉夫逊(Newton-Raphson)方法。牛顿在17世纪提出用来求解方程的根。
假设点x*位函数f(x)的根,则f(x*)=0。
将函数f(x)在点
处进行一阶泰勒展开有:
![](https://img-blog.csdnimg.cn/20190529191004300.png)
假设点
为函数f(x)的根,则有:
![](https://img-blog.csdnimg.cn/20190529191320441.png)
那么可以得到:![](https://img-blog.csdnimg.cn/20190529191343500.png)
牛顿法通过迭代的方式求解方程f(x)=0的解。
牛顿法求解目标函数极值
对于最优化问题,极值点处函数的一阶导数为0
可以对一阶导数
利用牛顿法通过迭代的方式来求得最优解,即相当于求一阶导数对应函数的根。
![](https://img-blog.csdnimg.cn/20190529191956872.png)
牛顿法是二阶最优化算法。
对多元函数
,一阶导数换成梯度:
,二阶导数换成海森(Hessian)矩阵H,
![](https://img-blog.csdnimg.cn/20190529192249267.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4NDU2,size_16,color_FFFFFF,t_70)
则牛顿法迭代公式为:![](https://img-blog.csdnimg.cn/20190529192652607.png)
牛顿法求解目标函数极值步骤:
1、从t=0开始,初始化
为随机值;
2、计算目标函数f(x)在点
的梯度
和海森矩阵
;
3、计算移动方向:
(一般用线性方程组计算
。线性方程组求解可用共轭梯度等方法求解)。
4、根据迭代公式,更新x的值:
;
5、判断是否满足迭代终止条件。如果满足,循环结束,返回最佳参数
和目标函数最小值
;否则转到第2步。
与一阶梯度法
,移动方向为:![](https://img-blog.csdnimg.cn/20190529195341978.png)
拟牛顿法
牛顿法比一般的梯度下降法收敛速度快。
但在高维情况下,计算目标函数的二阶偏导数的复杂度大,而且有时候目标函数的海森矩阵无法保持正定,不存在逆矩阵,此时牛顿法将不再能使用
因此,人们提出了拟牛顿法(Quasi-Newton Methods):不用二阶偏导数构造出可以近似Hessian矩阵(或Hessian矩阵的逆矩阵)的正定对称矩阵,进而再逐步优化目标函数。
不同的Hessian矩阵构造方法产生了不同的拟牛顿法:
BFGS/L-BFGS
拟牛顿条件
在t次迭代后,得到
。
将目标函数f(x)在
处进行二阶泰勒展开:
![](https://img-blog.csdnimg.cn/2019052920175099.png)
两边同时取梯度运算▽,得到
![](https://img-blog.csdnimg.cn/20190529201906895.png)
取
,令
,
,则
![](https://img-blog.csdnimg.cn/20190529202134291.png)
引入记号
,
,则![](https://img-blog.csdnimg.cn/20190529202234908.png)
令B表示H的近似,D表示
的近似,根据![](https://img-blog.csdnimg.cn/20190529202410118.png)
得到拟牛顿条件为:![](https://img-blog.csdnimg.cn/20190529202443586.png)
或:
。
BFGS
BFGS算法是Broyden,Fletcher,Goldfarb,Shanno四位研究者发明出来的,被认为是数值效果最好的拟牛顿法,并且具有全局收敛性和超线性收敛速度。
BFGS算法使用迭代法逼近Hessian矩阵:![](https://img-blog.csdnimg.cn/20190529203720802.png)
初始值
为单位矩阵,因此关键是如何构造
。
为了保证矩阵B的正定性,令
,代入
![](https://img-blog.csdnimg.cn/2019052920495531.png)
![](https://img-blog.csdnimg.cn/20190529205005525.png)
![](https://img-blog.csdnimg.cn/20190529205128601.png)
令
,得到:
![](https://img-blog.csdnimg.cn/20190529205213838.png)
将
代入
![](https://img-blog.csdnimg.cn/20190529205254443.png)
得到:![](https://img-blog.csdnimg.cn/20190529205306990.png)
不防令
,代入
![](https://img-blog.csdnimg.cn/20190529205429624.png)
代入:![](https://img-blog.csdnimg.cn/20190529205518302.png)
牛顿法中需要计算Hessian矩阵的逆矩阵。
根据Sherman-Morrison公式,可得到
![](https://img-blog.csdnimg.cn/20190529205658399.png)
Sherman-Morrison公式:若A为非奇异方阵,
,则
![](https://img-blog.csdnimg.cn/20190529210007542.png)
BFGS更新参数的流程:
1、从t=0开始,初始化
;
2、计算移动方向:
;
3、更新x的值:![](https://img-blog.csdnimg.cn/20190529210137191.png)
4、![](https://img-blog.csdnimg.cn/20190529210150621.png)
5、若
,迭代终止;
6、计算:
;
7、t=t+1,转第2步。
L-BFGS
L-BFGS(limited memory BFGS)不直接存储Hessian矩阵,而是通过存储计算过程中产生的
和
来计算Hessian矩阵,从而减少参数存储所需空间。
BFGS中Hessian矩阵更新公式为:
![](https://img-blog.csdnimg.cn/20190529221424517.png)
令
,
,
则:![](https://img-blog.csdnimg.cn/20190529223416356.png)
展开:
![](https://img-blog.csdnimg.cn/2019052922344419.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4NDU2,size_16,color_FFFFFF,t_70)
一般地:
![](https://img-blog.csdnimg.cn/20190529223547526.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDA4NDU2,size_16,color_FFFFFF,t_70)
计算将
需要用到
。如果只能存储m组
,从0开始,可以计算
。
要丢弃一部分
的话,丢弃较早生成的那些
。
则计算
,只存储了
,丢弃了
。
由于丢弃了部分信息,只能近似计算
。
当t>m+1时,构造近似公式:
![](https://img-blog.csdnimg.cn/20190529224135185.png)
计算
是为了得到搜索方向
。
利用上面的公式,设计快速计算
的方法
1、初始化:![](https://img-blog.csdnimg.cn/20190529224704616.png)
2、向后循环:![](https://img-blog.csdnimg.cn/20190529224732274.png)
3、向前循环:![](https://img-blog.csdnimg.cn/20190529224818487.png)
4、![](https://img-blog.csdnimg.cn/20190529224837495.png)