運籌學(xué)2.4 內(nèi)點算法

§2.4

內(nèi)點算法編輯ppt算法復(fù)雜性計算模型假設(shè)基本運算(﹢、﹣、×、÷、比較、轉(zhuǎn)移)均可在單位時間內(nèi)完成.算法執(zhí)行時間可用算法所需執(zhí)行基本運算的總次數(shù).輸入長度字符串(二進制或某大于1進制的代碼序列)對于優(yōu)化問題:問題維數(shù)、約束個數(shù)、n、m時間復(fù)雜性函數(shù)算法分類：多項式時間算法指數(shù)時間算法大量計算實踐表明，單純形法及其變形是求解LP問題的一類收斂很快、相當成功的算法.例如,對形如:的典型LP問題,在假設(shè)問題中的數(shù)據(jù)按某種合理的分布取值時,理論上可以證明單純形法平均經(jīng)次迭代即可確定問題的最優(yōu)解.因此,在一般情況或平均意義下,單純形法是很有效的.但是,當把單純形法應(yīng)用于下列LP問題時,則它需經(jīng)次迭代方能確定問題的最優(yōu)解.指數(shù)時間算法L.G.Khachiyan(1979)LP與嚴格線性不等式組的關(guān)系以下都假定A、b、c均為整數(shù)(1)Proof:

Th.

:

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

在多項式時間內(nèi)求解了問題(1)反之,若有一多項式時間方法求解閉(弱)的線性不等式組(1)考慮問題(2)的對偶:對偶Th求解問題(2)可歸結(jié)為求解關(guān)于變量的下述弱不等式組否則,再考慮另一個弱不等式組:若它有解→則問題(2)無界否則→問題(2)不可行總之,最多求解兩個弱不等式組就完全解決了LP問題(2)從而得到求解LP問題的一個多項式時間算法若該聯(lián)立不等式組有解則為問題(2)的最優(yōu)解,為其對偶最優(yōu)解.(1)與嚴格(強)線性不等式組的關(guān)系:(3)令則由線代行列式理論易證設(shè),且(否則LP問題很容易求解)引理:

設(shè)B是矩陣的任一子方陣,則記為A的第i個行向量,.代替(3),考察不等式組其中令顯然,x為弱不等式組(1)的解引理:對中任一點,必定存在一個,使得:1.

2.

A的每個行向量均可表示為向量集滿足的線性組合.推論:

若有一個求解嚴格線性不等式組的多項式時間算法,則就有一個求解弱線性不等式組的多項式時間算法.Th.

:

弱不等式組(1)可行嚴格不等式組(3)可行橢球算法(ellipsoidmethod)將嚴格不等式組(3)的解集用k表示:思想:先選取一個很大的球,由于它可取的足夠大,故若,則可認為.然后用一個迭代方法,依次產(chǎn)生一系列的橢球k這樣隨著迭代的進行,橢球的體積漸趨于0,但其中仍包含有k中的點.當?shù)揭欢ǔ潭葧r,則可求得(3)的一個解或判定它無解.否則,將用一適當超平面分成兩半,使其中的一半必與k相交,設(shè)法產(chǎn)生另一個橢球,使其包含的這一半,從而保證.同時,又要求的體積至多為的β<1倍關(guān)鍵:由產(chǎn)生滿足要求的,實質(zhì)上只要決定和即可.一般地,若已知橢球檢驗的中心是否為(3)的解.若是,終止,輸出n階對稱正定陣求解嚴格線性不等式組的橢球算法:S1:

取

S2:

若滿足(3),則已得到解,停止.S3:若,則不等式組(3)無解,停止.S4:設(shè)不等式組(3)中未被滿足的某個行向量及右端向量分別為與令,轉(zhuǎn)S2.L—問題的輸入規(guī)模正確性:冗長但直接可證理論上的重要突破!復(fù)雜性:最壞情況下需次迭代每次迭代,為找不滿足的不等式:,最壞需要次運算計算新的橢球(即確定與)每次迭代需次運算橢球算法的復(fù)雜性

多項式時間算法!Karmarkar算法受橢球算法啟發(fā),復(fù)雜性比它低,實際計算效果好.一般的LP問題:由前面關(guān)于LP問題與弱線性不等式組的關(guān)系,一般的LP問題可歸結(jié)為求解形如的不等式組,通過添加松弛變量,可再轉(zhuǎn)化為Karmarkar已知求,使且(1)則(1)再添加一個松弛變量若(1)有解,則在通常假設(shè)條件下,由橢球法收斂性分析,知(1)的基本可行解的各個分量均不超過(2)調(diào)整變量的尺度,將取作新的變量x,且把向量b也做同樣改變令為新的矩陣ACase1:若,則e除以其維數(shù)后得上述不等式組的解.Stop.Case2:若,則對A的行做如下初等變換:對所有的,將A的第i行除以,再把某個這樣的行加到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算法的思想:作為一個迭代算法,它不像單純形方法那樣沿可行區(qū)域多面體的表面搜索前進,而是從多面體內(nèi)部一點(稱為內(nèi)點)出發(fā),產(chǎn)生一個直接穿過多面體內(nèi)部的點列而達到最優(yōu)解.且使目標函數(shù)獲得實質(zhì)性的減少,以保證有多項式的時間復(fù)雜性.在第k次迭代,若已知,則需尋找處的可行方向和沿從出發(fā)的步長,使有:兩個構(gòu)成部分:1)為使每步迭代有一個足夠大的“移動空間”,每次迭代開始時先做一個投影變換T(x)2)為獲得有效的可行下降方向,構(gòu)造勢函數(shù)V(x).單純形:內(nèi)切球半徑:上述LP問題的可行域即為該單純形的一部分.1)變換T(x):將單純形映射到其自身投影變換定義為下列映射:在第k次迭代,已知,因而但是把當前迭代點映射到單純形的中心.變換T(x)(等價地),將原LP問題變換成如下關(guān)于的問題:∵設(shè)最優(yōu)值=0易證獲得了足夠大的“移動空間”雖可能很靠近可行區(qū)域S的某個邊界,但卻是中單純形的中心,遠離邊界為了獲得多項式的算法復(fù)雜性,Karmarkar利用非線性規(guī)劃中障礙懲罰函數(shù)的思想構(gòu)造了如下的勢函數(shù):(△)2)勢函數(shù):.以控制收斂.做法:每次迭代,在投影變換后的--空間中,將勢函數(shù)在點負梯度向量正交投影到問題(△)的可行區(qū)域上獲得方向:從當前點沿方向取一個適當步長得利用的逆變換返回到原來的x--空間:Karmarkar算法迭代步驟:S1:取,令;S2:若(L為標準LP問題的輸入長度),停止,輸出;S3:令,計算投影方向;S4:計算(其中為單純形內(nèi)切球半徑,為某個小于的正數(shù))S5:取,令,轉(zhuǎn)S2.可以證明:若Gauss消去根據(jù)B的結(jié)構(gòu)特點(每次迭代僅改變對角方陣D)改進每次迭代均可使勢函數(shù)至少減少一個正常量,即迭代次數(shù)上界每次迭代的主要計算量是計算Karmarkar算法時間復(fù)雜性Note:①初始可行內(nèi)點可采用兩階段法確定;②對未知的情況,只要知道的一個下界,則前面的計算公式稍作改動,增加一個逐步調(diào)整下界,并使下界趨于的程序即可.③