介紹
內點法任何凸最佳化問題都可轉化成凸集上的線性目標函式問題。早在19世紀60年代，就有人在研究非線性規劃時，試圖通過設計懲罰函式來描述可行區域。
內點法1972年，V.Klee和G.Minty給出一個例子，他們構造一個線性規劃問題，用單純形方法求解，需要的計算時間為。這個例子表明，單純形算法雖然在實際套用中非常有效，至今占有絕對優勢，但在理論上它還不是多項式算法。於是產生這樣的問題：對於線性規劃，能否找到多項式算法？
內點法1979年，前蘇聯數學家第一個給出了求解線性規劃的多項式算法，這就是所謂的橢球算法。它的計算複雜性為，其中n是變數的維數，L是輸入長度。這個算法在理論上是重要的，但是計算結果很不理想，遠不及單純形方法有效。
內點法算法上突破性的進展和當代科學技術發展的需要，又給人們提出進一步的問題：能否找到實用上也確實有效的多項式時間算法？正是在這樣的背景下，產生了內點法，它的計算複雜性是。
原理
內點法中有一個懲罰函式，用於描述凸集。與單純形法不同，它通過遍歷內部可行區域來搜尋最優解。
線性規劃問題描述如下：
內點法
內點法與（1）對應的對數型懲罰函式為：
內點法
內點法 內點法
內點法這裡是一個小的正參數，常被稱作“懲罰因子”。當趨近於0時，將趨近於（1）的解。
懲罰函式的梯度為：
內點法
內點法
內點法
內點法
內點法是原始函式的梯度，且是的梯度。
內點法
內點法除了原始變數，我們還引入了拉格朗日乘子（有時也稱鬆弛變數）：
內點法
內點法（4）有時被稱為擾動互補條件，類似於KKT條件中的互補鬆弛。我們試圖找到那些使得懲罰函式梯度為0的。
對比（3）與（4）我們容易得到一個關於梯度的等式：
內點法
內點法
內點法其中，是限制條件的雅克比矩陣。
內點法（5）式意味著的梯度應該位於限制條件梯度所張成的子空間中。對（4）和（5）套用牛頓法我們得到：
內點法
內點法 內點法
內點法
內點法其中，是的黑塞矩陣，是的的對角矩陣。
內點法
內點法因為（1）和（4），所以在每次疊代時都必須滿足，所以可以通過選擇合適的來計算：
內點法套用
•單純形法最古老，被研究的最為透徹，商業化的軟體程式也最成熟
•橢球算法像曇花一現，雖然在理論上證明了線性規劃問題可在多項式時間內求解，但在實際套用上反而不如單純形法來的有效便捷
•內點法是最新的設計，理論上它比橢球法還要有效，實際套用上它也可以與單純形法相抗衡，不少商業化軟體已經上市，前景甚佳
