卡马卡算法

卡马卡算法(Karmarkar algorithm)是求解线性规划的一种算法，是哈奇扬方法之后又一个线性规划的多项式算法，它的特点是使迭代过程的各点严格远离约束多面体的各个界面，为此，每次迭代都须借助于投影变换，把问题归结为一类典型问题，有利于目标值改善，此方法由美籍印度学者卡马卡(N.Karmarkar)于1984年给出，所以得此名。

基本介绍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。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所