1樓：Allos
大部分人學線性規劃的內點法容易有誤解，認為內點法是為了求解線性規劃設計出來的。歷史上內點法早就存在，為了求解「非線性」規劃問題就設計出來了。對於非線性規劃，最重要的指標是收斂以及收斂的速度。
收斂到哪個解不是那麼重要；對於線性規劃，收斂到全域性最優解那已經是很好的事情了。
更重要的事情是，對於非線性規劃來說，內點法不是乙個特別好的演算法；導致內點法長期以來都不被重視甚至遺忘。到了Leo khachiyan那幫蘇聯人搞清楚計算複雜性的時候，內點法終於又被找出來測試了。
目前的教科書上一般只介紹內點法的原理，偏理論；缺乏系統化實現的講述。當然對於系統化實現內點法就不是一般教科書能夠講清楚的。
對於求解線性規劃的具體問題而言，單純型法還是首選。
2樓：
假設線性規劃問題（標準型）如下，同時有且只有乙個解
對偶問題（標準型）是
最為典型的內點法，像primal-dual algorithm的幾個變種，是利用KKT條件，將優化問題轉化成了方程求解問題。Affine-Scaling型的內點法，求解的是下式：
注意到第三個等式，即凸優化中的互補鬆弛條件（標準型）是非線性方程；所以這個問題是非線性方程組求解問題。非線性方程組求解問題的典型方法是牛頓法及其變種。在原問題有且只有乙個解時，這個方程的解應該是頂點（vertex）。
不過，現實中情況很複雜。用牛頓法求的時候，需要求解下降的方向，即下式中的 , , 。如果自己寫過內點法求解器會發現，下式中第乙個矩陣往往條件數非常大，也就是接近於奇異矩陣，是乙個比較棘手的問題；這個問題跟line search演算法也有一點關係，步長調小能緩解，但不能解決，還會降低速度。
此時為了求解下降方向，需要求第乙個矩陣的逆矩陣，這時會帶來很多數值方法上的問題。因為條件數很大的矩陣求逆，求秩，都依賴於tolerance，非常不穩定，不可靠。常見的解決方法，會用到一些矩陣分解、偽逆等，但都是近似，因為問題本身是某種程度上病態的(ill-defined)。
所以實際中求解到的，不是真正在邊界上的頂點，而是乙個近似解。比如變數應該求得0，實際得到的是乙個非常接近於0的數。跟你設定的tolerance這些有很大的關係。
也需要根據你設定的tolerance來看，是否可以看做頂點。
在Path-Following這類的內點法中，求解的是下式：
注意到第三式中， 可以看做無窮小，所以是「弱」的互補鬆弛條件。這樣的話，在原問題有且只有乙個解時，這個方程的解不是頂點，是頂點鄰域中的點，也是近似解。
正是因為內點法是一種近似方法，某個約束是否被真正啟用都未必說得清楚，所以很多人不喜歡。為了解決這種問題，於是有了後處理演算法。一些商業化的求解器裡，會有後處理演算法，從而保證內點法取到的點是頂點。
這些預處理、後處理演算法，大多數優化的課程都不會提到；但是對於寫乙個求解器而言卻非常重要。以CPLEX舉例，CPLEX裡有乙個叫crossover的後處理演算法，保證用內點法求解到的是乙個頂點，而且是最近的那個頂點。
據我所知，不是所有的科學計算軟體提供的內點法都有crossover那樣的後處理方法。Matlab應該是沒有的；CPLEX是預設使用crossover後處理的，如果需要可以手動關掉。其他商業求解器，我不是很確定，需要去查使用手冊。
怎麼理解線性規劃問題的基可行解對應可行域的頂點？
雲飛揚 如果是最小化問題，單看目標函式，是線性的，係數為正的變數當然該在可行域內取最小值，係數為負的當然該取最大值，也就是犄角旮旯的點。 楊一帥 對於可行域 並且A行滿秩，令 支撐集 當x是可行域的頂點，根據多面體理論中支撐集的性質，列向量 線性不相關。又因為A行滿秩，也就是Rank A m，必然存...
怎樣用拉格朗日乘數法解高中線性規劃問題
介紹一種active set 的思想，步驟 第一步.先求無約束最優解。然後把解代入不等式看看哪些不等式不成立。如果不等式都成立，解題結束。這裡無約束最優解顯然是負無窮,負無窮太大寫不下，那麼先假設乙個解是x 10 y 10 Z 40 如果假設滿足所有約束，要再找個假設點，直到有約束不成立。正常來講是...
為什麼我們要考慮線性規劃的對偶問題？
fredorfled 知乎上回答問題的水平真的堪憂，人家問的是提出對偶問題的數學直覺，這是乙個比什麼是對偶問題大得多和深刻得多的問題。回答全是對偶問題是什麼也是醉了。 蘇劍林 從Wasserstein距離 對偶理論到WGAN 科學空間 Scientific Spaces 也許這部分內容會有一定的參考...