可知，若某次选代中己取得点X⑹，从该点出发，取负梯度方向
眇一WO
||W（X⑷）||
为搜索方向。
则最速下降法的迭代公式为
当第k次的迭代初始点X⑹和搜索方向2⑹已经确定的情况下，原目标函数成为关于步长a的一维函数。
即
（p（a）=f（X<'K）+aS<'K））
最优步长Qk可以利用一维搜索的方法求得
nmi^（a）=/（XtA+1））=/iCt
根据一元函数极值的必要条件和多元复合函数的求导公式，得
0（a）=+加⑷）丁V/（XtK））=0
[vf（x（K+1））]rVf（X（K））=0
或写成[JtK+1）]rJa,=O
由此可知，在最速下降法中相邻两个搜索方向互相正交。
也就是说在用最速下降
法迭代求优的过程中，走的是一条曲折的路线，该次搜索方向与前一次搜索方向垂直,形成“之”字形的锯齿现象，如图4.1所示。
最速下降法刚开始搜索步长比较大，愈靠近极值点其步长愈小，收敛速度愈来愈慢。
特别是对于二维二次目标函数的等值线是校扁的椭圆时，这种缺陷更加明显。
因此所谓最速下降是指目标函数在迭代点附近出现的局部性质，从迭代过程的全局来看，负梯度方向并非是目标函数的最快搜索方向。
图4.1最速下降法的搜索路径此外，最速下降法的迭代公式也可以写成下面的形式
伙=0,1,2,...）（4.4）
X（K+l）=X（'K）-aK^f（X（k））
将其与式4.3相比较，可知，此处等于4.3式中步长除以函数在X00点导数的模||Vf（X^）||,而此时的搜索方向=也不再是个单位向量。
4.1.2最速下降法的迭代过程
1）给定初始点X（°>,收敛精度£,并令计算次数RUO;
2）计算X⑷点的梯度Vf（X^）及梯度的模冋（X⑷）||,并令
眇一WO
|W（X⑷）||
3）判断是否满足精度指标||Vf（XtAj）||<^;若满足，X⑹为最优点，迭代停止,输出最优解X*=X⑹和/（X*）=f（X。
，否则进行下一步计算；
4）以X⑷为出发点，沿2⑹进行一维搜索，求能使函数值下降最多的步长0.，即
min/（X⑷+a眇）=f（X{k）+aKd{k））
Ct
5）令X（g=X«）+aM®,k=k+l,转到步骤2）。
最速下降法的程序框图如图4.2所示。
4.2最速下降法的程序框图
例题4・1用最速下降法求目标函数/（X）=U-1）+（x2-1）2的极小值，设初始点X（o>=[0Of,计算精度"IO—?
。
解
（1）计算初始点X⑼处目标函数的梯度和梯度的模
（4）计算新的迭代点
由公式（4.2）可得
沿2⑷方向进行一维搜索（或对a求导，并令其为零）
令彳（产⑴）=0,,求得最优步长a二血。
da
（5）计算新迭代点
（6）计算新迭代点的梯度及梯度的模
||Vf（Xw）||=0<£
因已满足精度要求，停止迭代，得最优解为
X*=；,/（X*）=0
可见，对于目标函数的等值线为圆的情况，只要一次迭代就能达到极小值点X*。
这是因为圆周上任意一点的负梯度方向总是指向圆心的，如图4.3所示。
图4.3例题4.1目标函数极小值的搜索过程
通过上面的分析可知最速下降法具有以下特点：
（1）理论明确，程序简单，对初始点要求不严格，每次迭代所需的计算量和存储量也较小，适用于计算机计算。
（2）对一般函数而言，最速下降法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。
（3）最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。
（4）最速下降法的收敛速度与目标函数的性质以及初始点的选择密切相关。
对于等值线（面）为同心圆（球）的目标函数，一次搜索即可达到极小点。
若目标函数为二次函数，等值线为椭圆，当初始点选在长轴或短轴上时，一次搜索也可达到极小值点。
最速下降法的收敛速度和变量的尺度关系很大，这一点可从最速下降法收敛速度的估计式上看出来。
在适当条件下，有
II-X*II<（1-^1）II-X*II
式中Mf（x）的海赛矩阵最大特征值上界；m—；其
最小特征值下界。
当相邻两个迭代点之间满足上式时（右边的系数为小于等于1的正的常数），我们称相应的迭代方法是具有线性收敛速度的迭代法。
因此，最速下降法是具有线性收敛速度的选代法。
鉴于应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其它无约束优化方法配合使用。
即在开始阶段用梯度法求得一个较优的初始点，然后用其它收敛快的方法继续寻找极
小点。
4.2牛顿法
牛顿法是根据目标函数的等值线在极值点附近为同心椭圆族的特点，在极值点X*邻域用一个二次函数久X）来近似代替原目标函数/（X）,并将久X）的极小值点作为对目标函数/（X）求优的下一个迭代点，经多次迭代，使之逼近原目标函数/（X）的极小值点。
4.2.1牛顿法的基本原理
设目标函数是连续二阶可微的，将函数在X⑹点按泰勒级数展开，并保留到二次
项，得
f（X）〜久X）=+-X（K））+*（X-X^）rV7（X（^）（X一X（K））
此式是个二次函数，设XEU为0（X）的极小值点，则
V^（X（U1））=O
即y/xx⑹）+W/（x⑹）（X（e）—X⑷）=0
X（m）二x（K）-W（X（K））「叼（X（K））伙二0,12…）（4.5）
这就是多元函数求极值的牛顿法迭代公式。
式中取
J^=_[v7（x（^）r1vf（X^）称为牛顿方向，为常数。
式中没有步长冬，或者可以看成步长恒等于1,所以牛顿法是一种定步长的迭代。
例题4.4用牛顿法求目标函数f（X）=£+25用的极小值。
解
（1）取初始点Xw=[22]T
（2）计算梯度、二阶偏导数矩阵及其逆矩阵
[V7（X）]_1=2
0——
50
（3）计算新的迭代点
x⑴=x（o〉_iy7（x⑵）]耳[4~|=|~°~1
⑵°丄Lioo」Lo」_5O_
经过一次迭代即可求得极小值点X*=[00]T,函数极小值/（X*）=0o
4.2.2阻尼牛顿法
由以上的两个例题可以看出，对于二次函数，用牛顿法迭代一次即可得到最优点；对于非二次函数，若函数的迭代点已进入极小点的邻域，则其收敛速度也是很快的。
但是从牛顿法迭代公式的推导可以看出，迭代点是由近似二次函数仪X）的极值条件确定的，该点可能是0（X）极小值点，也可能是久X）的极大值点。
因此在用牛顿法迭代时，可能会出现函数上升的现象，即/（X^）>/（X^）,使迭代不能收敛于最优点。
例如上例中若取初始点Xw=[01]T,第一次迭代点的函数值就增大。
这表明牛顿法不能保证函数值稳定地下降，在严重的情况下甚至不能收敛而导致计算失败。
可见，牛顿法对初始点的要比较苛刻的，所选取的初始点离极小值点不能太远。
而在极小值点位置未知的情况下，上述要求很难达到。
为了消除牛顿法的上述这些弊病，需要对其做一些修改。
将牛顿法定步长的迭代，改为变步长的迭代，引入步长a,在x⑹的牛顿方向进行一维搜索，保证每次迭代点的函数值都是下降的。
这种方法称为阻尼牛顿法，其迭代公式为
X（K+1）二x{K）-ak[V2f（X{K））YlVf（X{K））（k=0,1,2,…）
（4.6）
式中，Qk为牛顿方向的最优步长。
这种方法对初始点的选取不再苛刻，从而提高了牛顿法的可靠度。
但采用阻尼牛顿法，毎次迭代都要进行一维搜索，使收敛速度大大降低。
例如，对于例4.6所示的目标函数，取同样的初始点，采用阻尼牛顿法进行迭代，达到同样的精度，要经过25次的迭代，越靠近极小值点收敛速度越慢，使牛顿法收敛速度快的优势损失殆尽。
阻尼牛顿法的迭代过程：
阻尼牛顿法的计算步骤如下：
1）给定初始点收敛精度£,并令计算次数kuO；
2）计算X⑷点的梯度和梯度的模||W（X⑷）||；
3）判断是否满足精度指标||Vf（Xu>）||<£；若满足，X⑹为最优点，迭代停止，输出最优解X*=X⑷和/（X*）=f（X（k））,否则进行下一步计算；
5）计算X⑴点的牛顿方向/⑴
d（k>=-[v2/（xg）FYf（xg）
6）以X⑹为出发点，沿/⑹进行一维搜索，求能使函数值下降最多的步长弧，即
mm/（X⑷+a眇）=于（X⑹+aKd{k））
（X
令X（k+[）=X{k）+aKd{k）,k=k+l,转到步骤2）。
阻尼牛顿法的程序框图如图4.7所示：
4.7阻尼牛顿法的程序框图
牛顿法的总结
牛顿法和阻尼牛顿法统称为牛顿型方法。
这类方法的最大优点是收敛速度快。
也就是说，它的迭代次数相对其他方法来说少得多。
特别是对于一些性态较好的目标函数，例如二次函数，只需保证求梯度和二阶偏导数矩阵时的精度，不管初始点在何处,均可一步就找出最优点。
可是这类方法也有很大的缺点。
首先，；方向时，都要计算目标函数的一阶导数和二阶导数矩阵及其逆矩阵。
这就使计算较为复杂，增加了每次迭代的计算工作量和计算机的存储量。
选用原则和条件：
该方法适用于目标函数具有一阶、二阶偏导数，海森矩阵非奇异,维数不太高的场合。
升级会员 