第四章約束最優(yōu)化方法

1、 min( ).( )0,1,2,.(1)min( )=|,( )0,1,2,.(2)ix Dnif xs tg ximf xDx xRg xim ；或或?qū)憣懗沙?；其其中中可可行行域域且? )0.( )0,( )0( )=0iiiixDxg xxg xxxxg xxg xx 設(shè)設(shè)，顯顯然然 應(yīng)應(yīng)滿滿足足所所有有的的約約束束條條件件. .現(xiàn)現(xiàn)考考慮慮某某一一個個不不等等式式約約束束條條件件滿滿足足這這一一不不等等式式有有兩兩種種情情況況：一一種種是是這這時時點點 不不在在由由這這一一約約束束條條件件所所形形成成的的可可行行域域邊邊界界上上，因因此此當(dāng)當(dāng)點點不不論論沿沿著著什什么么方方向向稍稍微

2、微離離開開點點 時時，都都不不會會違違背背這這一一約約束束條條件件，也也就就是是說說這這一一約約束束條條件件對對點點 在在選選擇擇可可行行方方向向時時不不起起約約束束作作用用. .因因此此稱稱這這樣樣的的為為點點 處處的的約約. .相相反反，另另一一種種情情況況是是，此此時時點點 位位于于由由該該約約不不起起作作用用束束.xxxx束束條條件件所所形形成成的的可可行行域域邊邊界界上上，當(dāng)當(dāng)點點沿沿某某些些方方向向稍稍微微離離開開 時時，仍仍能能滿滿足足約約束束條條件件，而而沿沿著著另另一一些些方方向向離離開開 時時，不不論論步步長長多多么么小小，都都將將不不滿滿足足這這個個約約束束條條件件. .

3、也也就就是是說說這這個個約約束束條條件件對對 選選擇擇可可行行方方向向是是有有約約束束作作用用的的. .將將這這樣樣的的約約束束條條件件稱稱為為點點 處處的的起起作作用用約約束束 (2)( )=0( )0.=|( )=0,( )0( )0( )0iiiiijxDg ximg xxI xi g ximxg ximg xxh x 對對于于問問題題式式，設(shè)設(shè)，若若有有（1 1），則則稱稱不不等等式式約約束束為為點點 處處的的起起作作用用約約束束 且且將將下下標(biāo)標(biāo)集集 ( ),1( ),1稱稱為為點點 的的起起作作用用下下標(biāo)標(biāo)集集. .若若有有（1 1），則則稱稱不不等等式式約約束束為為點點 的的不不

4、起起作作用用約約束束. .顯顯然然等等式式約約束束都都是是起起作作用用約約束束. .(2).xx對對于于非非線線性性規(guī)規(guī)劃劃問問題題式式，如如果果可可行行點點 處處，各各起起作作用用約約束束的的梯梯度度向向量量線線性性無無關(guān)關(guān)，則則稱稱 是是約約束束條條件件的的一一個個正正則則點點*(2)( )xDf xxxx 考考慮慮問問題題式式，設(shè)設(shè)，在在處處可可微微，若若是是局局部部最最優(yōu)優(yōu)解解，則則點點處處必必不不存存在在可可行行下下降降方方向向. .*1(1)(2).()0;1( )0.xxDxDxf xxDxxxgxx 考考慮慮問問題題式式或或式式，設(shè)設(shè)是是它它的的極極小小點點，那那么么可可能能在

5、在可可行行域域 的的內(nèi)內(nèi)部部，也也可可能能在在可可行行域域的的邊邊界界上上 若若在在 的的內(nèi)內(nèi)部部，實實際際上上是是個個無無約約束束問問題題, ,必必滿滿足足條條件件：若若在在 的的邊邊界界上上，分分為為幾幾種種情情況況來來討討論論：（ ）設(shè)設(shè)位位于于一一個個約約束束條條件件形形成成的的邊邊界界上上，即即只只有有一一個個起起作作用用約約束束，不不失失一一般般性性，設(shè)設(shè)位位于于第第一一個個約約束束條條件件生生成成的的邊邊界界上上，即即是是 點點處處的的起起作作用用約約束束*11*1*1*1()=0.-()().-()(),-()()( )( )gxxf xgxf xgxxpf xgxpxxf x

6、gxx故故有有若若是是局局部部最最優(yōu)優(yōu)解解，則則必必有有與與同同處處在在一一條條直直線線上上，且且方方向向相相反反 如如若若與與不不在在一一條條直直線線上上且且方方向向相相反反，則則必必可可在在 點點處處找找到到一一個個方方向向它它與與及及的的夾夾角角都都是是銳銳角角，即即 是是 點點處處的的可可行行下下降降方方向向，這這與與定定理理4.1.14.1.1相相矛矛盾盾. .用用向向量量語語言言來來描描述述上上述述幾幾何何性性質(zhì)質(zhì)，即即：若若是是局局部部最最優(yōu)優(yōu)解解，與與（起起作作用用約約束束）在在點點*1*10()-()=00()()f xgxf xgx 1 11 11 1一一階階可可微微，則則

