運(yùn)籌學(xué)非線性規(guī)劃126-7ppt課件

1、第十二章非線性規(guī)劃12.6 KKT條件12.7 二次規(guī)劃2022-2-112.6 約束優(yōu)化的KKT條件回顧最優(yōu)條件單變量非約束多變量非約束有約束的，但只有非負(fù)約束充分條件可能是： 是凹函數(shù)最優(yōu)性的必要條件：( )f xd0dfxd0 (1,2, )djfjnxd0 (1,2, )d(0,0)jjfjnxx或者12.6 約束優(yōu)化的KKT條件一般約束問(wèn)題充分條件可能是： 是凹函數(shù)并且 是凸函數(shù) （見(jiàn)12.2）最優(yōu)性的必要條件：KKT條件( )f x( ) (1,2,)ig xim12.6 約束優(yōu)化的KKT條件最優(yōu)性的充要條件表表12.4 最優(yōu)性的充要條件最優(yōu)性的充要條件問(wèn)題最優(yōu)性的必要條件充要條件

2、可能是單變量非約束 是凹函數(shù)多變量非約束 是凹函數(shù)有約束的，但只有非負(fù)約束 是凹函數(shù)一般約束KKT條件 是凹函數(shù)并且 是凸函數(shù) （見(jiàn)12.2）( )f xd0dfxd0 (1,2, )djfjnxd0 (1,2, )d(0,0)jjfjnxx或者( )f x( )f x( )f x( ) (1,2,)ig xim12.6 約束優(yōu)化的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（或當(dāng)），對(duì)（或當(dāng)），對(duì)12.6 約束優(yōu)化的KKT條件定理：假設(shè) 是滿足某些正則性條件的可微函數(shù)。只有當(dāng)存在 個(gè)數(shù) ，使所有KKT條件都滿足，這時(shí)可能是非線性規(guī)劃問(wèn)題的一個(gè)最優(yōu)解。推論假設(shè) 是一個(gè)凹函數(shù)， 是凸函數(shù)即該問(wèn)題為凸規(guī)劃問(wèn)題），并且這些函數(shù)都滿足正則性條件。那么當(dāng)且僅當(dāng)定理的所有條件都滿足時(shí)，是一個(gè)最優(yōu)解。12( ),( ),( ),( )mf x g x gxgxm12,mu uu12*(,)nx xxx( )f x12( ),( ),( )mg x gxgx12*(,)nx xxx12.6 約束優(yōu)化

4、的KKT條件例 雙變量非線性規(guī)劃問(wèn)題 可知：121212Max ( )ln(1)s.t. 23 00fxxxxxxx且，11221( )2nmgxxx12.6 約束優(yōu)化的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 約束優(yōu)化的

5、KKT條件KKT條件： 該問(wèn)題最優(yōu)解：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 二次規(guī)劃二次規(guī)劃與線性規(guī)劃問(wèn)題的不同之處僅僅在于目標(biāo)函數(shù)也包括 和 項(xiàng)。用矩陣符號(hào)表示二次規(guī)劃問(wèn)題：用向量元素表示：半正定矩陣：如果對(duì)任何非零向量 ，都有 成立，且有非零向量 ，使 ，則稱(chēng)矩陣A為半正定矩陣。T1Max ( )2s.t. 0fxcxx Qx A

6、xbx且2jx()ijijx xxxT11111( )22nnnjjijijjijfc xq x xxcxx Qx ijjiqq其中Q注意：目標(biāo)函數(shù)為凹函數(shù)的等價(jià)條件為是半正定矩陣。xTx Ax 0T00 x Ax00 x12.7 二次規(guī)劃例如 此時(shí)：22121212121212Max ( ,)1530424s.t. 230 00f x xxxx xxxxxxx 且，12441530 ,4812 ,30 xxcxQAb12.7 二次規(guī)劃對(duì)于二次規(guī)劃的KKT條件以上題為例） KKT條件： 將不等式變?yōu)榈仁健?2121212121212Max ( ,)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 二次規(guī)劃注意此時(shí)條件2與條件4可表示為：對(duì)于每個(gè)配對(duì) 其中的兩個(gè)變量稱(chēng)為互補(bǔ)變量。這些條件得到一個(gè)新的組合約束稱(chēng)為互補(bǔ)約束。11221 12(1). 02(2). 04. 0jx yjx yu v112211( ,), (,),

8、( ,)x yxyu v11221 1+0 x yx yu v 12.7 二次規(guī)劃整個(gè)條件集合的簡(jiǎn)便形式用矩陣符號(hào)表示：1211121212112112111221 1 44 15482 30 2 30000000+0 xxuyxxuyxxvxxuyyvx yx yu v，TTTT,QxA uycAxvbx0 u0 y0 v0 x yu v0線性規(guī)劃約束互補(bǔ)約束12.7 二次規(guī)劃改進(jìn)的單純形法引入人工變量 ，相當(dāng)于應(yīng)用單純形法求解以下的線性規(guī)劃問(wèn)題滿足從KKT條件得到的線性規(guī)劃約束，但也包括這些人工變量。Min =jjZz同原單純形法相比，修改發(fā)生于：限制-輸入規(guī)則：當(dāng)你選擇一個(gè)輸入基變量時(shí)，

9、考慮排除互補(bǔ)變量已經(jīng)是一個(gè)基變量的任一非基變量；選擇應(yīng)該是根據(jù)單純形表的一般標(biāo)準(zhǔn)從其他非基變量中做出的。z12.7 二次規(guī)劃依舊用本節(jié)剛開(kāi)始的例子說(shuō)明這種方法 在引入所需人工變量后，用改進(jìn)的單純形法顯性說(shuō)明的線性規(guī)劃問(wèn)題是附加的互補(bǔ)約束用限制-輸入規(guī)則，算法自動(dòng)的執(zhí)行該約束。121211112122121Min 44 + 15s.t. 482 +30 2 30 Zzzxxuyzxxuyzxxv且1211211211221 1 000000 00+0 xxuyyvzzx yx yu v，附加的互補(bǔ)約束 12.7 二次規(guī)劃表表12.5 改進(jìn)單純形法對(duì)二次規(guī)劃例子的應(yīng)用改進(jìn)單純形法對(duì)二次規(guī)劃例子的應(yīng)

10、用迭代基變量方程Zx1x2u1y1y2v1z1z2右端項(xiàng)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 二次規(guī)劃表表12.5 改進(jìn)單純形法對(duì)二次規(guī)劃例子的應(yīng)用改進(jìn)單純形法對(duì)二次規(guī)劃例子的應(yīng)用迭代基變量方程Zx1x2u1y1y2v1z1z2右端項(xiàng)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