![点击分享此内容可以赚币 分享](/master/images/share_but.png)
北邮最优化课件-7-最优性条件.ppt
《北邮最优化课件-7-最优性条件.ppt》由会员分享,可在线阅读,更多相关《北邮最优化课件-7-最优性条件.ppt(100页珍藏版)》请在咨信网上搜索。
1、最优化理论与算法帅天平北京邮电大学数学系7,最优性条件2024/5/25 周六1最优化理论第七章 最优性条件无约束问题的极值条件约束极值问题的最优性条件对偶及鞍点2024/5/25 周六2最优化理论7.17.1无约束问题的极值条件无约束问题的极值条件考虑非线性规划问题1,无约束极值问题称为无约束极值问题(UNLP)7.最优性条件-无约束12024/5/25 周六3最优化理论7.最优性条件-无约束2Th7.1.1(非极小点的充分条件)设f(x)在点x*处可微,若存在方向d(0)Rn,使得f(x*)d0,使得对任意(0,),有f(x*+d)f(x*).此时,我们称d 为f(x)在x*的一个下降方向
2、下降方向.证明证明.由 f(x)在 x*可微,则 f(x*+d)=f(x*)+f(x*)d+|d|(x*;d),其中(x*;d)0(当 0).2,必要条件,必要条件2024/5/25 周六4最优化理论7.最优性条件-无约束3移项且两边同除以移项且两边同除以(0),得(f(x*+d)f(x*))/f(x*)d+|d|(x*;d)由于 f(x*)d 0 使得对 任意(0,),f(x*)d+|d|(x*;d)0.定理立明.定理定理7.1.2-3(极小点的必要条件)设x*处是问题(UNLP)的局部极小点.(1)当 f(x)在 x*可微时,则梯度 f(x*)=0.(2)当f(x)在 x*二次可微时.则
3、f(x*)=0 且 Hessian 矩阵 H(x*)是半正定的2024/5/25 周六5最优化理论7.最优性条件-无约束4(2).给定任意向量 d.由 f(x)在 x*的二次可微性,有f(x*+d)=f(x*)+f(x*)d+dH(x*)d/2+|d|(x*;d)(I),其中(x*;d)0(0).由(1)的证明有 f(x*)=0.移项整理并两端除以 ,得 =dH(x*)d/2+|d|(x*;d)(II).因 x*局部极小,对充分小 有f(x*+d)f(x*)2222 f(x*+d)f(x*)22证明证明(1).若f(x*)0,作 d=f(x*).则有 f(x*)d 0 使得 f(x*+d)f(
4、x*),(0,),此与 x*为局部极小相矛盾,故 f(x*)=0.2024/5/25 周六6最优化理论7.最优性条件-无约束5dH(x*)d/2+|d|(x*;d)0 2由(II),显见对充分小的 成立,对 0取极限,则有 dH(x*)d 0,从而,H(x*)半正定定义定义1 若f(x)在点x*处可微,且f(x*)=0,则称x*为f(x)的一个驻点驻点或平稳点平稳点.d(0)Rn,既不是极大点也不是极小点的驻点称为鞍点鞍点.Th7.1.4(二阶充分条件二阶充分条件).假设 f(x)在 x*点二次可微,若 f(x*)=0 且 Hessian 矩阵 H(x*)是正定的,则 x*是(UNLP)的一个
5、(严格)局部极小点3,二阶充分条件,二阶充分条件2024/5/25 周六7最优化理论7.最优性条件-无约束6证明证明.因 f 在 x*二次可微,故对任意 x,有 f(x)=f(x*)+f(x*)(x-x*)+(x-x*)H(x*)(x-x*)/2+|x-x*|(x*;x-x*),这里(x*;x-x*)0,当 xx*.假设命题不真,x*不是局部极小,则存在序列 xk 收敛到 x*并使得 f(xk)0 使得 f(x*+d)f(x*)((0,)),则 d 称为 f(x)在 x*的下降方向(decedent direction)设 f(x)在 x*可微.若存在向量 d 满足 f(x*)d0,则 由Th
6、7.1.1,d 是 f(x)在 x*.的下降方向。记所有这样的向量集合为2024/5/25 周六14最优化理论7.最优性条件-有约束3由可行方向定义和下降方向知,可行方向定义和下降方向知,从点 x*,沿可行方向 dD(x*)作一个很小的移动还是可行点.进一步,由 Th 7.1.1,若 f(x*)d0,则d 是f在 x*的下降方向。下面定理将说明 若 x*是局部最优且 f(x*)d0,则 dD(x*).即不是可行方向。Theorem 7.2.1.(必要条件必要条件)考虑极小化问题考虑极小化问题:min f(x),subject to xS,其中其中 S 是是 Rn 中非空集合中非空集合,设设 f
7、(x)在在 x*可微。若可微。若 x*是局部极是局部极小点,则小点,则 F0(x*)D=,其中其中 F0(x*)=d|f(x*)d0,f(x*+d)0,x*+d S,(0,2)此与局部极小矛盾。此与局部极小矛盾。2024/5/25 周六16最优化理论177.最优性条件-不等式约束1为把最优性的几何条件用代数来表示,引入起作用约束的概为把最优性的几何条件用代数来表示,引入起作用约束的概念。问题的约束条件在点念。问题的约束条件在点x*S S处有两种情形处有两种情形3 不等式约束的一阶最优性条件不等式约束的一阶最优性条件1,I=i|gi(x*)=0在x*处起作用约束2,gi(x*)0.iI在x*处不
8、起作用约束G0(x*)=d|gi(x*)d0,iI.2024/5/25 周六最优化理论187.最优性条件-不等式约束2证明概要证明概要.设设 d G0(x*).因因 S 为开集,则存在为开集,则存在 10 使得对使得对 (0,1),x*+d S。另外存在另外存在 20使得使得对对 (0,2),i I.gi(x*+d)0,最后存在最后存在 30 使得使得对任意对任意 (0,3)and i I有有gi(x*+d)gi(x*),从而从而 d D,D 是是 x*处的可行方向锥处的可行方向锥.于是于是G(x*)D.由由Th 7.2.1,立明。立明。Th7.2.2.(必要条件必要条件)考虑极小化问题考虑极
9、小化问题 min f(x)subject to gi(x)0,i=1,m,x S,其中其中 S 是是 Rn中的非空开集。中的非空开集。设设 x*为可行点,为可行点,I=i|gi(x*)=0.进一步假设,进一步假设,f(x)和和 gi(x)(i I)在)在 x*可微,可微,gi(i I)在在 x*连续连续.若若 x*是局部最优解,则是局部最优解,则 F0(x*)G0(x*)=,其中其中F0(x*)=d|f(x*)d0,i I.2024/5/25 周六最优化理论7.最优性条件-不等式约束3g1(x)=-x -y +5,g2(x)=-x-y+3,g3(x)=x,g4(x)=y;I=2f(x)2(x
10、3),2(y 2)2 2Min (x-3)+(y-2)s.t.x +y 5 x +y 3 x,y 0.2 222f(x*)g2(x*)(9/5,6/5)F(x*)G(x*).g2(x)g1(x)x*2024/5/25 周六19最优化理论7.最优性条件-不等式约束4Min (x-3)+(y-2)s.t.x +y 5 x +y 3 x,y 0.2 222x*=(2,1)g1(x*)=(-4,-2),g2(x*)=(-1,-1),f(x*)(-2,-2)f(x*)g1(x*)x*是最优解g2(x*)(2,1)x*2024/5/25 周六20最优化理论7.最优性条件-不等式约束5Th7.2.3.(Fr
11、itz John Condition,1948)考虑极小化问题考虑极小化问题 min f(x)subject to gi(x)0,i=1,m,x S,其中其中 S 是是 En.中非空开集中非空开集.设设 x*为可行点为可行点,I=i|gi(x*)=0.进一进一步假设步假设 f(x)和和 gi(x)(i I)在在 x*可微可微,gi(i I)在在 x*连续连续.若若 x*是局部最优解是局部最优解.则则存在一组非负数存在一组非负数 u0,ui(iI)使得使得 u0f(x*)-uigi(x*)=0,u0,ui0 for iI and(u0,uI)0.iI进一步进一步,若若 gi(x)(iI)在 x*
12、也可微,则 u0f(x*)uigi(x*)=0,uigi(x*)=0,u0,ui(所有 i),且(u0,u)0.i=1i=m2024/5/25 周六21最优化理论227.最优性条件-不等式约束6证明证明.由由Th7.2.2,不存在向量不存在向量 d 同时满足同时满足 f(x*)d0 和和 gi(x*)d0,(i I).设设 A 是其行由是其行由 f(x*)和和 gi(x*)(i I)组成的矩阵组成的矩阵.则则 Ad0,可以对约束强加某种限制,这种限制条件叫做约束规格或约束品性(constraint qualifications).已有很多的约束规格,特别的,Karush 1939,MS The
- 配套讲稿:
如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文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。