一维搜索.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 一维搜索(优化)方法,一维搜索方法概述,初始搜索区间的确定,区间消去法原理,一维搜索的最优化方法 1、分割法 2、二次插值法,教学要求：1、掌握初始搜索区间的确定方法 2、掌握 分割法 3、掌握二次插值法,复 习,迭代公式：,x,(k+1),=x,(k),+a,（k）,S,(k),迭代点,x,(k),，当,k=0,时，,X,(0),称为初始点,搜寻方向,S,(k),步长,a,（k）,优化计算数值解法的迭代过程,一维搜索方法概述,在优化设计的迭代运算中，在搜索方向,S,(k),上寻求最优步长,a,（k）,的方法称一维搜索法。实际上一维搜索法就是一元函数极小化的数值迭代算法，其求解过程称为一维搜索。,一维搜索法是非线性优化方法的基本算法，例如：下图所示的二维优化的例子。,一维搜索方法概述,x,2,x,1,o,(k),S,(k),S,(k),x,(k+1),x,(k),x,*,F(x,(k),),F(x,(k+1),),二维优化问题中的一维搜索,注意：二维优化问题的一维搜索方向 是由具体的优化方法决定的，迭代公式,因此，二维优化问题就可以表示为一维优化问题,min f(),。,主要问题：1.初始区间,2.在区间中寻优,初始搜索区间的确定,在一维搜索时，需要,确定函数,f(),的极小点所在的初始搜索区间,a,b,。,因此搜索区间必须是,单峰区间,，即该区间内的函数值呈现“高-低-高”的趋势。,如图所示，通过将搜索区间,a,b,逐渐缩小，直至足够小，就可以得到近似最优点。,单峰区间有：,确定初始搜索区间的进退法,一、试探搜索极小点位置,设函数为,y=f,(,),给定初始点为,a,（0）,，选定的初始步长为,h,。,(最好取,a,（0）,接近于极小点,h,0),令,a,（1）=,a,（0）,由初始点,a,（1）,沿,a,轴正向取,a,（2）,点，,a,（2）,=,a,（1）,+h,，计算,a,（1）,、,a,（2）,的函数值,f,1,、f,2,，比较,f,1,、f,2,的大小，则极小点的位置有如图所示两种情况,1、若,f,2,f,1,(或者,y,2,f,1,(或者,y,2,y,1,)，则极小点位于 左方，应反向后退搜索。,二、前进搜索(,f,2,f,1,),(如图3-2),以,a,（,2,）,为初始点,，,以,h,为步长,前进搜索得到第三个试点方向的,a,（,3,）,，,a,（,3,）,=,a,（,2,）,+h,=,a,（,1,）,+2h,，其函数值,f,3,与,f,2,比较有如下情况,1、若,f,2,f,2,f,3,，则继续前进搜索，各点变换如下：,a,（,1,）,=,a,（,2,）,f,1,=,f,2,a,（,2,）,=,a,（,3,）,f,2,=,f,3,然后,步长加倍，前进搜索得到第三个试点方向的,a,（,3,）,，重复上述比较,f,2,与,f,3,的大小，直至出现,f,1,f,2,f,1,),(如图3-3),令,h,=,-,h,，并将,a,（1）,与,a,（2）,对调，取得,a,（3）,点，,a,（3）,=,a,（2）,+h,，其函数值,f,3,与,f,2,比较有如下情况：,1、若,f,2,f,2,f,3,，则继续后退搜索，各点变换如下：,a,（,1,）,=,a,（,2,）,f,1,=,f,2,a,（,2,）,=,a,（,3,）,f,2,=,f,3,然后步长加倍，前进搜索得到第三个试点方向的,a,（,3,）,，重复上述比较,f,2,与,f,3,的大小，直至出现,f,1,f,2,f3则新区间为a,a（1）为保持相同的区间缩短率，应有（1-）/=故：1-=2,2+-1=0,由此可得：,分割法可使相邻两次搜索区间都具有相同的缩短率。,a（1）=b-0.618(b-a),a（2）=a+0.618(b-a),二、分割法的搜索过程,1、给出初始搜索区间a,b及收敛精度。,2、在区间a,b内取两个试算点,a（1）=b-(b-a),a（2）=a+(b-a),计算函数值f1=f(a（1）)，f2=f(a（2),3、检查是否满足收敛条件，若满足转第五步，否则进行第四步,4、比较f1和f2大小，若f2f1，取a,a（2）新区间。转第三步,5、则取最后两点的平均值作为极小点的近似解。,三、分割法的流程图,给定：a,b,输出：,+,-,_,四、例题,用 分割法求函数的极小点，初始区间a，b=2,10，收敛精度2,解：第一次迭代,1、初始区间,a，b=2，10,2、在区间,2，10,中取两点，并计算函数值,944，计算新的试算点,a（2）=a+0.,分割法可使相邻两次搜索区间都具有相同的缩短率。,5、则取最后两点的平均值作为极小点的近似解。,x1=b-(b-a),解：第一次迭代,将区间分为三段，通过比较函数值的大小，删除其中的一段，使搜索区间缩短。,3、检查是否满足收敛条件，若满足转第五步，否则进行第四步,三、分割法的流程图,不同点：试验点位置的确定方法不同。,若f2f1，取a,a（2）新区间。,二、前进搜索(f2,f,1,，故取新的区间为,2，6.944,，计算新的试算点,第二次迭代,x,1,=b-,(b-a)=,x,2,=a+0.618(b-a),f,1,=f(x,1,f,2,=f(x,2,收敛判断,需要继续迭代,4、比较,f,1,和,f,2,的大小，因为,f,2,0的情形。,1、若f2 f2f1，故取新的区间为2，6.,f2=f(x2,一、分割法的原理,x,2,x,P,*,根据相对于的位置，并比较,f,p,*,与,f,2,，区间的缩短可以分为以下四种情况。具体见,p57,表,第一行,h0,的情形。,入口,f,2,f,P,*,?,f,2,f,P,*,?,出口,Y,Y,Y,N,N,N,a,b,c,d,区间缩短流程图,六、终止准则,当满足给定精度时，计算终止，并令,七、二次插值算法流程图,八、例题,用二次插值法求函数的极小点，给定初始区间,2，10，,解：第一次迭代,取,x,2,=(,x,1,+,x,3,)/2=(2+10)/2=6,计算,f,1,=12，,f,2,，,f,3,=12,得,x,p,*=6，,f,(,x,p,由于,x,p,*=,x,2,，取一点,(,x,1,+,x,2,)/2=4,，,因为：,f,(,x,1,+,x,2,)/2)=9,x,2,f,(,x,p,*),需要继续迭代一次即可达到精度,谢谢观看,