Abstract
We present a path-following algorithm for the linear programming problem with a surprisingly simple and elegant proof of its polynomial behaviour. This is done both for the problem in standard form and for its dual problem. We also discuss some implementation strategies.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K.M. Anstreicher, “A monotonic projective algorithm for fractional linear programming,”Algorithmica 1 (1986) 483–498.
K.M. Anstreicher and R.A. Bosch, “Long steps in an O(n 3 L) algorithm for linear programming,”Mathematical Programming 54 (1992) 251–265, this issue.
E.R. Barnes, “A variation on Karmarkar's algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182.
G. De Ghellinck and J.-Ph. Vial, “A polynomial Newton method for linear programming,”Algorithmica 1 (1986) 425–453.
I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Doklady Akademiia Nauk SSSR 174 (1967) 747–748.
R.M. Freund, “Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function,”Mathematical Programming 51 (1991) 203–222.
K.R. Frisch, “The logarithmic potential method of convex programming,” Memorandum, Institute of Economics, University of Oslo (Oslo, Norway, 1955).
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 method,”Mathematical Programming 36 (1986) 183–209.
D. Goldfarb and S. Liu, “An O(n 3 L) primal interior point algorithm for convex quadratic programming,”Mathematical Programming 49 (1991) 325–340.
C.C. Gonzaga, “An algorithm for solving linear programming problems in O(n 3 L) operations,” in: N. Megiddo, ed.,Progress in Mathematical Programming (Springer, New York, 1987) pp. 1–28.
C.C. Gonzaga, “Polynomial affine algorithms for linear programming,”Mathematical Programming 49 (1990) 7–21.
P. Huard, “Resolution of mathematical programming with nonlinear constraints by the method of centers,” in: J. Abadie, ed.,Non-Linear Programming (North-Holland, Amsterdam, 1967) pp. 207–219.
N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
M. Kojima, S. Mizuno and A. Yoshise, “A polynomial-time algorithm for a class of linear complementarity problems,”Mathematical Programming 44 (1989) 1–26.
N. Megiddo, “Pathways to the optimal set in linear programming,” in:Proceedings of the 6th Mathematical Programming Symposium of Japan (Nagoya, Japan, 1986) pp. 1–36.
R.C. Monteiro and I. Adler, “An O(n 3 L) primal—dual interior point algorithm for linear programming,”Mathematical Programming 44 (1987) 27–42.
V. Pan, “How can we speed up matrix multiplication?”SIAM Review 26 (1984) 393–415.
J. Renegar, “A polynomial-time algorithm based on Newton's method for linear programming,”Mathematical Programming 40 (1988) 59–95.
C. Roos, “A new trajectory following polynomial-time algorithm for the linear programming problem,”Journal on Optimization Theory and its Applications 63 (1989) 433–458.
Gy. Sonnevend, “An analytic centre for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming,” Preprint, Department of Numerical Analysis, Institute of Mathematics, Eötvös University (Budapest, Hungary, 1985).
M.J. Todd and B.P. Burrell, “An extension of Karmarkar's algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424.
M.J. Todd and Y. Ye, “A centered projective algorithm for linear programming,”Mathematics of Operations Research 15 (1990) 508–529.
P.M. Vaidya, “An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations,”Mathematical Programming 47 (1990) 175–201.
R.J. Vanderbei, M.S. Meketon and B.A. Freedman, “A modification of Karmarkar's linear programming algorithm,”Algorithmica 1 (1986) 395–407.
Y. Ye, “Interior algorithms for linear, quadratic and linearly constrained convex problems,” Ph.D. Thesis (Chapter 5), Department of Engineering-Economic Systems, Stanford University (Stanford, CA, 1987).
Y. Ye, “An O(n 3 L) potential reduction algorithm for linear programming,”Mathematical Programming 50 (1991) 239–258.
Author information
Authors and Affiliations
Additional information
This author completed this work under the support of the research grant No. 1467086 of the Fonds National Suisses de la Recherche Scientifique.
Rights and permissions
About this article
Cite this article
Roos, C., Vial, J.P. A polynomial method of approximate centers for linear programming. Mathematical Programming 54, 295–305 (1992). https://doi.org/10.1007/BF01586056
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01586056