牛顿法和拟牛顿法

牛顿法与拟牛顿法是求解无约束最优化问题的常用方法,有收敛速度快的优点。

牛顿法是迭代算法,每一步需要求解目标函数的海森矩阵的逆矩阵,计算比较复杂。

拟牛顿法通过正定矩阵近似海塞矩阵的逆矩阵或海塞矩阵,简化了这一计算过程。

15.1 牛顿法

无约束最优化问题:

其中为目标函数的极小点。

假设f(x)具有二阶连续偏导数,若第k次迭代值为,则可将附近进行二阶泰勒展开:

这里,是f(x)的梯度向量在点的值,的海森矩阵:

在点的值。函数f(x)有极值的必要条件是在极值点处一阶导数为0,即梯度向量为0。特别是当是正定矩阵时,函数的极值为极小值。

牛顿法利用极小点的必要条件:

每次迭代中,从点开始,求目标函数的极小点,作为第k+1次迭代值。具体地,假设满足:

由式(15.2)有:

其中。这样,式(15.5)成为

因此,

或者

其中,

用式(15.8)作为迭代公式的算法就是牛顿法。

算法15.1(牛顿法)

输入:目标函数f(x),梯度。海森矩阵H(x),精度要求

输出:f(x)的极小点

(1)取初始点,置k=0

(2)计算

(3)若,则停止计算,得近似解

(4)计算,并求

(5)置

(6)置k=k+1,转(2)

步骤(4)求,要求,计算比较复杂,所以有其他的改进方法。

15.2 拟牛顿法的思路

在牛顿法的迭代中,需要计算海塞矩阵的逆矩阵,这一计算比较复杂,考虑用一个n阶矩阵来近似代替。这就是拟牛顿法的基本想法。

在牛顿法迭代中,海森矩阵需要满足以下条件:

在(15.6)中取,即得

,则

式(15.12)或式(15.13)称为拟牛顿条件

如果是正定的(也是正定的),那么可以保证牛顿法搜索方向是下降方向。这是因为搜索方向是,由式(15.8)有:

所以的泰勒展开式(15.2)可以近似写成:

正定,故有。当为一个充分小的正数时,总有,也就是说是下降方向。

作为的近似或选择作为的近似的算法称为拟牛顿法

首先,每次迭代矩阵是正定的。同时,满足下面的拟牛顿条件:

按照拟牛顿条件选择作为的近似或选择作为的近似的算法称为拟牛顿法。

按照拟牛顿条件,在每次迭代中可以选择更新矩阵:

关于如何更新矩阵,有多种实现方法:

15.2.1 DEP(Davidon-Flecher-Powell)算法

DFP算法选择的方法是,假设每一步迭代中矩阵是由加上两个附加项构成的,即

其中是待定矩阵。这时,

为使满足拟牛顿条件,可使满足:

事实上,不难找出这样的,比如:

这样既可得到矩阵的迭代公式:

称为DFP算法。

可以证明,如果初始矩阵是正定的,则迭代过程中的每个矩阵都是正定的

算法15.2(DFP算法)

输入:目标函数,梯度,精度要求

输出:的极小点

(1)选定初始点,取为正定对称矩阵,置

(2)计算。若,则停止计算,得近似解;否则转(3)

(3)置

(4)一维搜索:求使得

(5)置

(6)计算,若,则停止计算,得近似解;否则,按式(15.24)算出

(7)置k=k+1,转(3)

15.2.2 BFGS(Broyden-Fletcher-Goldfarb-Shanno)算法

逼近海塞矩阵H。这时,相应的拟牛顿条件是:

可以用同样的方法得到另一迭代公式。

首先令:

考虑使满足:

找出适合条件的,得到BFGS算法矩阵的迭代公式:

可以证明,如果初始矩阵是正定的,则迭代过程中的每个矩阵都是正定的

下面写出BFGS拟牛顿法

算法15.3(BFGS算法)

输入:目标函数,精度要求

输出:的极小点.

(1)选定初始点,取为正定对称矩阵,置k=0

(2)计算。若,则停止计算,得近似解;否则转(3)

(3)由求得

(4)一维搜索:求使得

(5)置

(6)计算,若,则停止计算,得近似解;否则,按式(15.30)算出

(7)置k=k+1,转(3)

15.2.3 Broyden类算法

从BFGS算法矩阵的迭代公式(15.30)得到BFGS算法关于的迭代公式。

Sherman-Morrison公式:假设A是n阶可逆矩阵,u,v是n维向量,且也是可逆矩阵,则:

事实上,若记,那么对式(15.30)应用Sherman-Morrison公式即得:

称为BFGS算法关于的迭代公式。

由DFP算法的迭代公式(15.23)得到的记作,由BFGS算法的迭代公式(15.31)得到的记作,他们都满足都满足方程拟牛顿条件公式,所以他们的线性组合:

也满足拟牛顿条件式,而且是正定的

其中。这样就得到了一类拟牛顿法,称为Broyden类算法