最优化理论与方法11
d
1
1 0
,
d2
0 1
初始步长1。 2。 1， 3， 0.5
探测：第一轮（ij沿方向d i进行第j次探测所用步长）
y1
x1
0 0
,
f
(
y1 )
17
沿d 1探测：y1
11d 1
0 0
1
1 0
1 0
f ( y1 11d1) 12 f ( y1) 成功
f ( y2)
故，令y3
y2
e2
3/2 1/ 2
第1轮探测完成，由于f ( y3 ) f ( x1)，
故得第2个基点
x2
y3
3/2 1/ 2
再沿x2 x1进行模式移动，
y1
x2
(x2
x1)
1 1
模式移动后，立即从得到的点y1出发，
进行第2轮探测移动，探测情况如下.
第二轮：
初始数据为
y1
1 0
.
f ( y1) 12, 12 3, 22 0.5
先从 y1出发，沿d1探测：
y1
12 d 1
1 0
3
1 0
4 0
f ( y1 12d1) 9 f ( y1) 令:13 12 9
y j1 y j jd j j : j
若f ( y j jd j ) f ( y j ),则令
y j1 y j
j : j
3.若j n,则置j : j 1,转步骤2,否则,转4.
4.若f ( yn1) f ( y1),则令y1 yn1,置j 1, 转2,如果 f ( yn1) f ( y1), 转5 5.若f ( yn1) f ( xk ).转6;否则,如果对每个j,成立
无约束最优化的直接方法
2010-4-26
直接方法与使用导数的方法 相比，一般来说，收敛比较慢， 但是，它对目标函数不要求导数 存在，迭代比较简单，编制程序 一般也比较简单，根据数字计算 的经验，对于变量不多的问题， 能够收到较好的效果。
主要内容：
模式搜索法 Rosenborck方法（转轴法） Powell方法
步长，加速固子 1，缩减率 （0，1），允许 误差 0, 置y1 x1, k 1, j 1. 2.如果f ( y j e j ) f ( y j ),则令
y j1 y j e j
转4；否则转3，
3.若f ( y j e j ) f ( y j ),则令 y j1 y j e j
e1 (1, 0)T , e2 (0,1)T
1 , 1, 1
2
2.
先在x1周围进行探测移动，令y1 (2, 0)T，探测
情况如下：f ( y1) 81,
y1
e1
2 0
1 2
1 0
5/2 0
,
f
(
y1
e1 )
197
9 16
令12 11 3
y2
y1 11d1
1 0
再从y2出发，沿d 2探测：
y2
21
d2
1 0
1
0 1
ቤተ መጻሕፍቲ ባይዱ1 1
f ( y2 21 d 2 ) 22 f ( y2 ) 失败
令：22 21 0.5
y3
y2
1 0
_j
单位化:d
qj
P qj P
j
pj
j 1
q p
j
j1 i1
(qi (qi
)T )T
qj qi
qi
j2
_1 _ 2
_n
新方向为d , d ,L d .
例：用转轴法解下列问题
min f ( x) (x1 3)2 2(x2 2)2 解：取初始点x1 (0, 0)T , 初始搜索方向
d j d j,
j
0 j
,
j 1, 2,L
n
置y1 xk1, k : k 1, j 1,返回步骤2.
Powell方法
在算法的每一阶段，先依次沿着已知的n个方 向搜索，得一个最好点，然后沿本阶段的初点 与该最好点连线方向进行搜索，求得这一阶段 的最好点，再用最后的搜索方向取代前n个方 向之一，开始下一阶段的迭代。
k k 1, j 1,转2
(转轴法) Rosenborck方法
Rosenbrock方法每次迭代包括探测阶段和构造 搜索方向两部分内容。探测阶段中，从一点出 发，依次沿n个单位正交方向进行探测移动，一 轮探测之后，再从第1个方向开始继续探测。经 若干轮探测移动，完成一个探测阶段。然后，构 一组新的单位正交方向，称为转轴，在下一次迭 带中，将沿这个方向进行探测。
转4；否则，令 y j1 y j
转4. 4.若j n, j j 1, 转2；否则，转5 5.若f ( yn1) f ( xk ), 转6；否则，转7
6. xk1 yn1, y1 xk1 ( xk1 xk )
k k 1, j 1,转2.
7.若 ，停止，得xk，否则， ，y1 xk，xk1 = xk
并从y2出发，沿e2探测。 如果沿 e1也失败，令
y2 y1
再从y2出发，沿e2探测，直至沿n个坐标方向 探测完毕，得到点yn1.
如果f ( yn1) f ( x1),则yn1作为新的基点， 记作x2 yn1. 下一步，沿x2 x1方向作模式搜索，令
y1 x2 ( x2 x1)
f ( y1)
失败
y1
e1
3/ 0
2
f
(
y1
e1
)
25
9 16
f ( y1)
成功
故，
令
y2
=y1
e1
3/ 2 0
从y 2出发，沿e 2 探测：
y2
e2
3/ 0
2
1 2
0 1
3/2 1/ 2
f (y2
e2
)
15
9 16
2d 2
4
1 0
2
0 1
4 2
p2
2d 2
0 2
将p1 p2正交化,得:
q1
4 2
,
单位化得
q2
4
5 8
5
d1
2 5
-
1 5
T
,d
2
1 5
-
2
T
5
算法步骤
1.给定初始点x1 Rn ,单位正交方向
| j | ,则停止计算,xk作为最优解的估值,若不
满足终止准则,则令y1 = yn1,置j 1,转2.
6.令xk1 yn1, 若 P xk1 xk P ,则取xk1作为 极小点的估计,停止计算;否则,计算1, 2,L , n,
构造新的正交方向d1, d 2,L , d n ,并令
4 0.5
f ( y3) f ( y1),故进行下一轮探测
第三轮探测：
y1
4 0.5
f ( y1) 5.5, 13 9, 23 1.5
L
得x 2
4 2
求新的转轴方向
x2
x1
4 2
0 0
4 2
p1
1d 1
算法步骤
1.给定初始点x0, n个线形无关的方向
d (1,1) , d (1,2) ,L , d (1,n) 允许误差 >0,置k =1.
2.置x(k,0) xk1,从x(k,0)出发,依次沿方向 d (k,1) , d (k,2) ,L , d (k,n)进行搜索,得到点
x(k ,1) , x(k ,2) ,L x(k,n) 沿着方向d (k,n1) x(k,n) x(k,0)作一维 搜索,得到点xk .
y3
y2
1 1
比较：f ( y3) f ( x2 )
x3
y3
1 1
从x3出发，作模式移动，
y1
x3
（x3
x2)
1/ 2 3/ 2
从y1作探测移动失败,退回x3, 减小 ,
直到 满足精度.