7、必必存存在在實實數(shù)數(shù)，使使成成立立，或或說說梯梯度度向向量量可可由由梯梯度度向向量量正正線線性性表表出出. .*12*12*12*12122()=0()=0()()()()()()()()00,xgxgxxf xgxgxxxgxgxf xgxgx（ ）設(shè)設(shè) 同同時時位位于于兩兩個個約約束束條條件件形形成成的的邊邊界界上上，即即，或或說說有有兩兩個個起起作作用用約約束束，此此時時，必必位位于于與與所所形形成成的的夾夾角角內(nèi)內(nèi)；否否則則，點點處處必必可可找找到到一一個個可可行行下下降降方方向向. .用用代代數(shù)數(shù)語語言言來來描描述述：若若是是局局部部最最優(yōu)優(yōu)解解，且且與與線線性性無無關(guān)關(guān)，則則必必可

8、可由由與與的的正正線線性性組組合合表表出出. .即即：必必存存在在，使使*1122()-()-()=0f xgxgx成成立立. .*()*=1*()-()=0(3)0().()0,1,2,.(3)()-()=0,()0,iii I xiiimiiiiif xg xI xxxg ximf xg xg x 將將上上述述分分析析作作進(jìn)進(jìn)一一步步類類推推，有有在在上上式式中中，是是點點處處的的起起作作用用下下標(biāo)標(biāo)集集，且且它它們們的的起起作作用用約約束束梯梯度度向向量量線線性性無無關(guān)關(guān)，即即 同同時時也也是是一一個個正正則則點點為為了了把把不不起起作作用用約約束束也也包包括括到到上上式式中中，可可以以

9、增增加加一一個個松松緊緊條條件件: :則則式式就就可可改改寫寫為為：1,2,(4)0,1,2,.iimim *()( )0()0=0()(4)(3)(4)-(2),()()()iiiiiiiI xg xxg xiI xxD f g iI xxg iI xxg x 當(dāng)當(dāng)時時，即即是是 的的不不起起作作用用約約束束，故故有有，則則由由松松緊緊條條件件：（）. .因因此此式式第第一一組組方方程程與與式式第第一一組組方方程程實實際際上上是是相相同同的的. .式式就就是是著著名名的的庫庫恩恩 塔塔克克條條件件，簡簡稱稱為為K-TK-T條條件件，滿滿足足K-TK-T條條件件的的點點稱稱為為K-TK-T點點

10、. .定定理理4.1.24.1.2 考考慮慮問問題題式式，設(shè)設(shè)在在處處可可微微，在在點點處處連連續(xù)續(xù). . *12*=1*|()=(),()-()=0,()0,1,2,(5)0,1,2,.mmiiiiiiiI xxxf xg xg ximim 線線性性無無關(guān)關(guān)( (即即是是一一個個正正則則點點).).若若是是局局部部最最優(yōu)優(yōu)解解，則則存存在在向向量量， ，使使下下述述條條件件成成立立：min( )( )0,1,2,s.t(6)( )0,1,2, .(4)( )0( )0,-( )0(4)-ijjjjf xg ximh xjlh xh xh x 考考慮慮問問題題： ；為為了了利利用用式式，將將等

11、等式式約約束束，用用來來代代替替，這這樣樣就就可可以以利利用用式式，得得到到同同時時含含有有等等式式與與不不等等式式約約束束條條件件的的庫庫恩恩 塔塔克克條條件件，敘敘述述如如定定理理. . *12*4.1.3(6), ()=|()=0 1,( ),( )()()()( )(1,2, )()()|(),1,2,=()iiijijmxD I xi g ximf xg x iI xxg xiI xxh xjlxg xh xiI xjlx 定定理理考考慮慮問問題題式式，設(shè)設(shè)，在在處處可可微微，在在點點處處連連續(xù)續(xù), ,在在點點處處連連續(xù)續(xù)可可微微，且且向向量量集集，線線性性無無關(guān)關(guān). .若若是是問問

