文档介绍：第三章牛顿法
§ 最速下降法
一、最速下降法
在极小化算法中,若每次都以迭代点处的负梯度方向为搜索方向,产生的算法称为最速下降法,它是无约束最优化算法中最简单、最基本的算法。
算法描述:
给出初始点,允许误差,;
计算,若,Stop 令;
由一维搜索确定步长因子,使得

令,,go to 2).
二、最速下降算法的收敛性
设,则最速下降算法产生的点列的每个聚点均为驻点。
证明:设是的一个聚点,则存在子序列,使得

令,由,知是收敛序列,故有界,且

故有。
设二次连续可微,且,则对任何给定的初始点,最速下降算法或有限终止,或,或。
证明:不妨设,。

于是
令,由为单调下降序列,则要么
,要么。
最速下降算法若采用不精确一维搜索,仍有下列总体收敛性定理。
设,则采用不精确一维搜索得到的点列的每个聚点均为驻点。
证明:。
注:1) ;
2)最速下降算法的主要优点是方法简单、直观,有好的总体收敛性,但收敛很慢。
三、最速下降算法的收敛速度
1. 先考虑二次函数情形
对极小化问题,其中为对称正定矩阵,,分别为的最大与最小特征值。设是最优解,则最速下降算法的收敛速度至少是线性的,且下面的界成立:
,
其中(为矩阵的条件数)。
证明:由,有。故
其中使,
若设,
其中。则有
,而,
利用这些,可知
, (要求)

设是的特征值,而是对应得标准特征向量(两两正交的单位向量)。
令,则上式可进一步表示为:
(将作用到内每一项)
(由是标准正交向量组)
对,可适当选取,使。
事实上,只须令
即可求得
从而。
显然单调上升。由,及,即得。
由
及
即得.
再由
最后得.
由,并注意到是正定二次函数(), 则有。
再由为严格凸二次函数(正定二次型),故当且仅当时,,由此可推得必有
.
再注意到,则有
从而定理第一式得证。
下面再证定理第二式,记,。由是对称正定的,故有
由,则
故有,
注意到:
因而有
最后得(其中)。
这表明:最速下降算法至少具有线性收敛速度。
(Kantorovich不等式)设是阶对称正定矩阵,和分别为其最大和最小特征值,则,有。
证明:参见袁亚湘等《最优化理论与方法》第三章附录,略。
以上对特殊形式的二次函数的收敛速度进行讨论,对一般的二次函数
利用Kantorovich不等式可得类似的结论,其证明思路如下:设是极小点,则满足
且可表示为
记,
则与仅相差一个常数,它们有相同的最优解,且使用最速下降算法时,每次迭代方向产生的迭代序列均完全相同。现在考察对的极小化,这时最速下降算法的迭代公式为:
(这里为最优步长因子)
其中。直接计算可得:
(由Kantorovich不等式)
故有: (1)
由(1)即得: (或)。由正定,当且仅当时,
利用一致凸性,可证必有:。这表明:算法产生的点列是整体收敛到的。
由(1)有: (2)
注意到: ,
由(2)有
(3)