第五次模式搜索法和Powell算法.pdf

无约束最优化问题的直接方法
1. 模式搜索法
2. Powell 算法
3. 单纯形替换法
无约束最优化问题
xf ;)(min
直接方法：不用计算导数，只需计 算函数值的方法。
模式搜索法（Hooke  Jeeves 方法，1961 年）
.1 基本思想：算法从初始基点开始， 交替实施两种搜索：轴 向
搜索和模式搜索。轴向 搜索依次沿 n 个坐标轴的方向进行，
用来确定新的基点和有 利于函数值下降的方向 。模式搜索则
沿着相邻两个基点的连 线方向进行，试图使函 数值下降更快。
.2 算法分析
T
令 e j    j  ,,2,1,)0,,0,1,0,,0( 表示 nn 个坐标轴方向。
给定初始步长  ，加速因子  。任取初始点 x )1( 作为第一个基点。
以下用 x j )( 表示第 j 个基点。
i)(
在每一轮轴向搜索中， 用 y 表示沿第 i 个坐标轴 ei 方向搜索时
的出发点。
轴向搜索： e2
)1()1(
令  xy 。  yx )1()1( y )2(
沿e 方向搜索：
1 y )3(
)1( )1(
如果   1  yfeyf )()( ，则令
)1()2(
   eyy 1 ;
)1( )1(
否则，如果   1  yfeyf )()( ，
)1()2( O e1
则令    eyy 1 ;
否则，令  yy )1()2( 。
)2( )3(
再从 y 出发，仿上沿 e2 进行搜索得到 y ，
依次进行搜索，直到得到点 y n )1( 。 ( 一轮轴向搜索结束。 )
如果 n )1(  xfyf )1( ,)()( 则缩小步长  ，仍以 x1为起点进行新的
轴向搜索。 否则，进行模式搜索。
e2
模式搜索：
)1()1( )2(
如果 n )1(  xfyf )1( ,)()(  yx y
)3( )2(
则令  yx n )1()2( 。 y  x
 xx )1()2( 方向可能有利于函数
y )1(
值下降，因此下一步沿  xx )1()2(
O
方向进行模式搜索。 e1
即令  )2()1(   xxxy )1()2( )( 。
如何判断模式搜索是否 有效？
以 y )1( 为起点进行下一轮轴向 搜索，所得的点仍记为 y n )1( 。
如果 n )1(  xfyf )2( ,)()( 表明此次模式搜索成功 ，令
e2
 yx n )1()3( 。仿上继续进行迭代。
 yx )1()1( y )2(
n )1( )2(
如果