12、題題的的局局部部最最優(yōu)優(yōu)解解，則則必必存存在在向向量量， ，和和*12*=1=1*=()()-()-()=0,()0,1,2,(7)0,1,2,.(7)-lmliijjijiiif xg xh xg ximim 向向量量， ，使使下下述述條條件件成成立立：式式就就是是含含有有等等式式與與不不等等式式約約束束的的庫庫恩恩 塔塔克克條條件件. .*=1=1*1212*()-()-()(6)mliijjijmmf xg xh x通通常常稱稱函函數(shù)數(shù)為為問問題題式式的的廣廣義義拉拉格格朗朗日日函函數(shù)數(shù)，稱稱乘乘子子， ，和和， ，為為廣廣義義拉拉格格朗朗日日乘乘子子，稱稱向向量量和和為為乘乘子子向向量

13、量. .22112212221212min( )2210105.36f xxx xxxxxxs txx 22112212*T1212*121*12*2( )0( )50.( )360=(, ) ,4+2-10()=2+2-10-2()=-2-3()=-1ig xgxxxs tgxxxKTxxxxxf xxxxgxxgx 解解：將將上上述述問問題題的的約約束束條條件件改改寫寫為為的的形形式式：設(shè)設(shè)點點為為有有及及1211212122221122121212124.1.24+2-10+2+3=02+2-10+2+=0(5)0(63)000 xxxxxxxxxxxxKT 由由定定理理，且且將將式式中

14、中第第1 1個個向向量量方方程程拆拆成成分分量量形形式式，有有：求求解解上上述述聯(lián)聯(lián)立立方方程程組組( (若若原原問問題題有有等等式式約約束束的的話話，還還須須把把等等式式約約束束也也加加到到方方程程組組中中去去) )，即即可可求求出出 ， ， ，則則可可得得到到條條件件的的點點. .上上述述方方程程組組是是非非線線性性方方程程組組，*0,.ix 求求解解時時一一般般都都要要首首先先利利用用松松緊緊條條件件（即即上上述述方方程程組組中中的的第第3 3、第第4 4個個方方程程），其其實實質(zhì)質(zhì)是是分分析析點點處處，哪哪個個（那那些些）是是不不起起作作用用約約束束，以以便便得得到到這這樣樣分分情情況

15、況討討論論求求解解較較容容易易*12121212*1122121112121(1)=0=04+2-10=02+2-10=0=0=5()0(2)( )0( )=04+2-10+2=02+2-10+2=0(5xxxxxxxgxgxgxxxxxxx 假假設(shè)設(shè)兩兩個個約約束束均均是是 點點處處的的不不起起作作用用約約束束，即即有有，代代入入方方程程組組中中有有：解解之之有有: :但但將將該該點點代代入入約約束束條條件件，不不滿滿足足，因因此此該該點點不不是是可可行行點點. .若若是是起起作作用用約約束束，是是不不起起作作用用約約束束，則則有有，代代入入式式中中：22121)00 xx 1212*T12

16、112212221222=1=21=0=(1, 2)(3)( )0( )0=04+2-10+3=02+2-10+=0(63)00=0 xxxgxgxxxxxxx 解解出出：代代入入原原問問題題約約束束條條件件中中檢檢驗驗，可可知知該該點點是是可可行行點點，且且滿滿足足定定理理中中條條件件，又又是是一一個個正正則則點點，故故它它是是一一個個K-TK-T點點. .若若是是不不起起作作用用約約束束，是是起起作作用用約約束束，則則有有，代代入入式式中中：解解上上述述方方程程組組，可可得得到到2222122=-.=-055=0=0(1) 或或而而，不不滿滿足足的的條條件件，而而及及同同情情形形的的結(jié)結(jié)果

17、果1212112121222212121212*T(4)00 ,4+2-10+2+3=02+2-10+2+=0506300000 ,=(1, 2) .( )xxxxxxxxxxxf xKT 假假設(shè)設(shè)兩兩個個約約束束均均起起作作用用，這這時時，故故有有求求解解上上述述方方程程組組，得得到到的的解解不不滿滿足足與與故故舍舍去去. .因因此此本本題題的的K-TK-T點點為為 同同時時本本題題凸凸函函數(shù)數(shù)，故故本本題題是是凸凸規(guī)規(guī)劃劃，對對凸凸規(guī)規(guī)劃劃條條件件也也是是充充分分條條件件*T=(1, 2).x，因因此此也也是是本本題題的的全全局局極極小小點點min( ).( )0,1,2,.(1)ikkk

18、kf xs tg ximDxxp ( )( )( )( )( )( )考考慮慮問問題題：；記記上上述述問問題題的的可可行行域域為為 ，設(shè)設(shè)是是它它的的一一個個可可行行點點，但但并并不不是是所所要要求求的的極極小小點點. .為為了了求求得得極極小小點點或或近近似似極極小小點點，應(yīng)應(yīng)在在的的可可行行下下降降方方向向中中選選取取某某一一方方向向為為搜搜索索方方向向，然然后后確確定定該該方方向向上上的的步步長長，使使 +1+1+1+1=+(2)()()kkkkkkkkkxxpDf xf xxxx ()( )( )()( )( )()( )()( )()()()()( )( )若若滿滿足足精精度度要要求

