Interior path following primal-dual algorithms. I: Linear programming. (English) Zbl 0676.90038

Monteiro, Renato D. C.; Adler, Ilan

Math. Program., Ser. A 44, No. 1, 27-41 (1989).

Authors’ abstract: “We describe a primal-dual interior point algorithm for linear programming problems which requires a total of O(\(\sqrt{n}L)\) number of iterations, where L is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea.”
[For part II see the authors, ibid. A 44, No.1, 43-66 (1989; Zbl 0676.90039).]

Reviewer: N.Deng

MSC:

90C05	Linear programming
65K05	Numerical mathematical programming methods
68Q25	Analysis of algorithms and problem complexity

Keywords:

polynomial-time algorithms; primal-dual interior point algorithm; logarithmic barrier function; path following

Citations:

Zbl 0676.90039

References:

[1]	D.A. Bayer and J.C. Lagarias, ”The nonlinear geometry of linear programming,” manuscripts, AT&T Bell Laboratories (Murray Hill, NJ, 1986), to appear inTransactions of the American Mathematical Society. · Zbl 0671.90045
[2]	A. Fiacco and G. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques (John Wiley and Sons, New York, 1968). · Zbl 0193.18805
[3]	K.R. Frisch, ”The logarithmic potential method of convex programming,” unpublished manuscript, University Institute of Economics (Oslo, Norway, 1955).
[4]	P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, ”On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method,”Mathematical Programming 36 (1986) 183–209. · Zbl 0624.90062 · doi:10.1007/BF02592025
[5]	C.C. Gonzaga, ”An algorithm for solving linear programming problems in O(n 3 L) operations,” Memorandum Number UCB/ERL M87/10, Electronics Research Laboratory, Universtiy of California (Berkeley, CA, March, 1987).
[6]	N. Karmarkar, ”A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[7]	N. Karmarkar, Talk at the University of California at Berkeley (Berkeley, CA, 1984).
[8]	M. Kojima, S. Mizuno and A. Yoshise, ”A primal-dual interior point algorithm for linear programming,” Report No. B-188, Department of Information Sciences, Tokyo Institute of Technology (Tokyo, Japan, February, 1987). · Zbl 0708.90049
[9]	N. Megiddo, ”Pathways to the optimal set in linear programming,” Research Report, IBM Almaden Research Center (San Jose, CA, 1986). · Zbl 0612.90082
[10]	C.R. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, New Jersey, 1982). · Zbl 0503.90060
[11]	J. Renegar, ”A polynomial-time algorithm based on Newton’s method for linear programming,”Mathematical Programming 40 (1988) 59–93. · Zbl 0654.90050 · doi:10.1007/BF01580724
[12]	P.M. Vaidya, ”An algorithm for linear programming which requires O(((m + n)n 2+(m + n) 1.5 n)L) arithmetic operations,” preprint, AT&T Bell Laboratories (Murray Hill, NJ, 1987). · Zbl 0708.90047