第三章一维搜索方法 §3-1引言 §3-2确定最优解所在区间的进退法 §3-3一维搜索的区间消去方法 s3-4一维搜索的插值类方法
§3-1 引言 §3-2 确定最优解所在区间的进退法 §3-3 一维搜索的区间消去方法 §3-4 一维搜索的插值类方法
§3-1引言 当采用数学规划法寻求多元函数的极值点时, 一般要进行一系列如下格式的迭代计算: =x4+as(k=0,1,2,…) 当方向s4给定,求最佳步长c4就是求一元函数: f(x=f(x+as=o(a, 的极值问题,这一过程被称为一维搜索
当采用数学规划法寻求多元函数的极值点时， 一般要进行一系列如下格式的迭代计算: 1 ( 0,1,2, ) k k k k s k x x 当方向 给定，求最佳步长 就是求一元函数 : k s k 1 ( ) ( ) ( ) k k k k k f f s x x 的极值问题，这一过程被称为一维搜索
维搜索方法解析法高等数学已学过,即 利用一维函数的极值条件: 9(a)=0,求a 维搜索方法数值解法是讲解的重点! 维搜索方法数值解法分类∫试探法 插值法 维搜索也称直线搜索。这种方法不仅对 于解决一维最优化本身具有实际意义,而且也 是解多维最优化问题的重要支柱
一维搜索也称直线搜索。这种方法不仅对 于解决一维最优化本身具有实际意义，而且也 是解多维最优化问题的重要支柱。 一维搜索方法解析法高等数学已学过，即 利用一维函数的极值条件： * * ( ) 0 k k ， 求 一维搜索方法数值解法分类 试探法 插值法
§3-2确定最优解所在区间的进退法 维搜索的基本思想 1、单谷(峰)区间 在给定区间内仅有一个谷值的函数称为单谷函 数,其区间称为单谷区间。 函数值:“大一小 大 图形:“高—低—高” 单谷区间中一定能求得 一个极小点 2.找初始单谷区间是 维搜索的第一步; 第二步使区间缩小
1、单谷(峰）区间 在给定区间内仅有一个谷值的函数称为单谷函 数，其区间称为单谷区间。 O f( a ) a x* b x 函数值： “大－小－ 大” 图形： “高—低—高” 单谷区间中一定能求得 一个极小点 2. 找初始单谷区间是 一维搜索的第一步； 第二步使区间缩小
确定初始单谷区间的进退法 基本思想: 对八x)任选一个初始点a1及初始步长h,通过比较这两 点函数值的大小,确定第三点位置,比较这三点的函数 值大小,确定是否为“高—低—高”形态。 步骤: (1)选定初始点a,初始步长h=h,计算y1=f(a1), y2=f(alth 2)比较y和y2。 (a)如y1>y2,向右前进;加大步长h=2h,转(3)向前 (b)如y1<y2,向左后退;h=-h,将a1与a2,y1与y2的 值互换。转(3)向后探测; (c)如y1=y2,极小点在a1和a1+h之间
基本思想： 对f(x)任选一个初始点a1及初始步长h， 通过比较这两 点函数值的大小，确定第三点位置，比较这三点的函数 值大小，确定是否为 “高—低—高” 形态。 步骤： （1）选定初始点a, 初始步长h＝h0，计算 y1＝f(a1)， y2＝f(a1＋h)。 （2）比较y1和y2。 （a）如y1>y2, 向右前进；加大步长 h＝2 h ，转（3）向前； （b）如y1<y2, 向左后退；h＝－ h0， 将a1与a2，y1与y2的 值互换。转（3）向后探测； （c）如y1＝y2，极小点在a1和a1＋h之间
(3)产生新的探测点a3=a1+h,y3=f(a3); (4)比较函数值y2与y3: (b)如y2>y3,加大步长h=2h,a1=a2 a2=a3,转(3)继续探测。 (a)如y2<y3,则初始区间得到: a=mina1,n3,b=maxa3,ll,函数最 小值所在的区间为a,b
(3）产生新的探测点a3＝a1＋h，y3＝f(a3); (4) 比较函数值 y2与y3： （b）如y2>y3, 加大步长 h＝2 h ，a1=a2, a2=a3,转（3）继续探测。 （a）如y2<y3, 则初始区间得到： a=min[a1,a3]， b=max[a3,a1]，函数最 小值所在的区间为[a， b]
输入初始自变量和 步长值x1h 计f(x)和 x2=x+九∫(x2) Y f(x1)<∫( 力=-h, 力=2xh, 与x2·f(x1)与f(x2)互换 x, +h+ x2=2+内,计算f(x2) 计算f(x) Ne f(x2)<f(x2) [x,x满足高一低一高 做代换x1=x2,x2=2 min( xI, x3), b=max xI, xs)+ f(x2)=f(x2),x2=x+h 计算f(x3) 返回4 进退法程序框图
§3-3一维搜索的区间消去方法 基本思想 搜索区间确定之后,采用区间消去法逐步缩短 搜索区间,从而找到极小点的数值近似解 假定在搜索区间内[a,b]任取两点a1,b1 n=f(a1),几2=f(b1) f(bu fau (a1) fb1 fay f(bu b
l 搜索区间确定之后，采用区间消去法逐步缩短 搜索区间，从而找到极小点的数值近似解。 l 假定在搜索区间内[a,b] 任取两点a1,b1; f1＝f（a1）， f2＝f（b1） §3-3 一维搜索的区间消去方法 一、基本思想 f(a1) f(b1) f(a1) f(b1) f(a1) f(b1) a1 a a1 b1 b a a1 b1 b a b1 b
n=f(a1),n2=f(b1) ●(1)如1n2,则缩小的新区间为a1,b; ●(3)如n=2,则缩小的新区间为a1,b1l f(au) f(, fau Abu fau f(bu) b 综合为两种情况: ①若f(a)<f()则取ab]为缩短后的搜索区间。 ②若f(a)≥f(b)则取[an,b为缩短后的搜索区间
l f1＝f（a1）， f2＝f（b1） l (1)如f1f2, 则缩小的新区间为[a1 ,b]; l (3)如f1=f2, 则缩小的新区间为[a1 ,b1] f(a1) f(b1) f(a1) f(b1) f(a1) f(b1) a1 a a1 b1 b a a1 b1 b a b1 b 综合为两种情况： ①若 则取 为缩短后的搜索区间。 ②若 则取 为缩短后的搜索区间。 1 1 f (a ) f (b ) 1 [ a , b ] 1 1 f (a ) f (b ) 1 [a ,b]
二、黄金分割法 黄金分割法适用于[a,b区间上的任何单谷 函数求极小值问题。对函数除要求“单谷”外不 作其他要求,甚至可以不连续。因此,这种方法 的适应面相当广 黄金分割法也是建立在区间消去法原理基础 上的试探方法。 在搜索区间内[a,b适当插入两点ax,a2,将区 间分成三段; 利用区间消去法,使搜索区间缩小,通过迭代 计算,使搜索区间无限缩小,从而得到极小点的数 值近似解
l 黄金分割法适用于[a,b]区间上的任何单谷 函数求极小值问题。对函数除要求“单谷”外不 作其他要求，甚至可以不连续。因此，这种方法 的适应面相当广。 l 黄金分割法也是建立在区间消去法原理基础 上的试探方法。 1 2 l 在搜索区间内[a,b]适当插入两点 , ，将区 间分成三段； l 利用区间消去法，使搜索区间缩小，通过迭代 计算，使搜索区间无限缩小，从而得到极小点的数 值近似解