User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Strict Monotonicity and Improved Complexity in the Standard Form Projective Algorithm for Linear-programming

Primary tabs

Anstreicher, KM.

In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve O(square-root n L) step complexity, opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 1993
Language Anglais
Journal information "Mathematical Programming" - Vol. 62, no. 3, p. 517-535 (1993)
Peer reviewed yes
Publisher Elsevier Science Bv (Amsterdam)
issn 0025-5610
e-issn 1436-4646
Publication status Publié
Affiliation UCL
Keywords LINEAR PROGRAMMING ; KARMARKAR ALGORITHM ; PROJECTIVE ALGORITHM ; STANDARD FORM
Links
  1. K.M. Anstreicher, “A monotonic projective algorithm for fractional linear programming,”Algorithmica 1 (1986a) 483–498.
  2. K.M. Anstreicher, “A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm,”Operations Research Letters 5 (1986b) 211–214.
  3. 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.
  4. K.M. Anstreicher and P. Watteyne, “A family of search directions for Karmarkar's algorithm,” Discussion Paper 9030, Center for Operations Research and Econometrics, Université Catholoque de Louvain (Louvain-la-Neuve, Belgium, 1990).
  5. G. de Ghellinck and J.-P. Vial, “A polynomial Newton method for linear programming,”Algorithmica 1 (1986) 425–453.
  6. C. Fraley and J.-P. Vial, “Single-phase versus multi-phase projective methods for linear programming,” COMIN, University of Geneva (Geneva, Switzerland, 1989).
  7. R.M. Freund, “Projective transformations for interior point methods, part I: basic theory and linear programming,” Working Paper 179-88, OR Center, MIT (Cambridge, MA, 1988).
  8. 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.
  9. D.M. Gay, “A variant of Karmarkar's linear programming algorithm for problems in standard form,”Mathematical Programming 37 (1987) 81–90.
  10. C.C. Gonzaga, “Conical projection algorithms for linear programming,”Mathematical Programming 43 (1989) 151–173.
  11. C.C. Gonzaga, “Large step path-following methods for linear programming, part I: barrier function method,”SIAM Journal on Optimization 1 (1991a), 268–279.
  12. C.C. Gonzaga, “Large step path-following methods for linear programming, part II: potential reduction method,”SIAM Journal on Optimization 1 (1991b), 280–292.
  13. B. Kalantari, “Karmarkar's algorithm with improved steps,”Mathematical Programming 46 (1990), 73–78.
  14. N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
  15. M. Padberg, “A different convergence proof of the projective method for linear programming,”Operations Research Letters 4 (1986) 253–257.
  16. J. Renegar, “A polynomial-time algorithm, based on Newton's method, for linear programming,”Mathematical Programming 40 (1988) 59–93.
  17. C. Roos and J.-P. Vial, “Long steps with the logarithmic penalty barrier function in linear programming,” in: J. Gabszewicz, J.-F. Richard and L. Wolsey, eds.Economic Decision Making:Games, Econometrics and Optimisation. Contributions in Honour of Jacques H. Drèze (Elsevier, Amsterdam, 1990) pp. 433–441.
  18. A. Schrijver,Theory of Linear and Integer Programming (Wiley, New York, 1986).
  19. D. Shaw and D. Goldfarb, “A path-following projective interior point method for linear programming,” (1990), to appear in:SIAM Journal on Optimization.
  20. A.E. Steger, “An extension of Karmarkar's algorithm for bounded linear programming problems,” M.S. Thesis, State University of New York (Stonybrook, NY, 1985).
  21. M.J. Todd, “The effect of sparsity, degeneracy, and null and unbounded variables on variants of Karmarkar's linear programming algorithm,” Technical Report 857, School of OR/IE, Cornell University (Ithaca, NY, 1989).
  22. M.J. Todd and B.P. Burrell, “An extension of Karmarkar's algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424.
  23. M.J. Todd and Y. Ye, “A centered projective algorithm for linear programming,”Mathematics of Operations Research 15 (1990) 508–529.
  24. Y. Ye, “A class of projective transformations for linear programming,”SIAM Journal on Computing 19 (1990) 457–466.
  25. Y. Ye, “An O(n 3 L) potential reduction algorithm for linear programming,”Mathematical Programming 50 (1991) 239–258.
  26. Y. Ye and M. Kojima, “Recovering optimal solutions in Karmarkar's polynomial algorithm for linear programming,”Mathematical Programming 39 (1987) 305–317.
Bibliographic reference Anstreicher, KM.. Strict Monotonicity and Improved Complexity in the Standard Form Projective Algorithm for Linear-programming. In: Mathematical Programming, Vol. 62, no. 3, p. 517-535 (1993)
Permanent URL http://hdl.handle.net/2078.1/49203