ImageVerifierCode 换一换
格式:PPT , 页数:26 ,大小:324.50KB ,
文档编号:4946047      下载积分:22 文币
快捷下载
登录下载
邮箱/手机:
温馨提示:
系统将以此处填写的邮箱或者手机号生成账号和密码,方便再次下载。 如填写123,账号和密码都是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

优惠套餐
 

温馨提示:若手机下载失败,请复制以下地址【https://www.163wenku.com/d-4946047.html】到电脑浏览器->登陆(账号密码均为手机号或邮箱;不要扫码登陆)->重新下载(不再收费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  
下载须知

1: 试题类文档的标题没说有答案,则无答案;主观题也可能无答案。PPT的音视频可能无法播放。 请谨慎下单,一旦售出,概不退换。
2: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
3: 本文为用户(晟晟文业)主动上传,所有收益归该用户。163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

1,本文(运筹学-非线性规划-2-约束极值课件.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!

运筹学-非线性规划-2-约束极值课件.ppt

1、7.约束极值问题的最优性条件约束极值问题的最优性条件ljxgmixhtsxfji,1,0)(,1,0)(.)(min ,其其中中可可行行域域0)(,0)(|xgxhxD .)(,)(,)()()(,)(,)()(2121TlTmxgxgxgxgxhxhxhxh ):积积极极约约束束(起起作作用用约约束束处处的的积积极极约约束束。是是,则则称称不不等等式式约约束束,若若对对于于xxgxgDxjj0)(0)(1,0)(|)(ljxgjxIxj 处的积极约束指标集处的积极约束指标集处处的的积积极极约约束束指指标标集集。,求求点点令令设设例例xxxxgxxxgxxxgT 22,22,0)(,01)(,

2、02)(.13222122121.解解,022222)(21 xg,022221)(222 xg,022)(3 xg。2,1)(xI1x2xO0)(1 xg0)(2 xg0)(3 xgx。有有处处的的可可行行方方向向,则则为为性性质质:若若0)()(pxgxIjxpTj)(1xg)(2xg p0)(2 xg0)(1 xgx。处处的的可可行行方方向向必必是是则则有有若若,反反之之,对对于于方方向向xppxgxIjpTj,0)()(;0)(,0)(,)(tpxgxgxIjjj则则即即若若.0)()()()()()(,)(topxgttopxgtxgtpxgxIjTjTjjj则则若若有有因因为为对对

3、于于充充分分小小的的,0 t因因此此有有处处的的下下降降方方向向,为为,则则另另外外,若若xppxfT0)(.*)(,0*)(0*)(*xIjpxgpxfpxTjT 且且使使得得向向为为极极小小点点,则则不不存存在在方方定定理理:若若Kuhn-Tucker 条件(极值点的必要条件)条件(极值点的必要条件).0*)(*)()1(xgixIi,即即只只有有一一个个积积极极约约束束若若.*为为一一个个局局部部极极小小点点设设 x.*)(*)(pxfxgi可可行行下下降降方方向向否否则则存存在在一一个个共共线线且且方方向向相相反反,与与则则 )*(xgi)*(xf p*x.0*)(0*)(,*)()2

4、(两个积极约束两个积极约束和和,即有,即有若若 xgxgjixIji;*)(*)(*)(一一个个可可行行下下降降方方向向而而有有体体的的高高与与棱棱夹夹锐锐角角,从从,四四面面它它们们为为棱棱有有一一个个四四面面体体共共面面,若若不不然然,以以、则则xfxgxgji 。一一个个可可行行下下降降方方向向的的夹夹角角内内,否否则则也也有有与与必必在在进进而而,*)(*)(*)(xgxgxfji 。使使得得所所以以,*)(*)(*)(0,0 xgxgxfjjiiji )*(xgi)*(xf p*x)*(xgj)*(xgi)*(xf *x)*(xgj)*(xf 使使得得存存在在实实数数线线性性无无关关

5、,则则设设一一般般地地,)*)(0*)(*)()3(|xIjxIjxgjj *)(*)(*)(xIjjjxgxf.)*)(*)(*)(张张成成的的凸凸锥锥内内在在即即xIjxgxfj )*(xf *x使使得得、约约束束,因因此此有有正正数数极极代代替替,而而且且二二者者都都是是积积和和可可用用两两个个不不等等式式约约束束由由于于等等式式约约束束 iijiiixhxhxh 0)(0)(0)()4(miiiiixIjjjxhxhxgxf1*)()(*)(*)(*)(*)(,则则令令 iii miiixIjjjxhxgxf1*)(*)(*)(*)(Kuhn Tucker(K T)条件条件:),2,1