19、求，停停止止迭迭代代，就就是是所所要要求求的的點點；否否則則從從出出發(fā)發(fā)繼繼續(xù)續(xù)迭迭代代，直直到到滿滿足足要要求求為為止止，上上述述方方法法稱稱為為可可行行方方向向法法. .它它具具有有下下述述特特點點：迭迭代代過過程程中中所所采采用用的的搜搜索索方方向向為為可可行行方方向向，所所產(chǎn)產(chǎn)生生的的迭迭代代點點列列始始終終在在可可行行域域內(nèi)內(nèi)，目目標(biāo)標(biāo)函函數(shù)數(shù)值值單單調(diào)調(diào)下下降降. .這這是是一一類類算算法法，由由不不同同的的規(guī)規(guī)則則產(chǎn)產(chǎn)出出可可行行方方向向作作為為搜搜索索方方向向形形成成了了不不同同的的可可行行方方outendijkoutendijk1960向向法法. .下下面面介介紹紹Z Z可可

20、行行方方向向法法，它它是是由由Z Z于于年年提提出出的的一一種種算算法法，用用求求解解一一個個線線性性規(guī)規(guī)劃劃問問題題來來確確定定可可行行下下降降方方向向的的方方法法，是是一一種種線線性性化化的的方方法法. .min( ),s.t(3).( ),(3).nmlf xAxbExef xAmnElnxRbReRml 考考查查一一個個非非線線性性規(guī)規(guī)劃劃問問題題： ；其其中中：是是可可微微函函數(shù)數(shù)， 為為矩矩陣陣， 為為矩矩陣陣, ,即即式式中中有有 個個線線性性不不等等式式約約束束，有有 個個線線性性等等式式約約束束1122112214.2.1(3)=,=: 1)000.2)( )0.nTxxA

21、x b A x bAbAbAbp pRpxA pEppf xpp 定定理理設(shè)設(shè) 是是問問題題式式的的一一個個可可行行解解，且且在在點點處處有有，其其中中，則則向向量量（且且）是是點點 處處的的可可行行方方向向的的充充要要條條件件為為：，若若此此時時 又又滿滿足足：，則則 是是一一個個可可行行下下降降方方向向112(3)min( );0.0(4)11,1,2, .(,) .(4).=0TjTnxpzf xpA ps tEpdjnpd ddpppp 從從上上述述定定理理可可知知，要要尋尋找找問問題題式式的的可可行行點點 的的一一個個可可行行下下降降方方向向 就就相相當(dāng)當(dāng)于于要要求求解解如如下下的的

22、一一個個線線性性規(guī)規(guī)劃劃問問題題： 式式中中式式中中所所增增加加的的最最后后一一個個約約束束是是為為了了防防止止，而而求求 主主要要是是求求出出一一個個方方向向，對對模模的的大大小小無無關(guān)關(guān)緊緊要要 顯顯然然是是可可行行解解，因因此此函函數(shù)數(shù)的的最最優(yōu)優(yōu)值值必必小小于于或或等等于于零零，若若目目標(biāo)標(biāo)函函數(shù)數(shù)-px的的最最優(yōu)優(yōu)值值小小于于零零，則則得得到到可可行行下下降降方方向向 ； 若若目目標(biāo)標(biāo)函函數(shù)數(shù)的的最最優(yōu)優(yōu)值值等等于于零零，則則可可以以證證明明 即即為為庫庫恩恩 塔塔克克點點. .112211224.2.2(3)=,=-(4)xxA x b A x bAbAbAbx 定定理理設(shè)設(shè) 是是

23、規(guī)規(guī)劃劃問問題題式式的的一一個個可可行行解解，且且在在點點處處有有，其其中中，則則 是是庫庫恩恩 塔塔克克點點的的充充要要條條件件是是規(guī)規(guī)劃劃式式的的目目標(biāo)標(biāo)函函數(shù)數(shù)最最優(yōu)優(yōu)值值為為零零. .min( )s.t( )0,1,2,.(5)( )( )1,2,inif xg ximxRf xg xim考考查查一一個個非非線線性性規(guī)規(guī)劃劃問問題題： ；其其中中：，（）均均為為可可微微函函數(shù)數(shù). .如如何何求求上上式式的的可可行行下下降降方方向向？ 4.2.3(5)=|( )0( ),( )()( )()( )0( )0 ().iiiTTixIi g xxf xg x iIxg x iIxf xpg

