Abstract
In this paper we propose a long-step target-following methodology for linear programming. This is a general framework, that enables us to analyze various long-step primal-dual algorithms in the literature in a short and uniform way. Among these are long-step central and weighted path-following methods and algorithms to compute a central point or a weighted center. Moreover, we use it to analyze a method with the property that starting from an initial noncentral point, generates iterates that simultaneously get closer to optimality and closer to centrality.
Similar content being viewed by others
References
Altman A, Gondzio J (1993) An efficient implementation of a higher order primal-dual interior point method for large sparse linear programs. Archives of Control Sciences 2:23–40
Ding J, Li TY (1990) An algorithm based on weighted logarithmic barrier functions for linear complementarity problems. Arabian Journal for Science and Engineering 15:679–685
Gondzio J (1994) Multiple centrality corrections in a primal-dual method for linear programming. Technical report, Section of Management Studies, University of Geneva, Geneva
Gonzaga CC (1991) Large steps path-following methods for linear programming, Part I: Barrier function method. SIAM Journal on Optimization 1:268–279
Gonzaga CC (1992) Path following methods for linear programming. SIAM Review 34:167–227
den Hertog D (1994) Interior point approach to linear, quadratic and convex programming, Algorithms and complexity. Kluwer Publishers, Dordrecht
Jansen B, Roos C, Terlaky T (1993) A family of polynomial affine scaling algorithms for positive semi-definite linear complementarity problems. Technical Report 93-112, Faculty of Technical Mathematics and Computer Science, Delft University of Technology, Delft. To appear in SIAM Journal on Optimization
Jansen B, Roos C, Terlaky T (1993) A polynomial primal-dual Dikin-type algorithm for linear programming. Technical Report 93-36, Faculty of Technical Mathematics and Computer Science, Delft University of Technology, Delft. To appear in Mathematics of Operations Research
Jansen B, Roos C, Terlaky T, Vial J-Ph (1993) Primal-dual target-following algorithms for linear programming. Technical Report 93-107, Faculty of Technical Mathematics and Computer Science, Delft University of Technology, Delft. To appear in Annals of OR
Jansen B, Roos C, Terlaky T, Vial J-Ph (1994) Primal-dual algorithms for linear programming based on the logarithmic barrier method. Journal of Optimization Theory and Applications 83:1–26
Kojima M, Megiddo N, Noma T, Yoshise A (1991) A unified approach to interior point algorithms for linear complementarity problems. Volume 538 of Lecture Notes in Computer Science. Springer Verlag, Berlin
Mizuno S (1990) AnO(n3L) algorithm using a sequence for linear complementarity problems. Journal of the Operations Research Society of Japan 33:66–75
Mizuno S (1992) A new polynomial time method for a linear complementarity problem. Mathematical Programming 56:31–43
Monteiro RDC, Adler I, Resende MGC (1990) A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Mathematics of Operations Research 15:191–214
Nesterov Y, Todd MJ (1994) Self-scaled barriers and interior-point methods for convex programming. Technical Report 1091, School of OR and IE, Cornell University, Ithaca, New York. To appear in Mathematics of Operations Research
Roos C, Vial J-Ph (1990) Long steps with the logarithmic penalty barrier function in linear programming. In Gabszevwicz J, Richard J-F, Wolsey L (eds) Economic Decision-Making: Games, Economics and Optimization, dedicated to Jacques H. Drèze, pages 433–441. Elsevier Science Publisher B.V., Amsterdam
Ye Y, Todd MJ, Mizuno S (1994) AnO(√nL)-iteration homogeneous and self-dual linear programming algorithm. Mathematics of Operations Research 19:53–67
Author information
Authors and Affiliations
Additional information
This work is completed with the support of a research grant from SHELL.
The first author is supported by the Dutch Organization for Scientific Research (NWO), grant 611-304-028.
The fourth author is supported by the Swiss National Foundation for Scientific Research, grant 12-34002.92.
Rights and permissions
About this article
Cite this article
Jansen, B., Roos, C., Terlaky, T. et al. Long-step primal-dual target-following algorithms for linear programming. Mathematical Methods of Operations Research 44, 11–30 (1996). https://doi.org/10.1007/BF01246327
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01246327