可行方向法实用教案

《可行方向法实用教案》由会员分享，可在线阅读，更多相关《可行方向法实用教案（19页珍藏版）》请在装配图网上搜索。

1、可行方向法43 .定定义义,.0,nnCRxCdR 设设非非空空集集合合某某一一点点对对, ,(0, ),.txtdDdx 均均有有则则称称 为为从从点点 出出发发的的使使可可行行方方向向对对x1d2dD12,dxdx不不是是 处处的的可可行行方方向向是是点点 处处的的可可行行方方向向。第1页/共18页第一页，共19页。可行方向法.Ex 设设由由约约束束条条件件1234123412342342347, (1)232 (2)3 (3)2 5,2,41,0,1 (4) ,2,3 (5),4ixxxxxxxxxxxxxxxxi ,(0,1,2,3)TDx 所所确确定定的的可可行行集集任任求求一一个个

2、在在点点处处的的可可行行方方向向. .1(1),(2),(30.)xx 解解. .首首先先在在点点 处处的的有有效效约约束束为为和和设设所所求求可可行行方方向向为为1234,) ,(0,(0, ),Tddtddd 根根据据可可行行方方向向使使对对的的定定义义能能有有第2页/共18页第二页，共19页。1234,1,2,()3Ttdtttddxtdd 也也能能满满足足所所有有的的有有效效约约束束：12341234123412(1)3(2)4(37, 23(1)(2)2(3 )5,)2,03(1)(2)(3 , tdttdtdtdtdtdtdtdtdtdtddtd 整整理理即即为为123412341

3、23412340,23230,0,0.ddddddddddddd 第3页/共18页第三页，共19页。1234(,)Tdd ddd 满满足足上上述述不不等等式式组组的的均均为为可可行行方方向向. .现现只只求求一一个个可可行行方方向向, ,可可将将不不等等式式改改为为等等号号, ,求求解解得得132342,0ddddd 1301,dd 为为使使即即得得可可取取一一可可行行方方向向(2, 1,1,0) .Td ,kx, ,典典型型的的策策略略应应为为: :由由可可行行点点出出利利发发用用可可行行方方向向的的概概念念找找一一下下降降的的kd可可行行方方向向做做搜搜索索方方向向, ,然然后后确确定定沿

4、沿此此方方向向移移动动的的步步长长, ,得得到到下下一一1.kx 迭迭代代点点这这一一类类方方法法称称为为可可行行方方向向法法 搜搜索索方方向向的的选选择择方方式式不不同同就就形形成成不不同同的的可可行行方方向向法法. .第4页/共18页第四页，共19页。Zoutendijk可可行行方方向向法法考考虑虑min( ), (4.3.1). . , .bf xs tAxGxc 4 3 1,( . . ),kZoutendixjk处处 为为得得对对于于问问题题在在迭迭代代可可行行点点到到一一下下降降可可行行方方向向, ,19604 3 1.( . . ),在在年年首首先先提提出出借借助助于于线线性性规

5、规划划由由于于中中约约束束是是线线性性的的 仅仅目目标标( ),( ),kf xxf x函函数数是是非非线线性性的的 而而我我们们又又是是在在的的附附近近考考察察很很自自然然地地想想到到用用( )( ).kf xxf x在在处处的的一一阶阶泰泰勒勒多多项项式式近近似似代代替替第5页/共18页第五页，共19页。kx设设满满足足1122,kkkA xb A xb Gxc1122,.AbAbAb其其中中令令,kxxd( )().(kkTff xxxfd 于于是是得得到到线线性性规规划划1122min(),. . (), (), ( ().kkTkkkf xds tA xdA xdG xdcf xbb

6、 11(),kkf xA xb 由由于于为为常常数数和和所所以以上上述述线线性性规规划划等等价价于于第6页/共18页第六页，共19页。2min), (4.3.2). . 0, 0,.(0kTds tf xA dGdd ,0(4.3.2),0,d 显显然然为为线线性性规规划划的的可可行行点点 其其对对应应的的目目标标函函数数值值为为*(4.3.2),(0.(,)0)TTkkf xddf xd 所所以以若若为为的的最最优优若若解解 则则*(4.3.1)0,(kkTdfxdx 为为原原问问题题在在处处的的下下降降可可行行方方向向; ;若若表表明明20,0,)0(0,kTGddfddxAd则则表表明明

7、对对于于的的有有任任足足都都意意满满也也即即对对于于任任意意满满足足第7页/共18页第七页，共19页。20,0,0AGdGdd 12(0,0,0)0,Tkdf xFarkasd的的 也也满满足足根根据据引引理理 存存在在使使212212)()(TTTTkTf xAGGGA 2,TTAG 12,(4.3.1).kxKT 这这表表明明为为线线性性规规划划的的其其点点中中第8页/共18页第八页，共19页。Zoutendijk可可行行方方向向法法01.,0;stepxk 选选择择初初始始可可行行点点令令12122.,kstepxAA Abb b根根据据的的有有效效约约束束把把 分分解解为为相相应应地地

8、把把 分分解解为为使使1122,;kkA xb A xb3.step 求求解解线线性性规规划划2(0, 0, min),. . 11,1,2,. ,kTids tf xGddinA d *1,1idd设设其其最最优优解解为为是是为为了了保保证证解解限限制制是是有有界界的的；第9页/共18页第九页，共19页。*4.|(),|,kTkstepdf xx 即即为为所所求求的的最最则则优优点点若若停停算算; ;*15.)0,argmin(kktfstepAxdtd 则则由由线线搜搜索索若若得得1*,1,2;6;kkkxxt dkkstepstep 令令转转否否则则转转*1126.,kstepuA xb

9、 vA d设设计计算算min|.0iiiutvv *1*0),1,2m(.inkkkkt ttdxxt dfkkxstep 令令转转由由确确定定第10页/共18页第十页，共19页。.ExZoutendijk用用可可行行方方向向法法求求解解22121212121, 1512, 0, min4. . 10.0 xxxs txxxxx 0(0,2) ,Tx 解解. .取取分分解解111510,1001A 0120(1,0),xxA 一一个个因因为为在在处处有有效效约约束束故故仅仅第11页/共18页第十一页，共19页。01121111510 ,12 ,0().160,010bxAbf 012(,) ,

10、Tdd d 设设所所求求下下降降方方则则相相应应的的向向为为线线性性规规划划为为0022112()0, 11, min16 11 . . Tdds txdAdddf 000(0(0, 1) .)16,.TTdfdx 求求得得最最优优解解为为所所以以需需要要迭迭代代因因第12页/共18页第十二页，共19页。求求线线性性搜搜索索区区间间. .00111(1,8,2) ,( 1, 10, 1) .TTxbvAAdu 计计算算3121234441,2,0, 555uuuttvvv 中中选选出出在在从从最最小小者者中中求求0020)4(2)4min(,5tdttf x 的的于于是是1000(0,6)5.

11、Txtxd2作作第第 次次迭迭代代第13页/共18页第十三页，共19页。11211510120,xxxx 关关于于 的的有有效效和和约约束束为为所所以以1212111510112,011000AAbb 11120),(485ddxdf 设设相相应应线线性性规规划划为为2121124850, min 0, 11, . . 1510 11.ddddds td 第14页/共18页第十四页，共19页。1111111536,15xbvAudA 12123633,0, 5555uuttvv中中选选出出最最小小者者在在从从中中求求111240481443min(5),9525tdtf xtt 得得最最优优解

12、解于于是是2111(2, )5.35Txtxd第15页/共18页第十五页，共19页。330,45501xd 类类似似再再作作迭迭代代得得33,()0Tdf x 即即得得本本问问题题的的最最优优解解. .第16页/共18页第十六页，共19页。Zoutendijk从从可可行行方方向向法法可可以以体体会会到到线线性性规规划划在在处处理理非非线线性性规规划划时时的的作作用用. .对对于于非非线线性性约约束束的的情情况况显显然然也也可可以以用用类类似似的的方方法法, ,即即把把约约束束,kxTaylor函函数数也也用用在在迭迭代代点点处处的的一一阶阶多多项项式式代代替替 而而得得一一线线性性规规划划以以

13、kx确确定定处处的的下下降降可可行行方方向向. .ZoutendijkKT可可行行方方向向法法得得到到的的点点列列有有可可能能不不收收敛敛到到最最优优点点或或点点22,kkxA xb 一一种种改改进进策策略略是是在在迭迭代代点点处处 不不仅仅考考虑虑有有效效约约束束而而把把满满足足,.kiiibxAb 的的约约束束也也考考虑虑在在内内 这这样样的的约约束束称称为为有有效效约约束束第17页/共18页第十七页，共19页。谢谢您的观看(gunkn)！第18页/共18页第十八页，共19页。NoImage内容(nirng)总结可行方向法。第17页/共18页。谢谢您的观看(gunkn)第十九页，共19页。