卡馬卡算法

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

基本介紹

• 中文名：卡馬卡算法
• 外文名：Karmarkar  algorithm
• 所屬學科：數學
• 簡介：求解線性規劃的一種算法
• 提出者：卡馬卡(N.Karmarkar)

基本介紹

1984年，印度數學家N.Karmarkar針對線性規劃問題提出了一種新的多項式時間算法，在實際計算效率方面，Karmarkar算法顯示出可與單純形法競爭的巨大潛力，Karmarkar算法的提出是線性規劃理論研究的突破，而且對於處理非線性最佳化問題也顯示出強大的生命力和廣闊的套用前景。

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

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

滿足 及或者

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

1.在上述約束條件下；

2.；

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

時，即可停止疊代，並認為x即為所求的解。

卡馬卡算法的步驟

卡馬卡算法步驟如下：

1.(初始)　設k=0，

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

2.(判定)　若

則停止疊代，最優解為

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

設

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

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

5.設.

6.設，其中α為滿足

的常數，通常取。

7.令，轉至第2步。