Введение
Глава 1. Эволюционный вывод равновесных моделей распределения потоков в больших транспортных сетях и численные методы поиска равновесий в таких моделях 19
1.1 Трехстадийная модель равновесного распределения 19
1.1.1 Введение 19
1.1.2 Структура раздела и предварительные сведения 22
1.1.3 Энтропийная модель расчета матрицы корреспонденций 24
1.1.4 Модель равновесного распределения потоков Бэкмана 32
1.1.5 Краткий обзор подходов к построению многостадийных моделей транспортных потоков, с моделью типа Бэкмана в качестве модели равновесного распределения потоков 41
1.1.6 Модель стабильной динамики 49
1.1.7 Связь модели стабильной динамики с моделью Бэкмана 54
1.1.8 Учет расщепления потоков по способам передвижений 59
1.1.9 Трехстадийная модель стабильной динамики
1.1.10 Стохастический вариант трехстадийной модели стабильной динамики 62
1.1.11 Калибровка модели стабильной динамики 63
1.2 Эволюционные выводы энтропийной модели 66
1.2.1 Введение 66
1.2.2 Вывод на основе обменов 67
1.2.3 Вывод на основе модели равновесного распределения потоков 74
1.3 Об эффективной вычислимости конкурентных равновесий 79
1.3.1 Введение 79
1.3.2 Равновесное распределение потоков по путям 81
1.3.3 Равновесный расчет матрицы корреспонденций 84
1.3.4 Сетевая модель алгоритмического рыночного поведения 88
1.3.5 Общее конкурентное равновесие 91
1.4 О связи моделей дискретного выбора с разномасштабными по времени популя ционными играми загрузок 95
1.4.1 Введение 95
1.4.2 Постановка задачи 95
1.4.3 Двойственная задача 102
1.5 Численные методы поиска равновесного распределения 108
1.5.1 Введение 108
1.5.2 Метод Франк–Вульфа поиска равновесия в модели Бэкмана 109
1.5.3 Рандомизированный метод двойственных усреднений поиска равновесия в модели стабильной динамики (Нестерова–де Пальма) 116
1.5.4 Рандомизированный покомпонентный спуск для модели стабильной динамики в форме Ю.Е. Нестерова 128
1.5.5 Заключение 130
1.5.6 Дополнение 132
1.6 Поиск равновесий в многостадийных транспортных моделях 133
1.6.1 Введение 133
1.6.2 Поиск барицентра Вассерштейна 135
1.6.3 Универсальный метод с неточным оракулом 141
1.6.4 Заключительные замечания 152
Глава 2. Градиентные методы с неточным оракулом для задач выпуклой оптимизации 154
2.1 Стохастические градиентные методы с неточным оракулом 154
2.1.1 Введение 154
2.1.2 Стохастическая оптимизация 156
2.1.3 Стохастические градиентные методы с неточным оракулом 174
2.1.4 Стохастические безградиентные и покомпонентные методы с неточным оракулом 201
2.2 Универсальный метод для задач стохастической композитной оптимизации. 214
2.2.1 Введение 214
2.2.2 Метод треугольника для задач композитной оптимизации 214
2.2.3 Метод треугольника для сильно выпуклых задач композитной оптимизации 219
2.2.4 Универсальный метод треугольника 225
2.2.5 Универсальный метод треугольника для задач стохастической композитной оптимизации 233
2.3 Пример задачи композитной оптимизации (сильно выпуклый случай) 237
Глава 3. STRONG Прямо-двойственные градиентные методы для задач выпуклой оптимиза
ции STRONG 244
3.1 О численных методах решения задач энтропийно-линейного программирования
с помощью решения регуляризованной двойственной задач 244
3.1.1 Введение 244
3.1.2 Парадокс Эренфестов 245
3.1.3 Задача энтропийно-линейного программирования 247
3.1.4 Вспомогательные результаты для регуляризованной двойственной задачи к задаче энтропийно-линейного программирования 248
3.1.5 Основные результаты 250
3.1.6 Обсуждение основных результатов 252
3.1.7 Заключительные замечания 253
3.2 Двойственные подходы к задачам минимизации сильно выпуклых функциона лов простой структуры при аффинных ограничениях 259
3.2.1 Введение 259
3.2.2 Прямо-двойственность быстрого градиентного метода 260
3.2.3 Приложение к задаче минимизации сильно выпуклого функционала простой структуры при аффинных ограничениях
3.3 Параллелизуемые двойственные методы поиска равновесий в смешанных моделях распределения потоков в больших транспортных сетях 279
3.4 Прямо-двойственный метод зеркального спуска для условных задач стохастической оптимизации 287
Глава 4. Решение задач выпуклой оптимизации в пространствах сверхбольших размеров. Рандомизация и разреженность 294
4.1 Об эффективных рандомизированных алгоритмах поиска вектора PageRank. 294
4.1.1 Введение 294
4.1.2 Обзор и обсуждение известных ранее и новых способов численного поиска вектора PageRank 296
4.1.3 Метод Markov Сhain Monte Carlo 302
4.1.4 Алгоритм MCMC 306
4.1.5 Алгоритм Григориадиса–Хачияна 310
4.1.6 Доказательство теоремы 4.1.1 315
4.2 Эффективные численные методы решения задачи PageRank для дважды разре женных матриц 317
4.2.1 Введение 317
4.2.2 Метод условного градиента Франк–Вульфа 320
4.2.3 Седловое представление задачи PageRank и рандомизированный зеркальный спуск в форме Григориадиаса–Хачияна 322
4.3 О неускоренных эффективных методах решения разреженных задач квадратичной оптимизации 327
4.3.1 Введение 327
4.3.2 Прямой неускоренный градиентный метод в l1-норме 328
4.3.3 Метод условного градиента (Франк–Вульфа) 330
4.3.4 Неускоренный рандомизированный градиентный спуск в сильно выпуклом случае 334
4.3.5 Дополнение 337
4.4 Рандомизация и разреженность в задачах huge-scale оптимизации на примере работы метода зеркального спуска 342
4.4.1 Введение 342
4.4.2 Рандомизированный метод зеркального спуска 343
4.4.3 Рандомизированный метод зеркального спуска с функциональными ограничениями 348
4.4.4 Примеры решения разреженных задач с использованием рандомизированного метода зеркального спуска 351
Глава 5. Покомпонентные и безградиентные методы для задач выпуклой оптимизации 357
5.1 О нетривиальности быстрых (ускоренных) Введение Нетривиальность ускоренных покомпонентных методов Нетривиальность ускоренных методов рандомизации суммы
Получение ускоренных покомпонентных методов с помощью каплинга неускоренных прямых покомпонентных методов и покомпонентного метода зеркального спуска 366
5.1.5 Примеры применения ускоренных покомпонентных методов 383
5.1.6 Заключительные замечания 395
5.2 Безградиентные прокc-методы с неточным оракулом для негладких задач выпук
лой стохастической оптимизации на симплексе 397
5.2.1 Введение 397
5.2.2 Метод зеркального спуска для задач стохастической оптимизации с неточным оракулом 399
5.2.3 Безградиентная модификация метода зеркального спуска для задач стохастической оптимизации с неточным оракулом 401
5.2.4 Модификация метода зеркального спуска для гладких задач стохастической оптимизации при спусках по случайному направлению 407
5.2.5 Перенесение результатов подраздела
5.2.4 на безградиентные методы 415
5.2.6 Заключение 417
Глава 6. Онлайн оптимизация с точки зрения выпуклой оптимизации 419
6.1 Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации 419
6.1.1 Введение 419
6.1.2 Онлайн метод зеркального спуска со стохастическим субградиентом 421
6.1.3 Онлайн метод зеркального спуска со стохастической проекцией 428
6.1.4 Приложения метода зеркального спуска 432
6.2 Стохастическая онлайн оптимизация. Одноточечные и двухточечные нелиней ные многорукие бандиты. Выпуклый и сильно выпуклый случаи 442
6.2.1 Введение 442
6.2.2 Метод зеркального спуска для задач стохастической онлайн оптимизации с неточным оракулом 443
6.2.3 Одноточечные и многоточечные нелинейные многорукие бандиты. 447
Заключение 455
Список литературы
