任何凸优化问题都可转化成凸集上的线性目标函数问题。早在19世纪60年代，就有人在研究非线性规划时，试图通过设计惩罚函数来描述可行区域。

1972年，V.Klee和G.Minty给出一个例子，他们构造一个线性规划问题，用单纯形方法求解，需要的计算时间为。这个例子表明，单纯形算法虽然在实际应用中非常有效，至今占有绝对优势，但在理论上它还不是多项式算法。于是产生这样的问题：对于线性规划，能否找到多项式算法？

1979年，前苏联数学家第一个给出了求解线性规划的多项式算法，这就是所谓的椭球算法。它的计算复杂性为，其中n是变量的维数，L是输入长度。这个算法在理论上是重要的，但是计算结果很不理想，远不及单纯形方法有效。

算法上突破性的进展和当代科学技术发展的需要，又给人们提出进一步的问题：能否找到实用上也确实有效的多项式时间算法？正是在这样的背景下，产生了内点法，它的计算复杂性是。