內點算法是一類重要的數學規劃問題。
基本介紹
- 中文名：內點算法
- 簡介：一類重要的數學規劃問題
- 詞性：名詞
- 分類：算法
- 常用算法：單純形算法
線性規劃是一類重要的數學規劃問題，求解線性規劃的常用算法是單純形算法。單純形算法的特點是從可行域的一個頂點出發，通過一次疊代挪動到臨近較優的另一頂點，直至到達最優點為止。單純形算法簡單、實用，是目前常用的方法。
但是，1972年，V. Klee和G. Minty舉出了一個例子揭示了單純形算法的時間複雜性有可能是指數型。因此從計算複雜性的標準來看，單純形算法不是好算法；於是線性規劃是否存在多項式算法便成了計算機科學家和數學家十分感興趣的問題。
1979年，蘇聯數學家哈奇揚給出了一個求解線性規劃的多項式算法：橢球算法，其計算複雜性為O(n6^L^2)；
1984年，印度數學家卡瑪卡爾給出了線性規劃的一個新的多項式算法，其計算複雜性為O(n^3.5L^2)，大大改進了哈奇揚的結果，引起了人們極大的興趣。這些多項式算法的一個共同特點就是不再從可行域的頂點開始疊代，而是選取可行域內部一個適當的點，沿某個下降方向開始疊代到達最優解。我們把具有這種特點的算法統稱為內點算法。內點算法的理論比較成熟，但是套用起來還是有難度，究其原因就是初始內點難以找到，因此對內點算法的研究始終停留在理論上。
1989年，Renato D.C. Monteiro 和Ilan ADLER給出了求解線性規劃一個原—對偶內點算法，其疊代次數為 ，計算複雜性為O(n^3.5^L)，這是目前理論上最好且最完善的求解線性規劃的多項式算法；由於該算法對初始點的要求很嚴格，這就給數值實驗帶來更大的困難，迄今為止，也沒有關於該算法的數值例子問世。
