单纯形法

单纯形法是解决线性规划问题的一种方法。这种方法由 George Dantzig 于 1947 年发明，按顺序测试可行集（这是一个多胞形）的相邻顶点，以便在每个新顶点上，目标函数得到改善或保持不变。单纯形法在实践中非常有效，通常最多需要 到 次迭代（其中 是等式约束的数量），并且对于随机输入的某些分布，在预期的多项式时间内收敛 (Nocedal and Wright 1999, Forsgren 2002)。然而，它的最坏情况复杂度是指数级的，这可以通过精心构建的例子来证明 (Klee and Minty 1972)。

用于线性规划问题的另一种类型的方法是内点法，其平均和最坏情况的复杂度都是多项式的。这些方法构造一个严格可行点序列（即，位于多胞形内部但从不在其边界上），该序列收敛到解。 Karmarkar (1984) 的一篇论文激发了对内点方法的研究。在实践中，最好的内点方法之一是 Mehrotra (1992) 的预测-校正方法，它与单纯形法具有竞争力，尤其是在大规模问题中。

Dantzig 的单纯形法不应与下山单纯形法（Spendley 1962, Nelder and Mead 1965, Press et al. 1992）混淆。后一种方法通过在每次迭代中维护 个定义单纯形的点，来解决 维中的无约束最小化问题。在每次迭代中，通过对其应用某些变换来更新此单纯形，使其“滚下山”，直到找到最小值。