Abstract
本篇論文內容分為兩部份。第一部份是內點延續法鬆弛論點之原始對偶演 算法用於解線性規劃問題，其中分為五章，在第一章，我們對於內點演算 法在這幾年來的發展作一個縱覽性的介紹。在第二章，我們介紹由 Monteiro 和 Alder 兩位先生所提的內點延續法之原始對偶演算法。這個 方法對於解線性規劃問題是相當不錯的方法，但是若要在電腦上執行的話 ，仍然有兩個問題需要克服，一是在每次迭代中必須精確地解出最小平方 差問題，這是電腦運算中最耗費時間的關鍵所在。二是當演算法即將收斂 時那個矩陣會變成病態的矩陣。因此，在第三章我們提出內點延續法鬆弛 論點之原始對偶演算法，它使得上述的兩個問題同時獲得改善。同時，我 們也證明此種方法的最多的迭代次數跟原來的演算法有相同的 order 。 在第四章，我們用電腦實際地去比較由 Monteiro 和 Alder 兩位先生所 提出的演算法及我們所提出的演算法，結果我們所提出的演算法節省了相 當多的運算量。而且，我們的演算法比原先的演算法更穩定。所以，我們 的演算法改善了原先的問題。最後，在第五章對此部份下一個總結，以使 第一部份更為完備。而第二部份則是延續第一部份的研究，把內點延續法 鬆弛論點之原始對偶演算法用於解二次規劃問題，同時推導出相當不錯的 結果。