![点击分享此内容可以赚币 分享](/master/images/share_but.png)
最优性条件和罚函数法省公共课一等奖全国赛课获奖课件.pptx
《最优性条件和罚函数法省公共课一等奖全国赛课获奖课件.pptx》由会员分享,可在线阅读,更多相关《最优性条件和罚函数法省公共课一等奖全国赛课获奖课件.pptx(74页珍藏版)》请在咨信网上搜索。
1、 约束极值及最优性条件约束极值及最优性条件 等式约束等式约束 不等式约束不等式约束 普通约束问题普通约束问题 可行方向法可行方向法 既约梯度法既约梯度法 广义既约梯度法广义既约梯度法 处罚函数法处罚函数法 外点法外点法 内点法内点法 乘子法乘子法第六章第六章 约束最优化方法约束最优化方法第1页1 1、约束极值问题表示、约束极值问题表示一一 、约束极值问题最优性条件、约束极值问题最优性条件第2页第3页2 约束极值及最优性条件约束极值及最优性条件Kuhn-Tucker 条件条件(1 1)等式约束性问题最优性条件)等式约束性问题最优性条件 考虑 min f(x)s.t.h(x)=0 回顾高等数学中所
2、学条件极值:回顾高等数学中所学条件极值:问题问题 求求 z=f(x,y)极值,在极值,在(x,y)=0条件下条件下。即:即:min f(x,y)s.t.(x,y)=0 引入引入Lagrange乘子:乘子:Lagrange函数函数 L(x,y;)=f(x,y)+(x,y)第4页若若x*是其最优解是其最优解 ,则存在则存在*Rl 使使第5页 几何意义几何意义:考虑一个约束情况:考虑一个约束情况:x 最优性条件即:最优性条件即:第6页(2)(2)不等式约束极值问题最优性条件不等式约束极值问题最优性条件可行方向可行方向:可行方向与主动约束可行方向与主动约束:第7页主动约束主动约束:例:或起作用约束起作
3、用约束(紧约束紧约束主动约束主动约束有效约束有效约束)。)。第8页怎样判断一个方向是可行方向怎样判断一个方向是可行方向?第9页证实:定理定理1:可行下降方向可行下降方向:第10页定理2:定理3:证略极值点必要条件:第11页第12页第13页第14页第15页定理定理4(K-T条件条件):第16页第17页例例:求约束极值问题求约束极值问题第18页第19页第20页第21页定理定理5(Fritz John条件条件):第22页定理(K-T条件):第23页二、解线性约束问题既约梯度法二、解线性约束问题既约梯度法第24页第25页第26页第27页第28页第29页第30页算法:算法:x(1)S,k=1k=k+1J
4、k=j|xj为x(k)中最大m个正分量之一B=,aj(jJk),N=,aj(jJk),YNT=NfT(x(k)-BfT(x(k)B-1NdB=-B-1NdN解得 x(k+1)=x(k)+kdd=0?YNStop;x(k)K-T点 第31页第32页二、广义既约梯度法二、广义既约梯度法第33页第34页(一)处罚函数法(一)处罚函数法(SUMTSUMT)将有约束优化问题转化为一系列无约束优化问题进行求解。将有约束优化问题转化为一系列无约束优化问题进行求解。(Sequential Unconstrained Minimization Technique-SUMT)1 1、算法思想:、算法思想:2 2、
5、算法类型:、算法类型:q 外点法(外惩法)外点法(外惩法)q 内点法(内惩法)内点法(内惩法)三、约束极值问题算法三、约束极值问题算法第35页3 3、问题:、问题:第36页4 4、外点法(外部处罚函数法)、外点法(外部处罚函数法)第37页第38页第39页(1 1)几何解释)几何解释第40页(2 2)算法步骤(外点法):)算法步骤(外点法):第41页yesNo(2 2)外点法框图外点法框图第42页(4 4)应注意问题)应注意问题第43页例:第44页第45页q (7 7)普通模型外点法)普通模型外点法q q 算法步骤相同算法步骤相同第46页(8)(8)算法收敛性算法收敛性第47页5 5、内点法(障
6、碍函数法)、内点法(障碍函数法)(1 1)集合结构)集合结构第48页(2 2)算法思想)算法思想 内点法(障碍函数法)迭代点是在可行域点集内部内点法(障碍函数法)迭代点是在可行域点集内部移动,对靠近可行域边界上点施加越来越大处罚,对可移动,对靠近可行域边界上点施加越来越大处罚,对可行域边界上点施加无限大处罚,这好比边界是一道障碍行域边界上点施加无限大处罚,这好比边界是一道障碍物,妨碍迭代点穿越边界。物,妨碍迭代点穿越边界。内点法要求可行点集内点集合非空,不然算法无法运内点法要求可行点集内点集合非空,不然算法无法运行。这么一来行。这么一来内点法只对不等式约束优化问题内点法只对不等式约束优化问题才
7、可能有效。才可能有效。第49页(3 3)算法分析)算法分析第50页第51页(4 4)算法步骤(内点法):)算法步骤(内点法):第52页内点法框图内点法框图yesNo第53页例解第54页第55页(5 5)算法收敛性:)算法收敛性:(6 6)罚函数法缺点)罚函数法缺点第56页(7)(7)内、外点法优缺点比较内、外点法优缺点比较1.x(0)S 02.2.等式等式约约束不适用束不适用3.3.障碍函数障碍函数B(x)在在S 0可微可微阶阶数数与与gi(x)相同相同(可可选选取无取无约约束最束最优优化方法广化方法广)4.迭代中迭代中x(k)R(随(随时时可取可取x(k)x*)5.5.非凸非凸规规划适用划适
8、用1.任意任意x(0)Rn2.等式约束适用等式约束适用3.处罚项二阶偏导在处罚项二阶偏导在S边界边界上不存在上不存在 4.4.5.5.非凸非凸规规划适用划适用内点法内点法外点法外点法迭代中迭代中x(k)R 第57页6.乘子法乘子法乘子罚函数乘子罚函数:乘子罚函数与乘子罚函数与LangrangeLangrange函数及处罚函数区分:函数及处罚函数区分:多一项。多一项。(1)(1)等式约束等式约束第58页乘子罚函数:第59页(2)等式、不等式约束等式、不等式约束第60页算法步骤(乘子罚函数法):算法步骤(乘子罚函数法):第61页解:1.处罚函数法。对于处罚函数处罚函数法。对于处罚函数例:问题 最优
9、解为最优解为x x*=(0.25,0.75),=(0.25,0.75),分别用分别用处罚函数法和乘子法处罚函数法和乘子法 求它迭代点列。求它迭代点列。可求得最优解为:可求得最优解为:2.乘子法。对于乘子罚函数乘子法。对于乘子罚函数可求得最优解为:可求得最优解为:第62页 从表中可见,从表中可见,xk*比比 xk 近于近于x*速速度慢得多,用乘子法迭代度慢得多,用乘子法迭代6次就到次就到达处罚函数法迭代达处罚函数法迭代15次效次效 这里,处罚因子在处罚函数法这里,处罚因子在处罚函数法中要增大到中要增大到u153276.8,而在乘,而在乘子法中只要增大到子法中只要增大到u6=6.4 相比之下,乘子
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最优 条件 函数 公共课 一等奖 全国 获奖 课件
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。