Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Affine Scaling Algorithm

  • Chapter
Interior Point Methods of Mathematical Programming

Part of the book series: Applied Optimization ((APOP,volume 5))

  • 732 Accesses

Abstract

The affine scaling algorithm is the first interior point algorithm in the world proposed by the Russian mathematician Dikin in 1967. The algorithm is simple and efficient, and is known as the first interior point algorithm which suggested that an interior point algorithm can outperform the existing simplex algorithm. The polynomiality status of the algorithm is still an open question, but a number of papers have revealed its deep and beautiful mathematical structures related to other interior point algorithms. In this paper we survey interesting convergence results on the affine scaling algorithm

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Adler, I., Karmarkar, N., Resende, M., and Veiga, G., “ Data structures and programming techniques for the implementation of Karmarkar’s algorithm,” ORSAJournal on Computing, Vol. 1, No. 2 (1989), pp. 84–106.

    MATH  Google Scholar 

  2. Adler, I., Resende, M., Veiga, G., and Karmarkar, N., “An implementation of Karmarkar’ s algorithm for linear programming,”Mathematical Programming, Vol. 44 (1989), pp. 297–335.

    Article  MathSciNet  MATH  Google Scholar 

  3. Adler, I., and Monteiro, R. D. C., “ Limiting behavior of the affine scaling continuous trajectories for linear programming problems,”Mathematical Programming, Vol. 50 (1990), pp. 29–51.

    Article  MathSciNet  Google Scholar 

  4. Alizadeh, F., “Interior point methods in semidefinite programming with applications to combinatorial optimization,”SIAM Journal on Optimization, Vol. 5 (1995), pp. 13–52

    Article  MathSciNet  MATH  Google Scholar 

  5. Amari, S.-I., “Differential-Geometrical Methods in Statistics”Lecture Notes in Statistics, Vol. 28, Springer-Verlag, Berlin, 1985.

    Google Scholar 

  6. Anstreicher, K., “Linear programming and the Newton barrier flow,”Mathematical Programming, Vol. 41 (1988), pp. 367–373.

    Article  MathSciNet  MATH  Google Scholar 

  7. Barnes, E. R., “A Variation on Karmarkar’ s algorithm for solving linear programming problems,”Mathematical Programming, Vol. 36 (1986), pp. 174–182.

    Article  MathSciNet  MATH  Google Scholar 

  8. Bayer, D. A., and Lagarias, J. C., “ The nonlinear geometry of linear programming, I. Affine and projective trajectories,”Transactions of the American Mathematical Society, Vol. 314, No. 2 (1989), pp. 499–526.

    MathSciNet  MATH  Google Scholar 

  9. Bayer, D. A., and Lagarias, J. C., “The nonlinear geometry of linear programming, II. Legendre transform coordinates and centeral trajectories,”Transactions of the American Mathematical Society, Vol. 314, No. 2 (1989), pp. 527–581.

    MathSciNet  MATH  Google Scholar 

  10. Cavalier, T. M., and Soyster, A. L., “Some computational experience and a modification of the Karmarkar algorithm,” The Pennsylvania State University, ISME Working Paper 85–105, 1985.

    Google Scholar 

  11. Cheng, Y.-C., Houck, D. J., Liu, J.-M., Meketon, M. S., Slutsman, L., Vanderbei, R. J., and Wang, P., “ The ATjadeT KORBX system,”ATjadeT Technical Journal, Vol. 68, No. 3 (1989), pp. 7–19.

    MathSciNet  Google Scholar 

  12. Dikin, I. I., “Iterative solution of problems of linear and Quadratic programming,”Soviet Mathematics Doklady, Vol. 8 (1967), pp. 674–675.

    MATH  Google Scholar 

  13. Dikin, I. I., “O skhodimosti odnogo iteratsionnogo protsessa ” (in Russian),Upravlyaemye Sistemy, Vol. 12 (1974), pp. 54–60

    Google Scholar 

  14. Dikin, I. I., “Letter to the editor,”Mathematical Programming, Vol. 41 (1988), pp. 393–394.

    Article  MathSciNet  Google Scholar 

  15. Dikin, I. I., “The convergence of dual variables,” Technical Report, Siberian Energy Institute, Irkutsk, Russia, December, 1991.

    Google Scholar 

  16. Dikin, I. I., “Determining the interior point of a system of linear inequalities,”Cybernetics and Systems Analysis, Vol. 28 (1992), pp. 54–67

    Article  MathSciNet  MATH  Google Scholar 

  17. Dikin, I. I., “Affine scaling methods for linear programming,” Research Memorandum No. 479, The Institute of Statistical Mathematics, Tokyo, Japan, June, 1993

    Google Scholar 

  18. Dikin, I. I., Private communication, 1993

    Google Scholar 

  19. Dikin, I.I., and Roos, C., “ Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case,” Report No. 94–69, Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, Netherlands, 1994

    Google Scholar 

  20. Dikin, I. I., and Zorkaltsev, V. I., “ Iterativnoe Reshenie Zadach Matematicheskogo Programmirovaniya (Algoritmy Metoda Vnutrennikh Tochek) ” (in Russian), Nauka, Novosibirsk, USSR, 1980

    Google Scholar 

  21. Gay, D., “Stopping tests that compute optimal solutions for interior-point linear programming algorithms,” Numerical Analysis Manuscript 89–11, ATjadeT Bell Laboratories, Murray Hill, NJ, USA, 1989

    Google Scholar 

  22. Gonzaga, C. C., “Conial projection algorithms for linear programming,”Mathematical Programming, Vol. 43 (1989), pp. 151–173

    Article  MathSciNet  MATH  Google Scholar 

  23. Gonzaga, C. C., “Convergence of the large step primal affine-scaling algorithm for primal non-degenerate linear programs,” Technical Report, Department of Systems Engineering and Computer Sciences, COPPE-Federal University of Rio de Janeiro, Brazil, 1990

    Google Scholar 

  24. Gonzaga, C. C., and Carlos, A., “ A primal affine-scaling algorithm for linearly constrained convex programs,” Technical Report ES-238/90, Department of Systems Engineering and Computer Science, COPPE-Federal University of Rio de Janeiro, Brazil, December 1990

    Google Scholar 

  25. Güler, O., den Hertog, D., Roos, C., Terlaky, T., and Tsuchiya, T., “Degeneracy in interior point methods for linear programming,”Annals of Operations Research, Vol. 47 (1993), pp. 107–138.

    Article  Google Scholar 

  26. Hall, L. A., and Vanderbei, R. J., “Two-thirds is sharp for affine scaling,”Operations Research Letters, Vol. 13 (1993), pp. 197–201

    Article  MathSciNet  MATH  Google Scholar 

  27. Ishihara, T., and Kojima, K., “On the bigM in the affine scaling algorithm,”Mathematical Programming, Vol. 62 (1993), pp. 85–94

    Article  MathSciNet  MATH  Google Scholar 

  28. Karmarkar, N., “A new polynomial-time algorithm for linear programming.”Combinatorica, Vol. 4, No. 4 (1984), pp. 373–395

    Article  MathSciNet  MATH  Google Scholar 

  29. Karmarkar, N., and Ramakrishnan, K., “ Further developments in the new polynomial-time algorithm for linear programming,” Talk given at ORSA/TIMS National Meeting, Boston, MA, USA, April, 1985.

    Google Scholar 

  30. Kortanek, K. O., and Shi, M., “Convergence results and numerical experiments on a linear programming hybrid algorithm,”European Journal of Operations Research, Vol. 32 (1987), pp. 47–61.

    Article  MathSciNet  MATH  Google Scholar 

  31. Mascarenhas, W. F., “The affine scaling algorithm fails for λ = 0.999.” Technical Report, Universidade Estadual de Campinas, Campinas S. P., Brazil, October, 1993

    Google Scholar 

  32. McShane, K. A., Monma, C. L., and Shanno, D. F., “An implementation of a primal-dual interior point method for linear programming,”ORSA Journal on Computing, Vol. 1 (1989), pp. 70–83

    MATH  Google Scholar 

  33. Megiddo, N., and Shub, M., “Boundary behavior of interior point algorithms for linear programming,”Mathematics of Operations Research, Vol. 14, No. 1 (1989), pp. 97–146.

    Article  MathSciNet  MATH  Google Scholar 

  34. Mehrotra, S., “Implementations of affine scaling methods: approximate solutions of system of linear equations using preconditioned conjugate gradient methods,” Technical Report, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208, USA, 1989

    Google Scholar 

  35. Monma, C. L., and Morton, A. J., “Computationalexperience with a dual affine variant of Karmarkar’s method for linear programming,”Operations Research Letters, Vol. 6 (1987), pp. 261–267.

    Article  MathSciNet  MATH  Google Scholar 

  36. Monteiro, R., and Tsuchiya, T., “Global convergence of the affine scaling algorithm for convex quadratic programming,” Research Memorandum, The Institute of Statistical Mathematics, Tokyo, Japan, March 1995

    Google Scholar 

  37. Monteiro, R., Tsuchiya, T., and Wang, Y., “A simplified global convergence proof of the affine scaling algorithm,”Annals of Operations Research, Vol. 47 (1993), pp. 443–482.

    Article  MathSciNet  Google Scholar 

  38. Monteiro, R., and Wang, Y., “Trust region affine scaling algorithms for linearly constrained convex and concave programs,” Manuscript, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA, 1995.

    Google Scholar 

  39. Muramatsu,M.,and Tsuchiya,T.,“Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm,” Manuscript, September 1995. (To appear inMathematical Programming. A revised version of “A convergence analysis of a long-step variant of the projective scaling algorithm,” Research Memorandum No.454, The Institute of Statistical Mathematics, Tokyo, Japan, October 1992.)

    Google Scholar 

  40. Muramatsu,M.,and Tsuchiya,T.,“Affine scaling method with an infeasible starting point,” Research Memorandum No. 490, The Institute of Statistica Mathematics, Tokyo, Japan, 1994.

    Google Scholar 

  41. Muramatsu, M., and Tsuchiya, T., “Affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption,” Manuscript, 1995. (To appear inAnnals of Operations Research.)

    Google Scholar 

  42. Nesterov, Yu., and Nemirovskiy, A., “Interior Point Polynomial Methods in Convex Programming,” SIAM Publications, Philadelphia, Pensnsylvania, USA, 1994.

    Google Scholar 

  43. Resende, M., Tsuchiya, T., and Veiga, G., “Identifying the optimal face of a network linear program with a globally convergent interior point method,” InLarge Scale Optimization: State of the Art (eds. W. W. Hager et al.), Kluwer Academic Publishers, Netherlands, 1994.

    Google Scholar 

  44. Resende, M., and Veiga, G., “An efficient implementation of a network interior point method,” Manuscript, ATjadeT Bell Laboratories, Murray Hill, NJ, USA, March, 1992.

    Google Scholar 

  45. Saigal, R., “A simple proof of primal affine scaling method,” Technical Report, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI48109–2117, USA, March, 1993. (To appear inAnnals of Opearations Research.)

    Google Scholar 

  46. Saigal, R., “ A three step quadratically convergent implementation of the primal affine scaling method,” Technical Report No.93–9, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI48109, USA, 1993.

    Google Scholar 

  47. Saigal, R., “The primal power affine scaling method,” Technical Report No.93–21, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI48109, USA, 1993. (To appear inAnnals of Opearations Research.)

    Google Scholar 

  48. Saigal, R.,“Linear Programming: A Modern Integrated Analysis,” Kluwer Academic Publishers, Netherlands, 1995.

    MATH  Google Scholar 

  49. Schrijver, A., “Theory of Linear and Integer Programming ” John Wiley&Sons, Chichester, England, 1986.

    MATH  Google Scholar 

  50. Sinha, L., Freedman, B., Karmarkar, N., Putcha, N., and Ramakrishnan, K., “Overseas network planning,”Proceedings of “the Third International Network Planning Sysmposium —Networks’ 86” (IEEE Communications Society, held on June 1–6, 1986, Tarpon Springs, Florida, USA ), pp. 121–124.

    Google Scholar 

  51. Sonnevend, G., “ An “ analytic centre” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming,”Lecture Notes in Control and Information Sciences, Springer-Verlag, New York, Vol. 84, pp. 866–876, 1985.

    Google Scholar 

  52. Stewart, G. W., “On scaled projections and pseudo inverses,”Linear Algebra and its Applications, Vol. 112 (1989), pp. 189–193.

    Article  MathSciNet  MATH  Google Scholar 

  53. Sun, J., “A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions,”Mathematical Programming, Vol. 60 (1993), pp. 69–79.

    Article  MathSciNet  MATH  Google Scholar 

  54. Tanabe, K., “Center flattening transformation and a centered Newton method for linear programming,” Manuscript presented at MP seminar, the Operations Research Society of Japan, July, 1987.

    Google Scholar 

  55. Tanabe, K., “Differential geometry of Optimization” (in Japanese),Preliminary issue of the Bulletin of the Japan Society for Industrial and Applied Mathematics, No. 3 (1990), pp. 39–50.

    Google Scholar 

  56. Tanabe, K., and Tsuchiya, T., “New geometry of linear programming” (in Japanese),Mathematical Science, No. 303 (1988), pp. 32–37.

    Google Scholar 

  57. Terlaky, T., and Tsuchiya, T., “A note on Mascarenhas’ counter-example about global convergence of the affine scaling algorithm,” Manuscript, March, 1996.

    Google Scholar 

  58. Todd, M. J., “A Dantzig-Wolfe-like variant of Karmarkar’s interior point method for linear programming,”Operations Research, Vol. 38 (1990), pp. 1006–1018.

    Article  MathSciNet  MATH  Google Scholar 

  59. Tseng, P., and Luo., Z.-Q., “On the convergence of the affine-scaling algorithm,”Mathematical Programming, Vol. 56 (1992), pp. 301–319.

    Article  MathSciNet  MATH  Google Scholar 

  60. Tsuchiya, T., “ On Yamashita’s method and Freund’ s method for linear programming” (in Japanese), Cooperative Research Report of the Institute of Statistical Mathematics, Vol. 10 (1988), pp. 105–115.

    Google Scholar 

  61. Tsuchiya, T., “Dual standard form linear programming problems and Karmarkar’ s canonical form” (in Japanese), Lecture Note of the Research Institute of Mathematical Sciences, Vol. 676 (1988), pp. 330–336.

    Google Scholar 

  62. Tsuchiya, T., “Global convergence of the affine scaling method for degenerate linear programming problems,”Mathematical Programming, Vol. 52 (1991), pp. 377–404.

    Article  MathSciNet  MATH  Google Scholar 

  63. Tsuchiya, T., “Global convergence property of the affine scaling method for primal degenerate linear programming problems,”Mathematics of Operations Research, Vol. 17, No. 3 (1992), pp. 527–557.

    Article  MathSciNet  MATH  Google Scholar 

  64. Tsuchiya, T., and Monteiro, R. D. C., “Superlinear convergence of the affine scaling algorithm.” Technical Report, CRPC-92288, Center for Research on Parallel Computation, Rice University, Houston, USA, November, 1992. (To appear inMathematical Programming

    Google Scholar 

  65. Tsuchiya, T., and Muramatsu, M., “Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems,”SIAM Journal on Optimization, Vol. 5, No. 3 (1995), pp. 525–551.

    Article  MathSciNet  MATH  Google Scholar 

  66. Tsuchiya, T., and Tanabe, K., “C,”The Journal of the Operations Research Society of Japan, Vol. 33, No. 1 (1990), pp. 22–45.

    MathSciNet  MATH  Google Scholar 

  67. Vanderbei, R. J., and Lagarias, J. C., “I. I. Dikin’ s convergence result for the affine-scaling algorithm,”Contemporary Mathematics, Vol. 114 (1990), pp. 109–119.

    MathSciNet  Google Scholar 

  68. Vanderbei, R. J., Meketon, M. S., and Freedman, B. A., “A modification of Karmarkar’ s linear programming algorithm,” Algorithmica, Vol. 1 (1986), pp. 395–407.

    MathSciNet  MATH  Google Scholar 

  69. Vavasis, S. T., and Ye, Y., “A primal-dual accelerated interior point method whose running time depends only on A,” Technical Report, Department of Computer Science, Cornell University, December, 1994.

    Google Scholar 

  70. Wang, Y.,and Monteiro, R.,“Nondegeneracy of polyhedra and linear programs,” Manuscript,School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA, 1994. (To appear inComputational Optimization and Applications.)

    Google Scholar 

  71. Witzgall, C., Boggs, P. T., and Domich, P. D., “On the convergence behavior of trajectories for linear programming,”Contemporary Mathematics, Vol. 114 (1990), pp. 161–187.

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Prediction and Control, The Institute of Statistical Mathematics, 4–6–7 Minami-Azabu, Minato-ku, Japan, Tokyo, 106

    Takashi Tsuchiya

Authors
  1. Takashi Tsuchiya
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Delft University of Technology, The Netherlands

    Tamás Terlaky

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Kluwer Academic Publishers

About this chapter

Cite this chapter

Tsuchiya, T. (1996). Affine Scaling Algorithm. In: Terlaky, T. (eds) Interior Point Methods of Mathematical Programming. Applied Optimization, vol 5. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-3449-1_2

Download citation

  • DOI: https://doi.org/10.1007/978-1-4613-3449-1_2

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-1-4613-3451-4

  • Online ISBN: 978-1-4613-3449-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation