內點法

內點法(Interior Point Method)是一種求解線性規劃或非線性凸最佳化問題的算法。

它是由John von Neumann發明的，他利用戈爾丹的線性齊次系統提出了這種新的求解線性規劃的方法。後被Narendra Karmarkar於1984年推廣套用到線性規劃，即Karmarkar算法。

基本介紹

• 中文名：內點法
• 外文名：Interior Point Method
• 懲罰函式：線性目標函式、凸集
• 意義：求解線性規劃或非線性凸最佳化問題

介紹

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

1972年，V.Klee和G.Minty給出一個例子，他們構造一個線性規劃問題，用單純形方法求解，需要的計算時間為。這個例子表明，單純形算法雖然在實際套用中非常有效，至今占有絕對優勢，但在理論上它還不是多項式算法。於是產生這樣的問題：對於線性規劃，能否找到多項式算法？

1979年，前蘇聯數學家第一個給出了求解線性規劃的多項式算法，這就是所謂的橢球算法。它的計算複雜性為，其中n是變數的維數，L是輸入長度。這個算法在理論上是重要的，但是計算結果很不理想，遠不及單純形方法有效。

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

原理

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

線性規劃問題描述如下：

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

這裡是一個小的正參數，常被稱作“懲罰因子”。當趨近於0時，將趨近於（1）的解。

懲罰函式的梯度為：

是原始函式的梯度，且是的梯度。

除了原始變數，我們還引入了拉格朗日乘子（有時也稱鬆弛變數）：

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

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

其中，是限制條件的雅克比矩陣。

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

其中，是的黑塞矩陣，是的的對角矩陣。

因為（1）和（4），所以在每次疊代時都必須滿足，所以可以通過選擇合適的來計算：

套用

• 單純形法最古老，被研究的最為透徹，商業化的軟體程式也最成熟
• 橢球算法像曇花一現，雖然在理論上證明了線性規劃問題可在多項式時間內求解，但在實際套用上反而不如單純形法來的有效便捷
• 內點法是最新的設計，理論上它比橢球法還要有效，實際套用上它也可以與單純形法相抗衡，不少商業化軟體已經上市，前景甚佳