Skip to main content
SpringerLink
Log in

A simplified global convergence proof of the affine scaling algorithm

  • Part II: Specific Papers
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper presents a simplified and self-contained global convergence proof for the affine scaling algorithm applied to degenerate linear programming problems. Convergence of the sequence of dual estimates to the center of the optimal dual face is also proven. In addition, we give a sharp rate of convergence result for the sequence of objective function values. All these results are proved with respect to the long step version of the affine scaling algorithm in which we move a fraction λ, where λ ∈ (0,2/3), of the step to the boundary of the feasible region.

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.K. Karmarkar, M.G.C. Resende and G. Veiga, An implementation of Karmarkar's algorithm for linear programming, Math. Progr. 44 (1989) 297–335. Errata in: Math. Progr. 50 (1991) 415.

    Article  Google Scholar 

  2. I. Adler and R.D.C. Monteiro, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Math. Progr. 50 (1991) 29–51.

    Article  Google Scholar 

  3. E.R. Barnes, A variation on Karmarkar's algorithm for solving linear programming problems, Math. Progr. 36 (1986) 174–182.

    Google Scholar 

  4. D.A. Bayer and J.C. Lagarias, The nonlinear geometry of linear programming, Part I: Affine and projective scaling trajectories, Trans. AMS 314 (1989) 499–526.

    Google Scholar 

  5. J. Birge and C. Rosa, A simplified proof of the convergence of the affine scaling, Research Report 91-7, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI (1991).

    Google Scholar 

  6. I.I. Dikin, Iterative solution of problems of linear and quadratic programming, Doklady Akademii Nauk SSSR, 174 (1967) 747–748. [Transl.: Sov. Math. Doklady 8 (1967) 674–675.]

    Google Scholar 

  7. I.I. Dikin, On the convergence of an iterative process, Upravlyaemye Sistemi 12 (1974) 54–60 (in Russian).

    Google Scholar 

  8. I.I. Dikin, The convergence of dual variables, Technical Report, Siberian Energy Institute, Irkutsk, Russia (December 1991).

    Google Scholar 

  9. I.I. Dikin, Determination of the interior point of one system of linear inequalities, Kibern. Syst. Anal. 1 (1992).

  10. I.I. Dikin and V.I. Zorkaltsev,Iterative Solutions of Mathematical Programming Problems (Nauka Novosibirsk, 1980).

  11. C.C. Gonzaga, Convergence of the large step primal affine-scaling algorithm for primal non-degenerate linear programs, Technical Report ES-230/90, Dept. of Systems Engineering and Computer Science, COPPE Federal University of Rio de Janeiro, 21941 Rio de Janeiro, RJ, Brazil (September 1990).

    Google Scholar 

  12. L.A. Hall and R.J. Vanderbei, Two-thirds is sharp for affine scaling, Technical Report SOR-92/9, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ 08544 (September 1992).

    Google Scholar 

  13. A.J. Hoffman, On approximate solutions of systems of linear inequalities, J. Res. National Bureau of Standards 49 (1952) 263–265.

    Google Scholar 

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

    Google Scholar 

  15. N.K. Karmarkar and R.G. Ramakrishnan, Further developments in the new polynomial-time algorithm for linear programming, Talk given at ORSA/TIMS National Meeting, Boston, MA (April 1985).

  16. N. Megiddo and M. Shub, Boundary behavior of interior point algorithms in linear programming, Math. Oper. Res. 14 (1989) 97–114.

    Google Scholar 

  17. C.L. Monma and A.J. Morton, Computational experience with the dual affine variant of Karmarkar's method for linear programming, Oper. Res. Lett. 6 (1987) 261–267.

    Article  Google Scholar 

  18. R. Saigal, A simplified proof of primal affine scaling method, Technical Report, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI, USA (1993).

    Google Scholar 

  19. P. Tseng and Z.Q. Luo, On the convergence of the affine-scaling algorithm, Math. Progr. 56 (1992) 301–319.

    Article  Google Scholar 

  20. T. Tsuchiya, Global convergence of the affine-scaling methods for degenerate linear programming problems, Math. Progr. 52 (1991) 377–404.

    Article  Google Scholar 

  21. T. Tsuchiya, Global convergence property of the affine scaling method for primal degenerate linear programming problems, Math. Oper. Res. 17 (1992) 527–557.

    Article  Google Scholar 

  22. T. Tsuchiya and M. Muramatsu, Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems, Research Memorandum 423, The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106, Japan (January 1992; revised September 1992).

    Google Scholar 

  23. R.J. Vanderbei and J.C. Lagarias, I.I. Dikin's convergence result for the affine-scaling algorithm, in:Mathematical Developments Arising from Linear Programming: Proc. Joint Summer Research Conf., Bowdoin College, Brunswick, Maine, USA, eds. J.C. Lagarias and M.J. Todd, Contemp. Math. 114 (1990) 109–119.

    Google Scholar 

  24. R.J. Vanderbei, M.S. Meketon and B.A. Freedman, A modification of Karmarkar's linear programming algorithm, Algorithmica 1 (1986) 395–407.

    Article  Google Scholar 

  25. 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: Proc. Joint Summer Research Conf., Bowdoin College, Brunswick, Maine, USA, eds. J.C. Lagarias and M.J. Todd, Contemp. Math. 114 (1990) 161–187.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Systems and Industrial Engineering, University of Arizona, 85721, Tucson, AZ, USA

    R. D. C. Monteiro

  2. The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-Ku, 106, Tokyo, Japan

    T. Tsuchiya

  3. Department of Systems and Industrial Engineering, University of Arizona, 85721, Tucson, AZ, USA

    Y. Wang

Authors
  1. R. D. C. Monteiro
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. T. Tsuchiya
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Y. Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported by the National Science Foundation (NSF) under Grant No. DDM-9109404 and the Overseas Research Scholars of the Ministry of Education, Science and Culture of Japan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Monteiro, R.D.C., Tsuchiya, T. & Wang, Y. A simplified global convergence proof of the affine scaling algorithm. Ann Oper Res 46, 443–482 (1993). https://doi.org/10.1007/BF02023109

Download citation

  • Issue Date:

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

Keywords

Search

Navigation