Поиск стохастических равновесий в транспортных моделях равновесного распределения потоков
Автор: Гасников А.В., Гасникова Е.В., Двуреченский П.Е., Ершов Е.И., Лагуновская А.А.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Доклады
Статья в выпуске: 4 (28) т.7, 2015 года.
Бесплатный доступ
В работе предложены эффективные способы поиска стохастических равновесий в популяционных играх загрузок. Поиск равновесия Нэша в таких играх всегда сводится к задаче оптимизации. Мы рассматриваем модели равновесного распределения потоков по путям Бэкмана и Нестерова-де Пальмы. Поиск стохастических равновесий Нэша(-Вардропа) приводит к энтропийной регуляризации выпуклого функционала, отвечающего этим моделям. Данная работа посвящена тому, как эффективно решать такого рода задачи. В основе подхода лежит идея композитной оптимизации и особенность постановки, что функционал имеет вид суммы (сепарабельный функционал). Это обстоятельство вместе с неограниченностью константы Липшица градиента функционала мотивирует переформулировку исходной задачи оптимизации таким образом, чтобы этот сепарабельный функционал стал композитным членом. Рассматриваются и развиваются также и классические способы решения отмеченной задачи с помощью аппарата характеристических функций на графе.
Композитный быстрый градиентный метод, разреженность, равновесное распределение потоков
Короткий адрес: https://sciup.org/142186092
IDR: 142186092
Список литературы Поиск стохастических равновесий в транспортных моделях равновесного распределения потоков
- Гасников А.В., Дорн Ю.В., Нестеров Ю.Е, Шпирко С.В. О трехстадийной версии модели стационарной динамики транспортных потоков//Математическое моделирование. 2014. Т. 26:6. C. 34-70. arXiv:1405.7630
- Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики//Математическое моделирование. 2016. Т. 28. (принята к печати). arXiv:1506.00293
- Sheffi Y. Urban transportation networks: Equilibrium analysis with mathematical programming methods. N.J.: Prentice-Hall Inc., Englewood Cliffs, 1985
- Введение в математическое моделирование транспортных потоков. 2-е изд./под ред. А.В. Гасникова. М.: МЦНМО, 2013. 427 с. http://www.mou.mipt.ru/gasnikov1129.pdf
- Sandholm W. Population games and Evolutionary dynamics. Economic Learning and Social Evolution. MIT Press; Cambridge, 2010
- Andersen S.P., de Palma A., Thisse J.-F. Discrete choice theory of product differentiation. MIT Press; Cambridge, 1992
- Nesterov Yu. Gradient methods for minimizing composite functions//Math. Prog. 2013. V. 140. N 1. P. 125-161. http://www.uclouvain.be/cps/ucl/doc/core/documents/Composit.pdf
- Nesterov Yu., Nemirovski A. On first order algorithms for ℓ1/nuclear norm minimization//Acta Numerica. 2013. V. 22. P. 509-575
- Nesterov Y. Characteristic functions of directed graphs and applications to stochastic equilibrium problems//Optim. Engineering. 2007. V. 8. P. 193-214
- Гасников А.В. Об эффективной вычислимости конкурентных равновесий в транспортно-экономических моделях//Математическое моделирование. 2015. Т. 27, № 12. С. 121-136. (принята к печати). arXiv:1410.3123
- Бабичева Т.С., Гасников А.В., Лагуновская А.А., Мендель М.А. Двухстадийная модель равновесного распределения транспортных потоков//Труды МФТИ. 2015. Т. 7, № 3. С. 31-41
- Гасников А.В., Двуреченский П.Е., Камзолов Д.И., Нестеров Ю.Е., Спокойный В.Г., Стецюк П.И., Суворикова А.Л., Чернов А.В. Поиск равновесий в многостадийныйх транспортных моделях//Труды МФТИ. 2015. Т. 7, № 4. С. 143-155. (принята к печати). arXiv:1506.00292
- Ethier N.S., Kurtz T.G. Markov processes. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons Inc., New York, 1986
- Малышев В.А., Пирогов С.А. Обратимость и необратимость в стохастической химической кинетике//Успехи мат. наук. 2008. Т. 63, вып. 1(379). С. 4-36
- Гасников А.В., Гасникова Е.В. Об энтропийно-подобных функционалах, возникающих в стохастической химической кинетике при концентрации инвариантной меры и в качестве функций Ляпунова динамики квазисредних//Математические заметки. 2013. Т. 94, № 6. С. 816-824
- Баймурзина Д.Р.,Гасников А.В., Гасникова Е.В. Теория макросистем с точки зрения стохастической химической кинетики//Труды МФТИ. 2015. Т. 7, № 4. C. 95-103. (принята к печати)
- Санов И.Н. О вероятности больших отклонений случайных величин//Матем. сб. 1957. Т. 42(84):1. C. 11-44
- Patriksson M. The traffic assignment problem. Models and methods. Utrecht, Netherlands: VSP, 1994
- Ortuzar J.D., Willumsen L.G. Modelling transport. JohnWilley & Sons, 2011
- Гасников А.В., Гасникова Е.В., Нестеров Ю.Е., Чернов А.В. Об эффективных численных методах решения задач энтропийно-линейного программирования//ЖВМ и МФ. 2016. Т. 56, № 4. arXiv:1410.7719 (принята к печати)
- Anikin A., Dvurechensky P., Gasnikov A., Golov A., Gornov A., Maximov Yu., Mendel M., Spokoiny V. Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads//Proceedings of International conference ITAS-2015. Russia, Sochi, September, 2015. arXiv:1508.00858
- Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов. e-print, 2015. arXiv:1508.02182
- Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом//e-print, 2015. arХiv:1411.4218
- Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent//e-print, 2014. arXiv:1407.1537
- Nesterov Yu. Universal gradient methods for convex optimization problems//Mathematical Programming. 2015. V. 152. С. 381-404
- Гасников А.В, Двуреченский П.Е., Камзолов Д.И. Градиентные и прямые методы с неточным оракулом для задач стохастической оптимизации//Труды SDCP-2014. Екатеринбург, 2015. arXiv:1502.06259
- Лидбеттер М., Линдгрен Г., Ротсен Х. Экстремумы случайных последовательностей и процессов. М.: Мир, 1989
- Ким К., Нестеров Ю., Скоков В., Черкасский Б. Эффективные алгоритмы для дифференцирования и задачи экстремали//Экономика и математические методы. 1984. Т. 20. С. 309-318
- Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966
- Ahuja R.K., Magnati T.L., Orlin J.B. Network flows: Theory, algorithms and applications. Prentice Hall, 1993
- Kolokoltsov V.N., Maslov V.P. Idempotent analysis and applications. Dordrecht: Kluwer Acad. Publ., 1997
- Lugosi G., Cesa-Bianchi N. Prediction, learning and games. New York: Cambridge University Press, 2006
