一维搜索.pptx
《一维搜索.pptx》由会员分享,可在线阅读,更多相关《一维搜索.pptx(46页珍藏版)》请在咨信网上搜索。
1、1 1首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:51 18:51第三章第三章第三章第三章 一维搜索方法一维搜索方法一维搜索方法一维搜索方法3.1概述概述3.2搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理3.3一维搜索的试探方法一维搜索的试探方法3.4一维搜索的插值方法一维搜索的插值方法重点2 2首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:51 18:513.13.1概述概述概述概述q回顾当采用数学规划法寻求多元函数 的极值点 时一般要进行一系列迭代计算:其中 为第 次迭代的搜索方向,为沿 搜索的最佳步长因子(通常
2、也称作最佳步长)。当方向 给定,求最佳步长 就是求一元函数 的极值问题,它称作一维搜索。3 3首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:52 18:52q求多元函数极值点,需要进行一系列的一维搜索。可见一维搜索是优化搜索方法的基础。q求解一元函数 的极小点 ,可采用解析解法,在用函数 的导数求 时,所用的函数 是仅以步长因子 为变量的一元函数,而不是以设计点 为变量的多元函数 。1.利用一元函数的极值条件 求 。4 4首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:52 18:522.为了直接利用 的函数式求解最佳步长因子 。可把
3、或它的简写形式 进行泰勒展开,取到二阶项,即 将上式对 进行微分并令其等于零,给出 极值点 应满足的条件 从而求得5 5首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:52 18:52这里是直接利用函数 而不需要把它化成步长因子 。的函数 。不过,此时需要计算 点处的梯度 和海赛矩阵 。解析解法的缺点需要进行求导计算。对于函数关系复杂、求导困难或无法求导的情况,使用解析法将是非常不便的。q因此,在优化设计中,求解最佳步长因子 主要采用数值解法,利用计算机通过反复迭代计算求得最佳步长因子的近似值。数值解法的基本思路是:首先确定 所在的搜索区间,然后根据区间消去法原理不
4、断缩小此区间,从而获得 的数值近似解。返回返回6 6首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:52 18:523.23.2搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理q欲求一元函数 的极小点 ,首先必须先确定 所在的区间。确定搜索区间的外推法在一维搜索时,我们假设函数 具有如右图所示的单谷性,即在所考虑的区间内部,函数 有唯一的极小点 。为了确定极小点 所在的区间 ,应使函数 的 值在 区间里形成“高低高”趋势。7 7首页上页下页末页结束2024/8/27 2024/8/27 周二周二
5、 18:53 18:53从 开始,以初始步长 向前试探。如果函数值上升,则步长变号,即改变试探方向。如果函数值下降,则维持原来的试探方向,并将步长加倍。区间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升时为止,即可找到搜索区间的终点。最后得到的三点即为搜索区间的始点、中间三点和终点,形成函数值的“高低高”趋势。单谷区间8 8首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:53 18:53q外推法(进退法)确定搜索区间的步骤:v1)试探搜索v2)前进搜索v3)后退搜索9 9首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18
6、:53 18:53右图表示沿 的正向试探。每走一步都将区间的始点、中间点沿试探方向移动一步(进行换名)。经过三步最后确定搜索区间 ,并且得到区间始点、中间点和终点 所对应的函数值 。正向搜索的外推法1010首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:53 18:53右图所表示的情况是:开始是沿 的正方向试探,但由于函数值上升而改变了试探方向,最后得到始点,中间点和终点 及它们的对应函数值 ,从而形成单谷区间为一维搜索区间 。1111首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:54 18:54上述确定搜索区间的外推法,其程序框图如下
7、图所示(P50)1212首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:54 18:54q要求一元函数 的极小点 ,在确定 所在的区间之后,就需要不断的缩小这个区间,直到确定 的近似解。区间消去法原理在搜索区间 内任取两点 ,并计算函数值 。于是将有下列三种可能情形:1.,如下图(a)所示。由于函数为单谷,所以极小点必在区间 内。2.,如下图(b)所示。同理,极小点应在区间 内。3.,如下图(c)所示,这时极小点应在 内。1414首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:54 18:54根据以上所述,只要在区间 内取两个点,算出它们
8、的函数值并加以比较,就可以把搜索区间 缩短成 或 。对于第一种情况,我们已算出区间 内 点的函数值,如果要把搜索区间 进一步缩短,只需在其内再取一点算出函数值并与 加以比较,即可达到目的。对于第二种情况,同样只需再计算一点函数值就可以把搜索区间继续缩短。1515首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:54 18:54第三种情形与前面两种情形不同,因为在区间 内缺少已算出的函数值。要想把区间 进一步缩短,需在其内部取两个点(而不是一个点)计算出相应的函数值再加以比较才行。如果经常发生这种情形,为了缩短搜索区间,需要多计算一倍数量的函数值,这就增加了计算工作量。
9、1616首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:55 18:55程序设计技巧为了避免多计算函数值,我们把第三种情形合并到前面两种情形中去。例如,可以把前面三种情形改为下列两种情形:1.若 ,则取 为缩短后的搜索区间。2.若 ,则取 为缩短后的搜索区间。从上述的分析中可知,为了每次缩短区间,只需要在区间内再插入一点并计算其函数值。如此反复进行下去,当搜索区间长度足够小时,可用区间内的某点作为极小点的近似值。q一维搜索方法的分类可以用不同的方法来确定的插入点的位置,这样就形成了不同的一维搜索方法。概括起来,可将一维搜索方法分成两大类:1717首页上页下页末页结束
10、2024/8/27 2024/8/27 周二周二 18:55 18:55试探法(直接法)按某种给定的规律来确定区间内插入点的位置。此点位置的确定仅仅按照区间缩短如何加快,而不顾及函数值的分布关系。属于试探法一维搜索的有黄金分割法,裴波纳契(Fibonacci)法等。插值法(函数逼近法、间接法)根据某些点处的某些信息,如函数值、一阶导数、二阶导数等,构造一个插值函数来逼近原来函数,用插值函数的极小点作为区间的插入点。属于插值法一维搜索的有牛顿法(切线法)、二次插值法(抛物线法)、三次插值法等。以下我们分别讨论这两类一维搜索方法。1818首页上页下页末页结束2024/8/27 2024/8/27
11、周二周二 18:55 18:553.33.3一维搜索的试探方法一维搜索的试探方法一维搜索的试探方法一维搜索的试探方法0.6180.618法法法法q概述在搜索区间 内适当插入两点 ,并计算其函数值。将区间分成三段。应用函数的单谷性质,通过函数值大小的比较,删去其中一段,使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置,如此迭代下去,使搜索区间无限缩小,从而得到极小点的数值近似解。在实际计算中,最常用的一维搜索试探方法是黄金分割法,又称作0.618法。我们可以通过学习黄金分割法来了解一维搜索试探方法的基本思想。1919首页上页下页末页结束2024/8/27 2024/8/27 周二周二 1
12、8:55 18:55q黄金分割法黄金分割法是建立在区间消去法原理基础上的试探方法。适用于 区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其它要求,甚至可以不连续。因此,这种方法的适应面相当广。黄金分割法对插入点的要求:1)要求插入点 的位置相对于区间 两端点具有对称性,即 其中 为待定常数。2020首页上页下页末页结束2024/8/27 2024/8/27 周二周二 18:56 18:562)黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段,与原来区间的三段具有相同的比例分布。即每次缩小所得的新区间长度与缩小前区间长度之比(即:区间收缩率)为定值。2121首页上页下
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 搜索
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。