[科普中國]-卡馬卡算法

卡馬卡算法(Karmarkar algorithm)是求解線性規(guī)劃的一種算法，是哈奇揚方法之后又一個線性規(guī)劃的多項式算法，它的特點是使迭代過程的各點嚴格遠離約束多面體的各個界面，為此，每次迭代都須借助于投影變換，把問題歸結為一類典型問題，有利于目標值改善，此方法由美籍印度學者卡馬卡(N.Karmarkar)于1984年給出，所以得此名。

基本介紹1984年，印度數(shù)學家N.Karmarkar針對線性規(guī)劃問題提出了一種新的多項式時間算法，在實際計算效率方面，Karmarkar算法顯示出可與單純形法競爭的巨大潛力，Karmarkar算法的提出是線性規(guī)劃理論研究的突破，而且對于處理非線性優(yōu)化問題也顯示出強大的生命力和廣闊的應用前景。

單純形法是通過檢查可行域邊界上的極點的方法來求解(LP)問題，而Karmarkar算法則是建立在單純形結構之上的，該算法從初始內(nèi)點出發(fā)，沿著最速下降方向，通過可行域內(nèi)部直接達到最優(yōu)解，因此，Karmarkar算法也被稱為內(nèi)點法，由于是在可行域內(nèi)部尋優(yōu)，故對于大規(guī)模線性規(guī)劃問題，當約束條件和變量數(shù)目增加時，內(nèi)點算法的迭代次數(shù)變化較少，收斂性和計算速度均優(yōu)于單純形法1。

卡馬卡算法考慮如下標準形式的線性規(guī)劃問題

滿足 及或者

這里e為分量全為1的n維列向量，并且已知：

1.在上述約束條件下；

2.；

3.對于給定精度，當可行解滿足條件

時，即可停止迭代，并認為x即為所求的解。

卡馬卡算法的步驟卡馬卡算法步驟如下：

1.(初始) 設k=0，

是分量均為1/n的n維列向量。

2.(判定) 若

則停止迭代，最優(yōu)解為

3.以x的分量為對角元素，做對角陣

設

這里e為分量全為1的2n維列向量。

4.(投影變換) 對，設，記，有，

5.設.

6.設，其中α為滿足

的常數(shù)，通常取。

7.令，轉至第2步2。

本詞條內(nèi)容貢獻者為:

王沛 - 副教授、副研究員 - 中國科學院工程熱物理研究所