第三章 一维搜索方法PPT讲稿.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《第三章 一维搜索方法PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《第三章 一维搜索方法PPT讲稿.ppt(35页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第三章 一维搜索方法第1页,共35页,编辑于2022年,星期二求解求解一维目标函数一维目标函数一维目标函数一维目标函数最优解的过程,称为最优解的过程,称为一维优化一维优化一维优化一维优化(一维一维搜索搜索),所使用的方法称为,所使用的方法称为一维优化方法一维优化方法一维优化方法一维优化方法。由前由前数值迭代法数值迭代法数值迭代法数值迭代法可知,求某目标函数的最优值时,可知,求某目标函数的最优值时,迭代过迭代过程程每一步的格式都是从每一步的格式都是从某一定点某一定点 出发,沿着某一使目出发,沿着某一使目标函数下降的规定标函数下降的规定方向方向 搜索,以找出此方向的搜索,以找出此方向的极小点极小点
2、 。这一过程是各种最优化方法的一种。这一过程是各种最优化方法的一种基本过程基本过程基本过程基本过程。一维搜索方法一维搜索方法一维搜索方法一维搜索方法一般一般分两步进行分两步进行分两步进行分两步进行:首先首先确定确定一个包含函数极小点的一个包含函数极小点的初始区间初始区间,即,即确定确定 函数的搜索区间,该区间必须是函数的搜索区间,该区间必须是单峰区间单峰区间;然后采用缩小区间或插值逼近的方法然后采用缩小区间或插值逼近的方法得到得到最优步长最优步长,最终求出该搜索区间内的最终求出该搜索区间内的一维极小点一维极小点。3.1 3.1 搜索区间的确定搜索区间的确定第2页,共35页,编辑于2022年,星
3、期二根据函数的变化情况,可将根据函数的变化情况,可将区间区间区间区间分为分为单峰区间单峰区间和和多峰区间多峰区间。所谓。所谓单峰区间单峰区间单峰区间单峰区间,就是在该区间内的函数变化只有一个峰值,即函数的极小,就是在该区间内的函数变化只有一个峰值,即函数的极小值。值。即在即在单峰区间单峰区间单峰区间单峰区间内的内的极小值点极小值点极小值点极小值点X X*的的左侧左侧:函数呈:函数呈下降趋势下降趋势下降趋势下降趋势,而在而在单峰区间单峰区间单峰区间单峰区间内的内的极小值点极小值点X*的的右侧右侧:函数呈:函数呈上升趋势上升趋势。也就是说,也就是说,单峰区间单峰区间单峰区间单峰区间的函数值呈的函数
4、值呈“高高高高-低低低低-高高高高”的变化特征的变化特征。3.1 3.1 搜索区间的确定搜索区间的确定O f(a)b x*x a 第3页,共35页,编辑于2022年,星期二目目前前在在一一维维优优化化搜搜索索中中确确定定单单峰峰区区间间常常用用的的方方法法是是进退试算法进退试算法。进退试算法的进退试算法的进退试算法的进退试算法的基本思想基本思想基本思想基本思想为:为:1)1)按照一定的规律给出按照一定的规律给出若干试算点若干试算点,2)2)依次比较各依次比较各试算点的函数值试算点的函数值的大小,的大小,3)3)直到找到直到找到相邻三点相邻三点函数值按函数值按“高高-低低-高高”变化的变化的单峰
5、区间单峰区间为止为止3.1 3.1 搜索区间的确定搜索区间的确定第4页,共35页,编辑于2022年,星期二进退试算法的进退试算法的运算步骤运算步骤运算步骤运算步骤如下:如下:(2)将将0及及0+h 代入目标函数代入目标函数 f(x)进行计算并比较大小进行计算并比较大小(1)给定给定初始点初始点0和和初始步长初始步长h3.1 3.1 搜索区间的确定搜索区间的确定第5页,共35页,编辑于2022年,星期二 若若 ,则所计算的相邻三点,则所计算的相邻三点 的函数值已具的函数值已具“高高-低低-高高”特征,这时可确定特征,这时可确定 搜索区间搜索区间(3)若若 ,则表明极小点在试算点,则表明极小点在试
6、算点 的右侧,需做的右侧,需做前进试算前进试算。否则,将步长再加倍,并重复上述运算。否则,将步长再加倍,并重复上述运算。3.1 3.1 搜索区间的确定搜索区间的确定 在做在做前进运算前进运算时,为加速计算,可将步长时,为加速计算,可将步长h 增加增加2倍,并取计算新点为倍,并取计算新点为0+h+2h=0+3h第6页,共35页,编辑于2022年,星期二(4)若若 ,则表明极小点在试算点,则表明极小点在试算点 的左侧,需做的左侧,需做后退试算后退试算。在做后退运算时,应将在做后退运算时,应将步长变为步长变为-h,并从,并从 点出点出 发,得到后退点为发,得到后退点为 若若 ,则,则搜索区间搜索区间
7、可取为可取为否则,将步长加倍,继续后退,重复否则,将步长加倍,继续后退,重复上述步骤上述步骤,直到,直到满足满足单峰区间单峰区间条件为止。条件为止。3.1 3.1 搜索区间的确定搜索区间的确定第7页,共35页,编辑于2022年,星期二f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索区间确定搜索区间确定之后,采用区间消去法逐步之后,采用区间消去法逐步缩短搜索区间缩短搜索区间,找到极小,找到极小点的数值近似解。点的数值近似解。假定在搜索区间内假定在搜索区间内a,b 任取两点任取两点a1、b1,且且a1f2 f1f2 f1=f2 f(x)f(x)f(x)第8页,共35页,编辑于20
8、22年,星期二f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1(1)f1f2,新区间为新区间为a1,b;(3)如如f1=f2,新区间为新区间为a1,b1对于上述对于上述缩短后的新区间缩短后的新区间,可在其内再取一个,可在其内再取一个新点新点,然后将此点,然后将此点和该区间内剩下的那一点进行函数值大小的比较,以再次按照和该区间内剩下的那一点进行函数值大小的比较,以再次按照上述上述方法方法,进一步,进一步缩短区间缩短区间,这样不断进行下去,直到,这样不断进行下去,直到所保留的区间所保留的区间缩小到给定的误差范围内,而得到缩小到给定的误差范围内,
9、而得到近似最优解近似最优解。新区间为新区间为第9页,共35页,编辑于2022年,星期二ab a2a1 a2a a1f(a1)f(a2)f(a2)f(a1)b一、适用范围一、适用范围 适适用用于于a,b区区间间上上的的任任何何单单谷谷函函数数求求极极小小值值问问题题。对对函函数数除除要要求求“单单谷谷”外外不不作作其其他他要要求求,甚甚至至可可以以不不连连续续。适适应应面面相相当当广广。基本原理为基本原理为区间消去法区间消去法3.3 3.3 黄金分割法黄金分割法黄金分割法插入两点:黄金分割法插入两点:第10页,共35页,编辑于2022年,星期二黄金分割法还要求在保留下来的区间内再插入一点所形成的
10、黄金分割法还要求在保留下来的区间内再插入一点所形成的黄金分割法还要求在保留下来的区间内再插入一点所形成的黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段,与原来区间的三段具有相同的比例分布区间新三段,与原来区间的三段具有相同的比例分布区间新三段,与原来区间的三段具有相同的比例分布区间新三段,与原来区间的三段具有相同的比例分布 。3.3 3.3 黄金分割法黄金分割法第11页,共35页,编辑于2022年,星期二黄金分割法程序框图黄金分割法程序框图 开开 始始输入输入a,b,Y YN NY YN N结结 束束第12页,共35页,编辑于2022年,星期二例例 3-1 用黄金分割法求函数用
11、黄金分割法求函数f(x)=3x3-4x+2的极小点,的极小点,初始点初始点 x0=0,步长步长h=1,精度精度=0.2。解:解:1)确定初始区间确定初始区间 x1=x0=0,f1=f(x1)=2 x2=x0+h=0+1=1 f2=f(x2)=1 由于由于f1f2,应继续向前探测应继续向前探测 x3=x0+2h=0+2=2 f3=f(x3)=18 由于由于f2f3,可知初始区间已经找到,即可知初始区间已经找到,即 a,b=x1,x3=0,23.3 3.3 黄金分割法黄金分割法第13页,共35页,编辑于2022年,星期二2)用黄金分割法缩小区间用黄金分割法缩小区间 第一次缩小区间:第一次缩小区间:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三章 一维搜索方法PPT讲稿 第三 搜索 方法 PPT 讲稿
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内