无约束最优化问题的直接方法 1.模式搜索法 2. Powell算法 3.单纯形替换法
无约束最优化问题的直接方法 1. 模式搜索法 2. Powell 算法 3. 单纯形替换法
无约束最优化问题的直接方法 无约束最优化问题 直接方法不用计算导数,只需计算函数值的方法
无约束最优化问题的直接方法 无约束最优化问题min f (x); 直接方法：不用计算导数，只需计算函数值的方法
模式搜索法( Hooke- Jeeves方法,196年) 1.基本思想:算法从初始基点开始,交替实施两种搜索:辅向 搜索和模式搜索。轴向搜索依次沿n个坐标轴的方向进行, 用来确定新的基点和有利于函数值下降的方向。模式搜索则 沿着相邻两个基点的连线方向进行,试图使函数值下降更快。 2.算法分析 问题minf(x); 令e1=(0,…,0,1,0,…,0),j=1,2,…,n表示n个坐标轴方向。 给定初始步长δ,加速因子a。任取初始点x作为第一个基点 以下用x/表示第j个基点
一. 模式搜索法 （Hooke − Jeeves 方法，1961年） 基本思想： 算法从初始基点开始，交替实施两种搜索：轴向 搜索和模式搜索。轴向搜索依次沿n个坐标轴的方向进行， 用来确定新的基点和有利于函数值下降的方向。模式搜索则 沿着相邻两个基点的连线方向进行，试图使函数值下降更快。 1. 2. 算法分析 问题 min f (x); 令 e j = (0, ,0,1,0, ,0) T , j = 1,2, ,n 表示n个坐标轴方向。 给定初始步长 ，加速因子。任取初始点x 1作为第一个基点。 以下用x j 表示第 j个基点
在每一轮轴向搜索中,用y表示沿第个坐标轴e1方向搜索时 的出发点。 轴向搜索 令y2=x1 沿e1方向搜索 ,(3) 如果f(y+e1)<∫(y),则令 y=y+8e, 否则,如果f(y-8e1)<f(y2), 则令y2=y2-8e 否则,令y2=y 再从y2出发,仿上沿e2进行搜索得到y3
在每一轮轴向搜索中，用y i表示沿第i个坐标轴ei 方向搜索时 的出发点。 轴向搜索： 令 y 1 = x 1 。 O 1 e 2 e (1) (1) x = y 沿e1方向搜索： 如果 f ( y 1 + e1 ) f ( y 1 )，则令 ; 1 2 1 y = y + e 否则，如果 f ( y 1 − e1 ) f ( y 1 )， ; 1 2 1 则令 y = y − e 否则，令 y 2 = y 1 。 (2) y 再从 y 2出发，仿上沿e2 进行搜索得到y 3 ， (3) y
依次进行搜索,直到得到点y+。(一轮轴向搜索结束 如果∫(y+)≥f(x2),则缩小步长δ,仍以x为起点进行新的 轴向搜索。否则,进行模式搜索 模式搜索: x1)=p{1) 如果∫(y+)<f(x4), ,(3)(2) 则令x2=y x2-x1方向可能有利于函数 值下降,因此下一步沿x2-x 方向进行模式搜索。 即令y=x2+a(x2-x)
O 1 e 2 e (1) (1) x = y (2) y (3) y 依次进行搜索，直到得到点 y n+1 。 (一轮轴向搜索结束。) 模式搜索： ( ) ( ) , 1 1 f y f x n 如果 + 则令 x 2 = y n+1 。 x 2 − x 1方向可能有利于函数2 1 值下降，因此下一步沿x − x 方向进行模式搜索。 即令 y 1 = x 2 + ( x 2 − x 1 )。 (2) = x (1) y 如 果 f ( y n+1 ) f (x 1 ),则缩小步长 ，仍以x 1为起点进行新的 轴向搜索。否则，进行模式搜索
如何判断模式搜索是否有效? 以y为起点进行下一轮轴向搜索,所得的点仍记为y+t 如果∫(y+)<f(x2),表明此次模式搜索成功令 仿上继续进行迭代。 如果∫(y+)≥f(x2),表明此次 模式搜索失败,返回基点x2, 进行下一轮轴向搜索 O
如何判断模式搜索是否有效？ 以 y 1为起点进行下一轮轴向搜索，所得的点仍记为 y n+1 。 如 果 f ( y n+1 ) f (x 2 ),表明此次模式搜索成功， 令 x 3 = y n+1 。 仿上继续进行迭代。 如果 f ( y n+1 ) f (x 2 ),表明此次 进行下一轮轴向搜索。 模式搜索失败，返回基点x 2 ， O 1 e 2 e (1) (1) x = y (2) y (3) y (2) = x (1) y (2) y (3) = y
x 1 x 2 x 3 x 4 x 5 x 6 x
模式搜索法: (1)给定初始点x1∈R",初始步长δ,加速因子a≥1,缩减率 B∈(0,1),精度ε>0。令y2=x2,k=1,=1 (2)轴向搜索: 如果∫(y+e)<f(y),则令y=y+6e,转(3); 如果∫(y-0:1)<f(y),则令y=y1-6e1,转(3); 否则,令y+1=y。 (3)若j<n,则令j:=j+1,转(2) 如果∫(y+)<f(x),转(4);否则,转(5) (4)模式搜索:令x4+ cP+ ,y=x l+a(x k+1二x 令k:=k+1,=1,转(2) (5)如果δ≤E,停止,得到点x();否则,令8:=B6, k,k+1 k J≡X",x 令k:=k+1,=1,转(2)
模式搜索法： (1) 给定初始点x 1 R n ,初始步长 ，加速因子 1，缩减率 (0,1), 精度 0。 令 y 1 = x 1 ,k = 1, j = 1。 (2) 轴向搜索： 如 果 f ( y j + e j ) f ( y j ),则 令 y j+1 = y j + e j ,转（3） ； 如 果 f ( y j − e j ) f ( y j ),则 令 y j+1 = y j − e j ,转（3） ； 否则，令 y j+1 = y j 。 (3) 若 j n ，则令 j := j + 1,转(2)。 如果 f ( y n+1 ) f (x k ),转(4)；否则，转(5)。 (4) 模式搜索：令 x k +1 = y n+1 , y 1 = x k +1 + ( x k +1 − x k )。 令 k := k + 1, j = 1,转（2）。 (5) 如果 ,停止，得到点x (k)；否则，令 := , y 1 = x k , x k +1 = x k 。 令 k := k + 1, j = 1,转（2）
注将轴向搜索和模式搜索中的固定步长改为用—维搜索确定步长, 算法仍然收敛。 例1.用模式搜索法求解问题 min f(x)=xi+x2 取初始点x=(1,1),初始步长δ=0.25,加速因子a=1,缩减 率B=02。 解:第1轮迭代: 令y=x2=(1,1),则f(y)=2。 f∫(y+e1)=25625>f(y3), ∫(y-oe1)=15625<∫(y), ∴y2=y1-8e1=(0.75,1)
注 将轴向搜索和模式搜索中的固定步长改为用一维搜索确定步长， 算法仍然收敛。 例1. 用模式搜索法求解问题 min f (x) = x1 2 + x2 2 。 (1,1) , 0.25 1, 1 取初始点 = 初始步长 = ，加速因子 = T x 缩减 率 = 0.2。 解: 第1轮迭代： 令 y 1 = x 1 = (1,1) T , 则 f ( y 1 ) = 2。 ( ) 2.5625 ( ), 1 1 1 f y + e = f y ( ) 1.5625 ( ), 1 1 1 f y − e = f y y 2 = y 1 − e1 = (0.75,1) T
f(y2+e2)=2125>f(y2), ∫(y2-Se2)=1.125<∫(y2), y=y2-6e2=(0.75,0.75)。 ∫(y)<∫(x), ∴令x=y 取加速方向d1=x2-x1=(-0.25,-0.25)。 模式搜索: y=x2+ad=(0.5,0.5)
( ) 2.125 ( ), 2 2 2 f y + e = f y ( ) 1.125 ( ), 2 2 2 f y − e = f y y 3 = y 2 − e2 = (0.75,0.75) T 。 ( ) ( ), 3 1 f y f x 令 x 2 = y 3 。 取加速方向d 1 = x 2 − x 1 = ( − 0.25,− 0.25) T 。 模式搜索：y 1 = x 2 + d 1 = (0.5,0.5) T