对Karmarkar算法中两种具体算法的思考

开篇：润墨网以专业的文秘视角，为您筛选了一篇对Karmarkar算法中两种具体算法的思考范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

收稿日期：2006-06-16

作者简介：杜洪艳（1971-），女，湖北武汉人，武汉科技大学中南分校文法学院讲师。

（武汉科技大学中南分校 文法学院，湖北 武汉 430223）

摘 要：本文对二十世纪八十年代出现的解决线性规划问题的一种新的计算方法――[QX(Y15]karmarkar[QX)]算法的两种具体算法作了分析和思考，并提出了笔者自己对这两种具体算法的看法和观点。

关键词：[QX(Y15]Karmarkar[QX)]标准问题；线性规划问题；投影尺度法；内点法；最优解

1 问题的提出

AT&T贝尔实验室的NKKarmarkar于1984年提出一个新的解决线性规划问题的多项式时间算法。这种计算方法和占有绝对优势的单纯形法最大的不同点是，每次迭代不是从一个极点出发求改进的极点，而是使迭代点保持在某个单纯形的内部，因此是一种内点算法。算法计算复杂性为O(n3.5L2)，其中n是变量维数，L是输入长度（把一个问题的数据输入计算机时所需二进制代码的长度）。而使用最广泛的单纯形法的计算复杂性为O(2n)，1979年苏联数学家Л.Г.Хачиян给出的第一个多项式算法――椭球算法的计算复杂性O(n6L2)。显然，对于大规模的线性规划问题，Karmarkar算法是一个较优的算法。

虽然Karmarkar算法从理论上看运算速度应该很快，但在实际计算中效果并不是很理想。人们正在做进一步的研究，希望借助这种计算方法解决一些领域中的大规模问题的计算。本文旨在对已有的研究成果进行比较，提出笔者的看法。使大家在今后的运用中有所借鉴。

显然，此种方法仍属于内点法。由于x[TX-*4]为线性规划问题标准型的一个可行解，找寻起来较内点法寻找初始内点容易，且计算时没有寻找初始内点的过程。同时，采用了最速下降法与Newton法的组合并进行了改进，从而可获得良好的收敛性。因此会给计算带来极大的方便。在用Karmarkar算法求解线性规划问题时，这不失为一个较优的算法。

参考文献

[1]Karmarkar N．A new polynomial-time algorithm for linear programming[M]. Combinatorica 4(4)1984.

[2]马振华，郑乐宁等.现代应用数学手册运筹学与最优化理论卷[M].清华大学出版社,1998.

[3]周学良,陈锡斌.变量带上下界内点算法的理论与实现[J]. 武汉水利电力大学学报,1993,26（5）.

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读