2009-7-27 1
第四章 无约束优化方法
6,坐标轮换法 ;
7,鲍威尔法 ;
4,梯度法及共轭梯度法 ;
5,DFP变尺度法,
1,概述
2,最速下降法
3,牛顿型方法
2009-7-27 2
1.概述
有些实际问题，其数学模型本身就是一个无约束优化问题可以按无约束问题来处理
通过熟悉无约束优化问题的解法可以为研究约束优化问题打下良好的基础
约束优化问题的求解可以通过一系列无约束优化方法来达到
2009-7-27 3
无约束优化问题
对于无约束优化问题的求解，可以直接就用第三章讲述的极值条件来确定极值点位置。这就是把求函数极值的问题变成求解方程
数值求解
各种无约束优化方法的区别就在于确定其搜索方向的方法不同。
T
12[,,,]
( ) m i n
nx x x x
fx
=
L
使
0f?
1 ( 0,1,2,)k k kkx x d ka+ = + = L
2009-7-27 4
无约束优化方法的分类
一类是利用目标函数的一阶或二阶导数的无约束优化方法
最速下降法、共轭梯度法、
牛顿法及变尺度法等。
另一类是只利用目标函数值的无约束优化方法
坐标轮换法，单形替换法及鲍威尔（ Powell）法等。
开始给定 x d 的初始值计算 a*
使
( )fa+xd
最小
a *?x x d
满足收敛条件？
结束给定 新的 d
图 10 无约束极小化算法的粗框图是 否
2009-7-27 5
2,最速下降法
目标函数值 f(x) →min
从某点 x出发，其搜索方向 dk取该点的 负梯度方向 (最速下降方向 ),使函数值在该点附近的范围内下降最快
由于最速下降法是以负梯度方向作为搜索方向，所以最速下降法又称为 梯度法
问题转化为求最佳步长因子的一维搜索问题
( )1 0,1,2,k k k kx x a f x k+ = -? L
( ) ( )( ) ( )( ) ( )1 m i n m i nk k k k k kaaf x f x a f x f x a f x aj+ = -? -?
2009-7-27 6
根据一元函数极值的必要条件和多元复合函数求导公式，得
相邻两点的函数梯度相互垂直
局部最快，整体上并不是最快
( ) ( )[ ]{ } ( )T 0k k k ka f x a f x f xj ￠ = -? 蜒 =
( )[ ] ( )T1 0kkf x f x+蜒 =
( )1k k k kx x a f x+ = -
T1 0kkdd+ =
x 1
x 2
O
图 最速下降法的搜索路径
2009-7-27 7
例题
1,求目标函数 f(x)=x12+25x22的极小值取初始点 x0=[2,2]T
初始点处函数值及梯度分别为
( )0 104fx =
( ) 10
2
42
50 100
x
fx x 轾轾 犏犏?= 犏犏臌 臌沿负梯度方向搜索
( ) 01 0 000
0
2 4 2 4
2 1 0 0 2 1 0 0
a
x x a f x a a
-轾 轾 轾犏 犏 犏
= -? - =犏 犏 犏 -
臌 臌 臌
2009-7-27 8
a0为一维搜索最佳步长，应满足极值必要条件
( ) ( )[ ]
( ) ( ){ } ( )
1 0 0
22
00
m i n
m i n 2 4 25 2 100 m i n
a
aa
f x f x a f x
a a aj
= -
= - + - =
( ) ( ) ( )0 8 2 4 5 0 0 0 2 1 0 0 0a a aj ￠ = - - - - =
可算出一维搜索最佳步长
0 626 0,0 2 0 0 3 0 7 231252a ==
以及第一次迭代设计点的位置和函数值
01
20
1,9 1 9 8 7 724
2 1 0 0 0,3 0 7 1 7 8 5 1 0
a
x a -
轾-轾 犏犏
== 犏犏 - -
犏臌 臌从而完成了最速下降法的第一次迭代求最佳步长
2009-7-27 9
继续下去，经过 10次迭代后，可以得到最优解
该问题的目标函数 f(x)的等值线为一族椭圆，
迭代点从 x0走的是一段锯齿路线。
0
0x
* 轾犏= 犏臌
( ) 0fx* =
x0
x1
x2
2009-7-27 10
最速下降算法的程序框图给定 x0,?
k=0
dk=?f(xk)
ak=minf(xk+akdk)
xk+1=xk+akdk k=k+1
‖ xk+1－ xk‖ ＜?x*=xk+1
结束是 否
2009-7-27 11
最速下降法的特点
最速下降法是一个求解极值问题的古老算法
– 早在 1947年就已由柯西 (Cauchy)提出
– 直观、简单
要计算函数的梯度，故属于解析法，即间接求解法
采用了函数的负梯度方向作为下一步的搜索方向，所以收敛速度较慢，越是接近极值点收敛越慢，这是它的主要缺点
应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其他无约束优化方法配合使用
一些更有效的方法都是在对它改进后，或在它的启发下获得的，
因此最速下降法仍是许多有约束和无约束优化方法的基础。
2009-7-27 12
3,牛顿型方法
一维搜索的牛顿方法的迭代公式
对于多元函数 f(x)，设 xk为其极小点 x*附近的一个近似点，在 xk处进行泰勒展开，保留到二次项
( )
( )1 0,1,2,
kkk
k
fxx x k
fx+
￠= - =
ⅱ L
( ) ( ) ( ) ( )[ ] ( ) ( ) ( ) ( )T T 212k k k k k kf x x f x f x x x x x f x x xj? +? + -?
极值必要条件
( )1 0kxj +?
( ) ( ) ( )2 1 0k k k kf x f x x x+ =
( )[ ] ( )121k k k kx x f x f x-+ =- 蜒 二次收敛
2009-7-27 13
牛顿法例题
用牛顿法求 f(x1,x2)=x12+25x22的极小值取初始点为 x0=[2,2]T
( )
0
10
2
42
50 100x
x
fx x 轾轾 犏犏?= 犏犏臌 臌
( )20 200 50fx 轾犏? 犏臌
( )[ ] 120
1 0
2
10
50
fx -
轾犏犏? 犏犏犏臌代入牛顿法迭代公式
( )[ ] ( )11 0 2 0 0
1 02 4 0
2
1 02 1000
50
x x f x f x-
轾犏轾轾轾犏犏犏 犏
=- 蜒 = - =犏 犏臌犏臌臌 犏臌
2009-7-27 14
阻尼牛顿法
从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念
对于非二次函数，如果采用上述牛顿迭代公式，
有时会使函数值上升，即出现 f(xk+1)>f(xk)的现象
需对上述牛顿法进行改进，引入数学规划法的搜索概念，提出所谓“阻尼牛顿法”
2009-7-27 15
( )[ ] ( )12k k kd f x f x-=- 蜒将 看 作 是 搜 索 方 向,称 其 为 牛 顿 方 向
( )[ ] ( )121,0,1,2,k k k k k k k kx x a d x a f x f x k-+ = - = - 蜒 = L
阻尼牛顿法的迭代公式为
ak— 沿牛顿方向的一维最佳搜索步长，可称为 阻尼因子
ak可通过一维搜索的极小化过程求得
( ) ( ) ( )1 m i nk k k k k kaf x f x a d f x a d+ = + = +
ak 取为固定值 1时，阻尼牛顿法就成为了牛顿法
每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象
保持了牛顿法二次收敛的特性，而对初始点的选取并没有苛刻的要求
原来的牛顿法就相当于阻尼牛顿法的步长因子取成固定值 1的情况
2009-7-27 16
阻尼牛顿法的计算步骤
(1)给定初始点 x0，收敛精度?，置 k=0
(2)计算?f(xk),?2f(xk),[?2f(xk)]-1和 dk=-[?2f(xk)]-1
×?f(xk)
(3)求 xk+1＝ xk+akdk，其中 ak为沿 dk进行一维搜索的最佳步长
(4)检查收敛精度。若 ‖ xk+1－ xk‖ ≤?，则 x*=xk+1，否则，
置 k=k+1，返回到 2继续进行搜索。
2009-7-27 17
阻尼牛顿法的程序框图给定 x0,?
k=0
dk=[?2f(xk)]-1?f(xk)
ak=minf(xk+akdk)
xk+1=xk+akdk
‖ xk+1-xk‖ ≤?
x*=xk+1
结束
k=k+1
2009-7-27 18
牛顿型方法的特点
牛顿法和阻尼牛顿法统称为牛顿型方法
主要缺点
– 每次迭代都要计算函数的二阶导数矩阵，并对该矩阵求逆。这样工作量很大。特别是矩阵求逆，当维数高时工作量更大
– 从计算机存储方面考虑，牛顿型方法所需的存储量也是很大的
最速下降法的收敛速度比牛顿法慢，而牛顿法又存在上述缺点。针对这些缺点，近年来人们研究了很多改进的算法
– 如针对最速下降法 (梯度法 ) 提出只用梯度信息，但比最速下降法收敛速度快的共轭梯度法；
– 针对牛顿法提出变尺度法等
2009-7-27 19
4.梯度法及共轭梯度法一）梯度方向
*可取最优步长或下降步长二）基本思想梯度方向是目标函数上升最快的方向,负梯度方向则是最速下降方向；
)( )()()()1( kkkk XFXX2） 迭代公式
1） 沿 负梯度方向搜索,)()()( )( kkk gXFS
kg
三）终止判别条件梯度法
2009-7-27 20
给定 X0,ε
K=0,X（ K） =X0
K=K+1
X(k)=X△
X*= X（ K）
F*=F（ X*）
结 束
N
Y
计算
)()(,kk gg
)(kg
从 出发,沿 搜索得
)(kX )(kg?
)()()( kkk gXX
*,最速下降性,只是迭代点邻域的局部性质。从全局看，并非最速下降方向。
四,迭代步骤
2009-7-27 21
共轭梯度法
)1(1)2()2( )( SXFS第二方向：
)( )1()1( XFS第一方向：
二,共轭方向的构成
*利于突破函数的非二次性 ;
每轮搜索方向为一组共轭方向,但第一方向为负梯度方向,
一,基本思路
)1()1()1()2( SXX
* 可表示为两个负梯度方向的线性组合 。)2(S
)1(X
)2(S
)2(X
)1(S
)( )2(XF
2009-7-27 22
2)(
2)1(
)(
)(
k
k
k XF
XF
)()1()1( )( kkkk SXFS,
以后新方向均按下述迭代公式产生,
2)1(
2)2(
)1(
)1()2(
)1(
)1(
)1()2(
)2(
1
)(
)(
)()()]([
)]()([)]([
XF
XF
XFXFXF
XFXFXF
T
T
因而,
0][ )1()2(?ASS T因为 （ A是二次函数的 Hessian 矩阵 ）
CXBAXXXF TT 21)(
BAXXF )(
二次函数其梯度为故有 0])([ )1(
1)1(1)2( ASSXF T?
)1()1(
)1()2(
1 ][
)]([
ASS
ASXF
T
T?
)1()1()1()2( SXX
)1()1()1()2()1()2( )()()( ASXXAXFXF故有又 0)(][ )2()1( XFS T （ 正交 ）
刘 惟 信 用 数学归纳法对此法的共轭性作出过证明 。
2009-7-27 23
K <
n
给定 X0,n,ε
K=1,X(K)=X0
S(K)= -▽ F(X(K))
从 X(K)始,沿 S(K)进行一维搜索得 X(K+1)
K=K+1
是是否否计算
)(),( )1()1( KK XFXF
)( )1( KXF
结束
)( )1(
)1(
K
K
XFF
XX
)1(0 KXX
)()1()1(
2
)(
)1(
)(
)
)(
)(
(
K
K
KK
K
K
K
SXFS
XF
XF
重置负梯度方向三,迭代步骤
2009-7-27 24
四,共轭梯度法的特点
1.为共轭方向法,具有二次收敛性 ;
2.算法简单,编程容易,存储量小 ;
3.需用到一阶导数,
2009-7-27 25
5.DFP变尺度法
)( )()()()1( kkkk XFEXX
)()]([ )(1)()()()1( kkkkk XFXHXX
能否克服各自的缺点，综合发挥其优点？
2）阻尼牛顿法
1）梯度法一）问题的提出由 Davidan,Fletcher,Powell共同提出。
* 简单，开始时目标函数值下降较快，但越来越慢。
* 目标函数值在最优点附近时收敛快，但要用到二阶导数和矩阵求逆。
2009-7-27 26
二）基本思路
)( )()()()1( kkkkk XFAXX
1 kk HA2） 迭代终了,具有二阶收敛性 。
EAk k,0*1） 当 和梯度法一样，便于突破函数的非二次性 ；
式中,1.Ak —构造矩阵 （在迭代中产生，不用求导和作矩阵求逆）
迭代公式：
)( )()()()1( kkkk XFEXX
)()]([ )(1)()()()1( kkkkk XFXHXX
)( )()( kkk XFAS ---拟牛顿方向2.
2009-7-27 27
三）构造矩阵应满足的条件
kA
1） 应为正定对称矩阵；
kA
(1) 应为对称矩阵 ；
E和 均为对称矩阵1?KH
kA
(2) 应为正定矩阵 ；
因为 应使 为函数下降方向,即 与 的夹角应小于 900:
kA )(kS )(kS kg?
0][ )( kTk Sg
0][][ kkTk gAg
0][?kkTk gAg 二次型正定
2009-7-27 28
kA 1?kH
2） 能逼近以近似二次函数的梯度作为下一迭代点处的梯度,
)()()()( ][21][)()( kkTkkTkk XHXXgXFX
其梯度
)( kkk XHgg
)(1 kkkk XHgg
kkkkkk gHggHX 111)( )(
1?kA 1?kH用 代替,得
kkk gAX1)(
拟牛顿条件
k? ky
2009-7-27 29
1?kA
四,的构造方法
kkk AAA1
用递推方法构造
kkkkkk gAAgAX )(1)(
于是有
kA?
关键是确定校正矩阵
kkkkk gAXgA )(
(1)
再令 T
kkkkkTkkkk gAgAXXA ][][ )()(
(2)
代入 (1),
kkkkkTkkkkkTkkk gAXgAggAgXX )()()( ][][
,1][ )( kTkk gX,1 kkTkk gAg两边对比得,
),]/ ( [1 )( kTkk gX )./(1 kkTkk gAg
回代到 (2)得,
kk
T
k
T
kkkk
k
Tk
Tkk
k gAg
gAgA
gX
XXA
][
][
][
)(
)()( (3)
待定常数可保证 AK的对称性
963
642
321
321
3
2
1
2009-7-27 30
五,迭代步骤
,,0 nX给定
)(),(,00 XFgXFFXX
1?k
gASEA,
XSX 搜索得极小点沿始从?,
gg,计算
g?
是是否否
nk?
)(,
XFF X输出结束
XX
1kk
XXgg
gASAAA
A
gggXXX
,
,
...
,,
计算 因计算机的舍入误差,构造矩阵的正定性可能遭到破坏,
故作 n次后重置单位矩阵 。
2009-7-27 31
6.坐标轮换法
T
n
T
T
e
e
e
]1...00[
...
]0...10[
]0...01[
2
1
1)几何描述 (以二维问题为例）
二）迭代步骤依次沿个 n个正交坐标轴的方向搜索：
一）搜索方向
2009-7-27 32
2) 坐标轮换法流程图从 出发沿 方向进行一维搜索得,
1?iX ie?i?
iiii eXX1 )( iXFF?
1?i
ni?
给 定?,,0 nX
0XX n
1ii
FF
XX n
结束
10
kk
XX n
1?k
是否否是
2009-7-27 33
三 ) 算法特点如,(1)等值线为椭圆,且长短轴分别平行于坐标轴时 --高效
1x
2x
o
(2)等值线为如图脊线时 --无效
1x
2x
o
(3)一般情况 --低效
1） 编程简单,容易掌握；
2） 收敛速度通常较低 （ 其有效性取决于目标函数的性态 ）,仅适于低维的情况 。
2009-7-27 34
7,鲍威尔方法
2x
3x
1x
o
0X
1e?
2e?
3e?
3）若目标函数为正定二次函数,n轮结束后即可到达最优点。
2）每轮迭代产生一个新方向取代原来的第一方向,n
轮迭代后可产生 n个彼此共轭的方向 ；
nX
1）开始采用坐标轴方向 ；
一） Powell基本算法
2009-7-27 35
二） Powell法 （ Powell修正算法）
2x
3x
1x
o
0X
2e?
3e?1X
应用 Powell基本算法时，若有一次搜索的最优步长为 0，
且该方向被换掉，则该算法失效。
1）问题的提出
2009-7-27 36
2)Powell对基本算法的改进在获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,
在 n+1个方向中留下最接近共轭的 n个方向,
* ① 根据 Powell条件判定是否需换方向；
② 如需换向，则换掉函数值下降量最大的方向,
2009-7-27 37
三） Powell条件
),( )(01 kXFF?
)(0)()( 1 2 kknkn XXX
),( )(2 knXFF? )( )( 13 knXFF
}),()(ma x {,.,,,.,,2,1)()( 1 nmikiki XFXF
)()( )()( 1 kmkm XFXF
2
31
2
21321
13
)(
2
1))(2( FFFFFFF
FF
如下述两不等式同时成立则需换向，否则仍取原方向组。
计算,（映射计算）
)( 1knX?
)(knX
)(1kX)(0kX
P Q
大的方向的标号为目标函数值下降量最式中 m,
2009-7-27 38
四）更换方向的步骤
nmmiii SS,.,,,1,1,
)(0)(1 kknn XXS
3）更换方向：
2）构造新方向：
1）找出该轮迭代中目标函数值下降量最大的方向 （ 假定其标号为 m） ；
2009-7-27 39
Powell
修正算法
F3<F
1
Q<
D
Si=Si+1
i=m,m+1,… n
i =
n
输出 X*=Xn
F*=F（ X*）
结束给定 X0,Si=eii=1,2,…n,ε
K=0
i=1
自 Xi-1始,沿 Si方向搜索得一维最优点 Xi
i=i+1
Xn+1=2Xn-X0
Sn+1=Xn-X0
自 Xn始,沿 Sn+1方向搜索得一维最优点 X*
K=K+1
F1=F(X0),F2=F(Xn),F3=F(Xn+1)
求 Δ 及方向标号 m
Y
Y
Y
Y
N
N
N
X0=X*
N
Xn-X0 ≤ ε
2009-7-27 40
无约束优化方法的评价准则一）可靠性在满足合理精度要求的情况下、在一定时间内对各类问题解题的成功率 。 （梯度法较好，牛顿法较差，
其余居中）
二）有效性（收敛性）
在同一题目、同样精度、同一初始点情况下比较 。
（具有二次收敛性的方法较好）
三）简便性比较准备工作量和存储单元。（ 用到二阶导数及矩阵求逆的方法较差 ）
第四章 无约束优化方法
6,坐标轮换法 ;
7,鲍威尔法 ;
4,梯度法及共轭梯度法 ;
5,DFP变尺度法,
1,概述
2,最速下降法
3,牛顿型方法
2009-7-27 2
1.概述
有些实际问题，其数学模型本身就是一个无约束优化问题可以按无约束问题来处理
通过熟悉无约束优化问题的解法可以为研究约束优化问题打下良好的基础
约束优化问题的求解可以通过一系列无约束优化方法来达到
2009-7-27 3
无约束优化问题
对于无约束优化问题的求解，可以直接就用第三章讲述的极值条件来确定极值点位置。这就是把求函数极值的问题变成求解方程
数值求解
各种无约束优化方法的区别就在于确定其搜索方向的方法不同。
T
12[,,,]
( ) m i n
nx x x x
fx
=
L
使
0f?
1 ( 0,1,2,)k k kkx x d ka+ = + = L
2009-7-27 4
无约束优化方法的分类
一类是利用目标函数的一阶或二阶导数的无约束优化方法
最速下降法、共轭梯度法、
牛顿法及变尺度法等。
另一类是只利用目标函数值的无约束优化方法
坐标轮换法，单形替换法及鲍威尔（ Powell）法等。
开始给定 x d 的初始值计算 a*
使
( )fa+xd
最小
a *?x x d
满足收敛条件？
结束给定 新的 d
图 10 无约束极小化算法的粗框图是 否
2009-7-27 5
2,最速下降法
目标函数值 f(x) →min
从某点 x出发，其搜索方向 dk取该点的 负梯度方向 (最速下降方向 ),使函数值在该点附近的范围内下降最快
由于最速下降法是以负梯度方向作为搜索方向，所以最速下降法又称为 梯度法
问题转化为求最佳步长因子的一维搜索问题
( )1 0,1,2,k k k kx x a f x k+ = -? L
( ) ( )( ) ( )( ) ( )1 m i n m i nk k k k k kaaf x f x a f x f x a f x aj+ = -? -?
2009-7-27 6
根据一元函数极值的必要条件和多元复合函数求导公式，得
相邻两点的函数梯度相互垂直
局部最快，整体上并不是最快
( ) ( )[ ]{ } ( )T 0k k k ka f x a f x f xj ￠ = -? 蜒 =
( )[ ] ( )T1 0kkf x f x+蜒 =
( )1k k k kx x a f x+ = -
T1 0kkdd+ =
x 1
x 2
O
图 最速下降法的搜索路径
2009-7-27 7
例题
1,求目标函数 f(x)=x12+25x22的极小值取初始点 x0=[2,2]T
初始点处函数值及梯度分别为
( )0 104fx =
( ) 10
2
42
50 100
x
fx x 轾轾 犏犏?= 犏犏臌 臌沿负梯度方向搜索
( ) 01 0 000
0
2 4 2 4
2 1 0 0 2 1 0 0
a
x x a f x a a
-轾 轾 轾犏 犏 犏
= -? - =犏 犏 犏 -
臌 臌 臌
2009-7-27 8
a0为一维搜索最佳步长，应满足极值必要条件
( ) ( )[ ]
( ) ( ){ } ( )
1 0 0
22
00
m i n
m i n 2 4 25 2 100 m i n
a
aa
f x f x a f x
a a aj
= -
= - + - =
( ) ( ) ( )0 8 2 4 5 0 0 0 2 1 0 0 0a a aj ￠ = - - - - =
可算出一维搜索最佳步长
0 626 0,0 2 0 0 3 0 7 231252a ==
以及第一次迭代设计点的位置和函数值
01
20
1,9 1 9 8 7 724
2 1 0 0 0,3 0 7 1 7 8 5 1 0
a
x a -
轾-轾 犏犏
== 犏犏 - -
犏臌 臌从而完成了最速下降法的第一次迭代求最佳步长
2009-7-27 9
继续下去，经过 10次迭代后，可以得到最优解
该问题的目标函数 f(x)的等值线为一族椭圆，
迭代点从 x0走的是一段锯齿路线。
0
0x
* 轾犏= 犏臌
( ) 0fx* =
x0
x1
x2
2009-7-27 10
最速下降算法的程序框图给定 x0,?
k=0
dk=?f(xk)
ak=minf(xk+akdk)
xk+1=xk+akdk k=k+1
‖ xk+1－ xk‖ ＜?x*=xk+1
结束是 否
2009-7-27 11
最速下降法的特点
最速下降法是一个求解极值问题的古老算法
– 早在 1947年就已由柯西 (Cauchy)提出
– 直观、简单
要计算函数的梯度，故属于解析法，即间接求解法
采用了函数的负梯度方向作为下一步的搜索方向，所以收敛速度较慢，越是接近极值点收敛越慢，这是它的主要缺点
应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其他无约束优化方法配合使用
一些更有效的方法都是在对它改进后，或在它的启发下获得的，
因此最速下降法仍是许多有约束和无约束优化方法的基础。
2009-7-27 12
3,牛顿型方法
一维搜索的牛顿方法的迭代公式
对于多元函数 f(x)，设 xk为其极小点 x*附近的一个近似点，在 xk处进行泰勒展开，保留到二次项
( )
( )1 0,1,2,
kkk
k
fxx x k
fx+
￠= - =
ⅱ L
( ) ( ) ( ) ( )[ ] ( ) ( ) ( ) ( )T T 212k k k k k kf x x f x f x x x x x f x x xj? +? + -?
极值必要条件
( )1 0kxj +?
( ) ( ) ( )2 1 0k k k kf x f x x x+ =
( )[ ] ( )121k k k kx x f x f x-+ =- 蜒 二次收敛
2009-7-27 13
牛顿法例题
用牛顿法求 f(x1,x2)=x12+25x22的极小值取初始点为 x0=[2,2]T
( )
0
10
2
42
50 100x
x
fx x 轾轾 犏犏?= 犏犏臌 臌
( )20 200 50fx 轾犏? 犏臌
( )[ ] 120
1 0
2
10
50
fx -
轾犏犏? 犏犏犏臌代入牛顿法迭代公式
( )[ ] ( )11 0 2 0 0
1 02 4 0
2
1 02 1000
50
x x f x f x-
轾犏轾轾轾犏犏犏 犏
=- 蜒 = - =犏 犏臌犏臌臌 犏臌
2009-7-27 14
阻尼牛顿法
从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念
对于非二次函数，如果采用上述牛顿迭代公式，
有时会使函数值上升，即出现 f(xk+1)>f(xk)的现象
需对上述牛顿法进行改进，引入数学规划法的搜索概念，提出所谓“阻尼牛顿法”
2009-7-27 15
( )[ ] ( )12k k kd f x f x-=- 蜒将 看 作 是 搜 索 方 向,称 其 为 牛 顿 方 向
( )[ ] ( )121,0,1,2,k k k k k k k kx x a d x a f x f x k-+ = - = - 蜒 = L
阻尼牛顿法的迭代公式为
ak— 沿牛顿方向的一维最佳搜索步长，可称为 阻尼因子
ak可通过一维搜索的极小化过程求得
( ) ( ) ( )1 m i nk k k k k kaf x f x a d f x a d+ = + = +
ak 取为固定值 1时，阻尼牛顿法就成为了牛顿法
每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象
保持了牛顿法二次收敛的特性，而对初始点的选取并没有苛刻的要求
原来的牛顿法就相当于阻尼牛顿法的步长因子取成固定值 1的情况
2009-7-27 16
阻尼牛顿法的计算步骤
(1)给定初始点 x0，收敛精度?，置 k=0
(2)计算?f(xk),?2f(xk),[?2f(xk)]-1和 dk=-[?2f(xk)]-1
×?f(xk)
(3)求 xk+1＝ xk+akdk，其中 ak为沿 dk进行一维搜索的最佳步长
(4)检查收敛精度。若 ‖ xk+1－ xk‖ ≤?，则 x*=xk+1，否则，
置 k=k+1，返回到 2继续进行搜索。
2009-7-27 17
阻尼牛顿法的程序框图给定 x0,?
k=0
dk=[?2f(xk)]-1?f(xk)
ak=minf(xk+akdk)
xk+1=xk+akdk
‖ xk+1-xk‖ ≤?
x*=xk+1
结束
k=k+1
2009-7-27 18
牛顿型方法的特点
牛顿法和阻尼牛顿法统称为牛顿型方法
主要缺点
– 每次迭代都要计算函数的二阶导数矩阵，并对该矩阵求逆。这样工作量很大。特别是矩阵求逆，当维数高时工作量更大
– 从计算机存储方面考虑，牛顿型方法所需的存储量也是很大的
最速下降法的收敛速度比牛顿法慢，而牛顿法又存在上述缺点。针对这些缺点，近年来人们研究了很多改进的算法
– 如针对最速下降法 (梯度法 ) 提出只用梯度信息，但比最速下降法收敛速度快的共轭梯度法；
– 针对牛顿法提出变尺度法等
2009-7-27 19
4.梯度法及共轭梯度法一）梯度方向
*可取最优步长或下降步长二）基本思想梯度方向是目标函数上升最快的方向,负梯度方向则是最速下降方向；
)( )()()()1( kkkk XFXX2） 迭代公式
1） 沿 负梯度方向搜索,)()()( )( kkk gXFS
kg
三）终止判别条件梯度法
2009-7-27 20
给定 X0,ε
K=0,X（ K） =X0
K=K+1
X(k)=X△
X*= X（ K）
F*=F（ X*）
结 束
N
Y
计算
)()(,kk gg
)(kg
从 出发,沿 搜索得
)(kX )(kg?
)()()( kkk gXX
*,最速下降性,只是迭代点邻域的局部性质。从全局看，并非最速下降方向。
四,迭代步骤
2009-7-27 21
共轭梯度法
)1(1)2()2( )( SXFS第二方向：
)( )1()1( XFS第一方向：
二,共轭方向的构成
*利于突破函数的非二次性 ;
每轮搜索方向为一组共轭方向,但第一方向为负梯度方向,
一,基本思路
)1()1()1()2( SXX
* 可表示为两个负梯度方向的线性组合 。)2(S
)1(X
)2(S
)2(X
)1(S
)( )2(XF
2009-7-27 22
2)(
2)1(
)(
)(
k
k
k XF
XF
)()1()1( )( kkkk SXFS,
以后新方向均按下述迭代公式产生,
2)1(
2)2(
)1(
)1()2(
)1(
)1(
)1()2(
)2(
1
)(
)(
)()()]([
)]()([)]([
XF
XF
XFXFXF
XFXFXF
T
T
因而,
0][ )1()2(?ASS T因为 （ A是二次函数的 Hessian 矩阵 ）
CXBAXXXF TT 21)(
BAXXF )(
二次函数其梯度为故有 0])([ )1(
1)1(1)2( ASSXF T?
)1()1(
)1()2(
1 ][
)]([
ASS
ASXF
T
T?
)1()1()1()2( SXX
)1()1()1()2()1()2( )()()( ASXXAXFXF故有又 0)(][ )2()1( XFS T （ 正交 ）
刘 惟 信 用 数学归纳法对此法的共轭性作出过证明 。
2009-7-27 23
K <
n
给定 X0,n,ε
K=1,X(K)=X0
S(K)= -▽ F(X(K))
从 X(K)始,沿 S(K)进行一维搜索得 X(K+1)
K=K+1
是是否否计算
)(),( )1()1( KK XFXF
)( )1( KXF
结束
)( )1(
)1(
K
K
XFF
XX
)1(0 KXX
)()1()1(
2
)(
)1(
)(
)
)(
)(
(
K
K
KK
K
K
K
SXFS
XF
XF
重置负梯度方向三,迭代步骤
2009-7-27 24
四,共轭梯度法的特点
1.为共轭方向法,具有二次收敛性 ;
2.算法简单,编程容易,存储量小 ;
3.需用到一阶导数,
2009-7-27 25
5.DFP变尺度法
)( )()()()1( kkkk XFEXX
)()]([ )(1)()()()1( kkkkk XFXHXX
能否克服各自的缺点，综合发挥其优点？
2）阻尼牛顿法
1）梯度法一）问题的提出由 Davidan,Fletcher,Powell共同提出。
* 简单，开始时目标函数值下降较快，但越来越慢。
* 目标函数值在最优点附近时收敛快，但要用到二阶导数和矩阵求逆。
2009-7-27 26
二）基本思路
)( )()()()1( kkkkk XFAXX
1 kk HA2） 迭代终了,具有二阶收敛性 。
EAk k,0*1） 当 和梯度法一样，便于突破函数的非二次性 ；
式中,1.Ak —构造矩阵 （在迭代中产生，不用求导和作矩阵求逆）
迭代公式：
)( )()()()1( kkkk XFEXX
)()]([ )(1)()()()1( kkkkk XFXHXX
)( )()( kkk XFAS ---拟牛顿方向2.
2009-7-27 27
三）构造矩阵应满足的条件
kA
1） 应为正定对称矩阵；
kA
(1) 应为对称矩阵 ；
E和 均为对称矩阵1?KH
kA
(2) 应为正定矩阵 ；
因为 应使 为函数下降方向,即 与 的夹角应小于 900:
kA )(kS )(kS kg?
0][ )( kTk Sg
0][][ kkTk gAg
0][?kkTk gAg 二次型正定
2009-7-27 28
kA 1?kH
2） 能逼近以近似二次函数的梯度作为下一迭代点处的梯度,
)()()()( ][21][)()( kkTkkTkk XHXXgXFX
其梯度
)( kkk XHgg
)(1 kkkk XHgg
kkkkkk gHggHX 111)( )(
1?kA 1?kH用 代替,得
kkk gAX1)(
拟牛顿条件
k? ky
2009-7-27 29
1?kA
四,的构造方法
kkk AAA1
用递推方法构造
kkkkkk gAAgAX )(1)(
于是有
kA?
关键是确定校正矩阵
kkkkk gAXgA )(
(1)
再令 T
kkkkkTkkkk gAgAXXA ][][ )()(
(2)
代入 (1),
kkkkkTkkkkkTkkk gAXgAggAgXX )()()( ][][
,1][ )( kTkk gX,1 kkTkk gAg两边对比得,
),]/ ( [1 )( kTkk gX )./(1 kkTkk gAg
回代到 (2)得,
kk
T
k
T
kkkk
k
Tk
Tkk
k gAg
gAgA
gX
XXA
][
][
][
)(
)()( (3)
待定常数可保证 AK的对称性
963
642
321
321
3
2
1
2009-7-27 30
五,迭代步骤
,,0 nX给定
)(),(,00 XFgXFFXX
1?k
gASEA,
XSX 搜索得极小点沿始从?,
gg,计算
g?
是是否否
nk?
)(,
XFF X输出结束
XX
1kk
XXgg
gASAAA
A
gggXXX
,
,
...
,,
计算 因计算机的舍入误差,构造矩阵的正定性可能遭到破坏,
故作 n次后重置单位矩阵 。
2009-7-27 31
6.坐标轮换法
T
n
T
T
e
e
e
]1...00[
...
]0...10[
]0...01[
2
1
1)几何描述 (以二维问题为例）
二）迭代步骤依次沿个 n个正交坐标轴的方向搜索：
一）搜索方向
2009-7-27 32
2) 坐标轮换法流程图从 出发沿 方向进行一维搜索得,
1?iX ie?i?
iiii eXX1 )( iXFF?
1?i
ni?
给 定?,,0 nX
0XX n
1ii
FF
XX n
结束
10
kk
XX n
1?k
是否否是
2009-7-27 33
三 ) 算法特点如,(1)等值线为椭圆,且长短轴分别平行于坐标轴时 --高效
1x
2x
o
(2)等值线为如图脊线时 --无效
1x
2x
o
(3)一般情况 --低效
1） 编程简单,容易掌握；
2） 收敛速度通常较低 （ 其有效性取决于目标函数的性态 ）,仅适于低维的情况 。
2009-7-27 34
7,鲍威尔方法
2x
3x
1x
o
0X
1e?
2e?
3e?
3）若目标函数为正定二次函数,n轮结束后即可到达最优点。
2）每轮迭代产生一个新方向取代原来的第一方向,n
轮迭代后可产生 n个彼此共轭的方向 ；
nX
1）开始采用坐标轴方向 ；
一） Powell基本算法
2009-7-27 35
二） Powell法 （ Powell修正算法）
2x
3x
1x
o
0X
2e?
3e?1X
应用 Powell基本算法时，若有一次搜索的最优步长为 0，
且该方向被换掉，则该算法失效。
1）问题的提出
2009-7-27 36
2)Powell对基本算法的改进在获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,
在 n+1个方向中留下最接近共轭的 n个方向,
* ① 根据 Powell条件判定是否需换方向；
② 如需换向，则换掉函数值下降量最大的方向,
2009-7-27 37
三） Powell条件
),( )(01 kXFF?
)(0)()( 1 2 kknkn XXX
),( )(2 knXFF? )( )( 13 knXFF
}),()(ma x {,.,,,.,,2,1)()( 1 nmikiki XFXF
)()( )()( 1 kmkm XFXF
2
31
2
21321
13
)(
2
1))(2( FFFFFFF
FF
如下述两不等式同时成立则需换向，否则仍取原方向组。
计算,（映射计算）
)( 1knX?
)(knX
)(1kX)(0kX
P Q
大的方向的标号为目标函数值下降量最式中 m,
2009-7-27 38
四）更换方向的步骤
nmmiii SS,.,,,1,1,
)(0)(1 kknn XXS
3）更换方向：
2）构造新方向：
1）找出该轮迭代中目标函数值下降量最大的方向 （ 假定其标号为 m） ；
2009-7-27 39
Powell
修正算法
F3<F
1
Q<
D
Si=Si+1
i=m,m+1,… n
i =
n
输出 X*=Xn
F*=F（ X*）
结束给定 X0,Si=eii=1,2,…n,ε
K=0
i=1
自 Xi-1始,沿 Si方向搜索得一维最优点 Xi
i=i+1
Xn+1=2Xn-X0
Sn+1=Xn-X0
自 Xn始,沿 Sn+1方向搜索得一维最优点 X*
K=K+1
F1=F(X0),F2=F(Xn),F3=F(Xn+1)
求 Δ 及方向标号 m
Y
Y
Y
Y
N
N
N
X0=X*
N
Xn-X0 ≤ ε
2009-7-27 40
无约束优化方法的评价准则一）可靠性在满足合理精度要求的情况下、在一定时间内对各类问题解题的成功率 。 （梯度法较好，牛顿法较差，
其余居中）
二）有效性（收敛性）
在同一题目、同样精度、同一初始点情况下比较 。
（具有二次收敛性的方法较好）
三）简便性比较准备工作量和存储单元。（ 用到二阶导数及矩阵求逆的方法较差 ）