24、xpiIp 定定理理設(shè)設(shè) 是是問問題題式式的的一一個個可可行行解解，是是點點 處處的的起起作作用用約約束束下下標(biāo)標(biāo)集集，若若在在點點 處處可可微微，在在點點 處處連連續(xù)續(xù)，如如果果，則則 是是可可行行下下降降方方向向(5)( )0(6)( )0 ()( )-( )()(7)0TTiTTixpf xpg xpiIpf xpg xpiI 根根據(jù)據(jù)定定理理可可知知，規(guī)規(guī)劃劃問問題題式式在在可可行行解解 處處的的可可行行方方向向 應(yīng)應(yīng)滿滿足足：而而上上述述方方程程組組當(dāng)當(dāng)引引進(jìn)進(jìn)數(shù)數(shù) 后后，等等價價于于下下述述方方程程組組求求向向量量及及實實數(shù)數(shù) ：12min( ).-( )()(8)11,1,2,(

25、,) .TTijTnppf xps tg xpiIdjnpd dd 而而滿滿足足上上式式的的可可行行下下降降方方向向 及及數(shù)數(shù) 一一般般有有很很多多個個，而而希希望望求求出出能能使使目目標(biāo)標(biāo)函函數(shù)數(shù)值值下下降降最最多多的的方方向向 ，因因此此將將上上式式轉(zhuǎn)轉(zhuǎn)化化為為對對 求求極極小小值值的的一一個個線線性性規(guī)規(guī)劃劃問問題題： ；式式中中 ( )( )( +1)( +1)( )( )( +1)( +1)( )( )0( )( ),=+()min(+)(9)max|+kkkkkkkkkkkkkkkxpxDkxpxxxpxDf xf xpxpD 設(shè)設(shè)可可行行點點 處處的的可可行行下下降降方方向向 已

26、已求求出出，為為了了以以后后敘敘述述方方便便，假假定定就就是是第第 次次迭迭代代點點的的出出發(fā)發(fā)點點其其可可行行下下降降方方向向為為，則則后后繼繼點點為為為為了了使使，且且使使的的值值盡盡可可能能的的小小，求求解解一一維維搜搜索索問問題題：同同樣樣區(qū)區(qū)分分不不同同的的約約束束情情況況來來討討論論. .( )( )( )( )( )( )( )( )( )( )( )(3)min(+)(+).(10)(+)=0= .kkkkkkkkkkkf xpA xpbs tE xpepEpxExex 求求解解上上式式時時，考考慮慮到到線線性性約約束束時時式式，先先求求解解： ；而而上上式式可可進(jìn)進(jìn)一一步步化

27、化簡簡：因因為為是是可可行行方方向向，有有：； 而而是是可可行行點點，有有：因因此此上上式式中中第第2 2個個約約束束必必定定能能滿滿足足，可可不不再再考考慮慮它它. .在在點點處處將將不不等等式式約約束束分分為為起起作作用用約約束束與與不不起起作作用用約約束束，設(shè)設(shè)( )( )11221122( )( )111( )( )222( )( )1( )11=,=(10)+(11)+(12)0 .0=(11).(10)(12)(10)kkkkkkkkkA xb A xbAbAbAbA xA pbA xA pbpA pA xb 若若記記，則則式式中中第第一一個個約約束束就就可可記記成成又又因因是是可

28、可行行方方向向，由由定定理理知知又又設(shè)設(shè)，以以及及，因因此此式式也也自自然然滿滿足足 因因此此式式中中的的約約束束條條件件只只剩剩下下式式，故故式式可可簡簡化化為為：( )( )( )( )222( )( )222( )( )222( )( )2222min(+)+.(13)0-,(14)0-,0kkkkkkkkkkf xpA xA pbs tA pb A xbb A xpA ppbbb A xA xbb ；以以下下再再推推導(dǎo)導(dǎo)上上式式中中求求 上上限限的的公公式式，將將上上式式中中的的約約束束條條件件改改寫寫為為：若若記記則則有有：，同同時時考考慮慮到到，且且故故由由此此可可有有 的的上上限

29、限：( )22( )2( )( )( )(-)min0 ,0=()(15)0(10)min(+).0(16)(15).(4)kiiikiiiikkkbb A xpppA ppbpbpif xps txp 當(dāng)當(dāng)當(dāng)當(dāng)（式式中中， 表表示示 ， 中中第第 個個分分量量）因因此此求求解解式式就就化化為為求求解解： ；由由式式確確定定因因此此對對于于約約束束為為線線性性函函數(shù)數(shù)的的非非線線性性規(guī)規(guī)劃劃，若若已已知知一一個個迭迭代代點點后后，可可由由求求解解式式得得到到可可行行下下降降方方向向)(16).kk ，再再由由式式求求解解在在此此方方向向上上的的步步長長(0)12( )1122( )( )112

