Simplicial fixed point algorithm with $2^d$ integer labels

M. N. Matveev

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 161 (2019) no. 1, pp. 127-144

Résumé

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 $2^d$ integer labels. To achieve this goal, the paper proves new properties of triangulation $K_1$ 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.

Détail

Mots-clés : triangulations, fans
Keywords: polytopes, simplicial algorithms, fixed point algorithms.

Bibliographie

[1] Scarf H., “The approximation of fixed points of a continuous mapping”, SIAM J. Appl. Math., 15:5 (1967), 1328–1343 | DOI | MR | Zbl

[2] Scarf H., “The core of an $N$ person game”, Econometrica, 35:1 (1967), 50–69 | DOI | MR | Zbl

[3] Scarf H., “On the computation of equilibrium prices”, Ten Economic Studies in the Tradition of Irving Fisher, John Wiley and Sons, N. Y.–Sydney, 1967, 207–230

[4] Hansen T., Scarf H., On the applications of a recent combinatorial algorithm, Cowles Foundation Discussion Papers, No 272, Cowles Foundation for Research in Economics, Yale University, New Haven, 1969, 43 pp. | MR

[5] Hansen T., Scarf H., “On the applications of a recent combinatorial algorithm”, Mathematical Economics: Equilibrium Models, Optimization Planning, and Control, ed. Mityagin B. S., Mir, M., 1974, 143–169 (In Russian)

[6] Cohen D. I. A., “On the Sperner lemma”, J. Comb. Theory, 2 (1967), 585–587 | DOI | MR | Zbl

[7] Sperner E., “Neuer beweis für die invarianz der dimensionszahl und des gebietes”, Abh. math. Seminar Univ. Hamburg, v. 6, 1928, 265–272 | DOI | MR | Zbl

[8] Kuhn H. W., “Simplicial approximation of fixed points”, Proc. Natl. Acad. Sci. U. S. A., 61:4 (1968), 1238–1242 | DOI | MR | Zbl

[9] Todd M. J., The computation of fixed points and applications, Lecture Notes in Economics and Mathematical Systems, 124, 1976, vii+129 pp. | DOI | MR | Zbl

[10] Todd M. J., The Computation of Fixed Points and Applications, Nauka, M., 1983, 112 pp. (In Russian)

[11] Yang Z., Computing equilibria and fixed points, Kluwer Acad. Publ, Boston, 1999, x+344 pp. | MR | Zbl

[12] Yamamoto Y., “A variable dimension fixed point algorithm and the orientation of simplices”, Math. Program., 30:3 (1984), 301–312 | DOI | MR | Zbl

[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., 28 (1984), 288–328 | DOI | MR | Zbl

[14] Talman A. J. J., Yamamoto Y., “A simplicial algorithm for stationary point problems on polytopes”, Math. Oper. Res., 14:3 (1989), 383–399 | DOI | MR | Zbl

[15] Wright A. H., “The octahedral algorithm, a new simplicial fixed point algorithm”, Math. Program., 21:1 (1981), 47–69 | DOI | MR | Zbl

[16] van der Laan G., Talman A. J. J., “A class of simplicial restart fixed point algorithms without an extra dimension”, Math. Program., 20:1 (1981), 33–48 | DOI | MR | Zbl

[17] Reiser P. M., “A modified integer labeling for complementarity algorithms”, Math. Oper. Res., 6:1 (1981), 129–139 | DOI | MR | Zbl

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

[19] Freudenthal H., “Simplizialzerlegungen von Beschränkter Flachheit”, Ann. Math., 43 (1942), 580–582 (In German) | DOI | MR | Zbl

[20] Matveev M. N., “Invisible faces and face polytopes”, Tr. MFTI, 3:1 (2011), 102–106 (In Russian) | MR

[21] Matveev M. N., “A minimal nonpolytopal fan”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 154, no. 1, 2012, 202–207 (In Russian) | MR

[22] Brøndsted A., An introduction to convex polytopes, Graduate Texts in Mathematics, 90, 1983, viii+162 pp. | MR

[23] Freudenthal H., “Die Triangulation der differenzierbaren Mannigfaltigkeiten”, Proc. Konink. Acad. Wetensch. Amsterdam, 42 (1939), 880–901 (In German) | MR

[24] Freudenthal H., “Eine Simplizialzerlegung des Cartesischen Produktes zweier Simplexe”, Fund. Math., 29 (1937), 138–144 (In German)

[25] Lefschetz S., Introduction to topology, Princeton Univ. Press, Princeton, 1949, 228 pp. | MR | Zbl

[26] Kuhn H. W., “Some combinatorial lemmas in topology”, IBM J. Research and Development, 4:5 (1960), 518–524 | DOI | MR | Zbl

[27] Shapley L. S., “On balanced games without side payments”, Mathematical Programming, eds. Hu T. C., Robinson S. M., Acad. Press, N. Y., 1972, 261–290 | MR

[28] Scarf H., Hansen T., The computation of economic equilibria, Cowles Foundation for Research in Economics, 24, Yale Univ. Press, New Haven–London, 1973, x+249 pp. | MR | Zbl