运筹学非线性规划126-7ppt课件_第1页
运筹学非线性规划126-7ppt课件_第2页
运筹学非线性规划126-7ppt课件_第3页
运筹学非线性规划126-7ppt课件_第4页
运筹学非线性规划126-7ppt课件_第5页
已阅读5页,还剩15页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第十二章非线性规划12.6 KKT条件12.7 二次规划2022-2-112.6 约束优化的KKT条件回顾最优条件单变量非约束多变量非约束有约束的,但只有非负约束充分条件可能是: 是凹函数最优性的必要条件:( )f xd0dfxd0 (1,2, )djfjnxd0 (1,2, )d(0,0)jjfjnxx或者12.6 约束优化的KKT条件一般约束问题充分条件可能是: 是凹函数并且 是凸函数 (见12.2)最优性的必要条件:KKT条件( )f x( ) (1,2,)ig xim12.6 约束优化的KKT条件最优性的充要条件表表12.4 最优性的充要条件最优性的充要条件问题最优性的必要条件充要条件

2、可能是单变量非约束 是凹函数多变量非约束 是凹函数有约束的,但只有非负约束 是凹函数一般约束KKT条件 是凹函数并且 是凸函数 (见12.2)( )f xd0dfxd0 (1,2, )djfjnxd0 (1,2, )d(0,0)jjfjnxx或者( )f x( )f x( )f x( ) (1,2,)ig xim12.6 约束优化的KKT条件KKT条件1*1*1.0 ,1,2,2.03.0 1,2,4.05.0 1,2,6.0 miiijjmijiijjiiiiijigfuxxjngfxuxxgbimugbxjnuxxxx 1,2,im1*1.=0001,2, 2.0001,2,3.0 1,2

3、,4.0 1,2,miiijjjiiijigfuxxxjngbuimxjnuimx(或当),对(或当),对12.6 约束优化的KKT条件定理:假设 是满足某些正则性条件的可微函数。只有当存在 个数 ,使所有KKT条件都满足,这时可能是非线性规划问题的一个最优解。推论假设 是一个凹函数, 是凸函数即该问题为凸规划问题),并且这些函数都满足正则性条件。那么当且仅当定理的所有条件都满足时,是一个最优解。12( ),( ),( ),( )mf x g x gxgxm12,mu uu12*(,)nx xxx( )f x12( ),( ),( )mg x gxgx12*(,)nx xxx12.6 约束优化

4、的KKT条件例 双变量非线性规划问题 可知:121212Max ( )ln(1)s.t. 23 00fxxxxxxx且,11221( )2nmgxxx12.6 约束优化的KKT条件KKT条件:111111211211212111(1). 20112(1). 2011(2). 1-02(2). (1-)03. 2304. (23)05. 0,06. 0juxjxuxjujxuxxuxxxxu1*1*1.0 ,1,2,2.03.0 1,2,4.05.0 1,2,6.0 miiijjmijiijjiiiiijigfuxxjngfxuxxgbimugbxjnuxxxx 1,2,im12.6 约束优化的

5、KKT条件KKT条件: 该问题最优解:111111211211212111(1). 20112(1). 2011(2). 1-02(2). (1-)03. 2304. (23)05. 0,06. 0juxjxuxjujxuxxuxxxxu11u 10 x 111201ux10 x 122-30 xx2=3x11u *0,3x()12.7 二次规划二次规划与线性规划问题的不同之处仅仅在于目标函数也包括 和 项。用矩阵符号表示二次规划问题:用向量元素表示:半正定矩阵:如果对任何非零向量 ,都有 成立,且有非零向量 ,使 ,则称矩阵A为半正定矩阵。T1Max ( )2s.t. 0fxcxx Qx A

6、xbx且2jx()ijijx xxxT11111( )22nnnjjijijjijfc xq x xxcxx Qx ijjiqq其中Q注意:目标函数为凹函数的等价条件为是半正定矩阵。xTx Ax 0T00 x Ax00 x12.7 二次规划例如 此时:22121212121212Max ( ,)1530424s.t. 230 00f x xxxx xxxxxxx 且,12441530 ,4812 ,30 xxcxQAb12.7 二次规划对于二次规划的KKT条件以上题为例) KKT条件: 将不等式变为等式。22121212121212Max ( ,)1530424s.t. 230 00f x x

7、xxx xxxxxxx 且,211121112121211211211(1). 15+4402(1). (15+44)01(2). 3048202(2). (30482 )03. 23004. (230)05. 0,jxxujxxxujxxujxxxuxxu xxx2106. 0 xu211112121214415482 302 30 xxuyxxuyxxv 12.7 二次规划注意此时条件2与条件4可表示为:对于每个配对 其中的两个变量称为互补变量。这些条件得到一个新的组合约束称为互补约束。11221 12(1). 02(2). 04. 0jx yjx yu v112211( ,), (,),

8、( ,)x yxyu v11221 1+0 x yx yu v 12.7 二次规划整个条件集合的简便形式用矩阵符号表示:1211121212112112111221 1 44 15482 30 2 30000000+0 xxuyxxuyxxvxxuyyvx yx yu v,TTTT,QxA uycAxvbx0 u0 y0 v0 x yu v0线性规划约束互补约束12.7 二次规划改进的单纯形法引入人工变量 ,相当于应用单纯形法求解以下的线性规划问题满足从KKT条件得到的线性规划约束,但也包括这些人工变量。Min =jjZz同原单纯形法相比,修改发生于:限制-输入规则:当你选择一个输入基变量时,

9、考虑排除互补变量已经是一个基变量的任一非基变量;选择应该是根据单纯形表的一般标准从其他非基变量中做出的。z12.7 二次规划依旧用本节刚开始的例子说明这种方法 在引入所需人工变量后,用改进的单纯形法显性说明的线性规划问题是附加的互补约束用限制-输入规则,算法自动的执行该约束。121211112122121Min 44 + 15s.t. 482 +30 2 30 Zzzxxuyzxxuyzxxv且1211211211221 1 000000 00+0 xxuyyvzzx yx yu v,附加的互补约束 12.7 二次规划表表12.5 改进单纯形法对二次规划例子的应用改进单纯形法对二次规划例子的应

10、用迭代基变量方程Zx1x2u1y1y2v1z1z2右端项0Z(0)-10-4-311000-45z1(1)04-41-1001015z2(2)0-4820-100130v1(3)012000100301Z(0)-1-20-211/2001/2-30z1(1)0202-11/2011/230 x2(2)0-1/211/40-1/8001/83+3/4v1(3)020-1/201/410-1/422+1/212.7 二次规划表表12.5 改进单纯形法对二次规划例子的应用改进单纯形法对二次规划例子的应用迭代基变量方程Zx1x2u1y1y2v1z1z2右端项2Z(0)-100-5/213/4101/4-7-1/2z1(1)0005/2-1-3/4-113/47+1/2x2(2)0011/80-1/161/401/169+3/8x1(3)010-1/401/81/20-1/811+1/43Z(0)-1000000110u1(1)0001-2/5

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论