.,
13
为了克服牛顿法的上述缺陷，可以通过在迭代 中引入步长因子和一维搜索加以解决，即令
x(k1) x(k) (k)[H (x(k) )]1f (x(k) ) 3
式中，
(k
)
------一维搜索所得的最优步长因子。
因而将
向。
s(k) H(x(k) ) 1f (x(k) )
称为牛顿方
.,
12
5、修正牛顿法
当目标函数为非二次函数时，目标函数在 xk
点展开所得的二次函数是该点附近的一种近似表 达式，所求的极小点，当然也是近似的，需要继
续迭代。但是当目标函数严重非线性时，用式[2]
进行迭代则不能保证一定收敛，即在迭代中可能 会出现 f (x(k1) ) f (x(k ) ) ，所得到的下一点不 如原来的好。这和初始点的选择是否恰当有很大 的关系。
及其逆矩阵 H (x(k) ) 1 。
三 构造搜索方向
s(k) H(x(k) ) 1f (x(k) )
.,
8
四 沿 s(k)方向进行一维搜索，得迭代点
x(k1) x(k ) s(k )
五 收敛判断：
▪ 若 f (x(k1) ) ，则 x(k1) 为近似最优点，迭代停止，
输出最优解 xmin x(k 1)和 f (xmin) f (x(k1) ) 终止计算。
x12 2 f
x2 x1
2 f
x1x2
2 f
2 1
1
2
H
(
x(0)
)
1
1 3
2 1
1 2
x22
故 s(0) H (x(0) ) 1f (x(0) )
1 3
2 1
1 10
2
4
1 3
24
18
8 6
(3)极小值
x1
x(0)
s (0) (0)
0 0
8 1* 6
8 6
min f (x) 8
1 (x x(k ) )T H (x(k ) )( x x(k ) ) 2
.,
4
对x求导，其极值点必满足一阶导数为零，所以，
(x) f (x) f (x(k) ) x x(k) H (x(k) ) 0 x
得到
xmin x(k) H (x(k) ) 1f (x(k) )
[1]
▪ 若不满足，令k=k+1，转第二步继续迭代。
.,
9
例：
用牛顿法求函数 f (x) x12 x22 x1x2 10 x1 4x2 60 的极小值。
解：
(1)取初始点
x(0)
0 0
(2)计算牛顿方向
f
(x) 22xx12xx21140
xx(0)
10
4
.,
10
2 f
H (x(0) )
牛顿法与修正牛顿法
.,
1
1 、思想来源 2、基本思想 3、迭代步骤
牛顿法和 修正牛顿法
4、优缺点 5、修正牛顿法 6、评价
.,
2
1、思想来源
▪ 梯度法相邻两次搜索方向总是相互正交，搜索路线 呈锯齿形，使得其在极小点附近，收敛速度越来越 慢。人们试图找到这样一种方向：它直接指向最优 点，使得从任意选定的初始点出发，沿此方向迭代 一次就能达到极小点。
步长因子 (k ) 1
s(k) H (x(k) ) 1f (x(k) )
x(k 1) x(k ) s(k )
比 ，
牛顿法的 迭代算式
其中 S (k) 称为牛顿方向。
.,
7
3、迭代步骤
一 给定初始点 x(0)，计算精度ε，令k=0；
二 计算 x(k) 点的梯度 f (x(k) ) 、 H (x(k) )
.,
11
4、优缺点
▪ 数学分析表明，牛顿法具有很好的局部收敛性质，对
二次函数来说，仅一步就达到优化点，
▪ 但对一般函数来说，在一定条件下，当初始点的选取
充分接近目标函数的极小点时，有很快的收敛速度，但若 初始点选取离最小点比较远，就难保证收敛；
▪ 牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂
的目标函数来说，是较困难的。
式中， H (x(k) ) 1 为Hessian矩阵的逆矩阵。
.,
5
▪ 在一般情况下，f (x) 不一定是二次函数，因而 xmin 也不可能是 f (x）的极值点。
x x 但是在 （k ) 点附近，函数 (x) 和 f (x) 是近似的，所以可以用 (k1) 点作为
下一次迭代，即得
x(k1) x(k ) [H (x(K ) )]1f (x(k ) ) [2]
经过这种修改后的算法称为修正牛顿法。也称
牛顿方向法or阻尼牛顿法。
.,
14
举例：用修正牛顿法求解下列无约束优化问题，已知
x0 (1,
解：
因为
所以
1)T , 0.1. f (x) x12 2x22 2x1x2 4x2
f
(x)
2 [
x1
2x2
4 ];
H
(
x
(0
)
)
[
2
2 ]
2x1 4x2
▪
如果目标函数 f (x) 是正定二次函数，那么 H (x) 是个常矩阵，逼近式[1] 是准确 的。因此由 x(k ) 点出发只要迭代一次既可以求 f (x) 的极小点。
.,
6
[2] 式与一维搜索公式 x(k1) x(k) (k)s(k)
较，则有搜索 方 向 s(k) H(x(k) ) 1T f (x(k) )
2 4
f
(x(0) )
4 [ ];[H
2
(x(0)
)]1
1 [1
1
2 1
]
22
1 s(0) [H (x(0) )]1f (x(0) ) [ 1
1
2 1
4 ][ ]
2
3 [] 1
22
.,
15
由修正牛顿法，得
x(1)
x(0)
s(0)
13
[ ][ ]
1 3
[ ]
带入原函数
1 1 1
f (x(1) ) (1 3 )2 2(1 )2 2(1 3 )(1 ) 4(1 3 ) ( )
对 求导'( ) 6(1 3 ) 4(1 ) 6(1 ) 2(1 3 ) 12 0
解得 1
代入 因为
x (1)
x(0)
s(0)
13
[ ][ ]
1 3
[ 1) ) 8
f
(x(1) )
0 [ ],||
f
.,
3
2、基本思想
在求目标函数 f (x)的极小值时，先将它在 x(k ) 点附近展开
成泰勒级数的二次函数式，然后求出函数的极小值点，并以此点作
为欲求目标函数的极小值点 x* 的一次近似值。
设目标函数是连续二阶可微的，将函数在点 x(k ) 按泰勒级数
展开，并取到二次项：
f (x) (x(k) ) f (x(k) ) [f (x(k) )]T (x x(k) )