[教育]運(yùn)籌學(xué)2.4內(nèi)點(diǎn)算法

1、§ 2.4 內(nèi)點(diǎn)算法,算法復(fù)雜性,計算模型,假設(shè)基本運(yùn)算(﹢、﹣、×、÷、比較、轉(zhuǎn)移)均可在單位時間內(nèi)完成.,算法執(zhí)行時間可用算法所需執(zhí)行基本運(yùn)算的總次數(shù) .,輸入長度,字符串(二進(jìn)制或某大于1進(jìn)制的代碼序列),對于優(yōu)化問題 : 問題維數(shù)、約束個數(shù)、n、m,時間復(fù)雜性函數(shù),算法分類 ： 多項式時間算法,指數(shù)時間算法,,大量計算實踐表明， 單純形法及其變形是求解LP問題的一類收斂很快、相當(dāng)成功的算法

2、.,例如, 對形如 :,的典型LP問題, 在假設(shè)問題中的數(shù)據(jù)按某種合理的分布取值時, 理論上可以證明單純形法平均經(jīng)次迭代即可確定問題的最優(yōu)解. 因此, 在一般情況或平均意義下, 單純形法是很有效的.,但是, 當(dāng)把單純形法應(yīng)用于下列LP問題,時, 則它需經(jīng) 次迭代方能確定問題的最優(yōu)解.,,指數(shù)時間算法,L.G.Khachiyan (1979),LP與嚴(yán)格線性不等式組的關(guān)系,以下都假定A、b、c均為整數(shù),( 1 )

3、,Proof:,Th. : 存在求解LP問題的多項式時間算法的充分必要條件 是存在求解形如 的線性不等式組的多項式時間算法 。,令 , 寫出與(1)有關(guān)的LP :,行向量c可任意給定, 如取 c=0,( 2 ),若有多項式時間的LP算法, 則可判定 :,問題(2)不可行→這時不等式組(1)無解 .,得到(2)的最優(yōu)解或判定(2)

4、無界,→這時必可得(1)的一個解,,,在多項式時間內(nèi)求解了問題(1),反之, 若有一多項式時間方法求解閉(弱)的線性不等式組(1),考慮問題(2)的對偶 :,對偶Th,,求解問題(2)可歸結(jié)為求解關(guān)于變量 的下述弱不等式組,否則, 再考慮另一個弱不等式組 :,若它有解→則問題(2)無界,否則 →問題(2)不可行,總之, 最多求解兩個弱不等式組就完全解決了LP問題(2),從而得到求解LP問題的一個多項式時間

5、算法,若該聯(lián)立不等式組有解,則 為問題(2)的最優(yōu)解, 為其對偶最優(yōu)解.,(1)與嚴(yán)格(強(qiáng))線性不等式組的關(guān)系 :,( 3 ),令,則由線代行列式理論易證,設(shè) , 且 (否則LP問題很容易求解),引理 : 設(shè)B是矩陣 的任一子方陣, 則,記 為A的第i個行向量, . 代替(3), 考察不等式組,其中,令,

6、顯然, x為弱不等式組(1)的解,引理 : 對 中任一點(diǎn) , 必定存在一個 ,使得 :,1.,2. A的每個行向量均可表示為向量集 滿足 的線性組合 .,推論 : 若有一個求解嚴(yán)格線性不等式組的多項式時間算法 , 則就有一個求解弱線性不等式組的多項式時間算法 .,橢球算法( ellipsoid m

7、ethod ),將嚴(yán)格不等式組(3)的解集用k表示 :,思想 :,先選取一個很大的球 ,由于它可取的足夠大, 故若 , 則可認(rèn)為 . 然后用一個迭代方法 ,依次產(chǎn)生一系列的橢球,,,,,,,,,,,,,k,這樣隨著迭代的進(jìn)行, 橢球的體積漸趨于0, 但其中仍包含有k中的點(diǎn) .,當(dāng)?shù)揭欢ǔ潭葧r, 則可求得(3)的一個解或判定它無解 .,否則, 將 用

8、一適當(dāng)超平面分成兩半, 使其中的一半必與k相交, 設(shè)法產(chǎn)生另一個橢球 ,使其包含 的這一半, 從而保證 .,同時, 又要求 的體積至多為 的β<1倍,關(guān)鍵 : 由 產(chǎn)生滿足要求的 ,實質(zhì)上 只要決定 和 即可.,一般地

9、, 若已知橢球,檢驗 的中心 是否為(3)的解. 若是, 終止, 輸出,n階對稱正定陣,求解嚴(yán)格線性不等式組的橢球算法 :,S 1 : 取,S 2 : 若 滿足(3), 則已得到解, 停止 .,S 3 : 若 , 則不等式組(3)無解, 停止 .,S 4 : 設(shè)不等式組(3)中未被 滿足的某個行向量及右端向量

10、分別為 與,令,, 轉(zhuǎn) S 2 .,L—問題的輸入規(guī)模,正確性 : 冗長但直接可證,理論上的重要突破 !,復(fù)雜性 : 最壞情況下需 次迭代,每次迭代, 為找 不滿足的不等式 : , 最壞需要 次運(yùn)算,計算新的橢球( 即確定 與 ),每次迭代需

