內點法（interior-point method）

假設問題的容許區域是一座有圍籬的院子，而最佳點落在某道圍籬上或附近。較老的方法（如單純形法）沿著圍籬本身、一角一角地走。內點法反其道而行：它嚴格留在院子「內部」、遠離每道圍籬，並在逼近最佳點時逐漸讓自己往邊界漂移——彷彿被牆上一股緩緩減弱的隱形力場排斥著。

訣竅是一個障礙（barrier）函數。為強制不等式約束 g_i(x) <= 0，你加上一項，在任何約束被逼近時暴增到 +無限大——經典選擇是對數障礙 -sum log(-g_i(x))，它在區域嚴格內部有限、在邊界爆炸。接著你對某參數 t 最小化 f(x) + t * (障礙)，這讓迭代點嚴格可行（內部）。對一連串「遞縮」的障礙權重求解，描出「中心路徑」，當障礙權重趨於零，解逼近真正的受約束最佳——它可能落在邊界上。每個子問題都用牛頓法求解，所以內點法本質上就是沿中心路徑的牛頓步，反覆收緊以趨向 KKT 條件。

內點法在 1980 到 90 年代革新了最佳化：它們以可證明的多項式時間求解線性規劃（不像單純形法，其最壞情形是指數的），並優雅地擴展到二次規劃、二階錐規劃與半定規劃——整套現代凸最佳化工具箱。對大型結構化問題，它們往往是首選，幾乎不論問題規模都只需少量、近乎固定數目的牛頓迭代。誠實的權衡：每個牛頓步要解一個線性系統，對巨大的稠密問題可能很貴；它們需要一個嚴格可行的內部起點；而且不像單純形法，它們不會自然地回傳一個精確的頂點解，問題稍有變動時也不易便宜地暖啟動。對許多問題，單純形法與內點法是互補、而非對手。