第四章 无约束优化方法
§ 4-1 最速下降法（梯度法）
§ 4-2 牛顿类方法
§ 4-3 变尺度法
§ 4-4 共轭方向法
§ 4-5 鲍威尔方法
§ 4-6 其它方法（如坐标轮换法、单纯形法）
第 1章所列举的机械优化设计问题,都是在一定的限制条件下追求某一指标为最小,它们都属于约束优化问题 。 工程问题大都如此 。
为什么要研究无约束优化问题?
（ 1） 有些实际问题,其数学模型本身就是一个无约束优化问题 。
（ 2） 通过熟悉它的解法可以为研究约束优化问题打下良好的基础 。
（ 3） 约束优化问题的求解可以通过一系列无约束优化方法来达到 。 所以无约束优化问题的解法是优化设计方法的基本组成部分,也是优化方法的基础 。
（ 4） 对于多维无约束问题来说,古典极值理论中令一阶导数为零,但要求二阶可微,且要判断海赛矩阵为正定才能求得极小点,这种方法有理论意义,
但无实用价值 。 和一维问题一样,若多元函数 F(X)
不可微,亦无法求解 。 但古典极值理论是无约束优化方法发展的基础 。
目前已研究出很多种无约束优化方法，它们的主要不同点在于 构造搜索方向 上的差别。
m i n ( ) nfR?xx
（ 1）间接法 —— 要使用导数，如梯度法、（阻尼）
牛顿法、变尺度法、共轭梯度法等。
（ 2）直接法 —— 不使用导数信息，如坐标轮换法、
鲍威尔法、单纯形法等。
无约束优化问题是：
12[] Tnx x x?x求 n维设计变量
( ) m inf?x使目标函数
1 ( 0,1,2,)k k k
k sk?
xx
搜索方向的构成问题乃是无约束优化方法的关键 。
用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的
（ n ≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。
4-1 梯度法
1 ( 0,1,2,)k k k
k sk?
xx
1 ( ) ( 0,1,2,)k k k
ka f k
x x x
基本思想,函数的负梯度方向是函数值在该点下降最快的方向。将 n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。
()f x搜索方向 s取该点的负梯度方向 (最速下降方向 ),使函数值在该点附近的范围内下降最快 。
为了使目标函数值沿搜索方向 能够获得最大的下降值,其步长因子 应取一维搜索的最佳步长 。 即有
()kf x
k?
1( ) [ ( ) ] m in [ ( ) ]
m in ( )
k k k k k
k a
a
f f a f f a f
x x x x x
根据一元函数极值的必要条件和多元复合函数求导公式，得
'( ) [ ( ) ] ( ) 0Tk k kkf f fx x x
1[ ( ) ] ( ) 0k T kffxx
1( ) 0k T kss
在最速下降法中，
相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，
因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成,之,字形的锯齿现象，而且越接近极小点锯齿越细。
图 4-2 最速下降法的搜索路径方法特点
（ 1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，
然后慢慢逼近局部极小点。
（ 2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。
开始给定结束
0
,?x
()
kk
fdx
1
,m i n ( )
k k k
k
kk
k
f
x x d
xd
1kk
xx
*1 k?
xx
否是
1kk
0k?
sk
0
0
10
2
( ) 10 4
2 4
()
50 100
x
f
x
f
x
x
x
沿负梯度方向进行一维搜索,有
01 0 0
0
0
24()
2 100f
x x x
0? 为一维搜索最佳步长，应满足极值必要条件
1 2 2( ) m i n ( 2 4 ) 2 5 ( 2 1 0 0 ) m i n ( )fx
例 4－ 1 求目标函数 的极小点 。
解 取初始点则初始点处函数值及梯度分别为
0 [ 2,2 ]T?x
2212( ) 2 5f x xx
00'( ) 8 ( 2 4 ) 5 0 0 0 ( 2 1 0 0 ) 0
算出一维搜索最佳步长
0
626 0.0 20 030 72
31 252
第一次迭代设计点位置和函数值
01
2
0
24 1,9 1 9 8 7 7
2 1 0 0 0,3 0 7 1 7 8 5 1 0
x
1( ) 3,6 8 6 1 6 4f?x
继续作下去，经 10次迭代后，得到最优解00 Tx
( ) 0fx
这个问题的目标函数的等值线为一簇椭圆,迭代点从走的是一段锯齿形路线，见图 4-3。
0x
1
图 4-3
将上例中目标函数 引入变换 2212( ) 2 5f x xx
221 2 1 2(,)y y y y
其等值线由椭圆变成一簇同心圆。
仍从 即 出发进行最速下降法寻优。此时：
0 [ 2,2 ]T?x 0 [ 2,1 0 ]T?y
0
0
10
2
( ) 1 0 4
2 4
()
2 20
y
y
y
y
y
沿负梯度方向进行一维搜索：
则函数 f(X)变为：
y1=x1,y2=5x2
1 0 0
0
0
0
0
()
2424
10 2010 20
y y y
β为一维搜索最佳步长，可由极值条件：
1 0 0
22
( ) m in [ ( ) ] m in ( )
( ) ( 2 4 ) ( 10 20 )
y y y
0( ) 0
由
0
26 0,5
52
从而算得一步计算后设计点的位置及其目标函数：
01
0
1
24 0
10 20 0
( ) 0
y
y
经变换后，只需一次迭代，就可找到最优解。
这是因为经过尺度变换：
11
225
yx
yx
等值线由椭圆变成圆。
梯度法的特点
（ 1）理论明确，程序简单，对初始点要求不严格。
（ 2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。
（ 3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈 锯齿 状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。
（ 4）梯度法的收敛速度与目标函数的性质密切相关。
对于等值线 (面 )为同心圆（球）的目标函数，一次搜索即可达到极小点。
4-2 牛顿法及其改进
2
( ) ( ) ( ) ( ) ( )
1
( ) ( ) ( )
2
k k T k
k T k k
f f f
f
x x x x x x
x x x x x
设 为 的极小点1k?x ()? x
1( ) 0kx
基本思想,
在 xk邻域内用一个二次函数 来近似代替原目标函数，并将 的极小点作为对目标函数求优的下一个迭代点 。经多次迭代，使之逼近目标函数 的极小点。
牛顿法是求函数极值的最古老算法之一。
()? x
()? x ()f x
1k?x
()f x
21( ) ( ) ( ) 0k k k kffx x x x
1 2 1[ ( ) ] ( ) ( 0,1,2,)k k k kf f kx x x x
这就是多元函数求极值的牛顿法迭代公式。
对于二次函数,海赛矩阵 H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。
例 4－ 2 求目标函数 的极小点 。
解 取初始点
2212( ) 2 5f x xx
0 [ 2,2 ]T?x1 0 2 0 1 0
1
0
2 4 02
( ) ( )
12 100 0
0
50
ff
x x x x
00x
( ) 0fx
从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升 。
阻尼牛顿法
1 2 1[ ( ) ] ( ) ( 0,1,2,)k k k k k kkks f f kx x x x x
k? 阻尼因子,沿牛顿方向进行一维搜索的最佳步长，由下式求得：
1( ) ( ) m i n ( )k k k k kkkf f s f s
x x x
经过一次迭代即求得极小点函数极小值开始给定结束
0
,?x
21
[ ( ) ] ( )
k k k
ff
d x x
1
,m i n ( )
k k k
k
kk
k
f
x x d
xd
1kk
xx
*1 k?
xx
否是
1kk
0k?
阻尼牛顿法程序框图方法特点
（ 1） 初始点应选在 X*附近，有一定难度；
（ 2） 尽管每次迭代都不会是函数值上升，但不能保证每次下降 ；
（ 3） 若迭代点的海赛矩阵为奇异，则无法求逆矩阵，
不能构造牛顿法方向；
（ 4） 不仅要计算梯度，还要求海赛矩阵及其逆矩阵，
计算量和存储量大。此外，对于二阶不可微的 F(X)也不适用。
虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。
1 ( 0,1,2,)k k kk skxx
1 ( ) ( 0,1,2,)k k kka f kx x x
1 2 1[ ( ) ] ( ) ( 0,1,2,)k k k kf f kx x x x
1 2 1[ ( ) ] ( ) ( 0,1,2,)k k k kk f f kx x x x
一般迭代式：
梯度法：
牛顿法：
阻尼牛顿法：
梯度法与牛顿法：
1 ()k k k kk fx x A x
4-3 变尺度法
DFP变尺度法首先有戴维顿（ Davidon）与 1959
年提出，又于 1963年由弗莱彻（ Fletcher）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。
DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。
1,基本思想变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。
例如在用最速下降法求 的极小 2212( ) 2 5f x xx
值时,需要进行 10次迭代才能达到极小点 [0,0 ]Tx?
如作变换 y1=x1,y2=5x2
把 的尺度放大 5倍，则目标函数等值线由一簇椭圆变成一簇同心圆。
x2
22
1 2 1 2(,)y y y y
消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。
梯度法构造简单，只用到一阶偏导数，计算量小，
初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近 X*时，即使对二次正定函数收敛也非常慢。
牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，
但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。
能不能将两种算法的优点综合起来，扬长避短？
1 ()k k k kk fx x A x
Ak 是需要构造 n× n的一个对称方阵,
如 Ak=I,则得到梯度法 ；
21[ ( ) ]kkfAx则得到阻尼牛顿法 ；如当矩阵 Ak 不断地迭代而能很好地逼近 21[ ( ) ]kf x
时，就可以不再需要计算二阶导数。
变尺度法的关键在于尺度矩阵 Ak的产生 。
对于二次函数,
1()
2
TTfx x G x b x c
x Qx进行尺度变换在新的坐标系中，函数 f(x)的二次项变为：
11
22
T T T?x G x x Q G Q x
目的：减少二次项的偏心如 G是正定，则总存在矩阵 Q，使得：
T?Q G Q I
用矩阵 Q-1右乘等式两边，得：
用矩阵 Q左乘等式两边，得：
1TQ G Q
T?Q Q G I
所以 1TQ Q G
上式说明：二次函数矩阵 G的逆阵，可以通过尺度变换矩阵 Q来求得。
1 2 1[ ( ) ] ( ) ( 0,1,2,)k k k kk f f kx x x x
牛顿迭代公式：
1 ( ) ( 0,1,2,)k k T kk Q Q f kx x x
记,T A?QQ
搜索方向：
1 ( ) ( 0,1,2,)k k ks f kAx
迭代公式：
1 ( ) ( 0,1,2,)k k k k
k fk?
x x A x
A 称为变尺度矩阵
2212( ) 2 5f x xx在例 4－ 2中
122
1 2 1 2
2
2011( ) 2 5
0 5 022
Txf x x x x
x
x x G x
20
0 5 0
G
如取
1
0
2
1
0
52
Q
11
00
2 0 1 022
1 0 50 1 0 1
00
5 2 5 2
T
Q G Q I
求得,1
11 1
00 0
22 2
111
000
505 2 5 2
T?
G Q Q
2,构造尺度矩阵 Ak
从初始矩阵 A0=I(单位矩阵 )开始，通过对公式
1k k kA A A
因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度 。
1） DFP法（ Davidon-Fletcher-Powell)
[ ] [ ]
[ ] [ ]
Tk k k k k T k
k
k T k k T k k
x x A g g AA
x g g A g
11
1
( ) ( )k k k k k
k k k
ff
g g g x x
x x x式中中修正矩阵 的不断修正，在迭代中逐步逼近于k?A
1 ()k?Gx。
2） BFGS算法 (Broyden-Fletcher-Gold frob-
Shanno)
DFP算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不稳定。 BFGS算法对于维数较高问题具有更好的稳定性。
1 [ ] [ ]
{ [ ]
[ ] [ ]
[ ] [ ] }
k k T k T k k
k k k T
k T k k T k
kk k T k k T
x x g A g
A x x
x g x g
A g x x g A
开始给定结束
0
,?x
00
0
()f
gx
AI
1
,m i n ( )
k k k
k
kk
k
f
x x d
xd
1kk
xx
*1 k?
xx
否是
1kk
kn?
11
1
11
()
kk
k k k
k k k
f
gx
g g g
x x x
11k k k
A A A
01 k?
xx
0k?
k k k
d A g
是否例 4-3,用 DFP算法求下列问题的极值：
221 2 1 2 1 1 2(,) 2 4 2f x x x x x x x
解,1）取初始点,为了按 DFP法构造第一次搜寻方向 d0，需计算初始点处的梯度
0 [1 1]T?x
0
1200
21
2 2 4 4()
42 2
xxf
xx
x
gx
取初始变尺度矩阵为单位矩阵 A0=I，则第一次搜寻方向为
0 0 0 1 0 4 4
0 1 2 2
d A g
沿 d0方向进行一维搜索,得
01 0 0
00
0
1414
1212
x x d
为一维搜索最佳步长,应满足0?
1 0 0 2( ) m i n ( ) m i n ( 4 0 2 0 3 )ff
x x d
得,
0 0,2 5
1 2
0,5
x,
2） 再按 DFP法构造点 x1处的搜寻方向 d1,需计算
1
121
21
2 2 4 1
42 2
xx
xx
x
g
0 1 0 1 4 3
2 2 4
g g g
0 1 0 2 1 1
0,5 1 0,5
x x x
代入校正公式
0 0 0 0 0 0
0
0 0 0 0 0
[ ] [ ]
[ ] [ ]
T T
TT
x x A g g AA
x g g A g
13
1 0,5 3 4
0,5 4
33
1 0,5 3 4
44
=
1 0 0A A A
21 19
1 0 1 0,5 9 1211 25 50
0 1 0,5 0,25 12 16 19 415 25
50 10 0
=
第二次搜寻方向为 1 1 1
8
6
6
5
d A g
再沿 d1进行一维搜索,得
1
2 1 1
1
1
8
2
5
6
0,5
5
x x d
为一维搜索最佳步长,应满足1?
2 1 1 28 1 1( ) m in ( ) m in ( 4 )
52ffx x d
1
5
4
2 4
2
x,得
3） 判断 x2是否为极值点梯度,
2
122
21
2 2 4 0
()
42 0
xx
f
xx
x
x
海赛矩阵,22 22
()
24
f
x
梯度为零向量,海赛矩阵正定。可见点满足极值充要条件，因此为极小点。
*2 42 Txx
*( ) 8fx
4-4 共轭方向法
1.共 轭方向：
设 G为 n× n阶实对称正定矩阵，如果有两个 n
维向量 d0和 d1满足,则称向量 d0与 d1
关于矩阵 G共 轭。
01( ) 0T?d G d
当 G为单位矩阵时,01( ) 0T?dd
假设目标函数 f(x) 在极值点附近的二次近似函数为
1()
2
TfTx x G x b x c
对二维情况任选取初始点 x0沿某个下降方向 d0作一维搜索,得 x1
1 0 00x x d
因为 是沿 d0方向搜索的最佳步长,即在点 x1
处函数 f（ x） 沿方向 d0的方向导数为零 。 考虑到点
x1处方向导数与梯度之间的关系,故有
0?
1
10
0 [ ( ) ] 0
Tf f
x xdd
如果按最速下降法，选择负梯度方向 为搜索方向，则将发生锯齿现象 。
1()f x
取下一次的迭代搜索方向 d1直指极小点 x*。
α0d0x 0 x1
x*
1
α1d1
1()f x d
1
如果能够选定这样的搜索方向,那么对于二元二次函数只需顺次进行 d0,d1两次直线搜索就可以求到极小点 x*,即有
111x x d
那么这样的 d1方向应该满足什么条件呢?
对于前述的二次函数,1() 2 TfTx x G x b x c
当 时，1xx 1 0
x*是 f(x)极小点，应满足极值必要条件，故有
( ) 0fx Gx b
1 1 1 111( ) ( ) ( )ffx G x d b x G d 0
将等式两边同时左乘 得,0()Td 01( ) 0T?d G d
11()fx G x b有
01( ) 0T?d G d
就是使 d1直指极小点 x*,d1所必须满足的条件 。
两个向量 d0和 d1称为 G的共轭向量,或称 d0和 d1
对 G是共轭方向 。
2.共轭方向的性质性质 1 若非零向量系 d0,d1,d2,…,dm-1是对 G共轭,
则这 m个向量是线性无关的 。
性质 2 在 n维空间中互相共轭的非零向量的个数不超过 n。
性质 3 从任意初始点出发，顺次沿 n个 G的共轭方向 d0,d1,d2,…,进行一维搜索，最多经过 n次迭代就可以找到的二次函数 f(x)极小点。
0 2 1( ) ( ) 0T fd x d
开始给定结束
00
,,?xd
1
,m i n ( )
k k k
k
kk
k
f
x x d
xd
1kk
xx
*1 k?
xx
否是
1kk
0k?
提供新的共轭方向关键：新的共 轭方向 确定在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。
3.共轭梯度法
共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。
从 xk出发，沿负梯度方向作一维搜索,
1 ( 0,1,2,)k k kk kx x d
()kkfdx
设与 dk共 轭的下一个方向 dk+1由 dk和点 xk+1的负梯度的线形组合构成，即：
11 ()k k kkfd x d
21( ) ( ) 0k T kfd x d共轭条件：
则：
21[ ( ) ] ( ) [ ( ) ] 0k T k kkf f fx x x d
解得,21
2
[ ( ) ] ( ) ( )
[ ( ) ] ( ) ( )
k T k k
k k T k k
f f f
f f f?
x x xx x x
令 1() 2 TfTx x G x b x c为函数的泰勒二次展开式
()kkfx G x b则
11()kkfx G x b
上两式相减，并代入 1k k kkx x d
1( ) ( )k k kk ffG d x x
1( ) ( )k k kk ffG d x x将式
11 ()k k kkfd x d与式 两边相乘，并应用 共轭条件得,11[ ( ) ( ) ] [ ( ) ( ) ] 0k k k kkf f f fx x x x
21
11
2
()[ ( ) ] ( )
[ ( ) ] ( ) ()
kk T k
k k T k k
fff
ff f
xxx
xx x
因此
11 ()k k kkfd x d21
2
()
()
k
k k
f
f
x
x
1 ( 0,1,2,)k k kk kx x d
221 2 1 1 2( ) 2 4 2f x x x x xx,已知初始点 [1,1]T
例题 4-4 求下列问题的极值
解,1） 第一次沿负梯度方向搜寻
计算初始点处的梯度
0
120
21
2 2 4 4()
42 2
xxf
xx
x
x
01 0 0
00
0
1414
1212
x x d
为一维搜索最佳步长,应满足
1 0 0 2( ) m i n ( ) m i n ( 4 0 2 0 3 )ff
x x d
迭代精度 。0,0 0 1
得,
0 0,2 5
1 2
0,5
x
2）第二次迭代,21
20 0
() 5
0,2 5
20()
f
f
x
x
1 1()
2f
x
1 1 0
0
2()
1,5f?
d x d
2 1 1 2 2 2 2
0,5 1,5 0,5 1,5
x x d
代入目标函数
22( ) ( 2 2 ) 2 ( 0,5 1,5 )
2 ( 2 2 ) ( 0,5 1,5 ) 4 ( 2 2 ) ( )
fx
得 1
因 2( ) 0fx
收敛。
( ) 0由
2 2 240,( ) 8,( )
20ff
x x x
从而有：
4-5 鲍威尔方法鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。
1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。
1()
2
TfTx x G x b x c对函数：
基本思想,在不用导数的前提下，在迭代中逐次构造
G的共轭方向。
1.共轭方向的生成
j
j
k
k
k
d
d
dj
g
gk+1
x xk+1
设 xk,xk+1为从不同点出发，沿同一方向
dj进行一维搜索而到的两个极小点。
梯度和等值面相垂直的性质,dj和 xk,xk+1两点处的梯度 gk,gk+1之间存在关系,
1( ) 0,( ) 0j T k j T kd g d g
另一方面,对于上述二次函数,其 xk,xk+1两点处的梯度可表示为,
11,k k k kg G x b g G x b
因而有 11( ) ( ) ( ) ( ) 0j T k k j T k kd g g d G x x
1k k kd x x取这说明只要沿 dj方向分别对函作两次一维搜索,
得到两个极小点 xk和 xk+1,那么这两点的连线所给出的方向 dk就是与 dj一起对 G共轭的方向 。
2.基本算法
二维情况描述鲍威尔的基本算法,
1） 任选一初始点 x0，
再选两个线性无关的向量,如坐标轴单位向量 e1=[1,0]T 和
e2=[0,1]T 作为初始搜索方向 。
2） 从 x0出发,顺次沿 e1，
e1作一维搜索,得点,两点连线得一新方向 d1
0012,xx
1 0 02d x x
x1
x2
x0
o
e1
e2
d1
d2
x*
10
2x
10x
11x
12x
01x
x1
x2
x0
o
e1
e2
d1
d2
x*
10
2x
10x
11x
12x
01x
2 1 120d x x
沿 d2作一维搜索得点 x2 。
即是二维问题的极小点 x* 。
方法的基本迭代格式包括共 轭方向产生和方向替换两主要步骤。
用 d1代替 e1形成两个线性无关向量 d1,e2,作为下一轮迭代的搜索方向。再 从出发，沿 d1作一维搜索得点,作为下一轮迭代的初始点。
02x
10x
3） 从出发,顺次沿 e2,d1 作一维搜索,
得到点,两点连线得一新方向,
1112,xx
10x
把二维情况的基本算法扩展到 n维，则鲍威尔基本算法的要点是：
在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和 n个线性独立的搜索方向。从始点出发顺次沿 n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。
用这个方向替换原来 n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。
此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。
上述基本算法仅具有理论意义 。
因为在迭代中的 n个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成 n维空间，
可能求不到极小点，所以上述基本算法有待改进。
3.改进的算法在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的,好坏,,这是产生向量组线性相关的原因所在。
在改进的算法中首先判断原向量组是否需要替换 。 如果需要替换,还要进一步判断原向量组中哪个向量最坏,然后再用新产生的向量替换这个最坏的向量,以保证逐次生成共轭方向 。
为此，要解决两个关键问题,
（ 1） dk＋ 1是否较好？是否应该进入新的方向组？即方向组是否进行更新？
（ 2）如果应该更新方向组,dk＋ 1不一定替换方向,而是有选择地替换某一方向 。1kd kmd
令在 k次循环中
00
2
31
()
()
()
k
k
n
k
n
Ff
Ff
Ff
x
x
x
01,,kkknn?xxx 1 0 0( ) 2k k k k k kn n n nx x x x x x（ ）
分别称为一轮迭代的始点、终点和反射点 。
则在循环中函数下降最多的第 m次迭代是
1 ( 1,2,,)i i if f i n
( ) ( 0,1,2,,)kiif f i nx记,
11m a xm i m min ff
相应的方向为 。kmd
为了构成共 轭性好的方向组，须遵循下列准则,在 k次循环中，若满足条件：
30FF?
和 20 2 3 0 2( 2 ) ( )mF F F F F2030,5 ( )m FF
则选用新方向 dk,并在第 k+1迭代中用 dk替换对应于的方向 。否则，仍然用原方向组进行第 k+1迭代。kmd
m?
0 0 2,nF f F f因此
这样重复迭代的结果，后面加进去的向量都彼此对 G共轭，经 n轮迭代即可得到一个由 n个共轭方向所组成的方向组。对于二次函次，最多 n次就可找到极小点，而对一般函数，往往要超过 n次才能找到极小点（这里,n”表示设计空间的维数）。
例 4-5 用改进的鲍威尔法求目标函数
221 2 1 1 2( ) 2 4 2f x x x x xx
解,（ 1） 第 1轮迭代计算
，
0
0
1
1
x 00 0 0( ) 3F f fx
沿 e1方向进行一维搜索
0201m i n ( ) 4 3fxe
1 2得
00
1 0 1 1
1 1 32
1 0 1?
x x e011( ) 7ffx
0,0 0 1 。
的最优解。已知初始点 [1,1]T，迭代精度以 为起点，沿第二坐标轴方向 e2 进行一维搜索
01x
02
12m i n ( ) 2 2 7fxe
2 0.5
得
00
2 1 2 1
3 0 3
0,5
1 1 1,5
x x e
0
22 ( ) 7,5ffx
确定此轮中的最大下降量及其相应方向
001 0 1 0 1( ) ( ) 4f f f fxx
002 1 2 1 2( ) ( ) 0,5f f f fxx
12m a x [,] 4m
反射点及其函数值，
0 0 0
3 2 0
3 1 522
1,5 1 2
x x x033( ) 7Ffx
检验 Powell条件
20 2 3 0 2( 2 ) ( ) 1,2 5mF F F F F2030,5 ( ) 3 2m FF
3073FF
由于满足 Powell条件，则淘汰函数值下降量最大的方向 e1，下一轮的基本方向组为 e2,。03d
构成新的方向
0 0 0
3 2 0
3 1 2
1,5 1 0,5
d x x
沿 方向一维搜索得极小点和极小值03d
1 3,8
1,7
x 1( ) 7,9fx，
此点为下轮迭代初始点。
按点距准则检验终止条件
1 1 2 20 ( 3,8 1 ) ( 1,7 1 ) 2,8 8 6xx
需进行第二轮迭代机算 。
（ 2） 第 2轮迭代计算此轮基本方向组为 e2，,分别相当于,,
起始点为 ＝ 。
03d 11d 12d
10x 1x
沿 e2方向进行一维搜索得
1
1
3,8
1,9
x 111( ) 7,9 8ffx
以 为起点沿 方向一维搜索得11x 03d
1
2
3,9 6
1,9
x 122 ( ) 7,9 9 6ffx
确定此轮中函数值最大下降量及其相应方向
1 0,0 8
2 0,0 1 6
12m a x [,] 0,0 8m
反射点及其函数值
1 1 1
3 2 0
3,9 6 3,8 4,1 222
1,9 4 1,7 2,1 8
x x x
133 ( ) 7,9 6 4Ffx
检验 Powell条件，淘汰函数值下降量最大的方向 e2，下一轮的基本方向组应为,。03d 13d
构成新的方向
1 1 1
3 2 0
3,9 6 3,8 0,1 6
1,9 4 1,7 0,2 4
d x x
沿 方向进行一维搜索得13d
2 4
2
x 2( ) 8fx
检验终止条件
2 2 2 20 ( 4 3,8 ) ( 2 1,7 ) 0,3 6xx
（ 3） 第 3轮迭代计算此轮基本方向组为,,起始点为 ＝,先后沿,方向,进行一维搜索,得
03d 13d 20x 2x
03d 13d
2
2
4
2
x
2
1
4
2
x,
2220 0xx
* 4
2
x *( ) 8fx故最优解检验终止条件
实际上,前两轮迭代的,为共轭方向,由于本例目标函数是二次函数,按共轭方向的二次收敛性,
故前两轮的结果就是问题的最优解,但每一轮迭代都需要进行 n+1次迭代 。
13d 23d
前面介绍的许多优化方法，除鲍威尔（ Powell）
法外，都需要计算目标函数的导数，而在实际工程的最优化问题中，目标函数的导数往往很难求出或者根本无法求出。下面所介绍的方法只需要计算目标函数值，无需求其导数，因此计算比较简单，其几何概念也比较清晰，属于直接法的无约束最优化方法。这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。
§ 4-6 其它方法（如坐标轮换法、单纯形法）
坐标轮换法坐标轮换法的基本思想：
是将一个 n维优化问题转化为依次沿 n个坐标方向反复进行一维搜索问题 。 这种方法的实质是把 n维问题的求优过程转化为对每个变量逐次进行一维求优的循环过程 。 每次一维搜索时,只允许 n个变量的一次改动,其余 (n-1)个变量固定不变 。 故坐标轮换法也常称单变量法或变量交错法 。
坐标轮换法此法的效能在很大程度上取决于目标函数的性质。
（ 1）计算量少，程序简单，不需要求函数导数的直接探索目标函数最优解的方法；
（ 2）探索路线较长，问题的维数愈多求解的效率愈低。
当维数 n＞ 10时，则不应采用此法。仅适用于 n较少（ n
<10）的目标函数求优；
（ 3）改变初始点重新迭代，可避免出现病态。
方法特点步长加速法（ Hook-Reeves算法）
一、步长加速法原理步长加速法也称之为离散步长的 Hook-Reeves算法，
是一种不使用导数的直接搜索算法，其算法过程可分成两个基本阶段：坐标循环试探及模矢加速搜索。见下图，
从初始探点 Y0出发，依次沿 n个坐标方向用固定步长△进行试探，寻找更好的点 。 而模矢加速搜索，就是沿模矢方向 加大步长前进，
以得到第 k+1次迭代的出发点 Y0，这样就完成了一次迭代，
然后再从新的 Y0出发，进行下一轮坐标循环试探，如此重复进行，使目标值不断减小。
121,,,,?knn XYYYY 为并记?
)( 1 kk XX
二、步长加速法算法设问题为
nEXXf?),(m i n
X0为初始点,个坐标轴的单位方向向量，
初始坐标循环试探的步长为△ >0，模矢加速搜索的加速步长因子为 a>1（通常取 a=2），迭代终止准则为 ( 为预先确定的正数）。
neee n 依次是?,,21
);2(,1,0),""(),()( 10 转令成功步长加速即若 kkjXfYf k
0,0,00 jkXY
（ 1）
其它情形当当
,
)()(,
)()(,
11
11
1
j
jjjjj
jjjjj
j
Y
YfeYfeY
YfeYfeY
Y（ 2）
转令,1,1 jjnj（ 3）若 （ 2）；否则，转（ 4）
否则转（ 6）
)2(,1,0,10 转 kkjXY k否则，令;),(,,计算停止即近似极小点输出若 nY（ 6）
1,0,,21 0 kkjYY n令否则，,转（ 2）
（ 5） )( 10 kkk XXaXY令
,),""(),()( 10 nkn YXYfYf令成功试探即若（ 4） 转（ 5）；
单纯形方法一、基本思想单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。
定义：单纯形
n维空间中的恰好有 n+1个顶点（极点）的有界的凸多面体称之为一个单纯形。
根据定义，可知，一维空间中的单纯形是线段，
二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。
在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这 4个操作来实现。下面以二维问题为例来对 4种操作进行说明（参见下图）。
（ 1）反射 —— 设除了最劣点 X1以外的基余顶点的中心为 X4，
作 X1关于点 X4的对称点 X5，称 X5为 X1的反射点。求反射点的过程称之为反射。
)()()( 321 XfXfXf
（ 2）扩张 —— 在得到反射点 X5之后，如果 X5优于原单纯形的最劣点（即有 ），表明反射方向（ X5— X1）是有利方向，反射成功。若进一步有,可沿反射方向前进适当的距离到点 X6。 X6称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点 X6优于反射点 X5，则扩张成功，以 X6取代
X1，得新单纯形 {X6,X2,X3}；否则，扩张失败，舍弃扩张点，以反射 X5点取代 X1，得新单纯形 {X5,X2,X3}。
)()( 15 XfXf?
)()( 25 XfXf?
设当前的单纯形的顶点为 X1,X2,X3，且有
)()()( 251 XfXfXf
如果出现 。表示反射完全失败，应退回到介于 X4
与 X1之间的某个点 X8。
)()( 15 XfXf?
（ 3）收缩 —— 在得到反射点 X5之后，如果有表示反射部分成功，方向（ X5— X1）虽然是有利方向，但 X5前进过远，应收缩到介于 X4与 X5之间的某个点 X7。
上述两种从反射点向 X1方向后退的过程都称之为收缩。
如果收缩点优于原来的最劣点 X1，称收缩成功，并以收缩点取代原最劣点，构成新单纯形 {X7,X2,X3}或 {X8,X2,X3}；否则，称之为收缩失败，舍弃收缩点。
（ 4）缩边 —— 若收缩失败，则应压缩当前单纯形的边长：令最优点 X3不动，而其余顶点向 X3方向压缩，使边长缩短（通常缩短一半），以产生新单纯形。如下图所示，点 X1压缩到点 X9，
点 X2压缩到点 X10，得新单纯形 {X9,X10,X3}，这一过程称之为缩边。
二、单纯形替换算法设初始点为 X0，初始边长 h,ei为坐标轴方向的单位向量
,预定正数
,,,2,1 ni 21,
（ 2）比较各项点 Xi的函数值，挑出其中的最优点，记为 XL；最劣点，记 XH；次差点，记为 Xw；
（ 3）求反射中心
21 nn XX 和反射点
)(
1
112
)(
0
1
Hnnn
n
Hi
i
in
XXaXX
X
n
X
其中,a>0，通常取 a=1；
（ 1）令 },,,{,,,2,1,
100 nii XXXniheXX 构造单纯形；
输出 XL，为原问题近似极小点；否则，转（ 2）。
构造新单纯形；
5.0
（ 4）根据不同 情 况，分别进行扩张，
收缩或缩边，其中收缩因子
1
1
2
1
m a x
)()(
Li
n
i
Li
XX
XfXf（ 5）如果满足表 1 无约束优化方法搜索方向之间的相互联系
—— 间接法
kkdg
1[]k k kd G g
1[]k?G
k k kd Q g
1
11
[]
[]
k T k
k
k T k
gdQI
gg
k k kd A g
11k k kA A A
1[]kkAG
搜索方向 函数梯度的修正因子 所用目标函数信息梯度法 I（ 单位阵 ） 一阶导数
（ 阻尼 ） 牛顿法二阶导数共轭梯度法 一阶导数变尺度法 一阶导数，使
（海赛矩阵的逆阵）
无约束优化方法
—— 间接法总结
1、梯度法方向 负梯度 用到一阶导数适合于精度不高或用于复杂函数寻找一个好的初始点
2、牛顿法用到一阶导数和海色矩阵，具有二次收敛性要求海色矩阵奇异，且维数不宜太高
3、共轭梯度法用到一阶导数，具有二次收敛性
4、变尺度法收敛快，效果好，被认为是目前最有效的无约束优化方法。适用于维数较高，具有一阶偏导数的目标函数
1、坐标轮换法计算效率较低适合维数较低，目标函数无导数或导数较难求得
2、步长加速法同坐标轮换法，对目标函数的性态的适应性更好
3,Powell法具有二次收敛性，收敛速度较快，可靠性高，被认为是直接法中最有效的方法之一
4、单纯形法思路清楚，收敛慢无约束优化方法
—— 直接法总结无约束优化上机
Powell法优化设计程序 —— 与一维搜索黄金分割法组合题目：编程求解函数的极小点 x*。
22
1 2 1 1 2( ) 2 4 2f x x x x xx
初始点 x0=[1,1]T，迭代精度 。0,0 0 1
上机地点,4109(材控、装控）； 4211（机自）
时间：周一晚 6:00~9:30
§ 4-1 最速下降法（梯度法）
§ 4-2 牛顿类方法
§ 4-3 变尺度法
§ 4-4 共轭方向法
§ 4-5 鲍威尔方法
§ 4-6 其它方法（如坐标轮换法、单纯形法）
第 1章所列举的机械优化设计问题,都是在一定的限制条件下追求某一指标为最小,它们都属于约束优化问题 。 工程问题大都如此 。
为什么要研究无约束优化问题?
（ 1） 有些实际问题,其数学模型本身就是一个无约束优化问题 。
（ 2） 通过熟悉它的解法可以为研究约束优化问题打下良好的基础 。
（ 3） 约束优化问题的求解可以通过一系列无约束优化方法来达到 。 所以无约束优化问题的解法是优化设计方法的基本组成部分,也是优化方法的基础 。
（ 4） 对于多维无约束问题来说,古典极值理论中令一阶导数为零,但要求二阶可微,且要判断海赛矩阵为正定才能求得极小点,这种方法有理论意义,
但无实用价值 。 和一维问题一样,若多元函数 F(X)
不可微,亦无法求解 。 但古典极值理论是无约束优化方法发展的基础 。
目前已研究出很多种无约束优化方法，它们的主要不同点在于 构造搜索方向 上的差别。
m i n ( ) nfR?xx
（ 1）间接法 —— 要使用导数，如梯度法、（阻尼）
牛顿法、变尺度法、共轭梯度法等。
（ 2）直接法 —— 不使用导数信息，如坐标轮换法、
鲍威尔法、单纯形法等。
无约束优化问题是：
12[] Tnx x x?x求 n维设计变量
( ) m inf?x使目标函数
1 ( 0,1,2,)k k k
k sk?
xx
搜索方向的构成问题乃是无约束优化方法的关键 。
用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的
（ n ≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。
4-1 梯度法
1 ( 0,1,2,)k k k
k sk?
xx
1 ( ) ( 0,1,2,)k k k
ka f k
x x x
基本思想,函数的负梯度方向是函数值在该点下降最快的方向。将 n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。
()f x搜索方向 s取该点的负梯度方向 (最速下降方向 ),使函数值在该点附近的范围内下降最快 。
为了使目标函数值沿搜索方向 能够获得最大的下降值,其步长因子 应取一维搜索的最佳步长 。 即有
()kf x
k?
1( ) [ ( ) ] m in [ ( ) ]
m in ( )
k k k k k
k a
a
f f a f f a f
x x x x x
根据一元函数极值的必要条件和多元复合函数求导公式，得
'( ) [ ( ) ] ( ) 0Tk k kkf f fx x x
1[ ( ) ] ( ) 0k T kffxx
1( ) 0k T kss
在最速下降法中，
相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，
因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成,之,字形的锯齿现象，而且越接近极小点锯齿越细。
图 4-2 最速下降法的搜索路径方法特点
（ 1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，
然后慢慢逼近局部极小点。
（ 2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。
开始给定结束
0
,?x
()
kk
fdx
1
,m i n ( )
k k k
k
kk
k
f
x x d
xd
1kk
xx
*1 k?
xx
否是
1kk
0k?
sk
0
0
10
2
( ) 10 4
2 4
()
50 100
x
f
x
f
x
x
x
沿负梯度方向进行一维搜索,有
01 0 0
0
0
24()
2 100f
x x x
0? 为一维搜索最佳步长，应满足极值必要条件
1 2 2( ) m i n ( 2 4 ) 2 5 ( 2 1 0 0 ) m i n ( )fx
例 4－ 1 求目标函数 的极小点 。
解 取初始点则初始点处函数值及梯度分别为
0 [ 2,2 ]T?x
2212( ) 2 5f x xx
00'( ) 8 ( 2 4 ) 5 0 0 0 ( 2 1 0 0 ) 0
算出一维搜索最佳步长
0
626 0.0 20 030 72
31 252
第一次迭代设计点位置和函数值
01
2
0
24 1,9 1 9 8 7 7
2 1 0 0 0,3 0 7 1 7 8 5 1 0
x
1( ) 3,6 8 6 1 6 4f?x
继续作下去，经 10次迭代后，得到最优解00 Tx
( ) 0fx
这个问题的目标函数的等值线为一簇椭圆,迭代点从走的是一段锯齿形路线，见图 4-3。
0x
1
图 4-3
将上例中目标函数 引入变换 2212( ) 2 5f x xx
221 2 1 2(,)y y y y
其等值线由椭圆变成一簇同心圆。
仍从 即 出发进行最速下降法寻优。此时：
0 [ 2,2 ]T?x 0 [ 2,1 0 ]T?y
0
0
10
2
( ) 1 0 4
2 4
()
2 20
y
y
y
y
y
沿负梯度方向进行一维搜索：
则函数 f(X)变为：
y1=x1,y2=5x2
1 0 0
0
0
0
0
()
2424
10 2010 20
y y y
β为一维搜索最佳步长，可由极值条件：
1 0 0
22
( ) m in [ ( ) ] m in ( )
( ) ( 2 4 ) ( 10 20 )
y y y
0( ) 0
由
0
26 0,5
52
从而算得一步计算后设计点的位置及其目标函数：
01
0
1
24 0
10 20 0
( ) 0
y
y
经变换后，只需一次迭代，就可找到最优解。
这是因为经过尺度变换：
11
225
yx
yx
等值线由椭圆变成圆。
梯度法的特点
（ 1）理论明确，程序简单，对初始点要求不严格。
（ 2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。
（ 3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈 锯齿 状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。
（ 4）梯度法的收敛速度与目标函数的性质密切相关。
对于等值线 (面 )为同心圆（球）的目标函数，一次搜索即可达到极小点。
4-2 牛顿法及其改进
2
( ) ( ) ( ) ( ) ( )
1
( ) ( ) ( )
2
k k T k
k T k k
f f f
f
x x x x x x
x x x x x
设 为 的极小点1k?x ()? x
1( ) 0kx
基本思想,
在 xk邻域内用一个二次函数 来近似代替原目标函数，并将 的极小点作为对目标函数求优的下一个迭代点 。经多次迭代，使之逼近目标函数 的极小点。
牛顿法是求函数极值的最古老算法之一。
()? x
()? x ()f x
1k?x
()f x
21( ) ( ) ( ) 0k k k kffx x x x
1 2 1[ ( ) ] ( ) ( 0,1,2,)k k k kf f kx x x x
这就是多元函数求极值的牛顿法迭代公式。
对于二次函数,海赛矩阵 H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。
例 4－ 2 求目标函数 的极小点 。
解 取初始点
2212( ) 2 5f x xx
0 [ 2,2 ]T?x1 0 2 0 1 0
1
0
2 4 02
( ) ( )
12 100 0
0
50
ff
x x x x
00x
( ) 0fx
从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升 。
阻尼牛顿法
1 2 1[ ( ) ] ( ) ( 0,1,2,)k k k k k kkks f f kx x x x x
k? 阻尼因子,沿牛顿方向进行一维搜索的最佳步长，由下式求得：
1( ) ( ) m i n ( )k k k k kkkf f s f s
x x x
经过一次迭代即求得极小点函数极小值开始给定结束
0
,?x
21
[ ( ) ] ( )
k k k
ff
d x x
1
,m i n ( )
k k k
k
kk
k
f
x x d
xd
1kk
xx
*1 k?
xx
否是
1kk
0k?
阻尼牛顿法程序框图方法特点
（ 1） 初始点应选在 X*附近，有一定难度；
（ 2） 尽管每次迭代都不会是函数值上升，但不能保证每次下降 ；
（ 3） 若迭代点的海赛矩阵为奇异，则无法求逆矩阵，
不能构造牛顿法方向；
（ 4） 不仅要计算梯度，还要求海赛矩阵及其逆矩阵，
计算量和存储量大。此外，对于二阶不可微的 F(X)也不适用。
虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。
1 ( 0,1,2,)k k kk skxx
1 ( ) ( 0,1,2,)k k kka f kx x x
1 2 1[ ( ) ] ( ) ( 0,1,2,)k k k kf f kx x x x
1 2 1[ ( ) ] ( ) ( 0,1,2,)k k k kk f f kx x x x
一般迭代式：
梯度法：
牛顿法：
阻尼牛顿法：
梯度法与牛顿法：
1 ()k k k kk fx x A x
4-3 变尺度法
DFP变尺度法首先有戴维顿（ Davidon）与 1959
年提出，又于 1963年由弗莱彻（ Fletcher）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。
DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。
1,基本思想变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。
例如在用最速下降法求 的极小 2212( ) 2 5f x xx
值时,需要进行 10次迭代才能达到极小点 [0,0 ]Tx?
如作变换 y1=x1,y2=5x2
把 的尺度放大 5倍，则目标函数等值线由一簇椭圆变成一簇同心圆。
x2
22
1 2 1 2(,)y y y y
消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。
梯度法构造简单，只用到一阶偏导数，计算量小，
初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近 X*时，即使对二次正定函数收敛也非常慢。
牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，
但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。
能不能将两种算法的优点综合起来，扬长避短？
1 ()k k k kk fx x A x
Ak 是需要构造 n× n的一个对称方阵,
如 Ak=I,则得到梯度法 ；
21[ ( ) ]kkfAx则得到阻尼牛顿法 ；如当矩阵 Ak 不断地迭代而能很好地逼近 21[ ( ) ]kf x
时，就可以不再需要计算二阶导数。
变尺度法的关键在于尺度矩阵 Ak的产生 。
对于二次函数,
1()
2
TTfx x G x b x c
x Qx进行尺度变换在新的坐标系中，函数 f(x)的二次项变为：
11
22
T T T?x G x x Q G Q x
目的：减少二次项的偏心如 G是正定，则总存在矩阵 Q，使得：
T?Q G Q I
用矩阵 Q-1右乘等式两边，得：
用矩阵 Q左乘等式两边，得：
1TQ G Q
T?Q Q G I
所以 1TQ Q G
上式说明：二次函数矩阵 G的逆阵，可以通过尺度变换矩阵 Q来求得。
1 2 1[ ( ) ] ( ) ( 0,1,2,)k k k kk f f kx x x x
牛顿迭代公式：
1 ( ) ( 0,1,2,)k k T kk Q Q f kx x x
记,T A?QQ
搜索方向：
1 ( ) ( 0,1,2,)k k ks f kAx
迭代公式：
1 ( ) ( 0,1,2,)k k k k
k fk?
x x A x
A 称为变尺度矩阵
2212( ) 2 5f x xx在例 4－ 2中
122
1 2 1 2
2
2011( ) 2 5
0 5 022
Txf x x x x
x
x x G x
20
0 5 0
G
如取
1
0
2
1
0
52
Q
11
00
2 0 1 022
1 0 50 1 0 1
00
5 2 5 2
T
Q G Q I
求得,1
11 1
00 0
22 2
111
000
505 2 5 2
T?
G Q Q
2,构造尺度矩阵 Ak
从初始矩阵 A0=I(单位矩阵 )开始，通过对公式
1k k kA A A
因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度 。
1） DFP法（ Davidon-Fletcher-Powell)
[ ] [ ]
[ ] [ ]
Tk k k k k T k
k
k T k k T k k
x x A g g AA
x g g A g
11
1
( ) ( )k k k k k
k k k
ff
g g g x x
x x x式中中修正矩阵 的不断修正，在迭代中逐步逼近于k?A
1 ()k?Gx。
2） BFGS算法 (Broyden-Fletcher-Gold frob-
Shanno)
DFP算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不稳定。 BFGS算法对于维数较高问题具有更好的稳定性。
1 [ ] [ ]
{ [ ]
[ ] [ ]
[ ] [ ] }
k k T k T k k
k k k T
k T k k T k
kk k T k k T
x x g A g
A x x
x g x g
A g x x g A
开始给定结束
0
,?x
00
0
()f
gx
AI
1
,m i n ( )
k k k
k
kk
k
f
x x d
xd
1kk
xx
*1 k?
xx
否是
1kk
kn?
11
1
11
()
kk
k k k
k k k
f
gx
g g g
x x x
11k k k
A A A
01 k?
xx
0k?
k k k
d A g
是否例 4-3,用 DFP算法求下列问题的极值：
221 2 1 2 1 1 2(,) 2 4 2f x x x x x x x
解,1）取初始点,为了按 DFP法构造第一次搜寻方向 d0，需计算初始点处的梯度
0 [1 1]T?x
0
1200
21
2 2 4 4()
42 2
xxf
xx
x
gx
取初始变尺度矩阵为单位矩阵 A0=I，则第一次搜寻方向为
0 0 0 1 0 4 4
0 1 2 2
d A g
沿 d0方向进行一维搜索,得
01 0 0
00
0
1414
1212
x x d
为一维搜索最佳步长,应满足0?
1 0 0 2( ) m i n ( ) m i n ( 4 0 2 0 3 )ff
x x d
得,
0 0,2 5
1 2
0,5
x,
2） 再按 DFP法构造点 x1处的搜寻方向 d1,需计算
1
121
21
2 2 4 1
42 2
xx
xx
x
g
0 1 0 1 4 3
2 2 4
g g g
0 1 0 2 1 1
0,5 1 0,5
x x x
代入校正公式
0 0 0 0 0 0
0
0 0 0 0 0
[ ] [ ]
[ ] [ ]
T T
TT
x x A g g AA
x g g A g
13
1 0,5 3 4
0,5 4
33
1 0,5 3 4
44
=
1 0 0A A A
21 19
1 0 1 0,5 9 1211 25 50
0 1 0,5 0,25 12 16 19 415 25
50 10 0
=
第二次搜寻方向为 1 1 1
8
6
6
5
d A g
再沿 d1进行一维搜索,得
1
2 1 1
1
1
8
2
5
6
0,5
5
x x d
为一维搜索最佳步长,应满足1?
2 1 1 28 1 1( ) m in ( ) m in ( 4 )
52ffx x d
1
5
4
2 4
2
x,得
3） 判断 x2是否为极值点梯度,
2
122
21
2 2 4 0
()
42 0
xx
f
xx
x
x
海赛矩阵,22 22
()
24
f
x
梯度为零向量,海赛矩阵正定。可见点满足极值充要条件，因此为极小点。
*2 42 Txx
*( ) 8fx
4-4 共轭方向法
1.共 轭方向：
设 G为 n× n阶实对称正定矩阵，如果有两个 n
维向量 d0和 d1满足,则称向量 d0与 d1
关于矩阵 G共 轭。
01( ) 0T?d G d
当 G为单位矩阵时,01( ) 0T?dd
假设目标函数 f(x) 在极值点附近的二次近似函数为
1()
2
TfTx x G x b x c
对二维情况任选取初始点 x0沿某个下降方向 d0作一维搜索,得 x1
1 0 00x x d
因为 是沿 d0方向搜索的最佳步长,即在点 x1
处函数 f（ x） 沿方向 d0的方向导数为零 。 考虑到点
x1处方向导数与梯度之间的关系,故有
0?
1
10
0 [ ( ) ] 0
Tf f
x xdd
如果按最速下降法，选择负梯度方向 为搜索方向，则将发生锯齿现象 。
1()f x
取下一次的迭代搜索方向 d1直指极小点 x*。
α0d0x 0 x1
x*
1
α1d1
1()f x d
1
如果能够选定这样的搜索方向,那么对于二元二次函数只需顺次进行 d0,d1两次直线搜索就可以求到极小点 x*,即有
111x x d
那么这样的 d1方向应该满足什么条件呢?
对于前述的二次函数,1() 2 TfTx x G x b x c
当 时，1xx 1 0
x*是 f(x)极小点，应满足极值必要条件，故有
( ) 0fx Gx b
1 1 1 111( ) ( ) ( )ffx G x d b x G d 0
将等式两边同时左乘 得,0()Td 01( ) 0T?d G d
11()fx G x b有
01( ) 0T?d G d
就是使 d1直指极小点 x*,d1所必须满足的条件 。
两个向量 d0和 d1称为 G的共轭向量,或称 d0和 d1
对 G是共轭方向 。
2.共轭方向的性质性质 1 若非零向量系 d0,d1,d2,…,dm-1是对 G共轭,
则这 m个向量是线性无关的 。
性质 2 在 n维空间中互相共轭的非零向量的个数不超过 n。
性质 3 从任意初始点出发，顺次沿 n个 G的共轭方向 d0,d1,d2,…,进行一维搜索，最多经过 n次迭代就可以找到的二次函数 f(x)极小点。
0 2 1( ) ( ) 0T fd x d
开始给定结束
00
,,?xd
1
,m i n ( )
k k k
k
kk
k
f
x x d
xd
1kk
xx
*1 k?
xx
否是
1kk
0k?
提供新的共轭方向关键：新的共 轭方向 确定在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。
3.共轭梯度法
共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。
从 xk出发，沿负梯度方向作一维搜索,
1 ( 0,1,2,)k k kk kx x d
()kkfdx
设与 dk共 轭的下一个方向 dk+1由 dk和点 xk+1的负梯度的线形组合构成，即：
11 ()k k kkfd x d
21( ) ( ) 0k T kfd x d共轭条件：
则：
21[ ( ) ] ( ) [ ( ) ] 0k T k kkf f fx x x d
解得,21
2
[ ( ) ] ( ) ( )
[ ( ) ] ( ) ( )
k T k k
k k T k k
f f f
f f f?
x x xx x x
令 1() 2 TfTx x G x b x c为函数的泰勒二次展开式
()kkfx G x b则
11()kkfx G x b
上两式相减，并代入 1k k kkx x d
1( ) ( )k k kk ffG d x x
1( ) ( )k k kk ffG d x x将式
11 ()k k kkfd x d与式 两边相乘，并应用 共轭条件得,11[ ( ) ( ) ] [ ( ) ( ) ] 0k k k kkf f f fx x x x
21
11
2
()[ ( ) ] ( )
[ ( ) ] ( ) ()
kk T k
k k T k k
fff
ff f
xxx
xx x
因此
11 ()k k kkfd x d21
2
()
()
k
k k
f
f
x
x
1 ( 0,1,2,)k k kk kx x d
221 2 1 1 2( ) 2 4 2f x x x x xx,已知初始点 [1,1]T
例题 4-4 求下列问题的极值
解,1） 第一次沿负梯度方向搜寻
计算初始点处的梯度
0
120
21
2 2 4 4()
42 2
xxf
xx
x
x
01 0 0
00
0
1414
1212
x x d
为一维搜索最佳步长,应满足
1 0 0 2( ) m i n ( ) m i n ( 4 0 2 0 3 )ff
x x d
迭代精度 。0,0 0 1
得,
0 0,2 5
1 2
0,5
x
2）第二次迭代,21
20 0
() 5
0,2 5
20()
f
f
x
x
1 1()
2f
x
1 1 0
0
2()
1,5f?
d x d
2 1 1 2 2 2 2
0,5 1,5 0,5 1,5
x x d
代入目标函数
22( ) ( 2 2 ) 2 ( 0,5 1,5 )
2 ( 2 2 ) ( 0,5 1,5 ) 4 ( 2 2 ) ( )
fx
得 1
因 2( ) 0fx
收敛。
( ) 0由
2 2 240,( ) 8,( )
20ff
x x x
从而有：
4-5 鲍威尔方法鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。
1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。
1()
2
TfTx x G x b x c对函数：
基本思想,在不用导数的前提下，在迭代中逐次构造
G的共轭方向。
1.共轭方向的生成
j
j
k
k
k
d
d
dj
g
gk+1
x xk+1
设 xk,xk+1为从不同点出发，沿同一方向
dj进行一维搜索而到的两个极小点。
梯度和等值面相垂直的性质,dj和 xk,xk+1两点处的梯度 gk,gk+1之间存在关系,
1( ) 0,( ) 0j T k j T kd g d g
另一方面,对于上述二次函数,其 xk,xk+1两点处的梯度可表示为,
11,k k k kg G x b g G x b
因而有 11( ) ( ) ( ) ( ) 0j T k k j T k kd g g d G x x
1k k kd x x取这说明只要沿 dj方向分别对函作两次一维搜索,
得到两个极小点 xk和 xk+1,那么这两点的连线所给出的方向 dk就是与 dj一起对 G共轭的方向 。
2.基本算法
二维情况描述鲍威尔的基本算法,
1） 任选一初始点 x0，
再选两个线性无关的向量,如坐标轴单位向量 e1=[1,0]T 和
e2=[0,1]T 作为初始搜索方向 。
2） 从 x0出发,顺次沿 e1，
e1作一维搜索,得点,两点连线得一新方向 d1
0012,xx
1 0 02d x x
x1
x2
x0
o
e1
e2
d1
d2
x*
10
2x
10x
11x
12x
01x
x1
x2
x0
o
e1
e2
d1
d2
x*
10
2x
10x
11x
12x
01x
2 1 120d x x
沿 d2作一维搜索得点 x2 。
即是二维问题的极小点 x* 。
方法的基本迭代格式包括共 轭方向产生和方向替换两主要步骤。
用 d1代替 e1形成两个线性无关向量 d1,e2,作为下一轮迭代的搜索方向。再 从出发，沿 d1作一维搜索得点,作为下一轮迭代的初始点。
02x
10x
3） 从出发,顺次沿 e2,d1 作一维搜索,
得到点,两点连线得一新方向,
1112,xx
10x
把二维情况的基本算法扩展到 n维，则鲍威尔基本算法的要点是：
在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和 n个线性独立的搜索方向。从始点出发顺次沿 n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。
用这个方向替换原来 n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。
此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。
上述基本算法仅具有理论意义 。
因为在迭代中的 n个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成 n维空间，
可能求不到极小点，所以上述基本算法有待改进。
3.改进的算法在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的,好坏,,这是产生向量组线性相关的原因所在。
在改进的算法中首先判断原向量组是否需要替换 。 如果需要替换,还要进一步判断原向量组中哪个向量最坏,然后再用新产生的向量替换这个最坏的向量,以保证逐次生成共轭方向 。
为此，要解决两个关键问题,
（ 1） dk＋ 1是否较好？是否应该进入新的方向组？即方向组是否进行更新？
（ 2）如果应该更新方向组,dk＋ 1不一定替换方向,而是有选择地替换某一方向 。1kd kmd
令在 k次循环中
00
2
31
()
()
()
k
k
n
k
n
Ff
Ff
Ff
x
x
x
01,,kkknn?xxx 1 0 0( ) 2k k k k k kn n n nx x x x x x（ ）
分别称为一轮迭代的始点、终点和反射点 。
则在循环中函数下降最多的第 m次迭代是
1 ( 1,2,,)i i if f i n
( ) ( 0,1,2,,)kiif f i nx记,
11m a xm i m min ff
相应的方向为 。kmd
为了构成共 轭性好的方向组，须遵循下列准则,在 k次循环中，若满足条件：
30FF?
和 20 2 3 0 2( 2 ) ( )mF F F F F2030,5 ( )m FF
则选用新方向 dk,并在第 k+1迭代中用 dk替换对应于的方向 。否则，仍然用原方向组进行第 k+1迭代。kmd
m?
0 0 2,nF f F f因此
这样重复迭代的结果，后面加进去的向量都彼此对 G共轭，经 n轮迭代即可得到一个由 n个共轭方向所组成的方向组。对于二次函次，最多 n次就可找到极小点，而对一般函数，往往要超过 n次才能找到极小点（这里,n”表示设计空间的维数）。
例 4-5 用改进的鲍威尔法求目标函数
221 2 1 1 2( ) 2 4 2f x x x x xx
解,（ 1） 第 1轮迭代计算
，
0
0
1
1
x 00 0 0( ) 3F f fx
沿 e1方向进行一维搜索
0201m i n ( ) 4 3fxe
1 2得
00
1 0 1 1
1 1 32
1 0 1?
x x e011( ) 7ffx
0,0 0 1 。
的最优解。已知初始点 [1,1]T，迭代精度以 为起点，沿第二坐标轴方向 e2 进行一维搜索
01x
02
12m i n ( ) 2 2 7fxe
2 0.5
得
00
2 1 2 1
3 0 3
0,5
1 1 1,5
x x e
0
22 ( ) 7,5ffx
确定此轮中的最大下降量及其相应方向
001 0 1 0 1( ) ( ) 4f f f fxx
002 1 2 1 2( ) ( ) 0,5f f f fxx
12m a x [,] 4m
反射点及其函数值，
0 0 0
3 2 0
3 1 522
1,5 1 2
x x x033( ) 7Ffx
检验 Powell条件
20 2 3 0 2( 2 ) ( ) 1,2 5mF F F F F2030,5 ( ) 3 2m FF
3073FF
由于满足 Powell条件，则淘汰函数值下降量最大的方向 e1，下一轮的基本方向组为 e2,。03d
构成新的方向
0 0 0
3 2 0
3 1 2
1,5 1 0,5
d x x
沿 方向一维搜索得极小点和极小值03d
1 3,8
1,7
x 1( ) 7,9fx，
此点为下轮迭代初始点。
按点距准则检验终止条件
1 1 2 20 ( 3,8 1 ) ( 1,7 1 ) 2,8 8 6xx
需进行第二轮迭代机算 。
（ 2） 第 2轮迭代计算此轮基本方向组为 e2，,分别相当于,,
起始点为 ＝ 。
03d 11d 12d
10x 1x
沿 e2方向进行一维搜索得
1
1
3,8
1,9
x 111( ) 7,9 8ffx
以 为起点沿 方向一维搜索得11x 03d
1
2
3,9 6
1,9
x 122 ( ) 7,9 9 6ffx
确定此轮中函数值最大下降量及其相应方向
1 0,0 8
2 0,0 1 6
12m a x [,] 0,0 8m
反射点及其函数值
1 1 1
3 2 0
3,9 6 3,8 4,1 222
1,9 4 1,7 2,1 8
x x x
133 ( ) 7,9 6 4Ffx
检验 Powell条件，淘汰函数值下降量最大的方向 e2，下一轮的基本方向组应为,。03d 13d
构成新的方向
1 1 1
3 2 0
3,9 6 3,8 0,1 6
1,9 4 1,7 0,2 4
d x x
沿 方向进行一维搜索得13d
2 4
2
x 2( ) 8fx
检验终止条件
2 2 2 20 ( 4 3,8 ) ( 2 1,7 ) 0,3 6xx
（ 3） 第 3轮迭代计算此轮基本方向组为,,起始点为 ＝,先后沿,方向,进行一维搜索,得
03d 13d 20x 2x
03d 13d
2
2
4
2
x
2
1
4
2
x,
2220 0xx
* 4
2
x *( ) 8fx故最优解检验终止条件
实际上,前两轮迭代的,为共轭方向,由于本例目标函数是二次函数,按共轭方向的二次收敛性,
故前两轮的结果就是问题的最优解,但每一轮迭代都需要进行 n+1次迭代 。
13d 23d
前面介绍的许多优化方法，除鲍威尔（ Powell）
法外，都需要计算目标函数的导数，而在实际工程的最优化问题中，目标函数的导数往往很难求出或者根本无法求出。下面所介绍的方法只需要计算目标函数值，无需求其导数，因此计算比较简单，其几何概念也比较清晰，属于直接法的无约束最优化方法。这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。
§ 4-6 其它方法（如坐标轮换法、单纯形法）
坐标轮换法坐标轮换法的基本思想：
是将一个 n维优化问题转化为依次沿 n个坐标方向反复进行一维搜索问题 。 这种方法的实质是把 n维问题的求优过程转化为对每个变量逐次进行一维求优的循环过程 。 每次一维搜索时,只允许 n个变量的一次改动,其余 (n-1)个变量固定不变 。 故坐标轮换法也常称单变量法或变量交错法 。
坐标轮换法此法的效能在很大程度上取决于目标函数的性质。
（ 1）计算量少，程序简单，不需要求函数导数的直接探索目标函数最优解的方法；
（ 2）探索路线较长，问题的维数愈多求解的效率愈低。
当维数 n＞ 10时，则不应采用此法。仅适用于 n较少（ n
<10）的目标函数求优；
（ 3）改变初始点重新迭代，可避免出现病态。
方法特点步长加速法（ Hook-Reeves算法）
一、步长加速法原理步长加速法也称之为离散步长的 Hook-Reeves算法，
是一种不使用导数的直接搜索算法，其算法过程可分成两个基本阶段：坐标循环试探及模矢加速搜索。见下图，
从初始探点 Y0出发，依次沿 n个坐标方向用固定步长△进行试探，寻找更好的点 。 而模矢加速搜索，就是沿模矢方向 加大步长前进，
以得到第 k+1次迭代的出发点 Y0，这样就完成了一次迭代，
然后再从新的 Y0出发，进行下一轮坐标循环试探，如此重复进行，使目标值不断减小。
121,,,,?knn XYYYY 为并记?
)( 1 kk XX
二、步长加速法算法设问题为
nEXXf?),(m i n
X0为初始点,个坐标轴的单位方向向量，
初始坐标循环试探的步长为△ >0，模矢加速搜索的加速步长因子为 a>1（通常取 a=2），迭代终止准则为 ( 为预先确定的正数）。
neee n 依次是?,,21
);2(,1,0),""(),()( 10 转令成功步长加速即若 kkjXfYf k
0,0,00 jkXY
（ 1）
其它情形当当
,
)()(,
)()(,
11
11
1
j
jjjjj
jjjjj
j
Y
YfeYfeY
YfeYfeY
Y（ 2）
转令,1,1 jjnj（ 3）若 （ 2）；否则，转（ 4）
否则转（ 6）
)2(,1,0,10 转 kkjXY k否则，令;),(,,计算停止即近似极小点输出若 nY（ 6）
1,0,,21 0 kkjYY n令否则，,转（ 2）
（ 5） )( 10 kkk XXaXY令
,),""(),()( 10 nkn YXYfYf令成功试探即若（ 4） 转（ 5）；
单纯形方法一、基本思想单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。
定义：单纯形
n维空间中的恰好有 n+1个顶点（极点）的有界的凸多面体称之为一个单纯形。
根据定义，可知，一维空间中的单纯形是线段，
二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。
在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这 4个操作来实现。下面以二维问题为例来对 4种操作进行说明（参见下图）。
（ 1）反射 —— 设除了最劣点 X1以外的基余顶点的中心为 X4，
作 X1关于点 X4的对称点 X5，称 X5为 X1的反射点。求反射点的过程称之为反射。
)()()( 321 XfXfXf
（ 2）扩张 —— 在得到反射点 X5之后，如果 X5优于原单纯形的最劣点（即有 ），表明反射方向（ X5— X1）是有利方向，反射成功。若进一步有,可沿反射方向前进适当的距离到点 X6。 X6称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点 X6优于反射点 X5，则扩张成功，以 X6取代
X1，得新单纯形 {X6,X2,X3}；否则，扩张失败，舍弃扩张点，以反射 X5点取代 X1，得新单纯形 {X5,X2,X3}。
)()( 15 XfXf?
)()( 25 XfXf?
设当前的单纯形的顶点为 X1,X2,X3，且有
)()()( 251 XfXfXf
如果出现 。表示反射完全失败，应退回到介于 X4
与 X1之间的某个点 X8。
)()( 15 XfXf?
（ 3）收缩 —— 在得到反射点 X5之后，如果有表示反射部分成功，方向（ X5— X1）虽然是有利方向，但 X5前进过远，应收缩到介于 X4与 X5之间的某个点 X7。
上述两种从反射点向 X1方向后退的过程都称之为收缩。
如果收缩点优于原来的最劣点 X1，称收缩成功，并以收缩点取代原最劣点，构成新单纯形 {X7,X2,X3}或 {X8,X2,X3}；否则，称之为收缩失败，舍弃收缩点。
（ 4）缩边 —— 若收缩失败，则应压缩当前单纯形的边长：令最优点 X3不动，而其余顶点向 X3方向压缩，使边长缩短（通常缩短一半），以产生新单纯形。如下图所示，点 X1压缩到点 X9，
点 X2压缩到点 X10，得新单纯形 {X9,X10,X3}，这一过程称之为缩边。
二、单纯形替换算法设初始点为 X0，初始边长 h,ei为坐标轴方向的单位向量
,预定正数
,,,2,1 ni 21,
（ 2）比较各项点 Xi的函数值，挑出其中的最优点，记为 XL；最劣点，记 XH；次差点，记为 Xw；
（ 3）求反射中心
21 nn XX 和反射点
)(
1
112
)(
0
1
Hnnn
n
Hi
i
in
XXaXX
X
n
X
其中,a>0，通常取 a=1；
（ 1）令 },,,{,,,2,1,
100 nii XXXniheXX 构造单纯形；
输出 XL，为原问题近似极小点；否则，转（ 2）。
构造新单纯形；
5.0
（ 4）根据不同 情 况，分别进行扩张，
收缩或缩边，其中收缩因子
1
1
2
1
m a x
)()(
Li
n
i
Li
XX
XfXf（ 5）如果满足表 1 无约束优化方法搜索方向之间的相互联系
—— 间接法
kkdg
1[]k k kd G g
1[]k?G
k k kd Q g
1
11
[]
[]
k T k
k
k T k
gdQI
gg
k k kd A g
11k k kA A A
1[]kkAG
搜索方向 函数梯度的修正因子 所用目标函数信息梯度法 I（ 单位阵 ） 一阶导数
（ 阻尼 ） 牛顿法二阶导数共轭梯度法 一阶导数变尺度法 一阶导数，使
（海赛矩阵的逆阵）
无约束优化方法
—— 间接法总结
1、梯度法方向 负梯度 用到一阶导数适合于精度不高或用于复杂函数寻找一个好的初始点
2、牛顿法用到一阶导数和海色矩阵，具有二次收敛性要求海色矩阵奇异，且维数不宜太高
3、共轭梯度法用到一阶导数，具有二次收敛性
4、变尺度法收敛快，效果好，被认为是目前最有效的无约束优化方法。适用于维数较高，具有一阶偏导数的目标函数
1、坐标轮换法计算效率较低适合维数较低，目标函数无导数或导数较难求得
2、步长加速法同坐标轮换法，对目标函数的性态的适应性更好
3,Powell法具有二次收敛性，收敛速度较快，可靠性高，被认为是直接法中最有效的方法之一
4、单纯形法思路清楚，收敛慢无约束优化方法
—— 直接法总结无约束优化上机
Powell法优化设计程序 —— 与一维搜索黄金分割法组合题目：编程求解函数的极小点 x*。
22
1 2 1 1 2( ) 2 4 2f x x x x xx
初始点 x0=[1,1]T，迭代精度 。0,0 0 1
上机地点,4109(材控、装控）； 4211（机自）
时间：周一晚 6:00~9:30