6、(0),2,1(0*)(*)(*)(*)(11ljljxgxgxhxfjjjljjjmiii 满足满足、实数实数线性无关,则存在一组线性无关,则存在一组、可微,可微,在在、是局部极小点,是局部极小点,若若jijijixIjxgxhxxgxhxfx )*)(*)(*)(*)()()(*上述为上述为K T条件,满足该条件的可行点称为条件,满足该条件的可行点称为 K T点。点。若定义若定义 Lagrange 函数函数 ljjjmiiixgxhxfxL11)()()(),(条条件件为为乘乘子子,则则称称为为其其中中TKLagrangeji ,ljljxgnjxxLjjjj,2,1,0,2,1,0*)(

7、,2,1,0),*,(极值点的充分条件:极值点的充分条件:若若 x*为为 K T 点,且对符合以下条件的方向点,且对符合以下条件的方向 p )0,*)(0*)()0,*)(0*)()0)(0*)(jTjjTjiTixIjpxgxIjpxgxhpxh 为为等等式式约约束束是是严严格格局局部部极极小小点点。,则则有有*0),*,(2xpxLpxT 例例.用用 K T 条件解问题条件解问题0,02,01.)2()1(),(min212121222121 xxxxxxtsxxxxf解解.Lagrange 函数函数2312211122221)2()1()2()1(xxxxxxxxL K T 条件条件0,

8、0,0,0)2(0)2(20)1(2321231221131212111 xxxxxxLxxL0,02,01212121 xxxxxx可行性条件可行性条件,可解出,可解出,则,则若若00,0,0)2(32211 xx.0,1,0,23,2113221 xx.,02,2,12121不不可可行行但但这这导导致致 xxxx,可可解解出出则则若若0,1,0,0,0)3(32211 xxx.0,4,222矛矛盾盾与与 有有结结合合则则若若,01,02,0)1(21211 xxxx.,0,0)4(211不不可可行行若若 xx 点点,是是唯唯一一TKx 23,21*是是极极小小点点。正正定定,所所以以且且*

9、20022xLx 8.二次规划二次规划 njnkkjjknjjjxxqxq11121min)ii(,2,1,0)i(,2,1,.1njxmibxatsjinjjij njjjinjjijmiinjnkkjjknjjjxbxaxxqxqxL11111121),(Lagrange 函函数数.kjjkqq 其其中中)iii(,1,011njaxqqxLjmiiijnkkjkjj )iv(,1,0)(,1,0njnjxjjj K T 条件条件求二次规划的求二次规划的 K T 点等价于求线性等式及不等式组点等价于求线性等式及不等式组(i)、(ii)、(iii)、(iv)的一个可行点,并且满足互补条件的一

10、个可行点,并且满足互补条件(*)。设设 x 0 是一个满足条件是一个满足条件(i)、(ii)的基本可行解,则求的基本可行解,则求(i)-(iv)的可行点可转化为线性规划问题的可行点可转化为线性规划问题:njjz1minnjqzaxqjjjjmiiiijnkkjk,1,)(11 mibxainjjij,1,1 ,0,jiijjzx 。,其其中中jnkkjkjnkkjkjqxqqxq1010,1,1 上述线性规划有初始基本可行解:上述线性规划有初始基本可行解:nkkjkjjiijjjxqqzxx100,0,0,同同时时成成为为基基变变量量。和和不不能能让让线线性性规规划划时时述述在在用用单单纯纯形

11、形算算法法求求解解上上注注:为为了了满满足足互互补补条条件件jjx,)(初始基本可行解中的基变量包括初始基本可行解中的基变量包括 x 0 中的基变量和所有中的基变量和所有 z j。优优解解。,即即算算法法能能获获得得整整体体最最正正定定,则则行行且且收收敛敛性性:若若二二次次规规划划可可0min)(1 njjnnjkzq定定阵阵处处理理。增增大大主主对对角角元元后后化化为为正正定定成成立立,但但可可适适当当半半正正定定,上上述述结结论论不不一一若若nnjkq)(9.可行方向法可行方向法mixgtsxfi,1,0)(.)(min 在迭代点在迭代点 x k,选择一个可行下降方向,选择一个可行下降方

12、向 p k 为搜索方向,为搜索方向,则则 p k 应满足应满足)(,0)(0)(kkTkikTkxIipxgpxf p k 可以通过解下述线性规划获得:可以通过解下述线性规划获得:njpxIipxgpxftsjkTkiTk,2,1,11)(,)()(.min nppp1其其中中;)()(,0*线线性性无无关关)点点(若若已已是是处处不不存存在在可可行行下下降降方方向向则则性性质质:若若kkikkxIixgTKxx 。处处的的一一个个可可行行下下降降方方向向则则得得到到若若*,0*pxk 。点点,即即总总有有一一定定收收敛敛到到有有例例子子表表明明上上述述方方法法不不0*TK改进方法:在找可行下

13、降方向时考虑所有约束,即改进方法:在找可行下降方向时考虑所有约束,即njpmipxgxgpxftsjTkikiTk,2,1,11,2,1,)()()(.min 可可行行解解。是是上上述述线线性性规规划划的的一一个个Tp)0,0(,0 行行解解。也也是是上上述述线线性性规规划划的的可可Tp)0,0(,0 ;,0*点点是是则则性性质质:若若TKxk 处处的的可可行行下下降降方方向向。是是则则若若kxp*,0*是是可可行行方方向向。又又,时时,*,0*)(,0*)(0)()(ppxfpxgxgxIiTkTkikik 可证:改进方法具有全局收敛性。可证:改进方法具有全局收敛性。10.制约函数法制约函数

14、法将约束非线性规划问题转化为一系列无约束问题求解。将约束非线性规划问题转化为一系列无约束问题求解。(SUMT:Sequential Unconstrained Minimization Technique)(1)外点法)外点法ljxgmixhtsxfji,1,0)(,1,0)(.)(min 记可行域为记可行域为 D成成为为极极小小点点。数数值值很很大大,因因而而不不可可能能时时,对对应应的的目目标标函函的的目目标标函函数数值值为为时时,对对应应束束问问题题,使使得得出出发发点点:构构造造一一个个无无约约DxxfDx ;)(构造罚函数构造罚函数 DxcDxxp,0)(其中其中 c 是充分大的正数

15、。是充分大的正数。考虑无约束问题考虑无约束问题)()()(minxpxfxF F(x)称为增广目标函数,它的极小点也是原问题的极称为增广目标函数,它的极小点也是原问题的极小点,但小点,但 F(x)不能保持原目标函数不能保持原目标函数 f(x)可能具有的良可能具有的良好性态(如连续、光滑),因为好性态(如连续、光滑),因为 F(x)在可行域在可行域 D 的边的边界上发生跳跃。界上发生跳跃。另构造罚函数另构造罚函数2)(112)(,0min)()(ljjmiicxgcxhcxp增广目标函数增广目标函数)()()(minxpxfxFcc c 称为罚因子。称为罚因子。连连续续(可可导导)。(可可导导)

16、,则则连连续续和和性性质质:如如果果)(),1()(),1()(xpljxgmixhcji 的的最最优优解解。也也是是则则,的的最最优优解解,且且是是性性质质:设设)(min)(*)(*)(min)(*xfcxDcxxFcxDxc 。题题然然后后解解一一系系列列无无约约束束问问),(趋趋于于列列递递增增的的数数求求解解困困难难,因因此此常常取取一一会会造造成成无无约约束束问问题题实实际际计计算算中中,过过大大的的足足够够大大时时才才成成立立,但但在在仅仅在在一一般般说说来来,)(min)(min)(*xcFcxFccDcxkkc 01.)(2)(min.212221 xxtsxx例例 1)1(

17、)(2)(1)(2)(1,0min)(2)()(.2122122212122212122212)(xxxxcxxxxxxxxcxxxFc解解 1)1(2212)(212112111xxxxcxxxxxxFc 1)1(2414)(212122122xxxxcxxxxxxFc,因因此此称称为为外外点点法法。的的外外部部趋趋向向从从可可行行域域连连续续,则则和和、设设*)(*),1()(),1()()(xDcxljxgmixhxfkji 无无解解;时时,0)()(11121 xxFxxFxxcc得得由由时时,,0)()(11121 xxFxxFxxcc 0)1(240)1(22212211xxcxx

18、xcxccxccx32,32221 31,3221 xxc时时,.31,32*x(2)内点法)内点法D DintDDintD 可可行行域域0)(|xgjxDj使使得得至至少少有有一一个个边边界界0)(|jxgxDintj ,内内部部内点法的迭代点列在可行域的内部移动,并对接近可内点法的迭代点列在可行域的内部移动,并对接近可行域边界的点施加越来越大的惩罚,对可行域边界上行域边界的点施加越来越大的惩罚,对可行域边界上的点施加无限大的惩罚,这好比在边界上筑一道墙阻的点施加无限大的惩罚,这好比在边界上筑一道墙阻止迭代点穿越边界。止迭代点穿越边界。内点法要求可行域的内点集合非空,并且要求初始点内点法要求

19、可行域的内点集合非空,并且要求初始点必须是内点,因此内点法只能处理不等式约束。必须是内点,因此内点法只能处理不等式约束。mixgtsxfi,1,0)(.)(min miicmiicxgcxBxgcxB11)(ln)()(1)(或或设设)()()(minxBxfxFcc 考考虑虑无无约约束束问问题题可可行行域域的的内内部部。的的极极小小点点将将落落在在原原问问题题因因此此无无限限增增大大,界界时时,从从可可行行域域的的内内部部趋趋向向边边当当)()(xFxBxcc。题题然然后后解解一一系系列列无无约约束束问问减减趋趋于于零零的的罚罚参参数数单单调调递递的的影影响响,为为此此设设置置一一列列须须尽

20、尽可可能能减减弱弱因因此此必必的的目目标标是是另另一一方方面面,由由于于原原问问题题)()()(min,)(,)(minxBxfxFcxBxfkkcckc 。收收敛敛于于产产生生的的点点列列则则内内点点法法连连续续、收收敛敛性性:若若*)(*,),1()()(xcxmixgxfki 0)()(21.32min.222121 xxtsxx例例 222121)()(21ln32)(.xxcxxxFc 解解,由由0)()(2142)(222111 xxcxxxFc得得,0)()(2123)(222122 xxcxxxFc11113311112221 ccxccx,113,111021 xxc时时,.113,111*x

侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|