Abstract
In this paper we establish a basic theory for variable dimension algorithms which were originally developed for computing fixed points by Van der Laan and Talman. We introduce a new concept ‘primal—dual pair of subdivided manifolds’ and by utilizing it we propose a basic model which will serve as a foundation for constructing a wide class of variable dimension algorithms. Our basic model furnishes interpretations to several existing methods: Lemke's algorithm for the linear complementarity problem, its extension to the nonlinear complementarity problem, a variable dimension algorithm on conical subdivisions and Merrill's algorithm. We shall present a method for solving systems of equations as an application of the second method and an efficient implementation of the fourth method to which our interpretation leads us. A method for constructing triangulations with an arbitrary refinement factor of mesh size is also proposed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. Allgower and K. Georg, “Simplicial and continuation methods for approximating fixed points and solutions to systems of equations”,SIAM Review 22 (1980) 28–85.
R.W. Cottle and G.B. Dantzig, “Complementary pivot theory of mathematical programming”,Linear Algebra and Its Applications 1 (1968) 103–125.
G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, NJ, 1963).
B.C. Eaves, “A short course in solving equations with PL homotopies”,SIAM-AMS Proceedings 9 (1976) 73–143.
B.C. Eaves, “Homotopies for computation of fixed points”,Mathematical Programming 3 (1972) 1–22.
B.C. Eaves and R. Saigal, “Homotopies for computation of fixed points on unbounded regions”,Mathematical Programming 3 (1972) 225–237.
B.C. Eaves and H. Scarf, “The solution of systems of piecewise linear equations”,Mathematics of Operations Research 1 (1976) 1–27.
R. Freund, “Variable-dimension complexes with applications”, Ph.D. Dissertation, Stanford University (Stanford, CA, June 1980).
L. van der Heyden, “Restricted primitive sets in a regularly distributed list of vectors and simplicial subdivisions with arbitrary refinement factors”, Discussion Paper Series No. 79D, John Fitzgerald Kennedy School of Government, Harvard University (Cambridge, MA, January 1980).
M. Kojima, “Studies on piecewise-linear approximation of piecewise-C 1 mappings in fixed points and complementarity theory”,Mathematics of Operations Research 3 (1978) 17–36.
M. Kojima, “A note on ‘a new algorithm for computing fixed points’ by van der Laan and Talman”, in: W. Forster, ed.,Numerical solution on highly nonlinear problems (North-Holland, New York, 1980) pp. 37–42.
M. Kojima, “An introduction to variable dimension algorithms for solving systems of equations”, in: E.L. Allgower, K. Glashoff and H.-O. Peitgen, eds.,Numerical solution of nonlinear equations (Springer, Berlin, 1981) pp. 199–237.
G. van der Laan, “Simplicial fixed point algorithms”, Ph.D. Dissertation, Free University (Amsterdam, 1980).
G. van der Laan and A.J.J. Talman, “On the computation of fixed points in the product space of the unit simplices and an application to non cooperativen-person games”, Free University (Amsterdam, October 1978).
G. van der Laan and A.J.J. Talman, “A class of simplicial subdivisions for restart fixed point algorithms without an extra dimension”,Mathematical Programming 20 (1981) 33–48.
G. van der Laan and A.J.J. Talman, “Convergence and properties of recent variable dimension algorithms”, in: W. Forster, ed.,Numerical solution of highly nonlinear problems (North-Holland, New York, 1980) pp. 3–36.
G. van der Laan and A.J.J. Talman, “A restart algorithm for computing fixed points without extra dimension”,Mathematical Programming 17 (1979) 74–84.
G. van der Laan and A.J.J. Talman, “A restart algorithm without an artificial level for computing fixed points on unbounded regions”, in: H.-O. Peitgen and H.-O. Walther, eds.,Functional differential equations and approximation of fixed points, Lecture Notes in Mathematics 730 (Springer-Verlag, Berlin, 1979) pp. 247–256.
G. van der Laan and A.J.J. Talman, “A new subdivision for computing fixed points with a homotopy algorithm”, Free University (Amsterdam, February 1979).
C.E. Lemke and J.T. Howson Jr., “Equilibrium points of bimatrix games”,SIAM Journal on Applied Mathematics 12 (1964) 413–423.
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, University of Michigan (Ann Arbor, MI, 1972).
S. Mizuno, “A simplicial algorithm for finding all solutions to polynomial systems of equations”, Master Thesis, Department of System Sciences, Tokyo Institute of Technology (Tokyo, February 1981).
P.M. Reiser, “A modified integer labelling for complementarity algorithms”,Mathematics of Operations Research 6 (1981) 129–139.
C.P. Rourke and B.J. Sanderson,Introduction to piecewise-linear topology (Springer-Verlag, New York, 1972).
R. Saigal, “Fixed point computing methods”, in: A.G. Holzman, ed.,Operations research support methodology (Marcel Dekker, New York, 1979) pp. 545–566.
H. Scarf, “The approximation of fixed points of a continuous mapping”,SIAM Journal on Applied Mathematics 15 (1967) 1328–1343.
S. Shamir, “A homotopy fixed point algorithm with an arbitrary integer refinement factor”, Department of Engineering-Economic Systems, Stanford University (Stanford, CA, May 1979).
A.J.J. Talman, “Variable dimension fixed point algorithms and triangulations”, Ph.D. Dissertation, Free University (Amsterdam, 1980).
M.J. Todd,The computation of fixed points and applications (Springer-Verlag, New York, 1976).
M.J. Todd, “Exploiting structure in fixed-point computation”,Mathematical Programming 18 (1980) 233–247.
M.J. Todd, “Fixed-point algorithm that allow restarting without an extra dimension”, Technical Report No. 379, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, September 1978).
M.J. Todd, “Global and local convergence and monotonicity results for a recent variabledimension simplicial algorithm”, in: W. Forster, ed.,Numerical solution of highly nonlinear problems (North-Holland, New York, 1980) pp. 43–69.
M.J. Todd, “Traversing large large pieces of linearity in algorithms that solve equation by following piecewise-linear paths”,Mathematics of Operations Research 5 (1980) 242–257.
M.J. Todd and A.H. Wright, “A variable-dimension simplicial algorithm for antipodal fixedpoint theorems”,Numerical Functional Analysis and Optimization 2 (1980) 155–186.
A.H. Wright, “The octahedral algorithm, a new simplicial fixed point algorithm”,Mathematical Programming 21 (1981) 47–69.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kojima, M., Yamamoto, Y. Variable dimension algorithms: Basic theory, interpretations and extensions of some existing methods. Mathematical Programming 24, 177–215 (1982). https://doi.org/10.1007/BF01585103
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585103