Abstract
Recently, Todd has analyzed in detail the primal-dual affine-scaling method for linear programming, which is close to what is implemented in practice, and proved that it may take at leastn 1/3 iterations to improve the initial duality gap by a constant factor. He also showed that this lower bound holds for some polynomial variants of primal-dual interior-point methods, which restrict all iterates to certain neighborhoods of the central path. In this paper, we further extend his result to long-step primal-dual variants that restrict the iterates to a wider neighborhood. This neigh-borhood seems the least restrictive one to guarantee polynomiality for primal-dual path-following methods, and the variants are also even closer to what is implemented in practice.
Similar content being viewed by others
References
K.M. Anstreicher, On the performance of Karmarkar's algorithm over a sequence of iterations, SIAM J. Optim. 1(1991)22.
K.M. Anstreicher, J. Ji, F. Potra and Y. Ye, Average performance of a self-dual interior-point algorithm for linear programming, in:Complexity in Numerical Optimization, ed. P. Pardalos (World Scientific, New Jersey, 1993) p. 1.
D. Bertsimas and X. Luo, On the worst case complexity of potential reduction algorithms for linear programming, Working Paper 3558-93, Sloan School of Management, MIT, Cambridge, MA 02139, USA (1993).
D. Goldfarb and M.J. Todd, Linear programming, in:Optimization, Volume 1 ofHandbooks in Operations Research and Management Science, ed. G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (North-Holland, Amsterdam, The Netherlands, 1989) p. 73.
C.C. Gonzaga, Path following methods for linear programming, SIAM Rev. 34(1992)167.
J. Ji and Y. Ye, A complexity analysis for interior-point algorithms based on Karmarkar's potential function, SIAM J. Optim. 4(1994)512.
N.K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4(1984)373.
M. Kojima, N. Megiddo and S. Mizuno, A primal-dual infeasible-interior-point algorithm for linear programming, Math. Progr. 61(1993)263.
M. Kojima, S. Mizuno and A. Yoshise, A primal-dual interior point algorithm for linear programming, in:Progress in Mathematical Programming: Interior Point and Related Methods, ed. N. Megiddo (Springer, New York, 1989) p. 29.
M. Kojima, S. Mizuno and A. Yoshise, A polynomial-time algorithm for a class of linear complementarity problems, Math. Progr. 44(1989)1.
M. Kojima, S. Mizuno and A. Yoshise, An\(O(\sqrt {nL} )\) iteration potential reduction algorithm for linear complementarity problems, Math. Progr. 50(1991)331.
I.J. Lustig, R.E. Marsten and D.F. Shanno, Computational experience with a primal-dual interior point method for linear programming, Lin. Alg. Appl. 152(1991):191.
I.J. Lustig, R.E. Marsten and D.F. Shanno, Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming, Math. Progr 66(1994)123.
S. Mehrotra and Y. Ye, On finding an interior point on the optimal face of linear programs, Math. Progr. 62(1993)497.
S. Mizuno, M.J. Todd and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res. 18(1993)964.
R.D.C. Monteiro and I. Adler, Interior path following primal-dual algorithms: Part I: Linear programming, Math. Progr. 44(1989)27.
A.S. Nemirovsky, An algorithm of the Karmarkar type, Tekhnicheskaya Kibernetika 1(1987)105, translated in: Sov. J. Comp. Syst. Sci. 25(5)(1987)61.
M.J.D. Powell, On the number of iterations of Karmarkar's algorithm for linear programming, Math. Progr. 62(1993)153.
G. Sonnevend, J. Stoer and G. Zhao, On the complexity of following the central path of linear programs by linear extrapolation II, Math. Progr. 52(1991)527.
M.J. Todd, Recent developments and new directions in linear programming, in:Mathematical Programming: Recent Developments and Applications, ed. M. Iri and K. Tanabe (Kluwer Academic, Dordrecht The Netherlands, 1989), p. 109.
M.J. Todd, A lower bound on the number of iterations of primal-dual interior-point methods for linear programming, in:Numerical Analysis 1993, Volume 303 ofPitman Research Notes in Mathematics, ed. G.A. Watson and D.F. Griffiths (Longman, Burnt Hill, UK, 1994) p. 89.
Y. Ye, Toward probabilistic analysis of interior-point algorithms for linear programming, Math. Oper. Res. 19(1994)38.
Author information
Authors and Affiliations
Additional information
Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550.
This author is supported in part by NSF Grant DDM-9207347. Part of thiw work was done while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.
Rights and permissions
About this article
Cite this article
Todd, M.J., Ye, Y. A lower bound on the number of iterations of long-step primal-dual linear programming algorithms. Ann Oper Res 62, 233–252 (1996). https://doi.org/10.1007/BF02206818
Issue Date:
DOI: https://doi.org/10.1007/BF02206818