第四章无约束优化方法.pptx
《第四章无约束优化方法.pptx》由会员分享,可在线阅读,更多相关《第四章无约束优化方法.pptx(58页珍藏版)》请在咨信网上搜索。
1、第四章无约束优化方法第四章无约束优化方法第四章无约束优化方法第四章无约束优化方法34 4、1 1 坐标轮换法坐标轮换法基本思想基本思想:把一个把一个n维无约束最优化维无约束最优化问题转化为依次沿问题转化为依次沿n个坐标轴方向得个坐标轴方向得一维最优化问题。一维最优化问题。即迭代方向依次为即迭代方向依次为:第一轮第一轮:任取一初始点任取一初始点X(0)一维搜索求一维搜索求得得一维搜索求一维搜索求得得第二轮第二轮:4终止准则终止准则:上式点距准则中得上式点距准则中得两点应就是一轮迭两点应就是一轮迭代得始点与终点代得始点与终点利用一维优化方法确定沿该方向上具有最小目标函数值得步长利用一维优化方法确定
2、沿该方向上具有最小目标函数值得步长,即即:minF(X:minF(X(k)(k)+S S(k)(k)=F(X)=F(X(k)(k)+(k)(k)S S(k)(k)迭代步长迭代步长得确定得确定:5坐坐标轮换法法得得流流程程图 6坐标轮换法得特点坐标轮换法得特点:具有程序结构简单具有程序结构简单,易于掌握等优点。但收敛慢易于掌握等优点。但收敛慢,适用于适用于n10得低维优化问题得低维优化问题。另收敛速度与等值线得形状有关另收敛速度与等值线得形状有关7例题例题4、1 用坐用坐标轮换法求目法求目标函数函数得无得无约束最束最优解。解。给定初始点定初始点 精度要求精度要求=0、1 解解:作第一轮迭代计算。
3、作第一轮迭代计算。沿沿e1方向进行一维搜索方向进行一维搜索 按最按最优步步长原原则确定步确定步长1,即极小化即极小化此此问题可用某种一可用某种一维优化方法求出化方法求出1。在在这里里,我我们暂且借用微分学求且借用微分学求导解出解出,令其一令其一阶导数数为零零,1=5 以以为新起点,沿新起点,沿e2方向一方向一维搜索搜索以最以最优步步长原原则确定确定2,即极小化即极小化得得2=4、5,对于第一轮按终止条件检验对于第一轮按终止条件检验 8例题例题4、1 对于第一轮按终止条件检验对于第一轮按终止条件检验:继续第二轮迭代计算。以下各轮得计算结果列于表继续第二轮迭代计算。以下各轮得计算结果列于表4、1。
4、9例题例题4、1 计算五算五轮后有后有故近似故近似优化解化解为F*F(x*)=7、95025 10例题例题4、1 用解析法验证用解析法验证 解解:令令正定正定114、2 鲍威尔鲍威尔(Powell)法法v鲍威威尔尔法法就就是是直直接接搜搜索索法法中中一一个个十十分分有有效效得得算算法法。该算算法法就就是是沿沿着着逐逐步步产生生得得共共轭方方向向进行行搜搜索索得得,因因此此本本质上上就就是是一一种种共共轭方向法方向法,鲍威威尔尔法得收法得收敛速率速率较快。快。v以以共共轭方方向向作作为搜搜索索方方向向,不不只只限限于于鲍威威尔尔法法,也也用用于于其其她她一一些些较为有有效效得得方方法法,可可以以
5、统称称为共共轭方方向向法法。因因此此,共共轭方方向向得得概概念在念在优化方法研究中占有重要得地位。化方法研究中占有重要得地位。v共共轭轭方方向向在在最最优优化化问问题题中中得得应应用用就就是是基基于于其其具具有有一一个个重重要要性性质质,即即:设设 S1、S2、Sn就就是是关关于于A得得n个个互互相相共共轭轭得得向向量量,则则对对于求正定二次函数于求正定二次函数 得极小点得极小点,从从 任任意意初初始始点点出出发发,依依次次沿沿Si(i=1,2,n)方方向向进进行行一一维维最最优优化化搜索搜索,至多至多n步便可以收敛到极小点、步便可以收敛到极小点、122、5 关于优化方法中搜寻方向得理论基础关
6、于优化方法中搜寻方向得理论基础2、5、2 共轭方向共轭方向(见第二章见第二章)一、共轭方向得基本概念一、共轭方向得基本概念若有两个若有两个n维矢量维矢量S1、S2,对对nn阶对称正定矩阵阶对称正定矩阵A能满足能满足:称称n维空空间矢量矢量S1与与S2对A共共轭共共轭矢量所代表得方向称矢量所代表得方向称为共共轭方向。方向。正交正交:可以瞧作就是共可以瞧作就是共轭得特例得特例例例:(1)共共轭并正交并正交大家学习辛苦了,还是要坚持继续保持安静继续保持安静继续保持安静继续保持安静14例例:(2)共共轭但不正交但不正交设设A A为为nnnn阶实对称正定矩阵阶实对称正定矩阵,有一组非零得有一组非零得n
7、n维矢量维矢量S S1 1、S S2 2、SqSq,若满足若满足 ij ij 则称矢量系则称矢量系S Si i(i(i1 1,2 2,qn)qn)对于矩阵对于矩阵A A共轭共轭 15以二维函数为例以二维函数为例:二维正定二次函数具有两个重要特性二维正定二次函数具有两个重要特性:1 1)二维正定二次函数得等值线就是同心得椭圆族二维正定二次函数得等值线就是同心得椭圆族,且椭圆中心就且椭圆中心就 就是正定二元二次函数得极小点。就是正定二元二次函数得极小点。2)2)过同心椭圆族中心过同心椭圆族中心x*x*作任意直线作任意直线,此直线与诸椭圆交点处得切线此直线与诸椭圆交点处得切线相互平行。或者说相互平行
8、。或者说:两条平行得任意方向得切线两条平行得任意方向得切线,其切点得连线必通其切点得连线必通过椭圆簇得中心。过椭圆簇得中心。可以证明上诉可以证明上诉S S1 1与与S S2 2方向就是方向就是关于矩阵关于矩阵A A得共轭方向。得共轭方向。16S1与与S2就是对就是对A共轭得一对矢量共轭得一对矢量证明证明:设直线方程为设直线方程为代入代入F(X),并关于并关于求极值求极值即即结论结论:两个平行方向得极小点构成两个平行方向得极小点构成得新方向与原方向相互得新方向与原方向相互共轭共轭即即S S1 1与与S S2 2对对A A共轭共轭也即对于也即对于二维正定二次函数只要分别沿两个共轭方向寻优二维正定二
9、次函数只要分别沿两个共轭方向寻优即可找到最优点即可找到最优点、17v与此类似与此类似,可以推出对于可以推出对于n n维正定二次函数维正定二次函数,共轭方向得一个共轭方向得一个十分重要得极为有用得性质十分重要得极为有用得性质:从任意初始点出发从任意初始点出发,依次沿依次沿n n个个线性无关得与线性无关得与A A共轭得方向共轭得方向S S1 1,S S2 2,S Sn n各进行一维搜索各进行一维搜索,那么那么总能在第总能在第n n步或步或n n步之前就能达到步之前就能达到n n维正定二次函数得极小点维正定二次函数得极小点;并且这个性质与所有得并且这个性质与所有得n n个方向得次序无关。简言之个方向
10、得次序无关。简言之,用共轭用共轭方向法对于二次函数从理论上来讲方向法对于二次函数从理论上来讲,n n步就可达到极小点。因步就可达到极小点。因而说共轭方向法具有有限步收敛得特性。通常称具有这种性而说共轭方向法具有有限步收敛得特性。通常称具有这种性质得算法为二次收敛算法。质得算法为二次收敛算法。v共轭矢量之所以引起优化研究者得重视共轭矢量之所以引起优化研究者得重视,就就是因为它得这就就是因为它得这些性质对提高优化方法得收敛速率极为有用。些性质对提高优化方法得收敛速率极为有用。18例例设二二维目目标函数函数,给定方向定方向S1e2,初始点,初始点,求与,求与S1相共相共轭的的S2,并求函数的极小点。
11、,并求函数的极小点。解解:(1)第一个搜索方向第一个搜索方向(2)函数的海函数的海赛矩矩阵 对称正定称正定(3)从从点沿点沿S1方向求极小点方向求极小点x(1),即,即 19例例解解:(4)任取另初始点任取另初始点 沿沿S1方向一方向一维搜索求得搜索求得该方向极小点方向极小点x(2)X(2)=(5)求与求与S1相共相共轭得方向得方向S2S2=X(2)-X(1)=核核验计算算 矢量矢量S1与与S2确确为对A矩矩阵共共轭。(6)从从x(1)点出点出发,沿沿S2方向作一方向作一维搜索搜索,得极得极小点小点 X*=0 0T 204、2、1 鲍威尔基本算法鲍威尔基本算法(共轭方向得原始构成共轭方向得原始
12、构成)214、2、1 鲍威尔基本算法鲍威尔基本算法任取一初始点任取一初始点 X(0)X0(1)第一环第一环:e1,e2,e3 S1第二环第二环:e2,e3,S1 S2第三环第三环:e3,S1,S2 S3第第一一轮轮 S1,S2 ,S3两两两两共轭共轭由前结论由前结论:两个平行方向得极小点构成两个平行方向得极小点构成得新方向与原方向相互得新方向与原方向相互共轭共轭224、2、1 鲍威尔基本算法鲍威尔基本算法第一环第一环:e1,e2,e3 S1第二环第二环:e2,e3,S1 S2第三环第三环:e3,S1,S2 S3第第一一轮轮S1就是就是e1,e2,e3 得线性组合得线性组合S2就是就是e2,e3
13、,S1得线性组合得线性组合S3就是就是e3,S1,S2得线性组合得线性组合新一环方向组新一环方向组:e2,e3,S1 线性相关线性相关!降维降维23鲍威尔法得基本思想鲍威尔法得基本思想:对原始共轭方向法进行修正对原始共轭方向法进行修正,即在某即在某环已取得得环已取得得n+1n+1个方向中个方向中,选取选取n n 个线性无关个线性无关,共轭程度尽可能共轭程度尽可能高得方向作为下一环得基本高得方向作为下一环得基本方向组方向组,从而避免出现从而避免出现“退化退化”现现象、象、鲍威尔法与原始共轭方向法得主要区别就是鲍威尔法与原始共轭方向法得主要区别就是:在构成在构成K+1K+1环基本方向组时环基本方向
14、组时,不再总就是淘汰前一环不再总就是淘汰前一环(K(K环环)中得中得第一个方向第一个方向,而就是根据条件式而就是根据条件式就是否得到满足分两种情况来处理。就是否得到满足分两种情况来处理。4、2、1 鲍威尔修正算法鲍威尔修正算法24映射点一、一、Powell 修正算法得搜索方向修正算法得搜索方向Powell 判别式判别式25情况一情况一:Powell 判别式中若至少判别式中若至少 有一个不等式成立有一个不等式成立,则则第第K+1环得方向组仍用老方向组环得方向组仍用老方向组 初始点初始点:当当F2 F3时时,当当F2F3时时,情况二情况二:Powell 判别式中若两个判别式中若两个 不等式均不成立
- 配套讲稿:
如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。