В.И. Шмырев. Полиэдральная комплементарность на симплексе. Метод встречных путей для убывающих квазирегулярных отображений ... C. 273-286

УДК 519.865.3

MSC: 90C33, 90-08

DOI: 10.21538/0134-4889-2019-25-2-273-286

Работа выполнена при поддержке РФФИ (проект№ 19-010-00910 А), целевой программы Президиума РАН (проект № 227) и междисциплинарного интеграционного проекта СО РАН (проект № 7Б).

В работе исследуется математическая первооснова оригинального подхода полиэдральной комплементарности, предложенного автором для отыскания экономического равновесия в моделях обмена и различных их вариаций. Проблема  равновесия сводится к отысканию неподвижной точки точечно-множественных отображений симплекса цен в себя. Это приводит к задаче полиэдральной комплементарности, порождаемой парой полиэдральных комплексов в двойственности. Рассматривается новый класс убывающих отображений, не имеющих аналогов в $\mathbb{R}^n,$ - класс квазирегулярных  отображений.  Исследуется  процедура встречных путей, которая обобщает известный метод Лемке для задач линейной комплементарности. Показано, что в рассматриваемом случае процедура обладает свойством монотонности, характерным для задач линейной комплементарности с положительными главными минорами матрицы ограничений (Р-класс). Следствием монотонности является единственность искомого решения.

Ключевые слова: cимплекс,полиэдральный комплекс, комплементарность, монотонность, неподвижная точка, алгоритм

СПИСОК ЛИТЕРАТУРЫ

1.   Шмырев В.И. Об отыскании неподвижных точек кусочно-постоянных монотонных отображений в $\mathbb{R}^n$ // Докл. АН СССР. 1981. Т. 259, No. 2. С. 299–301.

2.   Шмырев В.И. Задача полиэдральной комплементарности // Оптимизация: cб. науч. тр. / Ин-т математики СО АН СССР. Новосибирск, 1988. Вып. 44(61). С. 82–95.

3.   Шмырев В.И. Полиэдральная комплементарность на симплексе. Потенциальность регулярных отображений// Сиб. журн. индустр. математики. 2018. Т. 21, № 1(73). С. 118–128. doi: 10.17377/SIBJIM.2018.21.111 

4.   Шмырев В.И. Полиэдральная комплементарность на симплексе: отыскание неподвижных точек убывающих регулярных отображений // Дискрет. анализ и исслед. операций. 2019. Т. 26, № 1. С. 94–114. doi: 10.33048/daio.2019.26.598 

5.   Lemke C.E. Bimatrix equilibrium points and mathematical programming // Managment Sience. 1965. Vol. 11, no. 7. P. 681–689. doi: 10.1287/mnsc.11.7.681 

6.   Шмырев В.И. Алгоритм поиска равновесия в линейной модели обмена // Сиб. мат. журн. 1985. Т.  26, № 2. С. 162–175.

7.   Eisenberg E., Gale D. Consensus of subjective probabilities: The pari-mutuel method // Ann. Math. Statist. 1959. Vol. 30, no. 1. P. 165–168. doi: 10.1214/aoms/1177706369 

8.   Devanur N. R., Papadimitriou C. H., Saberi  A., Vazirani V. V. Market equilibrium via a primal–dual algorithm for a convex program // JACM. 2008. Vol. 55, no. 5. Paper 22. doi: 10.1145/1411509.1411512 

9.   Шмырев В. И. Алгоритмы полиэдральной комплементарности для отыскания равновесия в линейных моделях конкурентной экономики // Дискрет. анализ и исслед. операций. 2014. Сер. 2. Т. 21, № 2. С. 84–101.

10.   Шмырев В. И. Об одном подходе к отысканию равновесия в простейших моделях обмена // Докл. АН СССР. 1983. Т.  268, № 5. С. 1062–1066.

11.   Nikhil R. Devanur, Kamal Jain, Tung Mai, Vijay  V. Vazirani, Sadra Yazdanbod. New convex programs for Fisher’s market model and its generalizations. 2016. arXiv: 1603.01257v1 [cs.GT]. (Available at: https://arxiv.org/pdf/1603.01257.pdf). 23 p.

12.   Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay  V. Vazirani, Sadra Yazdanbod. Convex program duality, fisher markets, and nash social welfare // Proc. 18th ACM Conf. Econom. and Comput. 2017. P. 459–460. doi: 10.1145/3033274.3085109 

13.   Шмырев В. И. Об одном алгоритме отыскания равновесия в линейной модели обмена с фиксированными бюджетами // Сиб. журн. индустр. математики. 2008. Т. 11, № 2. С. 139–154.

14.   Понтрягин Л. С. Основы комбинаторной топологии. М.: Гл. ред. физ. -мат. лит., 1986. 120 с.

15.   Александров П. С. Общая теория гомологий. М.: Гл. ред. физ.-мат. лит., 1979. 416 с.

Поступила 28.01.2019

После доработки 15.03.2019

Принята к публикации 15.04.2019

Шмырев Вадим Иванович
д-р физ.-мат. наук, вед. научный сотрудник
Институт математики им. С.Л.Соболева СО РАН;
Новосибирский государственный университет, г. Новосибирск
e-mail: shvi@math.nsc.ru

Ссылка на статью: В.И. Шмырев. Полиэдральная комплементарность на симплексе. Метод встречных путей для убывающих квазирегулярных отображений // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 2. С. 273-286.

English

V.I. Shmyrev. Polyhedral complementarity on a simplex. Method of meeting paths for decreasing quasi-regular mappings

The paper explores the mathematical basis of a novel polyhedral complementarity approach proposed by the author for finding an economic equilibrium in a linear exchange model and its variations. The equilibrium problem reduces to finding fixed points of point-to-set mappings of the price simplex to itself. As a result, we obtain a polyhedral complementarity problem generated by a pair of polyhedral complexes in duality. The class of quasi-regular mappings, which is a new class of decreasing mappings having no analogs in $\mathbb{R}^n$, is considered. The procedure of meeting paths, which generalizes the known Lemke method for linear complementarity problems, is studied. It is shown that in the case under consideration the procedure has the property of monotonicity characteristic of linear complementarity problems with positive principal minors of the constraint matrix (P-class). The uniqueness of the desired fixed point is a consequence of monotonicity.

Keywords: simplex, polyhedral complex, complementarity, monotonicity, fixed point, algorithm

Received January 28, 2019

Revised March 15, 2019

Accepted April 15, 2019

Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 19-010-00910 A), by Program no. 227 of the Presidium of the Russian Academy of Sciences, and by Interdisciplinary Integration Project no. 7B of the Siberian Branch of the Russian Academy of Sciences.

Vadim Ivanovich Shmyrev, Dr. Phys.-Math. Sci., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: shvi@math.nsc.ru

Cite this article as: V.I.Shmyrev. Polyhedral complementarity on a simplex. Method of meeting paths for decreasing quasi-regular mappings, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 2, pp. 273–286.

[References -> on the "English" button bottom right]