Abstract
When we apply the affine scaling algorithm to a linear program, we usually construct an artificial linear program having an interior feasible solution from which the algorithm starts. The artificial linear program involves a positive number called the bigℳ. Theoretically, there exists anℳ * such that the original problem to be solved is equivalent to the artificial linear program ifℳ >ℳ *. Practically, however, such anℳ * is unknown and a safe estimate ofℳ is often too large. This paper proposes a method of updatingℳ to a suitable value during the iteration of the affine scaling algorithm. Asℳ becomes large, the method gives information on infeasibility of the original problem or its dual.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. Adler, N. Karmarkar, M. Resende and G. Veiga, “An implementation of Karmarkar's algorithm for linear programming,”Mathematical Programming 44 (1988) 297–335.
E.R. Barnes, “A variation on Karmarkar's algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182.
I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675.
I.I. Dikin, “On the speed of an iterative process,”Upravlyaemye Sistemi 12 (1974) 54–60.
I.I. Dikin, “The convergence of dual variables,” Technical Report, Siberian Energy Institute (Irkurtsk, Russia, 1991).
C.C Gonzaga, “Convergence of the large step primal affine-scaling algorithm for primal nondegenerate linear programs,” Department of Systems Engineering and Computer Sciences, COPPE-Federal University of Rio de Janeiro (Rio de Janeiro, Brazil, 1990).
N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
M. Kojima, S. Mizuno and A. Yoshise, “A primal-dual interior point algorithm for linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming, Interior-Point and Related Methods (Springer, New York, 1989) pp. 29–47.
M. Kojima, S. Mizuno and A. Yoshise, “A little theorem of the big ℳ in interior point algorithm,”Mathematical Programming 59 (1993) 361–375.
N. Megiddo, “Pathways to the optimal set in linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming, Interior-Point and Related Methods (Springer, New York, 1989) pp. 131–158.
T. Tsuchiya, “Global convergence of the affine scaling methods for degenerate linear programming problems,”Mathematical Programming 52 (1991) 377–404.
T. Tsuchiya and M. Muramatsu, “Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems,” Research Memorandum No. 423, The Institute of Statistical Mathematics (Minato-ku, Tokyo, Japan, 1992).
T. Tsuchiya and K. Tanabe, “Local convergence properties of new methods in linear programming,”Journal of the Operations Research Society of Japan 33 (1990) 22–45.
R.J. Vanderbei, “Affine-scaling for linear programs with free variables,”Mathematical Programming 43 (1989) 31–44.
R.J. Vanderbei and J.C. Lagarias, “I.I. Dikin's convergence results for the affine-scaling algorithm,” Preprints, AT&T Bell Laboratories (Murray Hill, NJ, 1988).
R.J. Vanderbei, M.S. Meketon and B.A. Freedman. “A modification of Karmarkar's linear programming algorithm”Algorithmica 1 (1986) 395–407.
Author information
Authors and Affiliations
Additional information
This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.
Supported by Grant-in-Aids for Co-Operative Research (03832017) of the Japan Ministry of Education, Science and Culture.
Rights and permissions
About this article
Cite this article
Ishihara, T., Kojima, M. On the bigℳ in the affine scaling algorithm. Mathematical Programming 62, 85–93 (1993). https://doi.org/10.1007/BF01585161
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585161