线性规划是一类重要的数学规划问题，求解线性规划的常用算法是单纯形算法。单纯形算法的特点是从可行域的一个顶点出发，通过一次迭代挪动到临近较优的另一顶点，直至到达最优点为止。单纯形算法简单、实用，是目前常用的方法。但是，1972年，V. Klee和G. Minty举出了一个例子揭示了单纯形算法的时间复杂性有可能是指数型[1]。因此从计算复杂性的标准来看，单纯形算法不是好算法；于是线性规划是否存在多项式算法便成了计算机科学家和数学家十分感兴趣的问题。1979年，苏联数学家哈奇扬给出了一个求解线性规划的多项式算法：椭球算法，其计算复杂性为O(n6L2)；1984年，印度数学家卡玛卡尔给出了线性规划的一个新的多项式算法，其计算复杂性为O(n3.5L2)，大大改进了哈奇扬的结果，引起了人们极大的兴趣[2]。这些多项式算法的一个共同特点就是不再从可行域的顶点开始迭代，而是选取可行域内部一个适当的点，沿某个下降方向开始迭代到达最优解。我们把具有这种特点的算法统称为内点算法。内点算法的理论比较成熟，但是应用起来还是有难度，究其原因就是初始内点难以找到，因此对内点算法的研究始终停留在理论上。1989年，Renato D.C. Monteiro 和Ilan ADLER给出了求解线性规划一个原—对偶内点算法，其迭代次数为 ，计算复杂性为O(n3.5L)，这是目前理论上最好且最完善的求解线性规划的多项式算法[3]；由于该算法对初始点的要求很严格，这就给数值实验带来更大的困难，迄今为止，也没有关于该算法的数值例子问世。