Abstract
N. Karamaker 在 1984 年提出多項式時間收斂(polynomial time con -vergence)解線性規劃問題的內點法後，一些變異(variants)的演算法相 繼被提出。 這些方法包括對偶可行解內點法(primal-dual feasible int- erior points methods)及對偶不可行解內點法(primal-dual infeasible interior points methods)。對於對偶不可行解內點法， Kojima 在 1992年提出一個演算法, 並證明其演算法的全域收斂(global convergence)性質；之後，Mizuno 在 1994 年提出一個 $O(nL)$ 多項式 時間收斂的不可行解內點法。其演算法是 Kojima 在 1992 年所提出的全 域收斂演算法的修正。在這篇論文中, 我們根據 Mizuno 的演算法來延伸 其演算法到一個鬆弛的版本(relax version)；我們並證明我們的演算法 和 Mizuno 的演算法同樣是有 $O(nL)$ 多項式時間收斂性質。除此之 外, 我們還報告我們演算法的一些數值結果；這些數值結果是和非鬆弛( non-relax)版本來做比較。本篇論文中, 第一節簡單介紹可行解與不可行 解內點法的演進；第二節回顧 Kojima 和 Mizuno 的演算法；第三節敘述 我們的演算法；第四節證明我們所提出的演算法是 $O(nL)$ 多項式時間 收斂；第五節是敘述不可行解內點法的 implementation；第六節是一些 數值結果的比較；第七節則是敘述我們未來要研究的方向。