Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Математическое моделирование транспортных потоков

По субботам (с 11 февраля) с 16.00 до 19.00 в ауд. 303 НМУ будет проводиться семинар, на котором будут ставиться разнообразные насущные научные транспортные задачи и намечаться пути решения рядом ведущих ученых в области математического моделирования транспортных потоков.

Координатор:  А. В. Гасников (ФУПМ МФТИ и ПреМоЛаб)

Поддержан Лабораторией структурных методов анализа данных в предсказательном моделировании (ПреМоЛаб http://www.premolab.ru/), ФУПМ МФТИ, грант правительства РФ дог. 11.G34.31.0073.

В новом весеннем семестре 2013/2014 учебного года планируется вести исследования в следующих направлениях:

 

1.  Разработка эффективных численных методов поиска равновесий в транспортных моделях (равновесного распределения потоков, расчета матрицы корреспонденций, в многостадийных моделях)

А) Методы условного градиента (Франк-Вульф) хорошо учитывают разреженную специфику задачи (матрица смежности транспортного графа имеет число отличных от нуля элементов порядка числа вершин)

Bubeck S.  Conditional gradient descent and structured sparsity // Princeton Course “The Complexities of Optimization”, 2013.

http://blogs.princeton.edu/imabandit/2013/04/09/orf523-conditional-gradient-descent-and-structured-sparsity/

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

Б) Ввиду специфики транспортной задачи

http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=7856

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

http://www.maths.ed.ac.uk/~prichtar/ ,

 которые планируется развивать.

В) Недавно Ю.Е. Нестеровым был предложен класс универсальных методов и методов с неточным оракулом, адаптивных, самонастраивающихся на задачу

http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=7244

 На данный момент эти методы самонастраиваются в основном на гладкость задачи, планируется развить эти методы также и на свойство сильной выпуклости. Планируется применить эти методы к транспортным задачам, которые, вообще говоря, негладкие, но в большинстве точек все-таки гладкие. Здесь также планируется создать общую теорию универсальных методов. Введя не большой набор операций над алгоритмами, с помощью которых из алгоритмов подточенных, скажем, под гладкие задачи, можно получить алгоритмы для негладких задач, а также для задач с дополнительным свойством сильной выпуклости и т.д. И если исходить из некоторого оптимального базиса (то есть оптимальных для своего класса алгоритмов), то с помощью этих операций можно получать из этого базиса оптимальные методы для других классов. Качество методов (речь идет градиентных методах, т.е. о методах, на каждой итерации которых мы можем запрашивать и проектировать на допустимое множество градиент или некоторый его аналог) мы будем оценивать с точки зрения числа итераций, обращений к оракулу за градиентом. Не много в другом ключе планируется исследовать алгебру над эффективными алгоритмами решения многоуровневых задач оптимизации, возникающих при поиске равновесий в многостадийных моделях. Планируется развивать здесь ряд идей Александра Шапиро

http://www.mathnet.ru/php/person.phtml?option_lang=rus&personid=82644

Г) Недавно Ю.Е. Нестеровым был предложен класс сходящихся прямо-двойственных методов решения разнообразных негладких задач выпуклой оптимизации, в которых не всегда есть возможность считать значения функции (при этом субградиент функции можно как-то оценивать), и в которых важно отслеживать не только прямые, но и двойственные переменные

http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=8364

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

В) При поиске равновесий макросистем, к которым относятся и транспортные системы (например, если смотреть на расчет матрицы корреспонденций или Traffic   Rank – транспортная модель Томлина ранжирования web-страниц и др.)  возникают задачи типа Энтропийно-линейного программирования (ЭЛП). Планируется максимально расширить класс таких задач (в частности, сюда примыкают задачи с ограниченной вариацией оптимизируемой функции) так, чтобы они решались одним общим методом, не требующем на входе никакой информации о локализации решения двойственной задачи.  Напомним, что основная идея решения задачи ЭЛП – это решать двойственную задачу, в которой нет ограничений на двойственные множители, то есть нельзя применять классические методы решения задач выпуклой (вогнутой) оптимизации на выпуклых КОМПАКТАХ. Планируется предложить адаптивные методы, в которые в сам метод не будет входить размер решения двойственной задачи, этот размер будет входить только в оценки числа требуемых итераций. Более того, также планируется предложить такой способ регуляризации двойственной задачи, чтобы размер решения двойственно задачи вообще никуда не входил.

http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=8056

 

2.  Эволюционная интерпретация равновесий в транспортных сетях. Развитие концепции ограниченной рациональности в контексте макросистемного подхода (на основе принципов стохастической химической кинетики)

А) Используя разработанный на прошлом этапе макросистемный подход (Мат. Заметки, Т. 94. № 6. 2013)

http://www.mathnet.ru:8080/PresentFiles/6372/%cd%cc%d3_10_%ff%ed%e2%e0%f0%ff_2013.pdf

