Skip to main content
SpringerLink
Log in

Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals

  • Published:
Applied Mathematics and Optimization Submit manuscript

Abstract

In this paper we study a particular class of primal-dual path-following methods which try to follow a trajectory of interior feasible solutions in primal-dual space toward an optimal solution to the primal and dual problem. The methods investigated are so-called first-order methods: each iteration consists of a “long” step along the tangent of the trajectory, followed by explicit recentering steps to get close to the trajectory again. It is shown that the complexity of these methods, which can be measured by the number of points close to the trajectory which have to be computed in order to achieve a desired gain in accuracy, is bounded by an integral along the trajectory. The integrand is a suitably weighted measure of the second derivative of the trajectory with respect to a distinguished path parameter, so the integral may be loosely called a curvature integral.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. I. Adler, N. Karmarkar, M. G. C. Resende, and G. Veiga: An implementation of Karmarkar's algorithm for linear programming. Mathematical Programming 44 (1989), 297–335.

    Google Scholar 

  2. D. A. Bayer and J. C. Lagarias: The nonlinear geometry of linear programming, I, II, III. Transactions of the American Mathematical Society, 314 (1989), 499–526, 527–581, and 320 (1990), 193–225.

    Google Scholar 

  3. R. M. Freund: Polynomial time algorithms for linear programming. Preprint OR 182-88, Sloan School of Management, M.I.T., Cambridge, MA, 1988.

    Google Scholar 

  4. Fl. Jarre: On the method of analytic centers for solving smooth, convex programs. In: Optimization (S. Dolecki, ed.), Lecture Notes in Mathematics, Vol. 1405, Springer-Verlag, Berlin, 1989, pp. 69–85.

    Google Scholar 

  5. Fl. Jarre, G. Sonnevend, and J. Stoer: An implementation of the method of analytic centers. In: Analysis and Optimization of Systems (A. Bensoussan, J. L. Lions, eds.), Lecture Notes in Control and Information Sciences, Vol. 111, Springer-Verlag, Berlin, 1988, pp. 297–307.

    Google Scholar 

  6. N. Karmarkar: A new polynomial time algorithm for linear programming. Combinatorica 4 (1984), 373–395.

    Google Scholar 

  7. N. Karmarkar: Riemannian geometry underlying interior point methods. Lecture and preprint presented at the 13th International Symposium on Mathematical Programming, Tokyo, 1988.

  8. N. Karmarkar, J. Lagarias, L. Slutsman, and P. Wang: Power series variants of Karmarkar-type algorithms. AT&T Technical Journal, to appear.

  9. M. Kojima, Sh. Mizuno, and A. Yoshise: AnO(√nL) iteration potential reduction algorithm for linear complementarity problems. Report 8-217, Department of Information Science, Tokyo Institute of Technology, Tokyo, 1988.

    Google Scholar 

  10. J. Renegar: A polynomial-time algorithm, based on Newton's method, for linear programming. Mathematical Programming 40 (1988), 59–93.

    Google Scholar 

  11. C. Roos and I.-Ph. Vial: A polynomial method of approximate centers for linear programming. Technical Report 88-68, Technical University, Delft, 1988.

    Google Scholar 

  12. G. Sonnevend: An analytic center for polyhedrons and new classes for linear (smooth-convex) programming. In: System Modelling and Optimization (A. Prekopa, ed.), Lecture Notes in Control and Information Sciences, Vol. 84, Springer-Verlag, Berlin, 1985, pp. 866–876.

    Google Scholar 

  13. G. Sonnevend and J. Stoer: Global ellipsoidal approximations and homotopy methods for solving convex analytic programs. Applied Mathematics and Optimization 21 (1990), 139–166.

    Google Scholar 

  14. G. Sonnevend, J. Stoer, and G. Zhao: On the complexity of following the central path of linear programs by linear extrapolation. Methods of Operations Research, 62 (1989), 19–31.

    Google Scholar 

  15. M. Todd: Recent developments and new directions in linear programming. In: Mathematical Programming: Recent Developments and Applications (M. Iri, K. Tanabe, eds.), Kluwer Academic Press, Dordrecht, 1989, pp. 109–157.

    Google Scholar 

  16. C. Witzgall, P. T. Boggs and P. D. Domich: On the convergence behavior of trajectories for linear programming. In: Mathematical Developments Arising from Linear Programming Algorithms (J. C. Lagarias, M. J. Todd, eds.), Contemporary Mathematics, Vol. 114, American Mathematical Society, Providence, RI, 1991, pp. 161–187.

    Google Scholar 

  17. Y. Ye: A class of potential functions for linear programming. Report 88-13, Department of Management Science, The University of Iowa, Iowa City, IA, 1988.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Angewandte Mathematik und Statistik, Universität Würzburg, Am Hubland, W-8700, Würzburg, Germany

    G. Zhao & J. Stoer

Authors
  1. G. Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Stoer
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zhao, G., Stoer, J. Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals. Appl Math Optim 27, 85–103 (1993). https://doi.org/10.1007/BF01182599

Download citation

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01182599

Key words

AMS classification

Search

Navigation