Searching equillibriums in Beckmann's and Nesterov - de Palma's models

Abstract

In this paper we propose and develop classical Frank--Wolf algorithm for Beckmann's type models. This is not new, but we investigate details that allows us to speed up. We also consider stable dynamic like models. First model of this type was proposed 15 years ago by Yu. Nesterov and A. DePalma. We propose randomized dual averaging method with special (sum-type) randomization. For both of the problems we obtain the rates of convergences. It seems that this estimations to be unimprovable without additional assumption about problem formulation. В работе рассматриваются две модели транспортного равновесия: модель Бэкмана (1955) и модель стабильной динамики (Нестеров–де Пальма, 1998). В статье описаны эффективные численные процедуры поиска равновесия в этих моделях. Для модели Бэкмана будет использован метод Франк–Вульфа, а для модели стабильной динамики используется переход к двойственной задаче. Эта задача решается методом методом зеркального спуска с евклидовой прокс-структурой с помощью “рандомизации суммы”. В работе также приводится другой способ решения (сглаженной) двойственной задачи. Этот способ базируется на современных вариантах метода ускоренного блочно-покомпонентного спуска. Такие подходы, насколько нам известно, представляются но-выми. Кроме того, даже при использовании классического метода Франк–Вульфа, мы исходим из современных результатов о его сходимости.