планируется существенно расширить класс задач (в основном на различные транспортные задачи), к которому он применим. А именно планируется сделать континуальный предел. То есть число агентов в системе стремить не к счетной бесконечности и рассуждать в терминах бесконечномерных векторов, а к несчетной бесконечности и рассуждать в терминах функций распределения агентов по стратегиям.  Все это связано с концепцией mean-field   games. В частности, планируется перенести теорему Е.В. Гасниковой (2012) об унивесральности “энтропии” (эта функция описывает концентрацию инвариантной меры макросистемы и, одновременно, является функцией Ляпунова прошкалированной динамики этой макросистемы) на континуальные модели. Ожидается, что все это поможет с решением таких задач, как например, задача Нестерова-деПальмы (см. Введение в математическое моделирование транспортных потоков. Под ред. А.В. Гасникова М.: МЦНМО, 2013. 427 стр.)

Б) Используя концепцию ограниченной рациональности (discrete   choice   theory) можно содержательно проинтерпретировать прямо-двойственный метод Ю.Е. Нестерова, который можно использовать при поиске равновесий в транспортных сетях. К сожалению, эта интерпретация не строго формализована на данный момент. Хотя этому и посвящаются монографии

Andersen S.P., de Palma A., Thisse J.-F.  Discrete choice theory of product differentiation. MIT Press; Cambridge, 1992.

Аккуратной завязки на теорию макросистем и на эволюционную теорию игр до сих пор не сделано. Хотя необходимый научный задел уже во многом создан

Sandholm W.  Population games and Evolutionary dynamics. Economic Learning and Social Evolution. MIT Press; Cambridge, 2010.

Планируется завязать, на примере задач поиска равновесий в транспортных сетях (в том числе в многостадийных моделях), теорию макросистем, эволюционную (популяционную) теорию игр и теорию ограниченной рациональности в одну общую органичную теорию.

В) Разработанная концепция равновесия макросистемы (Мат. Заметки, Т. 94. № 6. 2013) имеет много различных транспортных, экономических, биологических приложений. Однако, в ряде постановок (например, кинетика социального неравенства) равновесие удобнее описывать не вектором с огромным числом компонент, а кривой. Предельной формой (limit   shape). Здесь возникают новые вопросы относительно равномерности тех оценок (скорости сходимости к равновесию, плотности концентрации инвариантной меры около равновесия), которые получены в случае, когда исследуется макросистема, состояние которой описывается вектором (компоненты вектора = числами заполнения) с небольшим числом компонент (характерный пример – модель Эренфестов), по числу компонент, если их становится все больше и больше. Планируется получить достаточные условия, когда оценки будут равномерными по числу компонент вектора, описывающего состояние макросистемы.

 

3.  Онлайн интерпретация транспортных равновесий. Оптимальная тарифная политика, как основной инструмент долгосрочного управления транспортными потоками

А) Известно (Ю.Е. Нестеров, 2005), что прямо-двойственные методы допускают онлайн интерпретацию. Мы планируем добавить стохастическую составляющую и завязать все это на теорию макросистем, эволюционную (популяционную) теорию игр и теорию ограниченной рациональности. На наш взгляд это позволит глубже понять принципы возникновения тех или иных равновесных конфигураций, определить их “живучесть” к изменению внешних условий.

Б) На основе разрабатываемых моделей (в частности, стабильной динамики) планируется заниматься mechanism   design

Algorithmic game theory. Ed. N. Nisan, T. Roughgarden, E. Trados, V.V. Vazirani. Cam-bridge Univ. Press., 2007.http://www.eecs.harvard.edu/cs285/Nisan_Non-printable.pdf   

В частности, формализовать и вырабатывать эффективные алгоритмы оптимальной политики взимания плат за проезд, эксплуатации выделенных полос и платных парковок. Полезным здесь представляется использование класса новых “облачных” транспортных моделей.[1] Здесь также ожидается новая эволюционная интерпретация двойственных множителей Лагранжа, развивающая идеи статической интерпретации Л.В. Канторовича.

В) Также планируется учитывать (зашивать в разрабатываемые многостадийные транспортные модели) долгосрочное развитие (рост) городов. Здесь планируется привлекать некоторые идеи из Социодинамики (В. Вайдлих) и исходить из разрабатываемых макросистемных подходов в классе облачных моделей.



[1] Предположим, что все вершины, отвечающие источникам корреспонденций, соединены ребрами с одной вспомогательной вершиной (облако № 1). Аналогично, все вершины, отвечающие стокам корреспонденций, соединены ребрами с другой вспомогательной вершиной (облако № 2). Припишем всем новым ребрам постоянные веса. И проинтерпретируем веса ребер, отвечающих источникам, например, как средние затраты на проживание (в единицу времени, скажем, в день) в этом источнике (районе), а веса ребер, отвечающих стокам, как уровень средней заработной платы со знаком минус  (в единицу времени) в этом стоке (районе), если изучаем трудовые корреспонденции. Можно работать с новым транспортным графом с одним источником и одним стоком.

 

 

Подробности на сайте www.mathnet.ru.

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика