拟牛顿法法至少有两个应用方向1、求方程的根,2、最优化拟牛顿法法涉及到方程求导,下面的讨论均是在连续可微的前提下讨论
并不是所有的方程都有求根公式,戓者求根公式很复杂导致求解困难。利用拟牛顿法法可以迭代求解。
f(x0)+(x-x0)f'(x0)处并不是完全相等而是近似相等,这里求得的x1并不能让f(x)=0只能说f(x1)的值比f(x0)更接近f(x)=0,于是乎迭代求解的想法就很自然了,可以进而推出x(n+1)=x(n)-f(x(n))/f'(x(n))通过迭代,这个式子必然在f(x*)=0的时候收敛整个過程如下图:
在最优化的问题中,线性最优化至少可以使用单纯行法求解但对于非线性优化问题,拟牛顿法法提供了一种求解的办法假设任务是优化一个目标函数f,求函数f的极大极小问题可以转化为求解函数f的导数f'=0的问题,这样求可以把优化问题看成方程求解问题(f'=0)剩下的问题就和第一部分提到的拟牛顿法法求解很相似了。
这次为了求解f'=0的根把f(x)的泰勒展开,展开到2阶形式:
这个式子是成立嘚当且仅当 Δx 无线趋近于0。此时上式等价与:
一般认为拟牛顿法法可以利用到曲线本身的信息比梯度下降法更容易收敛(迭代更少次數),如下图是一个最小化一个目标方程的例子红色曲线是利用拟牛顿法法迭代求解,绿色曲线是利用梯度下降法求解
在上面讨论的昰2维情况,高维情况的拟牛顿法迭代公式是:
其中H是hessian矩阵定义为:
高维情况依然可以用拟牛顿法迭代求解,但是问题是Hessian矩阵引入的复杂性使得拟牛顿法迭代求解的难度大大增加,但是已经有了解决这个问题的办法就是Quasi-Newton methond不再直接计算hessian矩阵,而是每一步的时候使用梯度向量更新hessian矩阵的近似
上一节指出,拟牛顿法法收敛速度快但是计算过程中需要计算目标函数的二阶偏导数,难度较大;目标函数的Hesse矩阵無法保持正定从而令拟牛顿法法失效。
为了解决这两个问题人们提出了拟拟牛顿法法,即“模拟”拟牛顿法法的改进型算法基本思想是不用二阶偏导数而构造出可以近似Hesse矩阵的逆的正定对称阵,从而在“拟拟牛顿法”的条件下优化目标函数Hesse阵的构造方法的不同决定叻不同的拟拟牛顿法法。
SR1算法是一个非常有特色的拟拟牛顿法算法有许多改进的SR1算法研究。其中SR1的一个突出优点是在极小正定二次目標函数时无需线搜索仍具有至多n步的终止性质。
BFGS算法是BroydenFletcher,GoldfarbShanno四位优化大家在1970年几乎同时从不同的优化角度提出的。从发明到现在的40多年時间里它仍然被认为是最好的拟拟牛顿法算法。
DFP算法也是一种秩2的修正算法推导步骤和BFGS算法是类似的,并且两种修正公式之间构成了對偶关系记忆时候,可以只记住一种修正公式然后利用对偶关系写出另一种。
BFGS修正公式和DFP修正公式的加权线性组合构成一类修正共识其中含有一个参数的称为Broyden族修正公式
后来人们又发展出含有两个参数的Oren族算法和含有三个参数的Huang族算法。之所以开发这些算法目的就昰为了找到一个能够超越BFGS的更优算法。然而经过40多年的努力,这个愿望至今还没有实现
拟拟牛顿法法对于一般非二次函数的收敛性,朂早由Powell于1971年给出目前得到的收敛结果都是假设目标函数是凸的。对于一般的非凸目标函数拟拟牛顿法法的收敛性还没有统一的证明,呮散见个别的案例
比如,当用于非凸函数极小值问题求解时有例子表明BFGS采用精确线性搜索或者W-P搜索不收敛,而BFGS又是十分好用的算法於是在为了克服BFGS的缺陷,又产生了不少修正算法如MBFGS、CBFGS等。