О связи имитационной логит-динамики в популяционной теории игр и метода зеркального спуска в онлайн оптимизации на примере задачи выбора кратчайшего маршрута
Автор: Гасников А.В., Лагуновская А.А., Морозова Л.Э.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Доклады
Статья в выпуске: 4 (28) т.7, 2015 года.
Бесплатный доступ
В работе описывается метод зеркального спуска для задач стохастической онлайн оптимизации на симплексе и прямом произведении симплексов. На базе этого метода строятся оптимальные стратегии пользователей транспортной сети при выборе маршрутов следования. Поведение всех пользователей, действующих согласно таким стратегиям, порождает имитационную логит-динамику в популяционной игре, соответствующей модели Бэкмана равновесного распределения потоков по путям. Таким образом, на конкретном примере (The Shortest Path Problem) в работе показывается связь онлайн оптимизации и популяционной теории игр. Обнаружение отмеченной связи составляет основной результат данной работы.
Короткий адрес: https://sciup.org/142186090
IDR: 142186090
Список литературы О связи имитационной логит-динамики в популяционной теории игр и метода зеркального спуска в онлайн оптимизации на примере задачи выбора кратчайшего маршрута
- Lugosi G., Cesa-Bianchi N. Prediction, learning and games. New York: Cambridge University Press, 2006
- Patriksson M. The traffic assignment problem. Models and methods. Utrecht, Netherlands: VSP, 1994
- Algorithmic game theory. Editors N. Nisan, T. Roughgarden, E. Trados, V.V. Vazirani. Cambridge University Press., 2007
- Sandholm W.H. Population games and Evolutionary dynamics. Economic Learning and Social Evolution. MIT Press; Cambridge, 2010
- Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979
- Sridharan K. Learning from an optimization viewpoint. PhD Thesis, Toyota Technological Institute at Chicago, 2011
- Bubeck S. Introduction to online optimization. Princeton University: Lecture Notes, 2011. http://www.princeton.edu/sbubeck/BubeckLectureNotes.pdf
- Shalev-Shwartz S. Online learning and online convex optimization//Foundation and Trends in Machine Learning. 2011. V. 4, N 2. P. 107-194
- Bubeck S., Cesa-Bianchi N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems//Foundation and Trends in Machine Learning. 2012. V. 5, N 1. P. 1-122. http://www.princeton.edu/sbubeck/SurveyBCB12.pdf
- Hazan E. Introduction to online convex optimization. e-print, 2015. http://ocobook.cs.princeton.edu/OCObook.pdf
- Гасников А.В., Нестеров Ю.Е., Спокойный В.Г. Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации//ЖВМ и МФ. 2015. Т. 55, № 4. С. 55-71
- Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. Philadelphia: SIAM, 2013
- Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent. e-print, 2014. arXiv:1407.1537
- Nesterov Y. Primal-dual subgradient methods for convex problems//Math. Program. Ser. B. 2009. V. 120(1). P. 261-283
- Juditsky A., Nemirovski A. First order methods for nonsmooth convex large-scale optimization, I, II. In: Optimization for Machine Learning. Eds. S. Sra, S. Nowozin, S. Wright. MIT Press, 2012
- 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
- Гасников А.В., Гасникова Е.В., Мендель М.А., Чепурченко К.В. Эволюционные выводы энтропийной модели расчета матрицы корреспонденций//Математическое моделирование. 2016. Т. 28. arXiv:1508.01077 (принята к печати)
- Баймурзина Д.Р, Гасников А.В., Гасникова Е.В. Теория макросистем с точки зрения стохастической химической кинетики//Труды МФТИ. 2015. Т. 7, № 4. C. 95-103
- Wibisono A., Wilson A.C. On accelerated methods in optimization. e-print, 2015. arXiv:1509.03616
