×
Kojima, Masakazu; Yamamoto, Yoshitsugu

Variable dimension algorithms: Basic theory, interpretations and extensions of some existing methods. (English) Zbl 0509.90070

Math. Program. 24, 177-215 (1982).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0509.90070

Cited in 1 Review
Cited in 20 Documents

MSC:

90C30 Nonlinear programming
65H10 Numerical computation of solutions to systems of equations
54H25 Fixed-point and coincidence theorems (topological aspects)
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)

Keywords:

triangulations; solutions to nonlinear equations; variable dimension algorithms; Lemke’s algorithm; Merrill’s algorithm; Van der Laan and Talman’s algorithm; primal-dual pair of subdivided manifolds; fixed point algorithm; unification of algorithms

Citations:

Zbl 0261.00016; Zbl 0267.90100; Zbl 0277.90092; Zbl 0289.90035
PDF BibTeX XML Cite
\textit{M. Kojima} and \textit{Y. Yamamoto}, Math. Program. 24, 177--215 (1982; Zbl 0509.90070)
Full Text: DOI

References:

[1] 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. · Zbl 0432.65027
[2] R.W. Cottle and G.B. Dantzig, ”Complementary pivot theory of mathematical programming”,Linear Algebra and Its Applications 1 (1968) 103–125. · Zbl 0155.28403
[3] G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, NJ, 1963).
[4] B.C. Eaves, ”A short course in solving equations with PL homotopies”,SIAM-AMS Proceedings 9 (1976) 73–143. · Zbl 0343.47048
[5] B.C. Eaves, ”Homotopies for computation of fixed points”,Mathematical Programming 3 (1972) 1–22. · Zbl 0276.55004
[6] B.C. Eaves and R. Saigal, ”Homotopies for computation of fixed points on unbounded regions”,Mathematical Programming 3 (1972) 225–237. · Zbl 0258.65060
[7] B.C. Eaves and H. Scarf, ”The solution of systems of piecewise linear equations”,Mathematics of Operations Research 1 (1976) 1–27. · Zbl 0458.65056
[8] R. Freund, ”Variable-dimension complexes with applications”, Ph.D. Dissertation, Stanford University (Stanford, CA, June 1980).
[9] 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).
[10] 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. · Zbl 0396.41012
[11] 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. · Zbl 0449.65020
[12] 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. · Zbl 0471.65030
[13] G. van der Laan, ”Simplicial fixed point algorithms”, Ph.D. Dissertation, Free University (Amsterdam, 1980). · Zbl 0464.90046
[14] 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).
[15] 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. · Zbl 0441.90112
[16] 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.
[17] 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. · Zbl 0411.90061
[18] 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. · Zbl 0447.65019
[19] 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). · Zbl 0411.90061
[20] C.E. Lemke and J.T. Howson Jr., ”Equilibrium points of bimatrix games”,SIAM Journal on Applied Mathematics 12 (1964) 413–423. · Zbl 0128.14804
[21] 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).
[22] 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).
[23] P.M. Reiser, ”A modified integer labelling for complementarity algorithms”,Mathematics of Operations Research 6 (1981) 129–139. · Zbl 0496.90077
[24] C.P. Rourke and B.J. Sanderson,Introduction to piecewise-linear topology (Springer-Verlag, New York, 1972). · Zbl 0254.57010
[25] R. Saigal, ”Fixed point computing methods”, in: A.G. Holzman, ed.,Operations research support methodology (Marcel Dekker, New York, 1979) pp. 545–566.
[26] H. Scarf, ”The approximation of fixed points of a continuous mapping”,SIAM Journal on Applied Mathematics 15 (1967) 1328–1343. · Zbl 0153.49401
[27] S. Shamir, ”A homotopy fixed point algorithm with an arbitrary integer refinement factor”, Department of Engineering-Economic Systems, Stanford University (Stanford, CA, May 1979).
[28] A.J.J. Talman, ”Variable dimension fixed point algorithms and triangulations”, Ph.D. Dissertation, Free University (Amsterdam, 1980). · Zbl 0464.90047
[29] M.J. Todd,The computation of fixed points and applications (Springer-Verlag, New York, 1976). · Zbl 0332.54003
[30] M.J. Todd, ”Exploiting structure in fixed-point computation”,Mathematical Programming 18 (1980) 233–247. · Zbl 0433.90088
[31] 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).
[32] 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.
[33] 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. · Zbl 0441.90111
[34] 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. · Zbl 0456.65024
[35] A.H. Wright, ”The octahedral algorithm, a new simplicial fixed point algorithm”,Mathematical Programming 21 (1981) 47–69. · Zbl 0475.65029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.