Efficient calculation of stochastic equilibriums in the Beckmann's and stable dynamic models

Abstract

We propose composite approache to the special sum-type convex optimization problem with affine restriction and special entropy type regularization. Since the fuctional has a penalty type form, we reformulate initial conditional optimization problem in a special unconstrained form that allows us to put the penalty type functional into the composite term. We also describe the characteristic functions on graphs technique (Yu. Nesterov, 2007) in application to the dual problem.

В работе предложены эффективные способы поиска стохастических равновесий в популяционных играх загрузок. Поиск равновесия Нэша в таких играх всегда сводится к задаче оптимизации. Мы рассматриваем модели равновесного распределения потоков по путям Бэкмана и Нестерова–де Пальмы. Поиск стохастических равновесий Нэша(–Вардропа) приводит к энтропийной регуляризации выпуклого функционала, отвечающего этим моделям. Данная работа посвящена тому, как эффективно решать такого рода задачи. В основе подхода лежит идея композитной оптимизации и особенность постановки, что функционал имеет вид суммы (сепарабельный функционал). Это обстоятельство, вместе с неограниченностью константы Липшица градиента функционала, мотивирует переформулировку исходной задачи оптимизации таким образом, чтобы этот сепарабельный функционал стал композитным членом. Рассматриваются и развиваются также и классические способы решения отмеченной задачи с помощью аппарата характеристических функций на графе.