Skip to main content
SpringerLink
Log in

A multiplicative barrier function method for linear programming

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

A simple Newton-like descent algorithm for linear programming is proposed together with results of preliminary computational experiments on small- and medium-size problems. The proposed algorithm gives local superlinear convergence to the optimum and, experimentally, shows global linear convergence. It is similar to Karmarkar's algorithm in that it is an interior feasible direction method and self-correcting, while it is quite different from Karmarkar's in that it gives superlinear convergence and that no artificial extra constraint is introduced nor is protective geometry needed, but only affine geometry suffices.

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. D. Avis and V. Chvátal, Note on Bland's pivoting rule,Math. Programming Stud.,8 (1978), 24–34.

    Google Scholar 

  2. M. Iri, Another “simple and fast” algorithm for linear programming, paper presented at the 12th International Symposium on Mathematical Programming, August 5–9, 1985, MIT, Boston.

    Google Scholar 

  3. M. Iri and H. Imai, A method of solving linear programming — with reference to the Karmarkar method and the penalty function method, Research Meeting of the Mathematical Programming Research Group of the Operations Research Society of Japan, February 16, 1985.

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

    Article  MATH  MathSciNet  Google Scholar 

  5. L. G. Khachian, A polynomial algorithm in linear programming,Dokl. Akad. Nauk SSSR,244 (1979), 1093–1096 (in Russian); transl. inSoviet Math. Dokl.,20 (1979), 191–194.

    MathSciNet  Google Scholar 

  6. L. G. Khachian, Polynomial algorithms in linear programming,Zh. Vychisl. Mat. i Mat. Fiz.,20 (1980), 51–68 (in Russian); transl. inU.S.S.R. Comput. Math. and Math. Phys.,20 (1980), 53–72.

    MathSciNet  Google Scholar 

  7. V. Klee and G. J. Minty, How good is the simplex algorithm?, inInequalities III (O. Shisha, ed.), Academic Press, New York, 1972, pp. 159–175.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Engineering and Instrumentation Physics, Faculty of Engineering, University of Tokyo, Bunkyo-ku, 113, Tokyo, Japan

    Masao Iri

  2. Department of Computer Science and Communication Engineering, Kyushu University, Hakozaki, 812, Fukuoka, Japan

    Hiroshi Imai

Authors
  1. Masao Iri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hiroshi Imai
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by Nimrod Megiddo.

The works of the first author and the second were supported in part by the Grant-in-Aid for Scientific Research (B) 60460130 (1985) and by the Grant-in-Aid for Encouragement of Young Scientists (A) 60790046 (1985), respectively, of the Ministry of Education, Science and Culture of Japan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Iri, M., Imai, H. A multiplicative barrier function method for linear programming. Algorithmica 1, 455–482 (1986). https://doi.org/10.1007/BF01840457

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation