On Accelerated Coordinate Descent Methods for Searching Equilibria in Two-Stage Transportation Equilibrium Traffic Flow Distribution Model

N. A. Iltyakov; Ильтяков Н. А.; M. A. Obozov; Обозов М. А.; I. M. Dyshlevski; Дышлевский И. М.; D. V. Yarmoshik; Ярмошик Д. В.; M. B. Kubentaeva; Кубентаева М. Б.; A. V. Gasnikov; Гасников А. В.; E. V. Gasnikova; Гасникова Е. В.

doi:10.31857/S0132347423060055

ОБ УСКОРЕННЫХ ПОКОМПОНЕНТНЫХ МЕТОДАХ ПОИСКА РАВНОВЕСИЙ В ДВУХСТАДИЙНОЙ МОДЕЛИ РАВНОВЕСНОГО РАСПРЕДЕЛЕНИЯ ТРАНСПОРТНЫХ ПОТОКОВ

Авторы: Ильтяков Н.А.¹, Обозов М.А.¹, Дышлевский И.М.¹, Ярмошик Д.В.¹^,2, Кубентаева М.Б.¹, Гасников А.В.¹^,2^,3, Гасникова Е.В.¹
Учреждения:
1. Московский физико-технический институт
2. Институт проблем передачи информации РАН
3. Кавказский математический центр Адыгейского гос. университета
Выпуск: № 6 (2023)
Страницы: 36-48
Раздел: АНАЛИЗ ДАННЫХ
URL: https://journals.rcsi.science/0132-3474/article/view/148118
DOI: https://doi.org/10.31857/S0132347423060055
EDN: https://elibrary.ru/GHHXBJ
ID: 148118

Цитировать

Полный текст

Открытый доступ
Доступ закрыт

Доступ предоставлен
Доступ закрыт

Только для подписчиков

Аннотация
Об авторах
Список литературы
Дополнительные файлы
Статистика

Аннотация

Поиск равновесия в двухстадийной модели транспортных потоков сводится к решению специальной негладкой задачи выпуклой оптимизации с двумя группами разных переменных. Для численного решения данной задачи в статье предложено использовать ускоренный блочно-покомпонентный метод Нестерова–Стиха со специальным выбором вероятностей блоков на каждой итерации (одного из двух). Теоретические оценки сложности такого подхода могут заметно улучшать оценки используемых ранее подходов. Однако в общем случае не гарантируют более быстрой сходимости. В статье проведены численные эксперименты с предложенными алгоритмами.

Список литературы

Ortúzar J.D., Willumsen L.G. Modelling transport. John Wiley and Sons. West Sussex, England. 2002.
Boyles S.D., Lownes N.E., Unnikrishnan A. Transportation network analysis. Volume I: Static and Dynamic Traffic Assignment, 2020.
Гасников А.В., Гасникова Е.В. Модели равновесного распределения потоков в больших сетях. М.: УРСС, 2023.
Evans S.P. Derivation and analysis of some models for combining trip distribution and assignment // Transportation Research. 1976. V. 10 (1). P. 37–57.
Гасников А.В. и др. О трехстадийной версии модели стационарной динамики транспортных потоков // Математическое моделирование. 2014. Т. 26. № 6. С. 34–70.
Gasnikova E. et al. An evolutionary view on equilibrium models of transport flows // Mathematics. 2023. V. 11. № 4. P. 858.
Котлярова Е.В. и др. Поиск равновесий в двухстадийных моделях распределения транспортных потоков по сети // Компьютерные исследования и моделирование. 2021. Т. 13. № 2. С. 365–379.
Kubentaeva M. et al. Primal-Dual Gradient Methods for Searching Network Equilibria in Combined Models with Nested Choice Structure and Capacity Constraints. arXive:2307.00427
Nesterov Y., Stich S. Efficiency of the accelerated coordinate descent method on structured optimization problems // SIAM Journal on Optimization. 2017. V. 27. № 1. P. 110–123.
Баймурзина Д.Р. и др. Универсальный метод поиска равновесий и стохастических равновесий в транспортных сетях // Журнал вычислительной математики и математической физики. 2019. Т. 59. № 1. С. 21–36.
Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов // Труды Московского физико-технического института. 2016. Т. 8. № 2 (30). С. 67–100.
Gasnikova E. et al. Sufficient conditions for multi-stages traffic assignment model to be the convex optimization problem. arXiv:2305.09069.
Allen-Zhu Z. et al. Even faster accelerated coordinate descent using non-uniform sampling // International Conference on Machine Learning. PMLR. 2016. V. 1110–1119.
Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков. Под ред. А.В. Гасникова с приложениями М.Л. Бланка, К.В. Воронцова и Ю.В. Чеховича, Е.В. Гасниковой, А.А. Замятина и В.А. Малышева, А.В. Колесникова, Ю.Е. Нестерова и С.В. Шпирко, А.М. Райгородского, с предисловием руководителя департамента транспорта г. Москвы М.С. Ликсутова. М.: МЦНМО, 2013. 427 с., 2-е изд.
Patriksson M. The traffic assignment problem: models and methods. Courier Dover Publications, 2015.
Stabler B., Bar-Gera H., Sall E. Transportation Networks for Research Core Team. Transportation Networks for Research. Accessed Month, Day, Year. [Electronic resource]: https://github.com/bstabler/TransportationNetworks (accessed 16.02.2021).
Nesterov Y., De Palma A. Stationary dynamic solutions in congested transportation networks: summary and perspectives // Networks and spatial economics. 2003. T. 3. № 3. P. 371–395.
Котлярова Е.В. и др. Обоснование связи модели Бэкмана с вырождающимися функциями затрат с моделью стабильной динамики // Компьютерные исследования и моделирование. 2022. Т. 14 : 2. С. 335–342.
Вильсон А.Дж. Энтропийные методы моделирования сложных систем. М.: Наука, 1978.
Гасников А.В. и др. Эволюционные выводы энтропийной модели расчета матрицы корреспонденций // Математическое моделирование. 2016. Т. 28. № 4. С. 111–124.
Nesterov Y. Smoothing technique and its applications in semidefinite optimization //Mathematical Programming. 2007. V. 110. № 2. P. 245–259.
Peyré G., Cuturi M. Computational Optimal Transport: With Applications to Data Science // Foundations and Trends® in Machine Learning. 2019. V. 11. № 5–6. P. 355–607.
Guminov S. et al. Accelerated alternating minimization // ICML 2021.
Tupitsa N. et al. Numerical Methods for Large-Scale Optimal Transport. arXiv:2210.11368.
Nesterov Y. Universal gradient methods for convex optimization problems // Mathematical Programming. 2015. V. 152. № 1–2. P. 381–404.
Гасников А.В., Нестеров Ю.Е. Универсальный метод для задач стохастической композитной оптимизации // Журнал вычислительной математики и математической физики. 2018. Т. 58. № 1. С. 51–68.
Kovalev D., Gasnikov A., Malinovsky G. An Optimal Algorithm for Strongly Convex Min-min Optimization. arXiv:2212.14439.
Gasnikov–Nesterov A universal method for stochastic problems composite optimization. arxiv preprint arXiv:1604.05275. 2016
Meruza Kubentayeva et al. Primal-Dual Gradient Methods for Searching Network Equilibria in Combined Models with Nested Choice Structure and Capacity Constraints. arXiv:2307.00427.
Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов. arxiv preprint arXiv:1508.02182. 2015.
Алиев А.С., Мазурин Д.С., Максимова Д.А., Швецов В.И. Структура комплексной модели транспортной системы г. Москвы // Труды Института системного анализа Российской академии наук. 2015. Т. 65 (1). С. 3–15.
Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. arXiv:1711.00394.
Ссылка на репозиторий с исходным кодом вычислительных экспериментов https://github.com/Lareton/transport_network_optimization
Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979.
Nesterov Y. Efficiency of coordinate descent methods on huge-scale optimization problems // SIAM Journal on Optimization. 2012. V. 22. № 2. P. 341–362.
De Cea J., Fernandez J. E., Dekock V., Soto A. Solving network equilibrium problems on multimodal urban transportation networks with multiple user classes // Transport Reviews. 2005. V. 25(3). P. 293–317.