Simplicial fixed point algorithm with 2d integer labels

M.N. Matveev

Moscow Institute of Physics and Technology, Dolgoprudny, 141701 Russia

E-mail:  miklem@mail.mipt.ru

Received September 17, 2018


Full text PDF

DOI: 10.26907/2541-7746.2019.1.127-144

For citation: Matveev M.N. Simplicial fixed point algorithm with 2d integer labels. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2019, vol. 161, no. 1, p. 127-144. doi: 10.26907/2541-7746.2019.1.127-144.

Abstract

Simplicial fixed point algorithms can be based on either integer or vector labels. An apparent advantage of the algorithms with integer labels is their simplicity and stability under round-off errors due to the discrete nature of integer labels. At the same time, the application of all existing algorithms with integer labels is limited by some rigidness of their construction, in particular, in the d-dimensional space they can bear only from d+1 to 2d labels. The numbers of labels comparable with the dimension of space make these algorithms not very fast, especially in high-dimensional tasks. This paper overcomes this rigidness and builds a new simplicial fixed point algorithm with 2d integer labels. To achieve this goal, the paper proves new properties of triangulation K1 and separates all approximations of fixed points into weak and strong ones. This separation, which has never been used until this moment, is caused by the high number of labels of the new algorithm.

Key words: triangulations, polytopes, fans, simplicial algorithms, fixed point algorithms

References

1. Scarf H. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math., 1967, vol. 15, no. 5, pp. 1328–1343. doi: 10.1137/0115116.

2. Scarf H. The core of an  person game. Econometrica, 1967, vol. 35, no. 1, pp. 50–69. doi: 10.2307/1909383.

3. Scarf H. On the computation of equilibrium prices. In: Ten Economic Studies in the Tradition of Irving Fisher. New York, Sydney, John Wiley and Sons, 1967, pp. 207–230.

4. Hansen T., Scarf H.  On the applications of a recent combinatorial algorithm: Cowles Foundation Discussion Papers No. 272. New Haven, Cowles Found. Res. Econ., Yale Univ., 1969. 43 p.

5. Hansen T., Scarf H. On the applications of a recent combinatorial algorithm. In: Mityagin B.S. (Ed.) Matematicheskaya ekonomika: Ravnovesnye modeli, optimizatsionnoe planirovanie i upravlenie [Mathematical Economics: Equilibrium Models, Optimization Planning, and Control]. Moscow, Mir, 1974, pp. 143–169. (In Russian)

6. Cohen D.I.A. On the Sperner lemma. J. Comb. Theory, 1967, vol. 2, pp. 585–587.

7. Sperner E. Neuer beweis fr die invarianz der dimensionszahl und des gebietes. Abh. math. Seminar Univ. Hamburg, 1928, Bd. 6, S. 265–272. (In German)

8. Kuhn H.W. Simplicial approximation of fixed points. Proc. Natl. Acad. Sci. U. S. A., 1968, vol. 61, no. 4, pp. 1238–1242. doi: 10.1073/pnas.61.4.1238.

9. Todd M.J. The computation of fixed points and applications. Lect. Notes Econ. Math. Syst., 1976, vol. 124. vii, 129 p.

10. Todd M.J. Vychislenie nepodvizhnykh tochek i prilozheniya k ekonomike [The Computation of Fixed Points and Applications]. Moscow, Nauka, 1983. 112 p. (In Russian)

11. Yang Z. Computing Equilibria and Fixed Points. Boston, Kluwer Acad. Publ., 1999. x, 344 p.

12. Yamamoto Y. A variable dimension fixed point algorithm and the orientation of simplices. Math. Program., 1984, vol. 30, no. 3, pp. 301–312. doi: 10.1007/BF02591935.

13. Kojima M., Yamamoto Y. A unified approach to the implementation of several restart fixed point algorithms and a new variable dimension algorithm. Math. Program., 1984, vol. 28, pp. 288–328. doi: 10.1007/BF02612336.

14. Talman A.J.J., Yamamoto Y. A simplicial algorithm for stationary point problems on polytopes. Math. Oper. Res., 1989, vol. 14, no. 3, pp. 383–399. doi: 10.1287/moor.14.3.383.

15. Wright A.H. The octahedral algorithm, a new simplicial fixed point algorithm. Math. Program., 1981, vol. 21, no. 1, pp. 47–69. doi: 10.1007/BF01584229.

16. van der Laan G., Talman A.J.J. A class of simplicial restart fixed point algorithms without an extra dimension. Math. Program., 1981, vol. 20, no. 1, pp. 33–48. doi: 10.1007/BF01589331.

17. Reiser P.M. A modified integer labeling for complementarity algorithms. Math. Oper. Res., 1981, vol. 6, no. 1, pp. 129–139. doi: 10.1287/moor.6.1.129.

18. Matveev M.N. An approximation of fixed points with integer labels. Proc. 18th IFAC World Congress (Milano), 2011, pp. 10174–10179.

19. Freudenthal H. Simplizialzerlegungen von Beschrnkter flachheit. Ann. Math., 1942, vol. 43, pp. 580–582. (In German)

20. Matveev M.N. Invisible faces and face polytopes. Tr. MFTI, 2011, vol. 3, no. 1, pp. 102–106. (In Russian)

21. Matveev M.N. A minimal nonpolytopal fan. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2012, vol. 154, no. 1. pp. 202–207. (In Russian)

22. Brndsted A. An introduction to convex polytopes. In: Graduate Texts in Mathematics, 1983, vol. 90. viii, 162 p.

23. Freudenthal H. Die Triangulation der differenzierbaren Mannigfaltigkeiten. Proc. Konink. Acad. Wetensch. Amsterdam, 1939, vol. 42, pp. 880–901. (In German)

24. Freudenthal H. Eine Simplizialzerlegung des Cartesischen Produktes zweier Simplexe. Fundam. Math., 1937, vol. 29, pp. 138–144. (In German)

25. Lefschetz S. Introduction to Topology. Princeton, Princeton Univ. Press, 1949. 228 p.

26. Kuhn H.W. Some combinatorial lemmas in topology. IBM J. Res. Dev., 1960, vol. 4, no. 5, pp. 518–524. doi: 10.1147/rd.45.0518.

27. Shapley L.S. On balanced games without side payments. In: Hu T.C., Robinson S.M. (Eds.) Mathematical Programming, New York, Acad. Press, 1972. pp. 261–290.

28. Scarf H., Hansen T. The Computation of Economic Equilibria. Monograph 24, Cowles Foundation for Research in Economics. New Haven and London, Yale Univ. Press, 1973. x, 249 p.


The content is available under the license Creative Commons Attribution 4.0 License.