內點法

內點法是一種線性或非線性規劃方法（Forsgren等人，2002），它透過穿過問題定義的實體的中間而不是繞其表面來實現最佳化。

Karmarkar (1984) 發現了一種使用內點法的多項式時間線性規劃演算法。可以說，內點法早在 20 世紀 60 年代就以障礙函式方法的形式為人所知，但伴隨 Karmarkar 宣告的媒體炒作導致這些方法受到了極大的關注。然而，應該指出的是，雖然 Karmarkar 聲稱他的實現比單純形法效率高得多，但內點法的潛力只是在後來才被確立。到 1994 年，關於內點法的已發表論文超過 1300 篇。

當前高效的實現主要基於預測-校正技術（Mehrotra 1992），其中使用法方程的Cholesky 分解或對稱不定系統的分解來執行牛頓法（以及一些啟發式方法來估計懲罰引數）。所有當前的內點法實現都嚴重依賴於用於分解稀疏對稱矩陣的非常高效的程式碼。