min f ( x ) 8
4、优缺点
数学分析表明，牛顿法具有很好的局部收敛性质，对
二次函数来说，仅一步就达到优化点，
但对一般函数来说，在一定条件下，当初始点的选取
充分接近目标函数的极小点时，有很快的收敛速度，但若
初始点选取离最小点比较远，就难保证收敛；
牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂
其中 S
(k )
称为牛顿方向。
3、迭代步骤 一 二 给定初始点 x (0) ，计算精度ε ，令k=0； 计算 x(k ) 点的梯度 及其逆矩阵 三
f ( x (k ) )
1
、 H ( x (k ) )
H ( x )
(k )
。
构造搜索方向
s
(k )
H ( x ) f ( x ( k ) )
2 ] 4
所以
1 4 (0) 2] f ( x ) [ ]; [ H ( x ( 0 ) )]1 [ 1 1 2 2 2 1 1 (0) ( 0 ) 1 (0) 2 ][ 4] [3] s [ H ( x )] f ( x ) [ 1 1 2 1 2 2
由修正牛顿法，得
如原来的好。这和初始点的选择是否恰当有很大
为了克服牛顿法的上述缺陷，可以通过在迭代 中引入步长因子和一维搜索加以解决，即令
x ( k 1) x ( k ) ( k ) [ H ( x ( k ) )]1 f ( x ( k ) )3
式中， ------一维搜索所得的最优步长因子。 因而将 称为牛顿方 1 向。 s ( k ) H ( x ( k ) ) f ( x ( k ) )
(1) (0) (0)
x x s 带入原函数 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求导，其极值点必满足一阶导数为零，所以，
( x)
得到 式中，
f ( x) f ( x ( k ) ) x x ( k ) H ( x ( k ) ) 0 x


xmin x
(k )
H ( x ) f ( x ( k ) )
(k )


1
[1]
H ( x )
2、基本思想
在求目标函数 f (x)的极小值时，先将它在
x (k ) 点附近展开
成泰勒级数的二次函数式，然后求出函数的极小值点，并以此点作 为欲求目标函数的极小值点
x * 的一次近似值。
设目标函数是连续二阶可微的，将函数在点 x (k ) 按泰勒级数 展开，并取到二次项：
f ( x) ( x ( k ) ) f ( x ( k ) ) [f ( x ( k ) )]T ( x x ( k ) ) 1 ( x x ( k ) )T H ( x ( k ) )( x x ( k ) ) 2
2 f 2 x H ( x (0) ) 2 1 f x x 2 1
2 f x1 x2 2 1 H ( x ( 0) )1 1 2 1 2 3 1 2 f 1 2 2 x2
1 3 1 3 [ ] [ ] [ ] 1 1 1
代入
x
(1)
x
(0)
s
(0)
1 3 1 3 4 [ ] [ ] [ ][ ] 1 1 1 2
因为
f ( x (1) ) 8 0 (1) f ( x ) [ ], || f ( x (1) ) || 0 0.1 0
比 ，
较，则有搜索 方 向 s ( k ) H ( x ( k ) ) 1 T f ( x ( k ) ) 步长因子 ( k ) 1


s
(k )
H ( x ) f ( x ( k ) )
(k )


1
x ( k 1) x ( k ) s ( k )
牛顿法的 迭代算式
min
若不满足，令k=k+1，转第二步继续迭代。
例：
2 用牛顿法求函数 f ( x) x12 x2 x1 x2 10 x1 4 x2 60
的极小值。
解：
0 (1)取初始点 x ( 0) 0
(2)计算牛顿方向
2 x1 x2 10 10 f ( x ) x x( 0) 2 x2 x1 4 4
牛顿法与修正牛顿法
小组成员：
王建领 裴希瑶
靳鹏程
任森 张世昌
1 、思想来源
4、优缺点
2、基本思想
牛顿法和 修正牛顿法
5、修正牛顿法
3、迭代步骤
6、评价
1、思想来源
梯度法相邻两次搜索方向总是相互正交，搜索路线 呈锯齿形，使得其在极小点附近，收敛速度越来越 慢。人们试图找到这样一种方向：它直接指向最优 点，使得从任意选定的初始点出发，沿此方向迭代 一次就能达到极小点。
(k )


1
四
沿 s (k )方向进行一维搜索，得迭代点
x ( k 1) x ( k ) s ( k )
五 收敛判断：


若 f ( x (k 1) ) ，则 x ( k 1) 为近似最优点，迭代停止， ( k 1) ( k 1) 和 f ( xmin ) f ( x ) 终止计算。 输出最优解 x x
的目标函数来说，是较困难的。
5、修正牛顿法 当目标函数为非二次函数时，目标函数在 x k 点展开所得的二次函数是该点附近的一种近似表 达式，所求的极小点，当然也是近似的，需要继
续迭代。但是当目标函数严重非线性时，用式[2]
进行迭代则不能保证一定收敛，即在迭代中可能 会出现 的关系。
f ( x ( k 1) ) f ( x ( k ) ) ，所得到经过这种修改后的算法称为修正牛顿法。也称 牛顿方向法or阻尼牛顿法。
举例：用修正牛顿法求解下列无约束优化问题，已知
2 x 0 (1, 1)T , 0.1. f ( x) x12 2 x2 2 x1 x2 4 x2
解：
因为
2 x1 2 x2 4 2 (0) f ( x ) [ ]; H ( x ) [ 2 x1 4 x2 2 1
[H ( x
(K )
)] f ( x )
(k )
1
如果目标函数 的。因此由
f ( x) 是正定二次函数，那么 H ( x) 是个常矩阵，逼近式[1] 是准确
x( k ) 点出发只要迭代一次既可以求 f ( x) 的极小点。
[2] 式与一维搜索公式
x
( k 1)
x
(k )
s
(k ) (k )
故
s
( 0)
H ( x ) f ( x ( 0) )
(0)


1
1 2 1 10 1 24 8 4 3 18 6 3 1 2
(3)极小值
x x
1 (0)
s
(0) (0)
0 8 8 1* 0 6 6
(k )
1
为Hessian矩阵的逆矩阵。

在一般情况下， f
（ 但是在 x k ) 点附近，函数 ( x) 和 下一次迭代，即得
的极值点。 ( x) 不一定是二次函数，因而 xmin 也不可能是 f ( x）
f ( x)
是近似的，所以可以用
x(k 1) 点作为
[2]
x

( k 1)
x
(k )
故迭代终止；
所以最优解为
xmin x
(1)
4 [ ], f ( x) min 8 2
6、牛顿法的评价
由于采用了目标函数的二阶导数信息，收敛速度比梯度法快。 牛顿法迭代公式与一般迭代公式的区别在于，没有最优步长 因子。这使得在接近最优点时，由于步长不能调节，可能会 错过最优点，造成算法的稳定性欠佳，甚至造成不能收敛而 导致计算失败。为了克服这一点，提出了修正牛顿法，它既 保持了牛顿法收敛快的特性，有放宽了对初始点选择的要求， 保证每次迭代的结果都是目标函数值下降。 需要计算Hessian矩阵及其逆矩阵，内存占用、计算量大；此 外二阶导数不存在，或者逆矩阵不存在的情况不能应用。