自從1984年 Narendra Karmakar [5]，線性規劃的內點法已經有許多變形。這篇論文專注於原始-對偶可行路徑追蹤演算法的其中一種變形，這個演算法的初始值可行，而且有目前已知最好的多項式複雜度 [1] [3] [10]。為了解釋內點法的想法，我們畫了具啟發性的圖來說明單形法和內點法的直觀看法。路徑追蹤演算法最重要的概念是中心路徑。我們也畫圖說明幾何概念。在實務演算法程式實作，我們從Netlib網站挑選了超過50個真實問題來測試，而我們挑選的問題當中，除了那些問題規模太大、超過電腦硬體負荷的問題，所有問題都能被演算法正確解出。這篇論文提供一個亦於理解內點法的方式，從直觀概念到數學理論證明，再到實務應用。

There have been many variants of interior point methods (IPMs) for solving linear programming since Narendra Karmakar in 1984 [5]. In this thesis, we focus on one of the variants of primal-dual feasible path-following algorithms, which has a feasible starting point and which has a nice mathematical analysis for the convergence with the best known polynomial complexity [1] [3] [10]. In order to explain the idea of IPMs, we plot inspiring figures to illustrate intuitive idea of the simplex method and IPMs. The most important concept of path-following algorithms is the central path. We also plot instructive graphics to illustrate the geometric concept. In practical implementations, we test over 50 problems from Netlib and report all optimal values. All the selected test problems can be solved correctly by the algorithm except for the problems whose sizes exceed the hardware limitation. This thesis provides an easy-to-understand way for IPMs from intuitive concepts to mathematical theory to practical implementations.

[1] Matousek, Jiri, G¨artner, Bernd, “Understanding and Using Linear Programming”, Springer–Verlag Berlin Heidelberg, 2007.
[2] Robert J. Vanderbei, “Linear Programming: Foundations and Extensions”, Springer-New York Heidelberg Dordrecht London, 4th ed. 2014 edition (July 16, 2013)
[3] Cornelis Roos, Tam´as Terlaky, Jean Philippe Vial “Interior Point Methods for Linear Optimization”, Springer, Berlin etc., 2005.
[4] G.B. Dantzig, “Maximization of a linear function of variables subject to linear inequalities, Activity Analysis of Production and Allocation”, T. C. Hoopmans ed., Wiley, New York, 339-347, 1951.
[5] N. Karmarkar, “A New Polynomial Time Algorithm for Linear Programming”, Institute for Operations Research and the Management Sciences (INFORMS), 4:373–395, 1984.
[6] V. Klee and G. Minty, “How good is the simplex algorithm”, in Inequalities, Vol. III O. Shisha, ed., Academic Press, 159–175, 1972.
[7] L. G. Khachiyan, “Polynomial algorithm in linear programming”, Zh. Vychisl. Mat. Mat. Fiz., 20:1 (1980), 51–68; U.S.S.R. Comput. Math. Math. Phys., 20:1, 53–72, 1980.
[8] Sheu, R.L.* and Fang, S.C., “On the relationship of interior-point methods”, Internat. J. Math. & Math. Sci. vol. 16 no. 3,, 565-572, 1993.
[9] S. Mehrotra., “On the implementation of a(primal-dual) interior point method”, SIAM Journal on Optimization, 2(4), 575-601, 1992.
[10] Tamas Terlaky, “An easy way to teach interior-point methods”, European Journal of Operational Research 130, 1-19, 2001.
[11] A.J. Goldman and A.W. Tucker, “Theory of linear programming, in: H.W. Kuhn, A.W. Tucker (Eds.), Linear Inequalities and Related Systems”, Annals of Mathematical Studies, vol. 38, Princeton University Press, Princeton, NJ, 53-97, 1956.
[12] A.J. Goldman and A.W. Tucker, “Dual systems of homogeneous linear relations, in: H.W. Kuhn, A.W. Tucker (Eds.), Linear Inequalities and Related Systems”, Annals of Mathematical Studies, vol. 38, Princeton University Press, Princeton, NJ, 3-18, 1956.