用投影梯度法解不等式約束線性規(guī)劃

1、用投影梯度法解不等式約束線性規(guī)劃libXPXCiTiT1, s.t.min考慮不等式約束的線性規(guī)劃考慮不等式約束的線性規(guī)劃nPPPA,21A其中其中 ， ， 假設(shè)已有可行解假設(shè)已有可行解 ，滿足，滿足nRX nl linbXPnibXPiTiiTi1,1,Tnbbbb,21bXATbAXTX是列滿秩矩陣是列滿秩矩陣由于由于 是方陣，所以存在是方陣，所以存在 ，記，記1A因?yàn)橐驗(yàn)?，所以，所以 XfAAAWTT1采用投影梯度法，先計(jì)算采用投影梯度法，先計(jì)算由于由于 ，所以，所以 ，因此，因此 XCXfT CXfCACAAAWTT11因?yàn)橐驗(yàn)?，只用考慮第二、三種情況，只用考慮第二、三種情況 Xf

2、WA首先考慮第三種情況首先考慮第三種情況0W此時(shí)此時(shí) 已經(jīng)滿足已經(jīng)滿足K-T條件，下面分析這樣得到的條件，下面分析這樣得到的是什么解？是什么解？XlibXPXCiTiT1, s.t.minliyCyPybiliiiliii1, 0 s.t.max11原問(wèn)題原問(wèn)題對(duì)偶問(wèn)題對(duì)偶問(wèn)題現(xiàn)在已知現(xiàn)在已知 ，如果令，如果令01CAW可知可知 是對(duì)偶問(wèn)題基可行解，目標(biāo)值為是對(duì)偶問(wèn)題基可行解，目標(biāo)值為00WYYWbT原問(wèn)題的可行解原問(wèn)題的可行解 ，目標(biāo)函數(shù)，目標(biāo)函數(shù)bAXT小結(jié)：當(dāng)?shù)谌N情況出現(xiàn)時(shí)，可以得到小結(jié)：當(dāng)?shù)谌N情況出現(xiàn)時(shí)，可以得到對(duì)偶問(wèn)題的基可行解對(duì)偶問(wèn)題的基可行解 ，bACTT00WYCAW1目標(biāo)

3、函數(shù)目標(biāo)函數(shù)CAbT1由弱對(duì)偶定理可知它們分別是原問(wèn)題和對(duì)偶問(wèn)題由弱對(duì)偶定理可知它們分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解，并且的最優(yōu)解，并且 是原問(wèn)題的最優(yōu)的基可行解是原問(wèn)題的最優(yōu)的基可行解Y再考慮第二種情況再考慮第二種情況kPD 121,AAAPPPTn00 , 0 , 1 , 0 , 0TkkTTePADAnwwCAW110 kw取取 ，則則kkTTTTTweWDAACDC直線搜索問(wèn)題直線搜索問(wèn)題linbtDXPbtDXAwtXCtDXCiTiTkTT1, s.t.minlinbtDXPbtDXAwtXCtDXCiTiTkTT1, s.t.min因?yàn)橐驗(yàn)閘inDtPbXPDtAbXAwtXCTi

4、iTiTTkT1, s.t.min0, 0DAbXAwTTk直線搜索問(wèn)題等價(jià)于直線搜索問(wèn)題等價(jià)于linDtPbXPtTiiTi1, s.t.maxlinDtPbXPtTiiTi1, s.t.max對(duì)直線搜索問(wèn)題對(duì)直線搜索問(wèn)題最優(yōu)解等于最優(yōu)解等于linDPDPbXPtTiTiiTi1, 0min改進(jìn)的可行解為改進(jìn)的可行解為DtXX由于由于 原來(lái)的原來(lái)的 個(gè)起作個(gè)起作用約束只有一個(gè)變成不起作用約束，如果上面的用約束只有一個(gè)變成不起作用約束，如果上面的最小值只在一個(gè)下標(biāo)達(dá)到（非退化），那么原來(lái)最小值只在一個(gè)下標(biāo)達(dá)到（非退化），那么原來(lái)的不起作用約束只有一個(gè)變成起作用約束，新可的不起作用約束只有一個(gè)變

5、成起作用約束，新可行解的起作用約束還是行解的起作用約束還是 個(gè)，可重復(fù)前面的過(guò)程個(gè)，可重復(fù)前面的過(guò)程kTTTe tbDAtXAXAnn結(jié)論結(jié)論用投影梯度法從滿足前面約定的初始可行解開(kāi)始用投影梯度法從滿足前面約定的初始可行解開(kāi)始求解線性不等式約束的線性規(guī)劃問(wèn)題求解線性不等式約束的線性規(guī)劃問(wèn)題libXPXCiTiT1, s.t.minliyCyPybiliiiliii1, 0 s.t.max11本質(zhì)上就是用對(duì)偶單純型法求解其下述標(biāo)準(zhǔn)線性本質(zhì)上就是用對(duì)偶單純型法求解其下述標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題規(guī)劃問(wèn)題用用簡(jiǎn)約梯度法簡(jiǎn)約梯度法解標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題解標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題ZXY 已知可行解已知可行解 滿足以下條件：滿

