單純形法

單純形法是解決線性規劃問題的一種方法。這種方法由 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）混淆。後一種方法透過在每次迭代中維護 個定義單純形的點，來解決 維中的無約束最小化問題。在每次迭代中，透過對其應用某些變換來更新此單純形，使其“滾下山”，直到找到最小值。