卡馬卡算法

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

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

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

滿足

及

或者

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

1.在上述約束條件下

；

2.

；

3.對於給定精度

，當可行解

滿足條件

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

卡馬卡算法步驟如下：

1.(初始)　設k=0，

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

2.(判定)　若

則停止迭代，最優解為

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

設

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

4.(投影變換)　對

，設

，記

，有

，

5.設

.

6.設

，其中α為滿足

的常數，通常取

。

7.令

，轉至第2步 ^[2]  。