11、 次運(yùn)算,橢球算法的復(fù)雜性,,多項式時間算法 !,Karmarkar 算法,受橢球算法啟發(fā), 復(fù)雜性比它低, 實際計算效果好 .,一般的LP問題 :,由前面關(guān)于LP問題與弱線性不等式組的關(guān)系 , 一般的LP問題可歸結(jié)為求解形如,的不等式組 ,,通過添加松弛變量 , 可再轉(zhuǎn)化為,Karmarkar,( 1 ),,則(1),再添加一個松弛變量,若(1)有解, 則在通常假設(shè)條件下, 由橢球法收斂性分析, 知(1)的基本

12、可行解的各個分量均不超過,( 2 ),調(diào)整變量的尺度, 將 取作新的變量x, 且把向量b也做同樣改變,令 為新的矩陣A,Case 1 : 若 , 則e除以其維數(shù)后得上述不等式組的解. Stop .,Case 2 : 若 , 則對A的行做如下初等變換 :,對所有的 ,將A的第i行除以 ,再把某個

13、這樣的行加到v的零分量所對應(yīng)的各行去, 則所產(chǎn)生新的矩陣A滿足 :,且這樣的初等變換不會影響(2)中的齊次關(guān)系 .,求解(2)又可歸結(jié)為求解x與 ,使得,現(xiàn)置 :,則(2)變?yōu)?:,為求解該不等式組, 可考慮如下LP問題 :,為敘述簡便, 不妨設(shè) :,b ) 問題的可行區(qū)域S的相對內(nèi)部非空, 即,a ),c ) 問題的最優(yōu)值,Karmarkar 算法的思想 :,作為一個迭代算法, 它不像

14、單純形方法那樣沿可行區(qū)域多面體的表面搜索前進(jìn),而是從多面體內(nèi)部一點(diǎn)(稱為內(nèi)點(diǎn))出發(fā), 產(chǎn)生一個直接穿過多面體內(nèi)部的點(diǎn)列而達(dá)到最優(yōu)解.,,,,,,,且使目標(biāo)函數(shù)獲得實質(zhì)性的減少, 以保證有多項式的時間復(fù)雜性 .,在第k次迭代, 若已知 , 則需尋找 處的可行方向 和沿 從 出發(fā)的步長 ,使有 :,兩個構(gòu)成部分 :

15、,1 ) 為使每步迭代有一個足夠大的“移動空間”, 每次迭代開始 時先做一個投影變換T(x),2 ) 為獲得有效的可行下降方向, 構(gòu)造勢函數(shù)V(x) .,單純形 :,內(nèi)切球半徑 :,上述LP問題的可行域即為該單純形的一部分 .,,1 ),變換T(x) : 將單純形映射到其自身,投影變換定義為下列映射 :,在第k次迭代, 已知 ,因而,但是把當(dāng)前迭代點(diǎn)映射

16、到單純形的中心 .,,,,,變換T(x) (等價地 ), 將原LP問題變換成如下關(guān)于 的問題 :,∵設(shè)最優(yōu)值=0,易證,獲得了足夠大的“移動空間”,雖 可能很靠近可行區(qū)域S的某個邊界,但 卻是 中單純形 的中心, 遠(yuǎn)離邊界,為了獲得多項式的算法復(fù)雜性,Karmarkar利用非線性規(guī)劃中障

17、礙懲罰函數(shù)的思想構(gòu)造了如下的勢函數(shù) :,( △ ),2 ) 勢函數(shù) : . 以控制收斂 .,做法 : 每次迭代, 在投影變換后的 --空間中, 將勢函數(shù) 在 點(diǎn)負(fù)梯度向量正交投影到問題(△)的可行 區(qū)域上獲得方向 :,從當(dāng)前點(diǎn) 沿方向

18、 取一個適當(dāng)步長得,利用 的逆變換返回到原來的x--空間 :,,Karmarkar 算法迭代步驟 :,S 1 : 取 , 令 ;,S 2 : 若 (L為標(biāo)準(zhǔn)LP問題的輸入長度) , 停止, 輸出 ;,S 4 : 計算,(其中 為單純形內(nèi)切球半徑 ,

19、 為某個小于 的正數(shù) ),S 5 : 取 , 令 , 轉(zhuǎn)S 2 .,可以證明 :,若Gauss消去,根據(jù)B的結(jié)構(gòu)特點(diǎn)(每次迭代僅改變對角方陣D),改進(jìn),每次迭代均可使勢函數(shù)至少減少一個正常量 , 即,迭代次數(shù)上界,每次迭代的主要計算量是計算,,,,Karmarkar 算法時間復(fù)雜性,,,Note :,① 初始可行內(nèi)點(diǎn)

20、 可采用兩階段法確定 ;,② 對 未知的情況, 只要知道 的一個下界, 則前面的計算 公式稍作改動, 增加一個逐步調(diào)整下界, 并使下界趨于 的程序即可 .,③ 步長 在每步迭代中可簡單的取為常數(shù)值,如 等,亦可從 點(diǎn)沿方向 對勢函數(shù)進(jìn)行有效一維搜索來確 定“最佳”步長 .,Karmarkar 算法的改進(jìn) :,投影方法 ( projective methods ),放射均衡尺度方法