（2） 计算 f ( x k ) ，若 f (xk ) 成立，则迭代停止， x k 即为
所求稳定点；否则，转（3）。
（3） 计算 H (x ) 1 和下降方向 pk 。
（4） 沿 p k 方向进行一维搜索，决定步长 k ：
f
x k k pk
min f ( x k pk ) 0
（5） 令 xk1 = x k k pk ， k k 1，返回（2）。
f ( x k )T pk 0
（4）
即可保证 f ( x) f ( x k pk ) f ( x k ) 。此时，若取
x k1 x k p k
（5）
就一定能使目标函数得到改善。
建模方法与应用
6.1 最速下降法
现在考察不同的方向 p k ，假设 p k 的模不为零，并设 f (x k ) 0（否
x x 点处的梯度方向，仅在 点的一个小邻域内才具有最速的
性质，而对于整个优化过程来说，那就是另外一回事了。由上
x2
x 0 (1,1)
1
x1
例可以看出，当二次函数的等值线为同心椭圆时，采用梯度法 其搜索路径呈直角锯齿状；最初几步函数值变化显著，但是迭 代到最优点附近时，函数值的变化程度非常小。因此，梯度法
用一维搜索法、微分法，也可以利用试算法，或者根据某些函数确定最佳步长，则只能选用前两种方法。
建模方法与应用
6.1 最速下降法
一般地，若 f (x k ) 2 ，则 x k 即为近似极小点；否则求步
长 k 并计算 xk1 = x k k f ( x k ) 。如此反复，直到达到要求
建模方法与应用
6.1 最速下降法
为了得到下一个近似点，在选定搜索方向之后，还要确定
步长 。的计算可以采用试算法，即首先选取一个 值进 行试算，看它是否满足不等式 f ( x k1 ) f ( x k pk ) f ( x k ) ； 如果满足就迭代下去，否则缩小 使不等式成立。由于采用 负梯度方向，满足该不等式的 总是存在的。
圆的问题，不管初始近似点选在哪里，
负梯度方向总是直接指向圆心，即圆
心为极值点。这样，只要一次迭代即
x1 能达到最优。
x0
图 12
建模方法与应用
6.1 最速下降法
[例] 试用梯度法求
f ( x) 4x1 6x2 2x12 2x1x2 2x22 的极大点。
解：该二次函数的绝对最优解
x
(
1 3
8 H (x) 4
4 8 是正定矩阵
取 x 0 (5,2)T ，则：
f
(
x0
)
48 36
，
H
(x
0
)
8 4
4 8
，
H
(
x
0
)
1
1 6
1 12
1 12
1 6
x1
x0
H ( x 0 )1f
(x0)
5 2
1 6
1 12
1 12
1 6
48 36
0 0
因 f ( x1 ) (0,0)T ，故 x1 (0,0)T 为 f (x) 的极小点，极小值
(
2,2)
2 0
0 2
2 2
16
2
x x 1 0
=
0
f
(
x
0
)
=
00
1 2
22
11
f ( x1 ) 2 [ (0)2 (0)2 ]2 0
建模方法与应用
6.1 最速下降法
x2
图 12 展示了该例的迭代过程，即
极小点 x1
从 x 0 (0,0) 经过负梯度方向一步到达
极小点 x1 (1,1) 。其实，对于等值线为
此时，按式（7）求得的极小点，只是 f (x) 的近似极小点。在
这种情况下，常按下式选取搜索方向：
pk H ( x k )1f ( x k )
（8）
x k1 = x k k p k
（9）
k： min f ( x k k P k ）
（10）
按照这种方式求函数 f (x) 极小点的方法称为牛顿法，式
另一种方法是通过在 x k 负梯度方向上的一维搜索，来确
定使得 f ( x k1 ) f ( x k p k ) 最小的，这种梯度法就是所谓的
最速下降法。
建模方法与应用
6.1 最速下降法
2．基本步骤
给定一个初始近似点 x 0 及其精度 0，若 f (x0 ) 2 ，则 x 0 即为近似
极小点；若 f (x0 ) 2 ，求步长0 并计算 x1= x0 0 f (x0 ) 。求步长可以
与一维问题类似，在局部，用一个二次函数近似代替目标
函数 f (x) ，然后用近似函数的极小点作为 f (x) 的近似极小
点。
若非线性目标函数 f (x) 具有二阶连续偏导， x k 为 f (x)
的一个近似极小点，在 x k 点取 f (x) 的二阶泰勒展开，即：
f (x) f ( x k ) f ( x k )T
xk1 ，在 x k 点沿方向 p k 作射线 x x k + pk ， （ 0）称为步长。现 将 f (x) 在 x k 处作泰勒展开，有：
f ( x) f ( x k pk ) f ( x k ) f ( x k )T p k o（）
其中 o（）是 的高阶无穷小。对于充分小的 ，只要
0
)
3 1
1
1
，
H (x0
) 1
1 2
1 2
1 2
3 2
x1
x0
H ( x 0 )1f
(x0)
0 0
1 2
1 2
1 2
3 2
2
0
1 1
因 f ( x1 ) (0,0)T ，故 x1 (1,1)T 为 f (x) 的极小点，极小值是
“-1”。
建模方法与应用
6.2 Newton型 法
即
x x k H ( x k )1f ( x k )
（7）
如果 f (x) 是二次函数，则其海赛矩阵为常数，式（6）是
精确的。在这种情况下，从任意一点出发，用式（7）只要一
步即可求出 f (x) 的极小点（假设海赛矩阵正定）。
建模方法与应用
6.2 Newton型 法
如果 f (x) 不是二次函数，式（6）仅是一个近似表达式。
f ( x(k ) )T f ( x(k ) )
= f ( x(k ) )T H ( x(k ) )f ( x(k ) ) ，可见最佳步长不仅与梯度有关，而且
与海赛矩阵有关。
建模方法与应用
6.1 最速下降法
[例] 试用梯度法求 f ( x) (x1 1)2 (x2 1)2 的极小点， 0.1。
则 x k 是稳定点）；那么，使式（4）成立的 p k 有无穷多个，为了使目标
函数能得到尽量大的改善，必须寻求能使 f ( x k )T pk 取最小值的 p k 。 由 于 f ( x k )T pk = f ( x k ) pk cos ， 当 p k 与 f ( x k ) 反 向 （ 即 cos1800 1）时，f ( x k )T pk 取最小值。 pk f ( x k ) 被称为负梯 度方向，在 x k 的某一小的邻域内，负梯度方向是使函数值下降最快的 方向。
是“0”。
建模方法与应用
6.2 Newton型 法
[例]
试用牛顿法求
f (x)
x 3 2
21
1 2
x22
x1 x2
2x1的极小
值。
解：
f ( x) (3x1 x2 2, x2 x1 )T
H
(
x)
3 1
1
1
是正定矩阵
取 x 0 (0,0)T ，则：
f
(
x
0
)
2
0
，
H
(
x
建模方法与应用
6.1 最速下降法
有 f ( x1 ) 2(1 2)2 2(1 2) 4
令函数 f ( x1 ) 对 的导数为零，可求得最佳步长
1
1 4
于是有
x1
(1
2,1)
(
1 2
,1)
，同理可进行后续的各步迭代。
第二次迭代： f ( x1 ) (0,1) ， 2
1 4
，
x2
(
1 2
解：取初始近似点 x 0 (0,0)T ， f ( x 0 ) (2,2)T
f ( x (0) ) 2 [ (2)2 (2)2 ]2 8
2 0 H (x) 0 2
f ( x(0) )T f ( x(0) )
(
2,
2)
2 2
81
0 = f ( x(0) )T H ( x(0) )f ( x(0) )
2．阻尼 Newton 法
在上面介绍的 Newton 法中，步长 k 总是取为 1。在阻尼 Newton
法中，每一步迭代沿方向
pk H ( x k )1f ( x k )
进行一维搜索来决定 k ，即取 k ，使得
f
x k k pk
min f ( x k pk ) 0
从而使用下面的迭代公式
xk1 = x k k H ( x k )1f ( x k )
来代替(8)-(10). 阻尼 Newton 法保持了 Newton 收敛速度快的优点，又不要
求初始点选的很好，因而在实际应用中取得较好的效果。
建模方法与应用
6.2 Newton型 法
阻尼 Newton 法的计算步骤
（1） 给的初始点 x 0 ，精度 0 ，令 k 0 。