开始 输入X(0) ，ε k?0 计算?f(X(K)) 及搜索方向 ?(k)?f(X(k))d???f(X(k)) Ｙ ?f(X(k))??? Ｎ k?k?1 X*?X(k)?一维搜索求最优步长k ?(k)??Kd f(X*)?f(X(k)) 结束
X(k?1)?X(k)4.2最速下降法的程序框图
例题4.1 用最速下降法求目标函数f(X)?(x1?1)2?(x2?1)2的极小值，设初始点X(0)?[0 0]T，计算精度??10?2。
解 （１）计算初始点X(0)处目标函数的梯度和梯度的模
??f(X)???x??2(x?1)???2?1(0)?f(X)?? ???1????2(x?1)?f(X)???2???2?
??x??2? ?f(X(0))?22（２）由于?f(X(0))?22??，不满足精度指标，转下一步计算。 （３）确定搜索方向
?(0)d??f(X(0))1??2????????2???(0)?f(X)22?????1?2?? 1?2??（４）计算新的迭代点 由公式（4.2）可得
X(1)?X(0)?(0)??d???0?????????0???1??2?????1??2??????2?? ??2??代入目标函数 f(X(1))?(?2?1)2?(?2?1)2
?(k)沿d方向进行一维搜索（或对?求导，并令其为零）
df(X(1))2?2??(?1)?(?1) d?2222df(X(1))?0，，求得最优步长?0?2。 令
d?（５）计算新迭代点
X(1)??0??2??1???????? ??0??1??2???（６）计算新迭代点的梯度及梯度的模
?2(x?1)??0??f(X(1))??1??? ??2(x2?1)??0??f(X(0))?0??
因已满足精度要求，停止迭代，得最优解为
?1?X*???，f(X*)?0
?1?可见，对于目标函数的等值线为圆的情况，只要一次迭代就能达到极小值点X*。这是因为圆周上任意一点的负梯度方向总是指向圆心的，如图4.3所示。
图4.3例题4.1目标函数极小值的搜索过程
通过上面的分析可知最速下降法具有以下特点：
（1）理论明确，程序简单，对初始点要求不严格，每次迭代所需的计算量和存储量也较小，适用于计算机计算。
（2）对一般函数而言，最速下降法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。
（3）最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。
（4）最速下降法的收敛速度与目标函数的性质以及初始点的选择密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。若目标函数为二次函数，等值线为椭圆，当初始点选在长轴或短轴上时，一次搜索也可达到极小值点。 最速下降法的收敛速度和变量的尺度关系很大，这一点可从最速下降法收敛速度的估计式上看出来。在适当条件下，有
式中 的海赛矩阵最大特征值上界；
其最小特征值下界。
当相邻两个迭代点之间满足上式时（右边的系数为小于等于1的正的常数），我们称相应的迭代方法是具有线性收敛速度的迭代法。因此，最速下降法是具有线性收敛速度的选代法。
鉴于应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其它无约束优化方法配合使用。
即在开始阶段用梯度法求得一个较优的初始点，然后用其它收敛快的方法继续寻找极小点。
4．2牛顿法
牛顿法是根据目标函数的等值线在极值点附近为同心椭圆族的特点，在极值点X*邻域内用一个二次函数?(X)来近似代替原目标函数f(X)，并将?(X)的极小值点作为对目标函数f(X)求优的下一个迭代点，经多次迭代，使之逼近原目标函数f(X)的极小值点。
4.2.1牛顿法的基本原理
设目标函数是连续二阶可微的，将函数在X(k)点按泰勒级数展开，并保留到二次项，得
f(X)??(X)?f(X(K))?[?f(X(K))](X?XT(K)1)?(X?X(K))T?2f(X(K))(X?X(K)) 2此式是个二次函数，设X(k?1)为?(X)的极小值点，则
??(X(k?1))?0
(k)2(k)(k?1)(k)?f(X)??f(X)(X?X)?0即
X(K?1)?X(K)?[?2f(X(K))]?1?f(X(K))这就是多元函数求极值的牛顿法迭代公式。式中取
(k?0,1,2,?)（4.5）
?(k)d??[?2f(X(K))]?1?f(X(K))称为牛顿方向，为常数。式中没有步长?k，或者可以
看成步长恒等于1，所以牛顿法是一种定步长的迭代。
22例题4.4 用牛顿法求目标函数f(X)?x1的极小值。 ?25x2解 （１）取初始点X(0)?[2 2]T
（２）计算梯度、二阶偏导数矩阵及其逆矩阵
?2x1??4??f(X)?????100?50x?2????20? ?2f(X)???
050??(0)?1?2?12???f(X)?????0??（３）计算新的迭代点
?0??1?50??X(1)?1?2??2(0)2(0)?1(0)?X?[?f(X)]?f(X)??????2??0???0??4??0?????0? 1??100????50??经过一次迭代即可求得极小值点X*?[0 0]T，函数极小值f(X*)?0。
4.2.2 阻尼牛顿法
由以上的两个例题可以看出，对于二次函数，用牛顿法迭代一次即可得到最优点；对于非二次函数，若函数的迭代点已进入极小点的邻域，则其收敛速度也是很快的。但是从牛顿法迭代公式的推导可以看出，迭代点是由近似二次函数?(X)的极值条件确定的，该点可能是?(X)极小值点，也可能是?(X)的极大值点。因此在用牛顿法迭代时，可能会出现函数上升的现象，即f(X(k?1))?f(X(k))，使迭代不能收敛于最优点。例如上例中若取初始点X(0)?[0 1]T，第一次迭代点的函数值就增大。这表明牛顿法不能保证函数值稳定地下降，在严重的情况下甚至不能收敛而导致计算失败。可见，牛顿法对初始点的要求是比较苛刻的，所选取的初始点离极小值点不能太远。而在极小值点位置未知的情况下，上述要求很难达到。
为了消除牛顿法的上述这些弊病，需要对其做一些修改。将牛顿法定步长的迭代，改为变步长的迭代，引入步长?，在X(k)的牛顿方向进行一维搜索，保证每次迭代点
的函数值都是下降的。这种方法称为阻尼牛顿法，其迭代公式为