内点法

内点法是一种线性或非线性规划方法（Forsgren等人，2002），它通过穿过问题定义的实体的中间而不是绕其表面来实现优化。

Karmarkar (1984) 发现了一种使用内点法的多项式时间线性规划算法。可以说，内点法早在 20 世纪 60 年代就以障碍函数方法的形式为人所知，但伴随 Karmarkar 声明的媒体炒作导致这些方法受到了极大的关注。然而，应该指出的是，虽然 Karmarkar 声称他的实现比单纯形法效率高得多，但内点法的潜力只是在后来才被确立。到 1994 年，关于内点法的已发表论文超过 1300 篇。

当前高效的实现主要基于预测-校正技术（Mehrotra 1992），其中使用法方程的Cholesky 分解或对称不定系统的分解来执行牛顿法（以及一些启发式方法来估计惩罚参数）。所有当前的内点法实现都严重依赖于用于分解稀疏对称矩阵的非常高效的代码。