基木原理：定步长搜索迭代的牛顿法

1.原始牛顿法

原始牛顿法的基本原理是：原目标函数f（X）用在迭代点X（k）邻域展开的泰勒二次多项式φ（X）去近似代替，再以φ（X）这个二次函数的极小点X_φ^*作为原目标函数的下一个迭代点X^（k+1），这样重复迭代若干次后，使迭代点点列逐步退近原目标函数f（X）的极小点X^*。

二次逼近函数φ（X）可写成

式中，▽f（X^（k））、H（X^（k））分别为原目标函数f（X）在X^（k）点的梯度和黑塞矩阵。

φ（X）的极小点X_φ^*可由极值存在的必要条件，今其梯度▽φ（X）=0来求得，亦即

▽φ（X^（k））=▽f（X^（k））+H（X^（k））（X-X^（k））=0

这样，H（X^（k））（X-X^（k））=-▽f（X^（k））

若H（X^（k））为可逆矩阵，将上式等号两边左乘以［H（X（k））]^-1，则得

X_φ^*=X^（k）-［H（X^（k））]^-1▽f（X^（k）） （4-6）

将X_φ^*取作下一个优化迭代点X^（k+1），即可得到原始牛顿法的迭代公式为

X^（k+1）=X^（k）-［H（X^（k））]^-1▽f（X^（k）） （4-7）(www.xing528.com)

由式（4-7）可知原始牛顿法的搜索方向为

S^（k）=-［H（X^（k））]^-1▽f（X^（k）） （4-8）

这个方向称为牛顿方向。由式（4-7）还可看到迭代公式中没有步长因子α^（k），所以原始牛顿法是一种定步长的搜索迭代。

2.阻尼牛顿法

为消除原始牛顿法的上述弊病，对其加以改迸，提出了“阻尼牛顿法”。阻尼牛顿法每次迭代方向仍采用式（4-8）表达的牛顿方向S（k），但每次迭代需沿此方向作一维搜索，求其最优步长因子α（k），即

f（X^（k）+α^（k）S^（k））=minf（X^（k）+α^（k）S^（k））

将原始牛顿法的迭代公式修改为

X^（k+1）=X^（k）-α^（k）［H（X^（k））]-1▽f（X^（k））（4-9）

此即牛顿法的迭代公式。式中，α^（k）称为阻尼因子，是通过沿牛顿方向一维搜索寻优而得。当目标函数f^（X）的黑塞矩阵H（X^（k））处处正定时，阻尼牛顿法能保证每次迭代点的函数值均有所下降，从而保持了二次收敛的特性。