30、2( )( )11,: 0.2=,.3=0=0(kkkkkxDkxAbAbAbAbA xb A xbxxEAf x 約約束束為為線線性性函函數(shù)數(shù)時時非非線線性性規(guī)規(guī)劃劃的的可可行行方方向向法法計計算算步步驟驟如如下下：第第 步步：給給定定初初始始可可行行點點允允許許誤誤差差0,00,0，置置第第 步步：在在點點處處把把 與與 分分解解成成：，使使第第 步步：判判斷斷是是否否是是問問題題的的可可行行域域的的內(nèi)內(nèi)點點. .（1 1）若若是是可可行行域域的的一一個個內(nèi)內(nèi)點點（此此時時問問題題中中沒沒有有等等式式約約束束，即即，且且），而而且且( )1( ),.kkx 停停止止迭迭代代，得得到到近近似

31、似極極小小點點( )( )1( )( )( )( )1()=-()64min( );0.011,1,2, .kkkkkkTjxf xpf xxxzf xpA ps tEpdjn （2 2）若若是是可可行行域域的的一一個個內(nèi)內(nèi)點點，且且，則則取取搜搜索索方方向向，然然后后轉(zhuǎn)轉(zhuǎn)第第 步步，即即用用目目標(biāo)標(biāo)函函數(shù)數(shù)的的負(fù)負(fù)梯梯度度方方向向作作搜搜索索方方向向再再求求步步長長，此此時時類類似似于于無無約約束束問問題題. .（3 3）若若不不是是可可行行域域的的一一個個內(nèi)內(nèi)點點（即即在在可可行行域域的的邊邊界界上上），則則要要尋尋找找可可行行下下降降方方向向，轉(zhuǎn)轉(zhuǎn)第第4 4步步. .第第 步步： 求求解

32、解線線性性規(guī)規(guī)劃劃問問題題： ( )( )12(,) .(,).Tkknpd ddpz 其其中中設(shè)設(shè)求求得得最最優(yōu)優(yōu)解解為為( )( )2( )( )( )( )( +1)( )( )5.(),.66min(+).0=+7:1,kkTkkkkkkkkkzf xpxpf xps txxpkk 第第 步步： 判判斷斷精精度度 若若則則停停止止迭迭代代. .輸輸出出否否則則以以為為搜搜索索方方向向轉(zhuǎn)轉(zhuǎn)第第 步步. .第第 步步：作作一一維維搜搜索索. .首首先先計計算算，然然后后作作一一維維搜搜索索： ；求求得得最最優(yōu)優(yōu)解解，令令第第 步步：置置返返回回第第2 2步步. .2212121212(0)

33、12min( )(6)(2)243212.00=(2,3)0.0010.001.Tf xxxxxxxs txxx + +；取取，(0)(0)1(0)2(0)3(0)4(0)1=(2,3)()=22 34()=3 22 312()=20()=301=Txg xg xg xg xxAb 解解：將將代代入入約約束束條條件件因因此此第第1 1、2 2個個約約束束為為點點的的起起作作用用約約束束故故-4-4， -12-1212(0)1(0)1212121212(,)min()0.011,1,2.0,( )(212,24)()( 8,2)min8220320.1111TTjTTpd dzf xpA ps

34、tEpdjEf xxxf xzdddddds tdd 令令，求求解解線線性性規(guī)規(guī)劃劃： 因因為為, ,故故. .故故求求解解線線性性規(guī)規(guī)劃劃: : 11221212121212121,1.82min82213252.200ydydzyyzyyyyyyys tyyy 做做變變量量代代換換：令令則則+6+6故故上上式式化化為為： +6 +6引引入入松松弛弛變變量量標(biāo)標(biāo)準(zhǔn)準(zhǔn)化化：121231241526(0)121122(1)(0)(0)min8221325.220, 1,2,6522,0,3321,113222233313jzyyyyyyyys tyyyyyjyyzdydyxxp +6 +6用用單

35、單純純形形法法解解之之，得得：故故：因因此此(0)(0)222(0)(0)(1)(1)22222,3313min31min()min().0321333100()(4)(1)()391313bbA xpA pf xpf xs tf x 作作一一維維搜搜索索：所所以以求求解解規(guī)規(guī)劃劃式式： 因因為為*(1)1(1)(0)(0)(1)1(1)(1)1(1)(1)1(1)233100,(()613136040()(,) ,()131348636()=24131313486()=-32121313Tfxxxpf xf xf xxg xg x 故故求求得得最最優(yōu)優(yōu)值值：故故因因

36、此此再再對對尋尋找找可可行行下下降降方方向向. .(1)3(1)41112(1)12121248()=0136()=013( 3, 2),12(,)6040min()1313320.1111TTg xg xAbpd dzf xpdddds tdd 因因此此令令，求求解解線線性性規(guī)規(guī)劃劃： 112212123142526*(2)12*116040100min1313133252.220, 1,2,55,0,0.-3486100(,) ,()13 1313jTydydzyyyyyyys tyyyyyjyyzxxf x 引引入入變變量量，且且添添加加人人工工變變量量后后，可可化化成成下下述述規(guī)規(guī)劃劃

37、： + +用用單單純純形形法法解解之之，得得：故故是是庫庫恩恩 塔塔克克點點. .故故： ( )( )( )( )( )( )( )min(+).0sup|(+)0,1,2,kkkkkkkkixppf xps tg xpim 設(shè)設(shè)對對于于規(guī)規(guī)劃劃(5)(5)式式，通通過過求求解解線線性性規(guī)規(guī)劃劃(8)(8)式式，得得到到了了及及可可行行下下降降方方向向. .現(xiàn)現(xiàn)要要沿沿方方向向進(jìn)進(jìn)行行一一維維搜搜索索，求求得得，即即求求解解：其其中中 (0)( )( )( )( )( )( )( )( )( )1: 0.():()|()0,0()()()()kkkkikkkkkxDkxI xI xi g xi

38、mI xf xxI xf x 1 12 21 1約約束束為為非非線線性性函函數(shù)數(shù)時時，非非線線性性規(guī)規(guī)劃劃式式的的可可行行方方向向法法的的計計算算步步驟驟如如下下：第第 步步：給給定定初初始始可可行行點點，允允許許誤誤差差00，00，并并置置 第第2 2步步：確確定定點點處處的的起起作作用用下下標(biāo)標(biāo)集集 (1) (1)若若為為空空集集，而而且且，則則停停止止迭迭代代，得得到到近近似似極極小小值值. .(2)(2)若若為為空空集集，但但( )( )()kkpf x 1 1，則則取取搜搜索索方方向向=-=-，然然后后轉(zhuǎn)轉(zhuǎn)第第5 5步步. .( )( )( )( )()()kkkkkI xxDI x

39、p 因因為為為為空空集集，表表明明是是可可行行域域 的的內(nèi)內(nèi)點點，因因此此任任一一方方向向均均是是可可行行方方向向，類類似似于于無無約約束束問問題題，故故可可用用最最速速下下降降法法尋尋求求下下一一個個迭迭代代點點，但但畢畢竟竟不不是是真真正正的的無無約約束束問問題題，步步長長要要受受到到可可行行域域邊邊界界的的限限制制. . (3) (3)若若不不為為空空集集，轉(zhuǎn)轉(zhuǎn)第第3 3步步. .第第3 3步步：求求解解線線性性規(guī)規(guī)劃劃問問題題(8)(8)式式. .設(shè)設(shè)求求得得最最優(yōu)優(yōu)解解為為(,).(,).( )( )( )( )( )( )(1)( )( )4-:1kkkkkkkkkkkkkxxxp

40、ppxxpkk 2 2第第 步步：判判斷斷精精度度. .若若 ，則則停停止止迭迭代代，因因為為0 0，說說明明在在點點處處找找不不到到可可行行下下降降方方向向，可可以以認(rèn)認(rèn)為為是是一一個個庫庫恩恩 塔塔克克點點（假假定定也也是是一一個個正正則則點點）；否否則則以以為為搜搜索索方方向向，轉(zhuǎn)轉(zhuǎn)第第5 5步步. .第第5 5步步：在在點點處處沿沿搜搜索索方方向向作作一一維維搜搜索索，確確定定可可行行的的最最優(yōu)優(yōu)步步長長. .計計算算： 第第6 6步步：置置，返返回回第第2 2步步. .min( )( )0,1,2,.(1)( )0,1,2, .,( ),( ),( ).ijnijf xg xims

41、th xjlxRf xg x h xD 考考慮慮問問題題：；其其中中均均存存在在一一階階連連續(xù)續(xù)偏偏導(dǎo)導(dǎo)數(shù)數(shù)，記記其其可可行行域域為為( )(1)( ),( ),( )min()(ikjkf xg xh xxf xf x ( )( )近近似似規(guī)規(guī)劃劃法法的的基基本本做做法法：將將問問題題式式中中的的在在點點處處作作一一階階泰泰勒勒展展開開，并并取取其其線線性性近近似似，從從而而得得到到線線性性近近似似規(guī)規(guī)劃劃，并并對對其其變變量量的的取取值值范范圍圍加加以以限限制制因因為為用用線線性性函函數(shù)數(shù)逼逼近近非非線線性性函函數(shù)數(shù)時時，一一般般只只在在展展開開點點附附近近的的近近似似程程度度較較好好，遠(yuǎn)

42、遠(yuǎn)離離展展開開點點，可可能能產(chǎn)產(chǎn)生生較較大大偏偏差差，特特別別是是函函數(shù)數(shù)的的非非線線性性程程度度較較高高時時，會會產(chǎn)產(chǎn)生生偏偏差差更更大大因因此此需需要要對對變變量量的的取取值值范范圍圍加加以以限限制制可可得得到到下下列列線線性性規(guī)規(guī)劃劃問問題題：+ +( )( )( )( )( )( )( )( )( )( )()()01,2,.()()01,2,(2),1,2,kkkkkiikkkjjkkjjjx xg xg xxxims th xh xxxjlxxjn （ - -）（），（），( )( +1)( +1)( +1)( )( +1)( +1).(1)=1,2,kjjkkkkkjjkjxxx

43、jxxjnx 上上述述線線性性規(guī)規(guī)劃劃中中最最后后一一組組不不等等式式約約束束，即即是是對對變變量量 所所施施加加的的限限制制，其其中中是是 中中第第 個個分分量量，是是預(yù)預(yù)先先給給定定的的變變量量限限制制范范圍圍，稱稱為為步步長長限限制制量量. .求求解解上上式式，設(shè)設(shè)得得到到的的最最優(yōu)優(yōu)解解為為若若是是原原問問題題式式的的可可行行解解，則則在在這這一一點點再再將將目目標(biāo)標(biāo)函函數(shù)數(shù)與與約約束束條條件件函函數(shù)數(shù)線線性性化化，并并沿沿用用步步長長限限制制：（）. .若若不不屬屬于于原原問問題題的的可可行行域域，則則減減小小步步長長限限制制量量，取?。? )=1 11,2,.2 4.kjjn （）

44、，一一般般 取取， 等等值值 重重新新求求解解當(dāng)當(dāng)前前的的線線性性規(guī)規(guī)劃劃問問題題(0)( +1)( )12( )( )( )( )( )( )( )( )( )1=1,2,.: 0min()()()()01,2,.()()01,2,kkjjkkkkkkiikkkjjjjxjnkf xf xx xg xg xxxims th xh xxxjlxx 第第 步步：給給定定初初始始可可行行點點，步步長長限限制制（），縮縮小小系系數(shù)數(shù)(0,1).(0,1).允允許許誤誤差差置置. .第第2 2步步：求求解解線線性性規(guī)規(guī)劃劃問問題題：+ +（ - -）（），（），( )( ),1,2,.kkjjnx 求

45、求得得最最優(yōu)優(yōu)解解(1)( )( )(1)( )1(1)( )2( )2(1)(1)(1)( )3,1,2, ,()(),1,2,1,2, .:1kkkjjkkkkkjkkkkjjxxxjnf xf xxxjnxxjnkk 第第 步步：若若 滿滿足足原原問問題題的的可可行行性性，則則令令= = ，轉(zhuǎn)轉(zhuǎn)第第4 4步步；否否則則 置置:=:=，返返回回第第2 2步步. . 第第4 4步步：若若 ，且且滿滿足足 或或 11（如如取取 = = 或或1010），允允許許誤誤差差，令令第第 步步：求求解解罰罰函函數(shù)數(shù)的的無無約約束束極極小小化化問問題題. .以以為為初初始始點點，選選擇擇適適當(dāng)當(dāng)?shù)牡姆椒椒?/p>

46、法求求解解，得得其其極極小小點點第第 步步：判判斷斷精精度度. .在在點點，若若罰罰項項 00，置置第第步步：構(gòu)構(gòu)造造障障礙礙函函數(shù)數(shù)第第步步：求求解解障障礙礙函函數(shù)數(shù)的的無無約約束束極極小小化化問問題題以以為為初初始始點點，求求解解min min 得得其其極極小小點點式式中中是是可可行行域域中中所所有有嚴(yán)嚴(yán)格格內(nèi)內(nèi)點點的的集集合合( )(*)+111( )( -1)( )(1)=:+11ln( )( )-()- ().kkkmmkkiiiikkkkxxrrkkrrg xg xxxf xf x 第第4 4步步：判判斷斷精精度度. .若若收收斂斂準(zhǔn)準(zhǔn)則則得得到到滿滿足足，則則迭迭代代停停止止，取取作作為為原原問問題題極極小小點點的的近近似