Abstract
Complementary pivot algorithms known at the present time fall into several quite general categories, with obvious similarities. This paper deals with general pivoting systems which provide a natural setting for the study of complementary pivot algorithms. A generalized algorithm is presented for these systems. We give results on the number of iterations necessary for such an algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. Adler, “Abstract polytopes”, Ph.D. Thesis, Department of Operations Research, Stanford University, Stanford, Calif. (1971).
I. Adler, “The Euler characteristic of abstract polytopes”, Tech. Rept. No. 71-11, Department of Operations Research, Stanford University, Stanford, Calif. (August 1971).
I. Adler and G.B. Dantzig, “Maximum diameter of abstract polytopes”, Tech. Rept. No. 71-12. Department of Operations Research, Stanford University, Stanford, Calif. (August 1971).
M. Bhezad and G. Chartrand,Introduction to the theory of graphs (Allyn and Bacon, Rockleigh, N.J., 1971).
R.W. Cottle and G.B. Dantzig, “A generalization of the linear complementarity problem”,Journal of Combinatorial Theory 8 (1) (1970).
G.B. Dantzig and R.W. Cottle, “Positive (semi-) definite programming”, in:Nonlinear programming Ed. J. Abadie (North-Holland, Amsterdam, 1967).
B.C. Eaves, “The linear complementarity problem in mathematical programming”, Tech. Rept. No. 69-4, Department of Operations Research, Stanford University, Stanford, Calif. (July 1969).
B.C. Eaves, “Computing Kakutani fixed points”,Journal of the Society for Industrial and Applied Mathematics 21 (2) (1971).
B.C. Eaves and R. Saigal, “Homotopies for computation of fixed points on unbounded regions”,Mathematical Programming 3 (2) (1972) 225–237.
T. Hansen and H. Scarf, “On the applications of a recent combinatorial algorithm”, Cowles Foundation Discussion Paper No. 272, Yale University, New Haven, Conn. (1969).
H.W. Kuhn, “Approximate search for fixed points”, in:Computing methods in optimization problems 2 (Academic Press, New York, 1969).
C.E. Lemke, “Bimatrix equilibrium points and mathematical programming”,Management Science 11 (7) (1965).
C.E. Lemke, “On complementary pivot theory”, in:Mathematics of the decision sciences, Part I, Eds. G.B. Dantzig and A.F. Veinott, Jr. (A.M.S., Providence, R.I., 1968).
C.E. Lemke, “Recent results on complementarity problems”, in:Nonlinear programming (Academic Press, New York, 1970).
C.E. Lemke and J.T. Howson, Jr., “Equilibrium points of bimatrix games”,Journal of the Society for Industrial and Applied Mathematics 12 (2) (1964).
O.H. Merrill, “Applications and extensions of an algorithm that computes fixed points of certain upper semi-continuous point to set mappings”, Ph.D. Dissertation, The University of Michigan, Ann. Arbor, Mich. (1972).
H. Scarf,The computation of economic equilibria (Yale University Press, New Haven, Conn.), to appear.
M.J. Todd, “Abstract complementary pivot theory”, Tech. Rept. No. 61, Dept. of Administrative Sciences, Yale University, New Haven, Conn. (October 1972).
Author information
Authors and Affiliations
Additional information
This paper is based on the author's doctoral dissertation for the Department of Administrative Sciences, Yale University. The author would like to thank his advisors, Professors G.H. Bradley, D. Brown and N. White. This research was supported in part by National Science Foundation grants GK-13757 and GP-32158X.
Rights and permissions
About this article
Cite this article
Todd, M.J. A generalized complementary pivoting algorithm. Mathematical Programming 6, 243–263 (1974). https://doi.org/10.1007/BF01580244
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580244