6、足以下條件：2)2) 的每個(gè)分量都大于零（非退化情況）的每個(gè)分量都大于零（非退化情況）1BZ1) , 1) , 存在存在AXBZNYb0 s.t.minXbAXXCT考慮標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題（考慮標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題（ ）nmRA于是于是 是下述問(wèn)題可行解（是下述問(wèn)題可行解（ ）Y 1min s.t. 0,0f YBbNYY并且，并且， （對(duì)應(yīng)的約束是不起作用約束）（對(duì)應(yīng)的約束是不起作用約束）10BbNY1( )TTBNf YC BbNYC Y( )TTBNf YC ZC Yid（檢驗(yàn)數(shù)）（檢驗(yàn)數(shù)） 1 ,TTn mTTBNrf Z Yf Z Yf YN BZYrN B CC 因?yàn)橐驗(yàn)?，所以簡(jiǎn)約梯度

7、為，所以簡(jiǎn)約梯度為1if 0,if 0Tiin mii iirrDdddy rr可行下降方向：可行下降方向： 不等于零的條件：不等于零的條件： 或或1( )miiif Yr y0ir 0 and0iiyriy（ 將增加）將增加）iy（ 將減少）將減少）ZXY 當(dāng)當(dāng) 是基可行解時(shí)是基可行解時(shí)0Y id 不等于零的條件：不等于零的條件： 或或0ir 0 and0iiyr0ir 不滿足檢驗(yàn)數(shù)條件的起作用約束變成不起作用約束不滿足檢驗(yàn)數(shù)條件的起作用約束變成不起作用約束和單純型法的區(qū)別：和單純型法的區(qū)別：一次迭代容許多個(gè)起作用約束變成不起作用約束一次迭代容許多個(gè)起作用約束變成不起作用約束推導(dǎo)不等式約束推

8、導(dǎo)不等式約束Kuhn-Tucker定理的一般途徑定理的一般途徑Gordan定理定理任意給定一組向量任意給定一組向量 ，不存在，不存在的充要條件是，存在一組不全為零的非負(fù)實(shí)數(shù)的充要條件是，存在一組不全為零的非負(fù)實(shí)數(shù)kiRCni, 2 , 1,滿足滿足nRDkiDCTi, 2 , 1, 0kiwi, 2 , 1,滿足滿足01kiiiCwGordanFritz JohnKuhn-TuckerGordan定理定理對(duì)于一般性非線性不等式約束，對(duì)于一般性非線性不等式約束， 是局部最優(yōu)解是局部最優(yōu)解根據(jù)根據(jù)Gordan定理，上述必要條件等價(jià)于存在不全定理，上述必要條件等價(jià)于存在不全這里不需要梯度線性無(wú)關(guān)的條

9、件這里不需要梯度線性無(wú)關(guān)的條件nRDX的必要條件是不存在的必要條件是不存在 滿足滿足不等式不等式Fritz John定理定理liDXgDXfiTT1, 0)(, 0)(為零的非負(fù)實(shí)數(shù)為零的非負(fù)實(shí)數(shù) 滿足滿足0)()(10liiiXgwXfwliwi, 2 , 1 , 0,Fritz John定理定理不等式不等式Kuhn-Tucker定理定理0)()(1liiiXgwXf由于進(jìn)一步假定由于進(jìn)一步假定 線性無(wú)關(guān)線性無(wú)關(guān)liXgi, 2 , 1),(可以推定可以推定 ，否則有不全為，否則有不全為0的的 滿足滿足00w說(shuō)明有關(guān)梯度線性相關(guān)，矛盾說(shuō)明有關(guān)梯度線性相關(guān)，矛盾0)(1liiiXgwiw由于由

10、于 ，令，令 ，可以將，可以將liwwwii1,000wFritz John定理寫成：存在非負(fù)定理寫成：存在非負(fù) 滿足滿足liwi1,這就是不等式約束的這就是不等式約束的Kuhn-Tucker定理定理推導(dǎo)推導(dǎo)Gordan定理的一般途徑定理的一般途徑凸集分離定理凸集分離定理對(duì)任意非空凸集對(duì)任意非空凸集 ，如果，如果 為空集，為空集，則存在超平面則存在超平面 滿足滿足幾何意義：幾何意義：12,kR kTHZR W Zb12,TTW ZbZW ZbZ Gordan凸集分離定理凸集分離定理21H12用用凸集分離定理凸集分離定理導(dǎo)出導(dǎo)出Gordan定理定理定義定義 如下：如下：12,1,2, ,0kTniikiZR zC D ik DRZR z 12,kR 無(wú)解無(wú)解kiDCTi, 2 , 1, 012為空集為空集12,TTW ZbZW ZbZ （凸集分離定理）（凸集分離定理）11,0,1,2,kkTiiiiiiniwC Dw zDRzik11,0,1,2,kkTiiiiiiniwC Dw zDRzik10,0,1,2,kiiiiw zzik0,1,2,iwik 10,kTni