On the number of iterations of Karmarkar’s algorithm for linear programming. (English) Zbl 0804.90092

Powell, M. J. D.

Math. Program. 62, No. 1 (B), 153-197 (1993).

Summary: Karmarkar’s algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a “potential function” by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective functions is at most a multiple of \(n\), where \(n\) is the number of inequality constraints. By considering a simple example that allows \(n\) to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example of Karmarkar’s original algorithm can require about \(n/20\) iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.

MSC:

90C05	Linear programming
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

interior point methods; semi-infinite programming; Karmarkar’s algorithm

References:

[1]	I. Adler, M.G.C. Resende, G. Veiga and N. Karmarkar, ”An implementation of Karmarkar’s algorithm for linear programming,”Mathematical Programming 44 (1989) 297–335. · Zbl 0682.90061
[2]	K.M. Anstreicher, ”On the performance of Karmarkar’s algorithm over a sequence of iterations,”SIAM Journal on Optimization 1 (1991) 22–29. · Zbl 0752.90044
[3]	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 of Karmarkar’s projective method,”Mathematical Programming 36 (1986) 183–209. · Zbl 0624.90062
[4]	C.C. Gonzaga, ”Interior point algorithms for linear programming with inequality constraints,”Mathematical Programming 52 (1991a) 209–225. · Zbl 0744.90052
[5]	C.C. Gonzaga, ”Large step path-following methods for linear programming, Part 1: Barrier function method,”SIAM Journal on Optimization 1 (1991b) 268–279. · Zbl 0754.90035
[6]	J.A. Kaliski and Y. Ye, ”Convergence behavior of Karmarkar’s projective algorithm for solving a simple linear program,”Operations Research Letters 10 (1991) 389–393. · Zbl 0748.90039
[7]	N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065
[8]	I.J. Lustig, R.E. Marsten and D.F. Shanno, ”Computational experience with a primal-dual interior point method for linear programming,”Linear Algebra and its Applications 152 (1991) 191–222. · Zbl 0731.65049
[9]	N. Megiddo and M. Shub, ”Boundary behaviour of interior point algorithms in linear programming,”Mathematics of Operations Research 14 (1989) 97–146. · Zbl 0675.90050
[10]	M.J.D. Powell, ”Karmarkar’s algorithm: a view from nonlinear programming,”IMA Bulletin 26 (1990) 165–181. · Zbl 0711.90052
[11]	M.J.D. Powell, ”The complexity of Karmarkar’s algorithm for linear programming,” in: D.F. Griffiths and G.A. Watson, eds.,Numerical Analysis 1991 (Longman Scientific & Technical, Burnt Mill, 1992) pp. 142–163. · Zbl 0809.65056
[12]	M.J. Todd and B.P. Burrell, ”An extension of Karmarkar’s algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424. · Zbl 0621.90048