3.4　Quasi-Newton优化算法搜索的最小二乘法

Quasi-Newton法(以下简称BFGS法)作为求解无约束最优化问题的拟牛顿方法类最有代表性的算法之一，BFGS方法处理凸非线性规划问题，以其完善的数学理论基础、采用不精确线性搜索时的超线性收敛性和处理实际问题的有效性受到重视。该方法使用了二阶导数信息，但是并不直接计算函数的Hesse矩阵，而是采用一阶梯度信息来构造一系列的正定矩阵来逼近Hesse矩阵;其搜索模式是:当梯度值可以直接得到时，用三次插值的方法进行一维搜索，当梯度值不能直接得到时，采用二次、三次混合插值法。

引入BFGS法来求解非线性的最小二乘法问题，首先选取搜索方向，使目标函数最速下降。最小二乘法的目标函数为残差平方和Q，假定A的一组初始近似值为A(0)，记A=A(0)+Δ。则将([Yk-f(Xk，A)])2=F(A)在A(0)附近进行二阶泰勒展开:

若矩阵为正定，则Nk(A)有唯一极小点，取其进行A的下一次近似A(1)，故A(1)应满足▽Nk(A(1))=0，可得

其中，

将式(3.8)改写为

式中:Hk为对称矩阵，αk为搜索步长。

然后作如下变换:

Hk具有正定继承性，此时式(3.9)即为BFGS法搜索，它是一个拟Newton算法，具有二次终止性、整体收敛性和超线性收敛性，且所产生的搜索方向是共轭的，因此算法的收敛速度比一般的线性收敛梯度下降法快。另外，在实际计算过程中，BFGS算法效率所受影响小，精度就相对较高。