[教育]運籌學2.4內點算法

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

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

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

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

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

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

7、ethod ),將嚴格不等式組(3)的解集用k表示 :,思想 :,先選取一個很大的球 ,由于它可取的足夠大, 故若 , 則可認為 . 然后用一個迭代方法 ,依次產生一系列的橢球,,,,,,,,,,,,,k,這樣隨著迭代的進行, 橢球的體積漸趨于0, 但其中仍包含有k中的點 .,當迭代到一定程度時, 則可求得(3)的一個解或判定它無解 .,否則, 將 用

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

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

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

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

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

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

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

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

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

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

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

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

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