Abstract
This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x k) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence (\(\bar x^k\)). Under the suitable assumptions it is shown that the sequence (\(\bar x^k\)) converges superlinearly faster to the solution than (x k). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.
Similar content being viewed by others
References
I. Adler and R.C. Monteiro, “Limiting behaviour of the affine scaling continuous trajectories for linear programming problems,”Mathematical Programming 50 (1991) 29–51.
M.D. Asic, V.V. Kovacevic-Vujcic and M.D. Radosavljevic-Nikolic, “Asymptotic behaviour of Karmarkar's method for linear programming,”Mathematical Programming 46 (1990) 173–190.
M.D. Asic, V.V. Kovacevic-Vujcic and M.D. Radosavljevic-Nikolic, “A note on limiting behaviour of the projective and the affine rescaling algorithms,” J.C. Lagarias and M.J. Todd, eds.,Mathematical Developments Arising from Linear Programming, AMS Series Contemporary Mathematics (AMS, Providence, RI, 1990) pp. 151–157.
E.R. Barnes, “A variation on Karmarkar's algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182.
D.A. Bayer and J.C. Lagarias, “The nonlinear geometry of linear programming. I. Affine and projective rescaling trajectories,”Transactions of the American Mathematical Society 314 (1989) 499–526.
D.A. Bayer and J.C. Lagarias, “The nonlinear geometry of linear programming. II. Legendre transform coordinates and central trajectories,”Transactions of the American Mathematical Society 314 (1989) 527–581.
I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675.
C.C. Gonzaga, “An algorithm for solving linear programming problems in O(n 3 L) operations,” in: N. Megiddo, ed.,Progress in Mathematical Programming, Interior Point and Related Methods (Springer, New York, 1988) pp. 1–28.
M. Iri and H. Imai, “A multiplicative barrier function method for linear programming,”Algorithmica 1 (1986) 373–395.
N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
V.V. Kovacevic-Vujcic, “Ubrzanje konvergencije metode kaznenih funkcija za linearno programiranje,” in:Proceedings of the 16th Yugoslav Symposium on Operations Research (Kupari, Yugoslvia, 1989) pp. 283–286.
J.C. Lagarias, “The nonlinear geometry of linear programming. III. Projective Legendre transform coordinates and Hilbert geometry,”Transactions of the American Mathematical Society 320 (1990) 193–225.
N. Megiddo and M. Shub, “Boundary behaviour of interior point algorithms for linear programming,”Mathematics of Operations Research 14 (1989) 97–146.
R.D.C. Monteiro, “Convergence and boundary behaviour of the projective scaling trajectories for linear programming,” to appear in:Journal of Complexity.
M.D. Radosavljevic-Nikolic, “Asymptotic behaviour of the affine variant of Karmarkar's algorithm for linear programming,”XX Conference “Mathematical Optimization,”Humboldt-Universität zu Berlin (Berlin, 1988).
J. Renegar and M. Shub, “Simplified complexity analysis for Newton LP methods,” Technical Report 807, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, 1988).
M. Shub, “On the asymptotic behaviour of the projective rescaling algorithm for linear programming,”Journal of Complexity 3 (1987) 258–269.
T. Tsuchiya and K. Tanabe, “Local convergence properties of new methods in linear programming,”Journal of the Operations Research Society of Japan 33(1) (1990) 22–45.
T. Tsuchiya, “Global convergence of the affine scaling methods for degenerate linear programming problems,”Mathematical Programming (Series B) 52 (1991) 377–404, this issue.
C. Witzgall, P. Boggs and P. Domich, “On center trajectories and their relatives in linear programming,” J.C. Lagarias and M.J. Todd, eds.,Mathematical Developments Arising from Linear Programming, AMS Series Contemporary Mathematics (AMS, Providence, RI, 1990) pp. 161–187.
Y. Zhang, R.A. Tapia and J.E. Dennis, “On the superlinear and quadratic convergence of primal—dual interior point linear programming algorithms,” Technical Report TR90-6, Rice University (Houston, TX, 1990).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kovacevic-Vujcic, V.V. Improving the rate of convergence of interior point methods for linear programming. Mathematical Programming 52, 467–479 (1991). https://doi.org/10.1007/BF01582901
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582901