內點法

任何凸優化問題都可轉化成凸集上的線性目標函數問題。早在19世紀60年代，就有人在研究非線性規劃時，試圖通過設計懲罰函數來描述可行區域。

1972年，V.Klee和G.Minty給出一個例子，他們構造一個線性規劃問題，用單純形方法求解，需要的計算時間為

。這個例子表明，單純形算法雖然在實際應用中非常有效，至今佔有絕對優勢，但在理論上它還不是多項式算法。於是產生這樣的問題：對於線性規劃，能否找到多項式算法？

1979年，前蘇聯數學家第一個給出了求解線性規劃的多項式算法，這就是所謂的橢球算法。它的計算複雜性為

，其中n是變量的維數，L是輸入長度。這個算法在理論上是重要的，但是計算結果很不理想，遠不及單純形方法有效。

算法上突破性的進展和當代科學技術發展的需要，又給人們提出進一步的問題：能否找到實用上也確實有效的多項式時間算法？正是在這樣的背景下，產生了內點法，它的計算複雜性是

。

內點法中有一個懲罰函數，用於描述凸集。與單純形法不同，它通過遍歷內部可行區域來搜索最優解。

線性規劃問題描述如下：

與（1）對應的對數型懲罰函數為：

這裏

是一個小的正參數，常被稱作“懲罰因子”。當

趨近於0時，

將趨近於（1）的解。

懲罰函數的梯度為：

是原始函數

的梯度，且

是

的梯度。

除了原始變量

，我們還引入了拉格朗日乘子

（有時也稱鬆弛變量）：

（4）有時被稱為擾動互補條件，類似於KKT條件中的互補鬆弛。我們試圖找到那些使得懲罰函數梯度為0的

。

對比（3）與（4）我們容易得到一個關於梯度的等式：

其中，

是限制條件

的雅克比矩陣。

（5）式意味着

的梯度應該位於限制條件梯度所張成的子空間中。對（4）和（5）應用牛頓法我們得到：

其中，

是

的黑塞矩陣，

是

的的對角矩陣。

因為（1）和（4），所以

在每次迭代時都必須滿足，所以可以通過選擇合適的

來計算：