Симплициальный алгоритм поиска неподвижных точек с 2d целочисленными метками
М.Н. Матвеев
Московский физико-технический институт, г. Долгопрудный, 141701, Россия
Полный текст PDF
DOI: 10.26907/2541-7746.2019.1.127-144
Для цитирования: Матвеев М.Н. Симплициальный алгоритм поиска неподвижных точек с 2d целочисленными метками // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2019. – Т. 161, кн. 1. – С. 127–144. – 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, pp. 127–144. doi: 10.26907/2541-7746.2019.1.127-144. (In Russian)
Аннотация
Симплициальные алгоритмы, применяемые для поиска неподвижных точек непрерывных функций, могут использовать или векторные, или целочисленные метки. Алгоритмы с целочисленными метками являются более простыми и в силу дискретности целочисленных меток устойчивыми к ошибкам округления. Однако вычислительная эффективность существующих алгоритмов с целочисленными метками ограничивается недостаточной гибкостью их конструкции, в частности, в пространстве Rd эти алгоритмы могут использовать только от d +1 до d меток. Не более чем сопоставимое с размерностью пространства количество меток делает алгоритмы с целочисленными метками недостаточно быстрыми, особенно в задачах большой размерности. Настоящая работа преодолевает эту трудность и представляет новый симплициальный алгоритм поиска неподвижных точек с 2d целочисленными метками.
Ключевые слова: триангуляции, многогранники, вееры, симплициальные алгоритмы, алгоритмы поиска неподвижных точек
Литература
1. Scarf H. The approximation of fixed points of a continuous mapping // SIAM J. Appl. Math. – 1967. – V. 15, No 5. – P. 1328–1343. – doi: 10.1137/0115116.
2. Scarf H. The core of an person game // Econometrica. – 1967. – V. 35, No 1. – P. 50–69. – doi: 10.2307/1909383.
3. Scarf H. On the computation of equilibrium prices // Ten Economic Studies in the Tradition of Irving Fisher. – N. Y., Sydney: John Wiley and Sons, 1967. – P. 207–230.
4. Hansen T., Scarf H. On the applications of a recent combinatorial algorithm: Cowles Foundation Discussion Papers No. 272. – New Haven: Cowles Foundation for Research in Economics, Yale University, 1969. – 43 p.
5. Хансен Т., Скарф Г. О приложениях нового комбинаторного алгоритма // Математическая экономика: Равновесные модели, оптимизационное планирование и управление / Ред. Б.С. Митягин. – М.: Мир, 1974. – С. 143–169.
6. Cohen D.I.A. On the Sperner lemma // J. Comb. Theory. – 1967. – V. 2. – P. 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.
8. Kuhn H.W. Simplicial approximation of fixed points // Proc. Natl. Acad. Sci. U. S. A. – 1968. – V. 61, No 4. – P. 1238–1242. – doi: 10.1073/pnas.61.4.1238.
9. Todd M.J. The computation of fixed points and applications // Lecture Notes in Economics and Mathematical Systems. – 1976. – V. 124. – vii, 129 p.
10. Тодд М.Дж. Вычисление неподвижных точек и приложения к экономике. – М.: Наука, 1983. – 112 c.
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. – V. 30, No 3. – P. 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. – V. 28. – P. 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. – V. 14, No 3. – P. 383–399. – doi: 10.1287/moor.14.3.383.
15. Wright A.H. The octahedral algorithm, a new simplicial fixed point algorithm // Mathematical Programming. – 1981. – V. 21, No 1. – P. 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. – V. 20, No 1. – P. 33–48. – doi: 10.1007/BF01589331.
17. Reiser P.M. A modified integer labeling for complementarity algorithms // Math. Oper. Res. – 1981. – V. 6, No 1. – P. 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. – P. 10174–10179.
19. Freudenthal H. Simplizialzerlegungen von Beschrnkter Flachheit // Ann. Math. – 1942. – V. 43. – P. 580–582.
20. Матвеев М.Н. Невидимые гиперграни и порождающие многогранники // Труды МФТИ. – 2011. – T. 3, № 1. – С. 102–106.
21. Матвеев М.Н. Минимальный непорождаемый веер // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2012. – T. 154, кн 1. – С. 202–207.
22. Бренстед А. Введение в теорию выпуклых многогранников. – М.: Мир, 1988. – 240 c.
23. Freudenthal H. Die Triangulation der differenzierbaren Mannigfaltigkeiten // Proc. Konink. Acad. Wetensch. Amsterdam. – 1939. – V. 42. – P. 880–901.
24. Freudenthal H. Eine Simplizialzerlegung des Cartesischen Produktes zweier Simplexe // Fund. Math. – 1937. – V. 29. – P. 138–144.
25. Lefschetz S. Introduction to topology. – Princeton: Princeton Univ. Press, 1949. – 228 p.
26. Kuhn H.W. Some combinatorial lemmas in topology // IBM J. Research and Development. – 1960. – V. 4, No 5. – P. 518–524. – doi: 10.1147/rd.45.0518.
27. Shapley L.S. On balanced games without side payments // Hu T.C., Robinson S.M. (Eds.) Mathematical Programming. – N. Y.: Acad. Press, 1972. – P. 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.
Поступила в редакцию
17.09.18
Матвеев Михаил Николаевич, кандидат физико-математических наук, доцент кафедры высшей математики
Московский физико-технический институт
Институтский пер., д. 9, г. Долгопрудный, Московская обл., 141701, Россия
E-mail: miklem@mail.mipt.ru
Контент доступен под лицензией Creative Commons Attribution 4.0 License.
