无约束最优化问题的直接方法 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为起点进行新的 轴向搜索。否则，进行模式搜索