WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

На правах рукописи

Гасникова Евгения Владимировна

Концепция равновесия макросистемы и е

теоретико-игровые аспекты с приложениями к

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

потоков

Специальность 05.13.18 – математическое моделирование,

численные методы и комплексы программ

Автореферат

диссертации на соискание учной степени кандидата физико-математических наук

Москва – 2012 1

Работа выполнена на кафедре анализа систем и решений Московского физико-технического института (государственного университета).

Научный руководитель:

кандидат физико-математических наук, доцент МЕНЬШИКОВ Иван Станиславович

Официальные оппоненты:

Член-корр. РАН, профессор ПОСПЕЛОВ Игорь Гермогенович кандидат физико-математических наук ШВЕЦОВ Владимир Иванович

Ведущая организация:

Защита состоится 29 ноября 2012 года в час. на заседании диссертационного совета Д 212.156.05 при Московском физикотехническом институте (государственном университете) по адресу: 141700, г. Долгопрудный Московской обл., Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ).

Автореферат разослан 2012 г.

Ученый секретарь диссертационного совета Федько О.С.

Общая характеристика работы

Актуальность темы. После работ Е.Т. Джейнса (конца 50-х годов XX века), А. Дж. Вильсона (конца 60-х годов ХХ века), И. Пригожина с коллегами, Г. Хакена (70-е годы XX века) в литературе достаточно прочно укрепилась концепция о плодотворности перенесения термодинамического формализма на различные макросистемы (в частности, встречающиеся экономике, биологии, социальной сфере). В России систематические исследования в этом направлении были предприняты Л.Н. Розоноэром в начале 70-x гг. XX века. В последние несколько десятков лет в России в этом направлении работают, например, В.П. Маслов, Ю.С. Попков. Упомянутая концепция часто используется для нахождения равновесия макросистемы. А именно, по аналогии с феноменологической термодинамикой, вводится вероятностное распределение на множестве состояний, в которых может пребывать макросистема.





Такое распределение может, например, совпадать с инвариантной мерой эргодической динамической системы, порождающей рассматриваемую макросистему, или с финальным (равным стационарному) распределением эргодического (например, марковского) случайного процесса, порождающего рассматриваемую макросистему. Если размерность макросистемы увеличивается, то, как правило, распределение сосредотачивается в окрестности наиболее вероятного макросостояния. Таким образом, с ростом времени наблюдения за макросистемой и размерности макросистемы следует ожидать нахождения макросистемы с большой вероятностью в окрестности наиболее вероятного состояния, которое, естественно, в связи с этим называть равновесием макросистемы. Задача нахождения наиболее вероятного макросостояния часто сводится (асимптотически по размерности системы) к задаче максимизации энтропийно-подобного функционала при ограничениях (в термодинамике таким образом можно получить статистики Больцмана, Ферми–Дирака, Бозе–Эйнштейна). Отметим, что в диссертации уделяется особое внимание тому случаю, когда эволюция макросистемы описывается законами аналогичными законам стохастической химической кинетики (равноправие агентов), причем число химических реакций и размерность пространства макросостояний системы могут расти с ростом числа агентов в системе.

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

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





Изучение теоретико-игровых аспектов концепции равновесия макросистемы.

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

Общая методика исследования. В первой главе диссертации при изучении равновесий макросистем широко используется классический вариант эргодической теории марковских процессов (фундаментальной монографии А.А. Боровкова (1999) здесь оказалось более чем достаточно), для получения стационарной (инвариантной) меры. Далее активно используется техника изучения явления концентрации этой меры: от формулы Стирлинга и метода Дарвина– Фаулера (базирующемся на аппарате производящих функций и асимптотическом оценивании интегралов методом Лапласа или методом перевала из ТФКП), до современных геометрических теорем о концентрации меры (базирующихся на таких понятиях как кривизна Риччи многообразия и изопериметрические неравенства). Для оценок скоростей сходимости в эргодической теореме среди прочего используются современные варианты неравенства Чигера (Фан Чанг, 2005) и дискретная кривизна Риччи (Жульен–Оливье, 2007). Во многом следуя Е.Т. Джейнсу, А.Дж. Вильсону и Ю.С. Попкову с помощью довольно стандартной техники гладко-выпуклой оптимизации (принципа Ферма и Лагранжа) мы сводим задачу поиска равновесия макросистемы (для важного класса макросистем) к задаче энтропийно-линейного программирования.

Во второй главе диссертации для построения эффективного итерационного алгоритма решения задачи энтропийно-линейного программирования активно используется второй метод Ляпунова (см., например, Б.Т. Поляк, 1983) и метод внутренних штрафных функций (барьеров), используемый в отделе Ю.Г. Евтушенко в ВЦ РАН уже более 20 лет. Также в случае огромных размеров макросистемы применяются идеи стохастического квазиградиентного спуска, восходящие к работам начала 70-х Ю.М. Ермольева. Однако нами эти идеи применяются в более современных вариантах, встречающихся, например, в работах А.С. Немировского, Ю.Е. Нестерова.

В третьей главе (также как и во второй) используется второй метод Ляпунова и некоторая техника работы с равновесиями макросистем из главы 1. Кроме того, используются идеи метаигрового синтеза (двухуровневой оптимизации) в задаче о платных дорогах. Также в этой части мы существенным образом опираемся на недавно предложенную (например, Немировским–Юдитским– Шапиро и др.) технику доказательства сходимости итерационного метода зеркального спуска решения задачи стохастической выпуклой оптимизации с оценкой скорости сходимости.

Научная новизна. Как уже упоминалось, исследование всевозможных макросистем является довольно популярным направлением математического моделирования на западе. Подтверждением этому могут служить, например, известные в России монографии А.Дж. Вильсона (1978), К.В. Гардинера (1986), В. Вайдлиха (2000) (мы лишь указали наиболее доступные российскому читателю книги). Акцент в этих работах делается, прежде всего, на интересные приложения.

Кульминацией исследований был результат о том, что в случае выполнения условия детального равновесия (баланса) эргодическая марковская динамика, лежащая в основе макросистемы, приводит к единственному равновесию, поиск которого сводится к решению задачи энтропийно-линейного программирования. Попытка обобщить этот результат привела В.В. Веденяпина и Я.Г. Батищеву около 10 лет назад к условию унитарности или (ШБП) условию (см. ниже). Отметим, что это условие было обнаружено путем анализа с помощью второго метода Ляпунова (с функцией Ляпунова, совпадающей с той самой энтропией, которую надо максимизировать, чтобы найти наиболее вероятное макросостояние) системы дифференциальных уравнений типа химической кинетики, полученной при скейлинге (предельном переходе по числу агентов – размерности макросистемы) из марковской динамики, лежащей в основе макросистемы. У Батищево–Веденяпина на этом пути были предшественники, из которых мы упомянем здесь лишь А.Н. Горбаня с концепцией обхода равновесия. В 2004 году при подготовке докторской диссертации С.А. Пирогов независимо получил условие унитарности, но в отличие от Батищевой–Веденяпина он делал сначала предельный переход по времени (получая инвариантную меру), и уже потом исследовал концентрацию этой меры, осуществляя предельный переход по размерности макросистемы. При выполнении условия унитарности эти предельные переходы оказались перестановочными. Тогда же С.А. Пироговым был придуман пример, показывающий, что условие унитарности не является необходимым условием существования и единственности равновесия. Отметим, что приблизительно в то же время сотрудники ИППИ РАН А.Н. Рыбко, С.Б. Шлосман, А.А. Владимиров изучали макросистемы, пришедшие из теории сетей массового обслуживания, в которых в результате всех предельных переходов возникает не равновесие, а некоторые предельные процессы. Это важное обстоятельство подчеркивает некоторую частность изучаемого нами объекта – концепции равновесия макросистемы. Другими словами, совсем не обязательно у динамической системы, задаваемой эргодическим марковским процессом, с огромным числом состояний на больших временах будет наблюдаться что-то похожее на равновесие.

В диссертации получено условие, обеспечивающее существование и единственность равновесия, отличное от условия унитарности. Полученное условие также не является необходимым. Также в диссертации объясняется (в общем случае), почему получилась такая завязка функции Ляпунова детерминированной динамики, полученной при скейлинге, на функцию характеризующую поведение инвариантной меры. Кроме этого, в работе показывается, что при весьма естественных условиях время сходимости к равновесию оказывается очень маленьким. Для понимания этого обстоятельства динамика макросистемы представляется в виде случайного блуждания на графе. Далее используются известные способы оценивания времени выхода таких марковских цепей на стационарное распределение, восходящие к работе Дайера–Фрайза–Каннана, 1989.

Работа посвящена приближенному вычислению объема выпуклого тела за полиномиальное время. Отметим, что в свое время эта работа была удостоена премии Фалкерсона.

Наряду с новыми результатами теоретического характера, в диссертации приводятся конкретные примеры макросистем, равновесия которых считаются.

Как правило, все эти примеры мотивированы приложениями, в особенности транспортными.

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

В третье главе новым является эволюционно-макросистемная интерпретация конструкции равновесия Нэша–Вардропа до этого использовавшейся только стационарно. Равновесие Нэша–Вардропа отвечает равновесному распределению потоков на графе транспортной сети. Такая эволюционная интерпретация, среди прочего, позволила усилить известный парадокс Брайеса (1968), отражающий хорошо известный факт, что равновесие по Нэшу не обязано быть оптимальным по Парето. При этом оно может быть устойчивым равновесием Нэша (Э. Мулен, 1985), т.е. разумная динамика наилучших ответов, приводит именно к такому равновесию. А также такая интерпретация позволила объяснить (мотивируя) эвристический способ отбора Бар-Гира–Швецова (2010) единственного равновесия Нэша–Вардропа в случае, когда имеет место не единственность равновесий.

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

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

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

Заметим, что именно эволюционность (наличие фактора времени) в изучении макросистем отличает наш подход от широко распространенного подхода анализа стационарно заданных макросистем (В.П. Маслов, Ю.С. Попков). Под “стационарно заданными” мы имели в виду, что инвариантная мера определяется исходя из каких-либо разумных соображений, например, симметрии.

Другой пример необходимости введения динамики, дают макросистемы, имеющие игровую природу, т.е. равновесие в этих системах может быть проинтерпретировано, как равновесие Нэша. Введение динамики позволяет, в случае если таких равновесий много, выбрать единственное. Важно отметить, что процедура отбора как раз и включает в себя использование концепции равновесия макросистемы. Именно это обстоятельство и отличает предложенную процедуру от ряда других.

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

Хотелось бы также обратить внимание на обнаруженную в диссертации “двойственность” энтропийно-подобного функционала. Этот функционал выступает как функция Ляпунова детерминированной кинетической динамики, полученной в результате скейлинга из исходно стохастической динамики макросистемы, а также как функция характеризующая концентрацию инвариантной меры (подобно неравенствам о больших уклонениях в теории вероятностей) той же самой стохастической динамики. Это наблюдение выглядит перспективно с точки зрения с возможности характеризовать (изучать) аттракторы диссипативных динамических систем, с помощью множества концентрации инвариантной меры стохастической макросистемы, породившей изучаемую детерминированную диссипативную систему.

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

Публикации. По материалам диссертации опубликовано 33 печатные работы (среди которых 4 статьи из списка ВАК, одна монография, одно учебное пособие и один электронный препринт, выложенный на arxiv.org).

Апробация работы. Результаты работы докладывались на нескольких десятках конференций, среди которых 10 международных конференций (в том числе в качестве приглашенного пленарного докладчика), а также семинаре ВЦ РАН И.С. Меньшикова (2009), семинаре-конференции по трафику РАН под рук.

акад. В.В. Козлова в Президиуме РАН (2010), в МФТИ на Стохастическом семинаре кафедры МОУ ФУПМ (2011), в Независимом Московском Университете на Транспортном семинаре и на семинаре Стохастический анализ в задачах (2012).

Структура и объм диссертации. Диссертация состоит из введения, трх глав, двух приложений и списка литературы. Общий объм работы составляет страниц, включая список литературы из наименований.

Во введении сформулированы цели работы, обосновывается е актуальность, дан краткий обзор работ связанных с темой диссертации, приводятся основные результаты и их предпосылки.

В главе 1 вводится понятие равновесия макросистемы, приводится ряд примеров, формулируются общие теоремы.

В начале главы разбираются мотивировочные примеры. Приведем некоторые из них.

Пример. PageRank Хорошо известно, что поисковая система Google была создана в качестве учебного проекта студентов Стэнфордского университета Лари Пейджа и Сергея Брина. В 1996 году они работали над поисковой системой BackRub, а в году на е основе создали новую поисковую систему Google. Ими был предложен определенный способ ранжирования web-страниц. Этот способ, также как и довольно большой класс задач ранжирования возникающих, например, при вычислении индексов цитирования ученых или журналов, сводится к нахождению левого собственного вектора pT некоторой стохастической матрицы P :

pT pT P. Обоснование этому дает теория цепей А. А. Маркова (1906). Точнее, эргодическая теорема для конечных однородных неразложимых (из любого состояния со временем с не нулевой вероятностью можно попасть в любое другое) и апериодических марковских цепей (для справедливости последнего утверждения выполнение условия апериодичности не требуется):

pT 1 lim pT n pT (все вектора являются распределениями вероятностей);

Цель настоящего примера предложить другое обоснование ранжирующему вектору p ( pT pT P ), базирующееся на концепции равновесия макросистемы.

Имеется ориентированный граф G V, E сети Интернет (вершины – webстраницы, ребра – ссылки: запись i, j E означает, что на i -й странице имеется ссылка на j -ю страницу), M – число пользователей сети (это число не меняется со временем, M V 1), P 1 E P, где E – единичная матрица, pij k : i, k E, i j, иначе = 0, 0,1 (часто полагают 0.85 ).

Пусть ni t – число посетителей web-страницы i в момент времени t. За один такт времени каждый посетитель с вероятностью pij переходит по ссылке на web-страницу j. Считаем стохастическую матрицу P неразложимой и апериодической. Ниже приведен основной результат, позволяющий по-другому интерпретировать вектор p (PageRank): pT pT P, согласно которому и происходит ранжирование web-страниц.

где p p P (решение единственно в классе распределений вероятностей в виду неразложимости). При этом здесь для удобства считаем p1 p2... pV.

Сделаем одно полезное в дальнейшем замечание. Осуществим в уравнении Колмогорова–Чэпмена (формуле полной вероятности), задающем марковскую динамику в дискретном времени, pT n 1 pT n P предельный переход к непрерывному времени (скейлинг): шаг по времени t 0 и pij : ij t, i j.

Тогда уравнение Колмогорова–Чэмпена перейдет в уравнение:

где ij ij при i j (интенсивности переходов) и ii ij, i 1,..., n.

Матрицу называют инфинитезимальной матрицей. Асимптотика по времени и числу агентов (в рассмотренном выше примере это число пользователей) решений именно такого типа СОДУ и есть предмет дальнейших исследований.

Заметим, что в рассматриваемых нами далее макросистемах, при задании инфинитезимальной матрицы используется принцип “равноправия агентов”. Впоследствии это будет выражено в (по сути комбинаторных) формулах для интенсивностей переходов. Эти формулы “пришли” из стохастической химической кинетики (агенты = молекулы, возможные переходы – химические реакции).

Заметим также, что эргодическая теорема для марковских процессов в непрерывном времени упрощается – исчезает условие апериодичности.

Важно заметить, дабы не возникло путаницы, что если мы захотим выписать уравнение Колмогорова–Фллера для PageRank модели, то размерность этой системы (вектора p t ) будет существенно выше M. Поскольку состоянием марковского процесса будет определенный способ распределения M одинаковых пользователей по V различным web-страницам.

Пример. Обобщение энтропийной модели А.Дж. Вильсона расчета матрицы корреспонденций В некотором городе имеется n районов, Li 0 – число жителей i -го района, W j 0 – число работающих в j -м районе (число рабочих мест), x ij t 0 – число жителей, живущих в i-м районе и работающих в j-м в момент времени t 0. Со временем пронумерованные жители (количество которых не меняется и равно M Li W j ) меняют места жительства (квартиры). Считается, что отмеченные изменения могут происходить только за счт обмена квартирами, т.е.

Пусть в момент времени t 0 r-й житель живет в k-м районе и работает в m-м, а s-й житель живет в p-м районе и работает в q-м. Тогда k,m; p,q t t o t – есть вероятность того, что жители с номерами r и s (1 r s M ) поменяются квартирами в промежутке времени t, t t.

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

Например, можно считать, что расстояние от района i до района j есть lij 0, а где коэффициент 0 характеризует интенсивность обменов, функция R l l ln l 2, 0, 0 (заметим, что при весьма общих предположениях считают, что 1), 0 отражает затраты в пути (первое слагаемое) и, одновременно, возможность найти подходящую работу на расстоянии порядка l от места жительства: чем больше l, тем больше территория для поиска 2 ll, тем больше вероятность успеха (найти подходящую работу), тем меньше должны быть затраты R l (второе слагаемое). В классической статической энтропийной модели (второй половины 60-ых годов XX века) А. Дж.

Вильсона 0. Однако по Москве наблюдается заметно лучшее соответствие реальных данных рассматриваемой модели, если допускать 0, и оптимально его подбирать.

Согласно эргодической теореме:

где статсумма Z находится из условия нормировки получившейся “пуассоновской” вероятностной меры. Отметим, что стационарное (инвариантудовлетворяет условию детального равновеное) распределение p xij сия (частный случай более общего условия инвариантности):

xkm 1 x pq 1 p x11,..., xkm 1,..., x pq 1,..., x pm 1,..., xkq 1,..., xnn k,m; p,q Распределение p xij (см. ниже) в окрестности наиболее вероятного значения xij ходится, как решение задачи энтропийно-линейного программирования:

Решение этой задачи можно представить как ляются из равенств системы (A). На практике мы имеем информацию о Li,Wi i1 и lij i1, j 1. Решив задачу (A), мы найдем Такой способ расчета матрицы корреспонденций с 0 в литературе часто называют (энтропийной) гравитационной моделью:

Приведем теперь оценку концентрации стационарного распределения предварительно, введем такую перестановку ij, что xij1 xij 2... xij n2, а затем введем обозначение nk t xij k t, k 1,..., n2.

Предположим, что некоторая макросистема может находиться в различных состояниях, характеризуемых вектором с неотрицательными целочисленными компонентами. Будем считать, что в системе происходят случайные превращения (химические реакции). Пусть n n,, J – все возможные типы реакций (конечный набор). Введем, следуя М. А. Леонтовичу (1935), интенсивность реакции:

где K 0 – константа реакции (в общем случае K n – функция, см. например, п. в) теоремы 1). При этом часто считают i ni t M. Таким образом, n – вероятность осуществления в единицу времени перехода n n. На макроуровне все это соответствует принципам химической кинетики (закон действующих масс Гульдберга–Вааге, 1864).

Следующая теорема отображает (немного уточняя) известные результаты а) В. В. Веденяпина (1999), б) В. А. Малышева, С. А. Пирогова, А. Н. Рыбко (2004) и в) обобщает результаты В. Вайдлиха (2000) и др. на случай, когда рассматривается более общая схема, чем модель миграции населения.

тогда и только тогда, когда вектор ортогонален каждому вектору семейства.

б) Пусть выполняется условие унитарности или динамического равновесия, которое, следуя В.В. Веденяпину, будем далее называть условием Штюкельберга–Батищевой–Пирогова:

Тогда мера n i i ni ei ni !, где i i*M, а * – произвольное решение (ШБП), будет инвариантной относительно предложенной стохастической марковской динамики. Эта мера на множестве (inv) экспоненциально быстро концентрируется, с ростом M, в окрестности наиболее вероятного состояния, которое и принимается за положение равновесия макросистемы. Задача поиска наиболее вероятного макросостояния асимптотически эквивалентна задаче максимизации энтропийного функционала (воспользовались формулой стве, задаваемом условием (inv). Отметим, что условие (ШБП), называемое также условием унитарности, обобщает хорошо известное в физике и экономике условие детального равновесия:

риантной относительно предложенной стохастической марковской динамики.

Эта мера экспоненциально быстро концентрируется, с ростом M ni t, в окрестности наиболее вероятного состояния, которое и принимается за положение равновесия макросистемы. Задача поиска наиболее вероятного макросостояния асимптотически эквивалентна задаче максимизации энтропийного типа функционала:

на множестве, задаваемом условием (inv).

Замечание. В пунктах б) и в) предполагалось, что марковский процесс неразложим (неприводим) в классе (inv): из любого состояния можно со временем прийти в любое другое (по-прежнему оставаясь на множестве (inv)). Отсюда следует единственность инвариантной меры. Это условие не выполняется, например, для хорошо известной модели хищник–жертва, в которой имеется поглощающие состояния: без хищников.

Схема доказательства п. б). Будем считать, что ограничения (законы сохранения) (inv) задаются системой ( ) : An d, где A Akl – матрица максимального ранга. Обозначим через множество неотрицательных целочисленных векторов n, удовлетворяющих An d. Тогда равновесие n* ni* нахоm дится как решение задачи E n max (поскольку функционал строго вогнуn( ) тый и считаем ni* 1, то целочисленностью переменных можно пренебречь – то есть произвести релаксацию задачи). Используя принцип Лагранжа, можно показать, что решение этой задачи представляется в виде где двойственные переменные (множители Лагранжа) y * определяются из системы An y d. Исследуем концентрацию меры p ni i 1 в окрестности наиm более вероятного значения ni*. Для этого, прежде всего, заметим, что из опm ределения n Поэтому Следовательно, приходим к «неравенству о концентрации меры»:

Отметим, что ряд макросистем, рассмотренных в главе 1, демонстрирует ситуацию, когда число состояний m dim n и число реакций J растут вместе с ростом числа агентов M. Это обстоятельство, равно как и зависимость K n, не позволяет напрямую использовать аппарат, разработанный в статьях Батищевой–Веденяпина (2005), Малышева–Пирогова–Рыбко (2004), связанный с анализом системы обыкновенных дифференциальных уравнений, возникающей при каноническом скейлинге (см. ниже) стохастической марковской динамики. Отметим также, что в приведенных выше рассуждениях нам даже не потребовалось существование при термодинамическом предельном переходе M, J “ненулевого” (“близкого к равномерному”) финального распределения. Как следствие концентрация получилась не такая плотная, как в моделях, в которых это условие выполняется (см., например, модель Вильфредо Парето “Кинетика социального неравенства”).

Пусть теперь m dim n и число реакций J не зависят от числа агентов M, и в начальный момент времени t 0 для любого i существует предел ci 0 lim ni 0 M. Тогда в произвольный момент времени t 0 для любого i существует не случайный предел ci t lim ni t M. Описанный выше прим называется каноническим скейлингом. В результате такого скейлинга приходим к «динамике квазисредних» (терминология В. Вайдлиха):

Это технически нетривиальное утверждение следует из результатов Т.Г. Куртца (1986).

Систему (ДК) можно получить и по-другому. А именно, как приближенную динамику средних ci t E ni t M. Приближенную в том смысле, что при выводе (ДК) используется приближение: F ci t E F ni t M для «достаточно хороших» функций F (например, полиномов). Это верно в случае пикообразного распределения ni t.

Можно показать (следуя Батищевой–Веденяпину, 2001), что если выполняются условия (ШБП), то траектория (ДК) сходится к неподвижной точке.

Какой именно, зависит, вообще говоря, от «точки старта»; но можно сказать и точнее: к той единственной неподвижной точке из семейства неподвижных точек, которая принадлежит аффинному многообразию (inv), инвариантному относительно (ДК). Для этого, вводится (минус) энтропия:

и показывается, что она является функцией Ляпунова для системы (ДК). Обратим внимание, что инвариантная мера n (при каноническом скейлинге) “породила” функцию Ляпунова H c. Подобные закономерности наблюдаются для рассматриваемых моделей и без условия (ШБП).

Теорема 2. Пусть инвариантная вероятностная мера представляется в функция. Тогда H c – функция Ляпунова системы (ДК).

Схема доказательства. Введем производящую функцию (А.В. Калинкин, 2002):

на которую можно выписать следующее уравнение в частных производных:

Отметим, что если взять частные производные si от обеих частей (УЧП), полагая s 1,...,1, то получим в пределе при M (попутно считая, что существуют пределы lim ni t M, см. п. в) теоремы 1) систему (ДК). ПоскольM где s определяется, притом единственным образом, из системы ln s grad H, а C 0 – не зависит от (воспользовались методом Лапласа асимптотического оценивания интеграла). Следовательно, – полная производная функции H c в силу системы (ДК) в точке s.

Естественно теперь задаться над вопросом: А что будет, если условия (ШБП) не выполняются, однако система (ДК) имеет на внутренности пересечения неотрицательного ортанта и инвариантного аффинного многообразия (inv) единственную неподвижную точку? Оказывается, имеет место Теорема 3. Если эта точка экспоненциально глобально устойчива, то 1) все законы сохранения (ДК) определяются (inv); 2) около положения равновесия инвариантная мера будет экспоненциально быстро концентрироваться (с ростом M ); 3) скорость сходимости к равновесию (mixing time) оценивается как poly M ; 4) элементы корреляционной матрицы случайного вектора n t равномерно ограничены по времени; 5) предельные переходы lim и lim перестановочны: lim lim lim lim.

Обратим внимание, что модель хищник–жертва является хорошим примером того, что может быть, если не выполняется условие устойчивости равновесия. В этой модели аттрактором (ДК) является цикл, которому соответствует инвариантная мера вида “кратера вулкана”. Однако, как уже было ранее отмечено, lim и lim не перестановочны.

Результаты главы 1 и ряда других работ наталкивают на гипотезу: аттрактор динамической системы (ДК), который как мы отмечали выше может быть сколь угодно сложным множеством (например, в приложениях типичны случаи предельных циклов, нескольких положений равновесия, и даже хаотических аттракторов), является таким множеством, в малой окрестности которого на больших временах с большой вероятностью будет пребывать рассматриваемая макросистема.

Причем тут возможны разные варианты поведения. Например, в случае двух притягивающих равновесий динамика системы “притянется” к каждому из них с вероятностями, зависящими от точки старта, и далее система может пребывать в малой окрестности равновесия длительное время, до большой флуктуации (вероятность такой флуктуации может быть ничтожна мала на фиксировано конечном временном отрезке), которая сможет перебросить е в другое положение равновесия (Вентцель–Фрейдлин, 1979). Другой тип поведение: постоянно циркулировать (перемешиваться) по аттрактору. Возможен, конечно, и симбиоз отмеченных типов поведения.

В главе 2 исследуется способы численного решения задачи энтропийнолинейного программирования. Напомним (см. главу 1), что именно к таким задачам часто сводятся задачи поиска равновесия макросистемы.

Рассматривается общая задача энтропийно–линейного программирования:

Для отыскания единственного решения (ЭЛП) было предложено семейство двойственных барьерно-мультипликативных итерационных алгоритмов, которое содержит алгоритмы Брэгмана–Шелейховского, MART, GISM, Ю. С. Попкова и др.:

нулю в нуле. Например, часто выбирают Однако, как правило, разумно (с точки зрения эффективности счета) обнулять на каждом шаге большую часть случайно выбранных компонент этих векторов, причем вероятностный отбор осуществляется исходя из текущего состояния итерационного процесса (отметим, что согласно алгоритму Кнута–Яо, задача разыгрывания случайной величины, принимающей n различных значений требует в среднем log 2 n 1 2 подбрасываний симметричной монетки, значит может быть довольно быстро решена), при этом после обнуления большинства компонент и соответствующего вытягивания по оставшимся (чтобы сохранить приблизительно длину) получившейся вектор должен быть довольно близким к градиенту. То есть разумно осуществлять в двойственном пространстве своеобразный стохастический субградиентный спуск.

Глобальная сходимость итерационного процесса была установлена в при следующих предположениях:

2) Строки матриц T и G линейно независимы в совокупности.

При этом было замечено, что предположение 2 не всегда выполняется в прикладных задачах (см., например, модель ранжирования web-страниц Дж.А.

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

Итерационные алгоритмы (ИП) особенно эффективны:

для сильно разреженных матриц T и G ;

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

Текст соответствующих компьютерных программ, написанных на МаtLab, имеется в приложении 2.

В главе 3 излагается модель Бэкмана равновесного распределения потоков, в которую вводятся две возможные динамики. Исследование возникающих макросистем позволяет глубже понять окрестности понятия равновесия Нэша– Вардропа.

Предварительно опишем модель Бэкмана равновесного распределения потоков на графе транспортной сети.

Ориентированный граф V, E – транспортная сеть города: V – узлы сети (вершины), E V V – дуги сети (рбра графа). Пусть W w i, j : i, j V – множество пар источник – сток; p v1, v2,..., vm – путь из v1 в vm, если k 1,..., m 1, m 1 ; Pw – множество путей, отвечающих корреспонденции w W, то есть если w i, j, то Pw – множество путей, начинающихся в вершине i и заканчивающихся в j ; P wW Pw – совокупность всех x x p : p P ; G p x – удельные затраты (временные, финансовые) на проезд по пути p ; ye [автомобилей/час] – величина потока по дуге e :

e ye – удельные затраты на проезд по дуге e (как правило, возрастающие, выпуклые, гладкие функции), естественно считать, что G p x e ye x ep.

Заметим, что в приложениях часто требуется учитывать и затраты на прохождения вершин графа, в свою очередь, эти затраты могут зависеть от величин всех потоков, по путям, проходящим через рассматриваемую вершину. Пусть также известна матрица корреспонденций d w, w W. Тогда вектор x, характеризующий распределение потоков, должен лежать в допустимом множестве:

Это множество может иметь и другой вид, если дополнительно учитывать, например, конечность пропускных способностей рбер (ограничения сверху на ye ).

Рассмотрим игру, в которой каждому элементу w W соответствует свой, достаточно большой ( d w 1), набор однотипных “игроков”, “сидящих на корреспонденции w ”. Множеством чистых стратегий каждого такого игрока является Pw, а выигрыш (потери со знаком минус) определяются формулой G p x.

Игрок “выбирает” путь следования p Pw, при этом он пренебрегает тем, что от его выбора также “немного” зависят Pw компонент вектора x и, следовательно, сам выигрыш G p x. Можно показать, что отыскание равновесия Нэша– Вардропа x * X (макро описание равновесия) равносильно решению задачи нелинейной комплементарности (принцип Вардропа):

Действительно допустим, что реализовалось какое-то другое равновесие x* X, которое не удовлетворяет этому условию. Покажем, что тогда найдется водитель, которому выгодно поменять свой маршрут следования. Действительно, тогда Каждый водитель (множество таких водителей не пусто x* 0 ), принадлежаp щий корреспонденции w W, и использующий путь p Pw, действует не разумно, поскольку существует такой путь такой путь q Pw, q p, что Gq x * min Gq x *. Этот путь q более выгоден, чем p. Аналогично показыqPw вается, что при x * X никому из водителей уже не выгодно отклоняться от своих стратегий. Но это по определению и называется равновесием Нэша, которое ввел в своей кандидатской диссертации в коне 40-х годов XX века Джон Нэш, получивший именно за эту концепцию в 1994 г. нобелевскую премию по экономике. Мы также добавляем фамилию Дж.Г. Вардропа, которой чуть позже Нэша привнес к этой концепции условие “конкурентного рынка”: игрок, принимающий решение, пренебрегает тем, что его решение сколько-нибудь значительно поменяет ситуацию на “рынке”. Когда игроков двое, трое (ситуации, рассматриваемые Нэшем), то, очевидно, что так делать нельзя. Но когда игроков (водителей) десятки и сотни тысяч … Все эта конструкция неявно предполагает, что x* 0 x* 1. Поэтому, не боясь сильно ошибиться, можно искать решение задачи нелинейной комплементарности, не предполагая целочисленности компонент вектора x * X. Такая релаксация изначально целочисленной задачи заметно упрощает е с вычислительной точки зрения!

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

Для этого, прежде всего, заметим, что рассматриваемая нами игра принадлежит к классу, так называемых, потенциальных игр. В нашем случае это ознаpP ep x p чает, что существует такая функция x e z dz, что x x p Gp x для любого p P. Оказывается, что x * X – равновесие Нэша–Вардропа тогда и только тогда, когда оно доставляет минимум x на множестве X. Действительно, предположим, что x * X – точка минимума.

Тогда, в частности, для любых w W, p, q Pw ( x* 0 ) и достаточно маленькоp го x p 0 выполняется:

Иначе, заменив x * на мы пришли бы к вектору x, доставляющему меньшее значение x на множестве X :

Вспоминая, что x x p Gp x, и учитывая, что q можно выбирать произвольно из множества Pw, получаем:

Но это и есть по-другому записанное условие нелинейной комплементарности.

Строго говоря, мы показали сейчас только то, что точка минимума x на множестве X будет равновесием Нэша–Вардропа. Аналогично рассуждая, можно показать и обратное: равновесие Нэша–Вардропа доставляет минимум x на множестве X. Таким образом, мы имеем дело с потенциальной игрой.

Введем теперь в эту стационарную модель динамику. Пусть свой путь на n 1 -м шаге игрок, сидящий на корреспонденции w, выбирает согласно смешанной стратегии (в независимости от всех остальных): с вероятностью выбрать путь p Pw ( 0 n 1 ), а с вероятностью 1 n – действовать согласно стратегии, использованной на предыдущем n-м шаге. Здесь x p n – количество игроков, сидящих на корреспонденции w и выбравших на n -м шаге стратегию характеризует желание имитировать, а также надежность использования этой стратегии. Параметр характеризует «консерватизм» («ленивость»), чем меньше, тем более консервативный игрок; «температура» T характеризует отношение к риску («горячность»), чем больше температура, тем более «горячий игрок», склонный к более рискованным действиям.

Как показали разнообразные численные эксперименты, часто вполне разумно выбирать n 1 n. При таком выборе n наблюдается сходимость к равновесию Нэша–Вардропа при наиболее общих условиях относительно T (вне зависимости от точки старта). Стоит также обратить внимание на высокую эффективность предложенной процедуры «нащупывания равновесия» с точки зрения количества итераций. Иначе говоря, на предложенный итерационный процесс можно смотреть просто как на эффективный способ численного нахождения равновесия Нэша–Вардропа. В экспериментах со студентами 5-го курса ФУПМ, проведенных несколько лет назад в Лаборатории Экспериментальной экономики ФУПМ МФТИ, также наблюдалась сходимость к равновесию и колебания около него. Колебания можно объяснить, например, тем, что n.

Предложенную схему можно трактовать как стохастическую динамику наилучших ответов в эволюционной (популяционной) игре, при этом имеется много общего с концепциями «quantal response equilibria» (используется похожая рандомизация) и «minority games» (наблюдаются похожие колебания около положения равновесия). Близкой к предложенному итерационному процессу является концепция генетических алгоритмов и эффективный приближенный вероятностный алгоритм Григориадиса–Хачияна, являющийся предтечей современных исследований по методу стохастического зеркального спуска.

Имеет место следующее утверждение, при доказательстве которого активно используется недавняя работа Немировского–Юдитского–Шапиро и др.

по стохастическому зеркальному спуску.

Если равновесие x единственно, то x x 0 x.

Пример (парадокс Брайеса, 1968). Пусть корреспонденция x14 6 (тысяч автомобилей/час). Вес ребра (удельные затраты на проезд по этому ребру) есть время движения по ребру (в минутах), если поток через ребро есть yij (тысяч автомобилей/час). Например, в случае 2: y24 x124 x1324 (см. рис. 1).

Естественно считать, что время движения – возрастающая функция потока.

Оба равновесия Нэша–Вардропа (в случаях 1 и 2) являются «притягивающими» положениями равновесия описанной выше динамики (положили 1, T 15 35 ), см. рис. 2–4 (для случая 2).

Кажется удивительным, но в парадоксе Брайеса в случае строительства “паразитной” дороги участники движения, действуя согласно описанной выше динамики (каждый преследует свои интересы), действительно “приходят” к единственно возможному “плохому” равновесию Нэша–Вардропа – не оптимальному по Парето. Такие ситуации уже давно наблюдались в реальной жизни (например, в Германии и Голландии). Пару лет назад был поставлен эксперимент, описанный в приложении 1, на базе парадокса Брайеса над студентами 5го курса физтеха в Лаборатории экспериментальной экономики ФУПМ МФТИ, который подтвердил, что после введения “паразитной” дороги, водители– студенты сходились, причем довольно быстро, к “плохому” равновесию и пребывали там большую часть времени эксперимента.

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

К сожалению, в случае не единственности равновесия, предложенная динамика ничего не говорит о том, какому из равновесий стоит отдавать предпочтение, то есть оно с большей вероятностью реализуется. Причина в том, что появляется зависимость от точки старта x * x 0. Чтобы разобраться с этой ситуацией, сначала рассмотрим из-за чего может возникать не единственность.

В виду ограниченности и замкнутости множества X из того, что равновесие Нэша–Вардропа доставляет минимум x на множестве X сразу следует:

равновесие Нэша–Вардропа всегда существует. Более тонко обстоит дело с единственностью. Далее мы приведем лишь достаточные условия. Если для любого e E имеет место e функция. Следовательно, равновесие y *, как точка минимума V y, – единственно. Отметим, что это еще не означает единственность равновесия x *, что демонстрирует следующий пример.

Пример (пенсне В.И. Швецова). На рис. 2 показано равновесное распределение потоков для любого значения параметра x 0, 0.5 и любой строго монотонной функции затрат, одинаковой для всех дуг графа. Обратим внимание, что здесь, как и во многих других модельных примерах, для наглядности умышленно нарушают условие x* 0 x* 1.

Предположим, теперь что свой путь на n 1 -м шаге игрок, сидящий на корреспонденции w, выбирает согласно смешанной стратегии (в независимости от всех остальных): с вероятностью выбрать путь p Pw ( 0 1), а с вероятностью 1 – действовать согласно стратегии, использованной на предыдущем n-м шаге. Здесь Z nw находится из условия нормировки. Это хорошо известное logit-распределение или распределение Гиббса в статистической физике. Оно может быть проинтерпретировано, как выбор каждым игроком наилучшей стратегии вчерашнего дня, если игрок “переносит” затраты вчерашнего дня G p x n на день сегодняшний, но допуская при этом случайные флуктуации Gp x n p, где p – независимые случайные величины, имеющие одинаковое двойное экспоненциальное распределение, также называемое распределением Гумбеля. Это распределение возникает именно в таком контексте совсем не случайно, и связано это с тем, что оно max-устойчиво. Тогда тот p Pw, который доставляет минимум Gp x n p как раз имеет указанное выше logit-распределение.

Оказывается, имеет место следующий факт. Если для любого e E имеет место 0, то введенная стохастическая динамика “сходится” на больших временах к некоторому стационарному, не изменяющемуся со временем, распределению вероятностей на множестве X. Это распределение вероятностей называют «стохастическим равновесием в транспортной сети». В предположении, что T 0 и 0 – должным образом малы, это стационарное распределение сконцентрировано в малой окрестности такого равновесия Нэша–Вардропа:

где y * – единственное решение задачи Скажем, в примере, В.И. Швецова это равновесие, в котором на каждом из 4-х возможных путей одинаковый поток 0.25.

В заключение скажем (во многом следуя У. Сэндхольму, 2002) несколько слов о платных дорогах, которые, на наш взгляд, могут частично решить проблему пробок в Москве, подобно Сингапуру. В перспективе плату за проезд по дорогам можно будет рассчитывать исходя из информации о треках автомобилей. Планируется оснастить все автомобили GPS (ГЛОНАСС) навигаторами, позволяющими определять каждые 5 минут положения автомобиля с точностью до нескольких десятков метров. Каждая дорога имеет свой тариф: за разовый проезд по дороге начисляется плата, подобно плате за разговор по мобильному телефону. В конце месяца приходит счет.

Введем Центр (государство). Обозначим через eс плату (штраф), взимаемую с каждого водителя за проезд по ребру e. Положим с eс : e E. После того, как игрок Центр выбирает ту или иную допустимую стратегию с, издержки на маршрутах, вообще говоря, возрастают что приводит к перераспределению потоков по маршрутам: изменению рядом игроков–водителей своих стратегий (маршрутов). Это перераспределение потоков происходит до тех пор, пока не будет достигнуто новое равновесное распределение по путям x * с ( y* с по дугам). Этому равновесию соответствуют свои суммарные издержки всех пользователей сети в единицу времени Задача Центра так подобрать с, чтобы Вектор x opt – называют системным оптимумом. Естественно, что в системном оптимуме системе “не хуже”, чем в равновесии. Насколько большой может быть “цена анархии” зависит от того, как себя ведут функции e ye, и “не зависит” от размеров графа транспортной сети. Далее приводятся (следуя Т. Роугардену, 2002), в ряде случаев не улучшаемые, оценки сверху для цены анархии (оценка цены анархии приводится для худшего случая, который во всех случаях достигается на графах с небольшим числом вершин):

На практике довольно часто отдают предпочтение функциям вида:

называемым BPR-функциями.

Несложно заметить, что решить задачу Центра с единственным ограничением с 0 оказывается довольно не сложным делом. Причем решение с оказывается не единственным и может оказаться довольно большим. Однако здесь не учитывается, что назначая непомерно большие платы за проезд, мы вынуждаем пользователей вообще отказаться от перемещений на данном виде транспорта (личных автомобилях). В принципе, это тоже один из способов побороть пробки (оптимально расщеплять потоки по типам перемещений), но тогда нужно предложить альтернативу, в виде общественного транспорта или велосипедных дорожек. Примечательно во всем этом то, что платы достаточно (можно) взимать с дуг (дорог), а не с путей. Это крайне важно для практики и, вообще говоря, сразу может быть и не очевидно!

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

2. Рассмотрен один пример введения динамики в макросистему, имеющую игровую природу, т.е. равновесие в этой макросистеме может быть проинтерпретировано, как равновесие Нэша. Введенная динамика позволяет, в случае если таких равновесий много, выбрать единственное. Важно отметить, что процедура отбора как раз и включает в себя использование концепции равновесия макросистемы.

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

4. Предложено обобщение и новая интерпретация известной энтропийной модели расчета матрицы корреспонденций и модели ранжирования webстраниц PageRank. Также была обобщена модель миграции населения.

5. Единообразно представлены многие известные алгоритмы решения задач энтропийно-линенйого программирования (Брэгмана–Шелейховского, MART, GISM, Ю.С. Попкова и др.), возникающие при поиске равновесий Гасникова Е.В. Двойственные мультипликативные алгоритмы для задачи энтропийнолинейного программирования // Труды 50-й научной конференции МФТИ. Современные проблемы фундаментальных и прикладных наук. Москва – Долгопрудный, 2007 г. Ч. 7.

Т. 1. С. 106-109.

Гасникова Е.В. Барьерно-мультипликативные алгоритмы для двойственных задач // Конференция молодых ученых и специалистов «Информационные технологии и системы ИТиС'08». 29 сентября – 3 октября 2008 года, г. Геленджик. С. 423-429.

http://www.iitp.ru/upload/content/340/itas08_proceedings.pdf Гасникова Е.В. Барьерно-мультипликативные алгоритмы для задач, двойственнх к задачам оптимизации энтропийно подобных функционалов на выпуклых множествах простой (аффинной) структуры // Труды 51-й научной конференции МФТИ. Современные проблемы фундаментальных и прикладных наук. Москва – Долгопрудный, 2008 г. Ч. 7.

Гасникова Е.В. Поиск равновесий макросистем с помощью мультипликативнобарьерных модификаций итерационных алгоритмов Коши и Ньютона // Международная конференция «Математическая теория систем» МТС-2009» 6 – 30 января 2009 года, Москва. С. 150-154.

Гасникова Е.В. Двойственные мультипликативно-барьерные алгоритмы отыскания вырожденных равновесий макросистем // Международная конференция «Современные проблемы математики, механики и их приложений» 30 марта – 02 апреля 2009 года МГУ, Москва. С. 317.

Гасникова Е.В. Двойственные мультипликативные алгоритмы для задач энтропийнолинейного программирования // ЖВМ и МФ Т.49 № 3 2009 г. С. 453-464. ВАК http://www.mathnet.ru/links/477d9abf29f4617e2884d66705be0b39/zvmmf22.pdf Гасников А.В., Гасникова Е.В. О принципе максимума энтропии в сетевых моделях // Тезисы докладов IV Всероссийской научной конференции «Математическое моделирование развивающейся экономики и экологии» (ЭКОМОД-2009), Киров, 6 – 12 июля 2009.

Киров: Изд-во ВятГУ, 2009. С. 38.

Гасников А.В., Гасникова Е.В. О принципе максимума энтропии в модели (А.Дж. Вильсона) расчета матрицы корреспонденций // Сборник трудов IV Всероссийской научной конференции «Математическое моделирование развивающейся экономики» (ЭКОМОДКиров, 6-12 июля 2009. Киров: Изд-во ВятГУ, 2009. С. 110-121.

Гасников А.В., Гасникова Е.В., Дорн Ю.В. О некоторых примерах конечных однородных эргодических марковских процессов с огромным числом состояний // Труды 52-ой научной конференции МФТИ, Москва – Долгопрудный, 2009. Ч. 7. Т. 1. С. 19-22.

Буслаев А.П., Гасников А.В., Гасникова Е.В., Холодов Я.А., Яшина М.В. Возможная динамика в модели Дж. Вардропа. Труды VI международной конференции по исследованию операций. М.: МАКС Пресс. 19-23 октября 2010. С. 22-23.

Гасникова Е.В. О равновесиях макросистем. Труды VI международной конференции по 11.

исследованию операций. М.: МАКС Пресс. 19-23 октября 2010. С. 139-140.

Гасников А.В., Гасникова Е.В. О возможной динамике в модели расчета матрицы корреспонденций (А.Дж. Вильсона) // Труды МФТИ (специальный выпуск, посвященный математическому моделированию транспортных потоков, под ред. акад. В.В. Козлова), Т.

2. № 4(8). 2010. С. 45-54. ВАК http://mipt.ru/nauka/trudy/N+4+%288%29/Pages_45-54_from_Trud-8-7-arpgtk3kdie.pdf Гасникова Е.В, Дорн Ю.В. О стохастической марковской динамике, приводящей к равновесию Нэша – Вардропа в модели распределения потоков // Труды МФТИ (специальный выпуск, посвященный математическому моделированию транспортных потоков, под ред.

акад. В.В. Козлова), Т. 2. № 4(8). 2010. С. 55-57. ВАК http://mipt.ru/nauka/trudy/N+4+%288%29/Pages_55-57_from_Trud-8-8-arpgtk3wgmt.pdf Гасникова Е.В. О социально-экономических приложениях уравнений стохастической 14.

химической кинетики, динамике средних и динамике, полученной в результате скейлинга // Труды 53-й научной конференции МФТИ, Москва – Долгопрудный, 2010. Ч. 7. Т. 1.

Гасникова Е.В. О стохастической марковской динамике наилучших ответов, приводящей 15.

к равновесию Нэша–Вардропа // Труды 53-й научной конференции МФТИ, Москва – Долгопрудный, 2010. Ч. 7. Т. 1. С. 106-107.

Введение в математическое моделирование транспортных потоков: учеб. пособие / Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б; Приложения:

Бланк М.Л., Гасникова Е.В., Замятин А.А. и Малышев В.А., Колесников А.В., Райгородский А.М; Учебное пособие. Под ред. А.В. Гасникова – М.: МФТИ, 2010. - 361 с.

http://zoneos.com/traffic/ Гасникова Е.В., Ишманов М.С., Колесников А.В., Нагапетян Т.А. О скорости сходимости 17.

к равновесию макросистемы // Тезисы докладов VI Всероссийской научной конференции «Математическое моделирование развивающейся экономики и экологии» (ЭКОМОДКиров, 27 июня – 3 июля 2011. Киров: Изд-во ВятГУ, 2011, С. 35.

Гасникова Е.В., Нагапетян Т.А. О достаточных условиях существования равновесия 18.

макроситсемы // Тезисы докладов VI Всероссийской научной конференции «Математическое моделирование развивающейся экономики и экологии» (ЭКОМОД-2011), Киров, 27 июня – 3 июля 2011. Киров: Изд-во ВятГУ, 2011, С. 36.

Аввакумов С.Я., Гасников А.В., Гасникова Е.В. О сходимости к равновесию НэшаВардропа // Тезисы докладов Международной научной конференции «Динамические системы, нелинейный анализ и их приложения», Армения (г. Ереван), 10 июля – 17 июля Гасников А.В., Гасникова Е.В., Колесников А.В., Нагапетян Т.А. О концепции равновесия 20.

макросистемы и е приложении к модели равновесного распределения потоков // Труды Международной научной конференции “50 лет ИППИ РАН”, Москва, 25 июля – 29 июля 2011. Москва, 2011. 8 стр. http://www.iitp.ru/ru/conferences/823.htm 21. Gasnikov A.V., Gasnikova E.V., Nagapetyan T.A. On the convergence to one of the NashWardrop's equilibriums // Traffic and granular flow’11. International conference. Moscow, September – 1 October 2011. P. 296-298. Plenary Talk Гасникова Е.В., Аввакумов С.Я. О равновесиях в моделях распределения потоков // Труды VI Всероссийской научной конференции «Математическое моделирование развивающейся экономики и экологии» (ЭКОМОД-2011), Киров, 27 июня – 3 июля 2011. Киров: Изд-во ВятГУ, 2011. С. 111-118.

Гасникова Е.В. О новых условиях существования равновесия макросистемы // Труды VI 23.

Всероссийской научной конференции «Математическое моделирование развивающейся экономики и экологии» (ЭКОМОД-2011), Киров, 27 июня – 3 июля 2011. Киров: Изд-во ВятГУ, 2011. С. 100-110.

Гасникова Е.В. Достаточные условия существования равновесия макросистем // Труды 24.

54-й научной конференции МФТИ, Москва – Долгопрудный, 2011. Ч. 7. Т. 1. С. 64-65.

Гасникова Е.В. Концепция равновесия макросистемы в модели распределения потоков // 25.

Труды 54-й научной конференции МФТИ, Москва – Долгопрудный, 2011. Ч. 7. Т. 1. С.

26. Gasnikova E.V., Nagapetyan T.A. About new dynamical interpretations of entropic model of correspondence matrix calculation and Nash–Wardrop's equilibrium in Beckmann's traffic flow distribution model. Ninth International Conference on Traffic and Granular Flow, 28 September – 1 October 2011. Moscow: Springer, 2011. arXiv:1112.1628v Гасников А.В., Гасникова Е.В., Федько О.С. О возможной динамике в модели ранжирования web-страниц PageRank и модернизированной модели расчета матрицы корреспонденций // Труды МФТИ. 2012. Т. 4. № 2. С. 101-120. ВАК http://ium.mccme.ru/postscript/s12/gasnikov-11.pdf 28. Gasnikov A.V., Gasnikova E.V. A conception of equilibrium of a macrosystem in application to the traffic flow distribution in large transport networks // International Conference "Instabilities and Control of Excitable Networks: From macro – to nano-systems" Dolgoprudny, Moscow Area, RUSSIA, May 25 – 30, 2012. P. 16. Plenary Talk Гасников А.В., Гасникова Е.В., Петрашко Д.И. Макросистемный подход к ранжированию web-страниц // «Информационные технологии и системы – 2012» 35-я конференция молодых ученых и специалистов ИППИ РАН, ПреМоЛаб, СТРАДО. г. Петрозаводск. С.

423-429. http://www.itas2012.iitp.ru/pdf/1569604803.pdf 30. Gasnikov A.V., Gasnikova E.V. Stochastic optimization in the model of correspondences matrix calculation and traffic flow distribution // 21st International Symposium on Mathematical Programming (ISMP 2012). Springer: Berlin, August 19 – 24, 2012. P. 217.

31. Gasnikov A.V., Gasnikova E.V. Stochastic subgradient barrier-multiplicative descent for entropy optimization // International conference OPTIMA-2012. September 23 – 30, 2012. Costa da Caparica, Portugal. P. 91-92.

Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков. Под ред. А.В. Гасникова с приложениями М.Л. Бланка, К.В. Воронцова и Ю.В. Чеховича, Е.В. Гасниковой, А.А. Замятина и В.А. Малышева, А.В. Колесникова, Ю.Е. Нестерова и С.В. Шпирко, А.М. Райгородского, PTV VISSION, с предисловием руководителя департамента транспорта г. Москвы М.С. Ликсутова. М.: МЦНМО, 2012. (изд. 2-е, исправ. и дополн.) Монография Гасников А.В., Гасникова Е.В. Об энтропийно-подобных функционалах, возникающих в 33.

стохастической химической кинетике при концентрации инвариантной меры и в качестве функций Ляпунова динамики квазисредних // Математические заметки. 2012. (отправлена в редакцию) ВАК Гасникова Евгения Владимировна Концепция равновесия макросистемы и е теоретикоигровые аспекты с приложениями к математическому моделированию транспортных потоков Подписано в печать 12.10.2012. Формат 60х90 1/16.

Государственное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ»

141700, Моск. обл., г. Долгопрудный, Институтский пер.,

 
Похожие работы:

«Попов Андрей Николаевич Управление скринингом патологии молочных желез на основе компьютерной радиотермометрии. Специальность: 05.13.01 – Системный анализ, управление и обработка информации Автореферат диссертации на соискание ученой степени кандидата медицинских наук Воронеж – 2006. Тел./Факс: (495) 229-41-83 Ассоциация E-mail: info@radiometry.ru Микроволновой Радиотермометрии Интернет: www.radiometry.ru Работа выполнена в Государственном образовательном учреждении высшего...»

«Матвеев Евгений Леонидович ОПТИМИЗАЦИЯ КВАНТИЛЬНОГО КРИТЕРИЯ ПРИ ВЫПУКЛОЙ ЦЕЛЕВОЙ ФУНКЦИИ С ПОМОЩЬЮ СТОХАСТИЧЕСКОГО КВАЗИГРАДИЕНТНОГО АЛГОРИТМА Специальность 05.13.01 Системный анализ, управление и обработка информации (авиационная и ракетно-космическая техника) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва, 2010 Работа выполнена на кафедре Теории вероятностей Московского авиационного института (государственного технического...»

«Мкртичян Вячеслав Виталиевич МОДЕЛЬ ЗАЩИТЫ ДАННЫХ ОТ НЕСАНКЦИОНИРОВАННОГО КОПИРОВАНИЯ, ОСНОВАННАЯ НА МЕТОДЕ НАБОРНЫХ КЛЮЧЕЙ И ПОМЕХОУСТОЙЧИВОМ КОДИРОВАНИИ, С ПРОТИВОДЕЙСТВИЕМ УГРОЗАМ КОАЛИЦИОННЫХ АТАК НА КЛЮЧИ 05.13.19 - Методы и системы защиты информации, информационная безопасность АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук г. Ростов-на-Дону – 2009 Работа выполнена на кафедре алгебры и дискретной математики факультета математики, механики...»

«Суров Максим Олегович Планирование и стабилизация траекторий неполноприводных динамических систем 05.13.01 – Системный анализ, управление и обработка информации (в технических системах) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург – 2013 Работа выполнена в Национальном исследовательском университете информационных технологий, механики и...»

«Грицутенко Станислав Семенович Управление информационными параметрами аналого-цифровых систем реального времени Специальность 05.13.01 – Системный анализ, управление и обработка информации (промышленность) АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук ОМСК 2011 1 Работа выполнена в ФГБОУ ВПО Омский государственный университет путей сообщения (ФГБОУ ВПО ОмГУПС). Научный консультант доктор технических наук, профессор ЧЕРЕМИСИН Василий Титович....»

«Пономарёв Иван Николаевич МАТЕМАТИЧЕСКИЙ АППАРАТ И ПРОГРАММНЫЕ СРЕДСТВА КОНЦЕПТУАЛЬНОГО ПРОЕКТИРОВАНИЯ Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2007 Работа выполнена на кафедре концептуального анализа и проектирования Московского физико-технического института (государственного университета). Научный руководитель : доктор...»

«Али Мансур Номан Мархуб Экспертная система поддержки принятия решений в интеллектуальной системе экологического мониторинга атмосферного воздуха промышленного региона (на примере г.Новомосковска Тульской области) 05.13.06 – Автоматизация и управление технологическими процессами и производствами (химическая технология, нефтехимия и нефтепереработка, биотехнология) 03.00.16 – Экология (технические наук и) АВТОРЕФЕРАТ Диссертации на соискание ученой степени кандидата технических...»

«Огурцов Евгений Сергеевич МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ИЗЛУЧЕНИЯ И ПРОХОЖДЕНИЯ ЭЛЕКТРОМАГНИТНЫХ ВОЛН В РЕТРАНСЛЯТОРАХ СВЯЗИ 05.13.18 Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Таганрог - 2011 2 Работа выполнена на кафедре Высшей математики Федерального государственного автономного образовательного учреждения высшего профессионального образования Технологического института...»

«ЕЛАЕВА Мария Сергеевна МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ КАПИЛЛЯРНОГО ЗОНАЛЬНОГО ЭЛЕКТРОФОРЕЗА 05.13.18 — математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Ростов-на-Дону 2010 Работа выполнена на кафедре вычислительной математики и математической физики факультета математики, механики и компьютерных наук Южного федерального университета, г. Ростов-на-Дону Научный руководитель...»

«Гильмуллин Ринат Абрекович МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В МНОГОЯЗЫКОВЫХ СИСТЕМАХ ОБРАБОТКИ ДАННЫХ НА ОСНОВЕ АВТОМАТОВ КОНЕЧНЫХ СОСТОЯНИЙ 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Казань – 2009 Работа выполнена на кафедре теоретической кибернетики государственного образовательного учреждения высшего профессионального...»

«РАДЧЕНКО СЕРГЕЙ АЛЕКСЕЕВИЧ ФОРМИРОВАНИЕ И ПОЗИЦИОНИРОВАНИЕ СИСТЕМЫ ОРГАНИЗАЦИОННО-УПРАВЛЕНЧЕСКОГО ПОВЕДЕНИЯ В МНОГОПРОФИЛЬНОЙ КОМПАНИИ Специальность: 05.13.10 – Управление в социальных и экономических системах (экономические наук и) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата экономических наук Ростов-на-Дону – 2007 Диссертация выполнена в ГОУ ВПО Ростовский государственный университет путей сообщения Научный руководитель : доктор технических наук, профессор...»

«Шульгин Максим Сергеевич ПАРАМЕТРИЧЕСКАЯ ИДЕНТИФИКАЦИЯ ЛИНИЙ ЭЛЕКТРОПЕРЕДАЧИ И ТРАНСФОРМАТОРОВ ДЛЯ ЦЕЛЕЙ УПРАВЛЕНИЯ ТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ В ЭЛЕКТРОЭНЕРГЕТИКЕ Специальность 05.13.06 - Автоматизация и управление технологическими процессами и производствами (промышленность) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Иркутск 2013 Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального...»

«ОБЕЙДАТ АТЕФ АХМЕД УПРАВЛЕНИЕ ДОСТУПОМ К ОБЩИМ РЕСУРСАМ В ПИРИНГОВЫХ СИСТЕМАХ Специальности: 05.13.13 - Телекоммуникационные системы и компьютерные сети АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург 2009 2 Работа выполнена в Государственном образовательном учреждении высшего профессионального образования Новосибирский государственный технический университет на кафедре вычислительной техники Научный руководитель : Заслуженный...»

«Есипов Денис Викторович МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ИНИЦИАЦИИ И РАСПРОСТРАНЕНИЯ ТРЕЩИН ГИДРОРАЗРЫВА ПЛАСТА 05.13.18 — Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Новосибирск — 2011 Работа выполнена в Институте вычислительных технологий Сибирского отделения РАН. Научный руководитель : доктор...»

«ЖИТКОВА ЕКАТЕРИНА МИХАЙЛОВНА ЗАДАЧИ ОПТИМИЗАЦИИ ПРОТИВОЭПИДЕМИЧЕСКОЙ ПРОФИЛАКТИКИ С УЧЕТОМ ОСОБЕННОСТЕЙ СЕЗОННЫХ ПОДЪЕМОВ ЗАБОЛЕВАЕМОСТИ ОРВИ 05.13.18 – Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Санкт-Петербург – 2009 Работа выполнена на кафедре управления медико-биологическими системами факультета прикладной...»

«Муравьева-Витковская Людмила Александровна МЕТОДЫ ИССЛЕДОВАНИЯ ПРОЦЕССОВ УПРАВЛЕНИЯ НЕОДНОРОДНЫМ ТРАФИКОМ В ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ Специальность 05.13.13 - Телекоммуникационные системы и компьютерные сети АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург - 2007 2 Работа выполнена в Государственном образовательном учреждении высшего профессионального образования Санкт-Петербургский государственный университет информационных...»

«Пирская Анна Сергеевна АВТОМАТИЗАЦИЯ УПРАВЛЕНИЯ ОБРАЗОВАТЕЛЬНЫМИ ТРАЕКТОРИЯМИ СТУДЕНТОВ НА ОСНОВЕ РЕЗУЛЬТАТОВ ОСВОЕНИЯ КОМПЕТЕНЦИЙ ФГОС ВПО Специальность 05.13.06 – Автоматизация и управление технологическими процессами и производствами (образование) Автореферат диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург - 2012 Работа выполнена в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики...»

«Скидин Антон Сергеевич Разработка эффективных методов кодирования для повышения пропускной способности современных линий волоконно-оптической связи Специальность 05.13.17 – Теоретические основы информатики АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук Красноярск – 2011 Работа выполнена в Учреждении Российской академии наук Институте вычислительных технологий Сибирского отделения РАН, г. Новосибирск. Научный руководитель : доктор...»

«ПЕЙСАХОВИЧ Даниил Григорьевич УПРАВЛЕНИЕ ИНТЕРАКТИВНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ В ЕДИНОМ ИНФОРМАЦИОННОМ ПРОСТРАНСТВЕ ПОСРЕДНИЧЕСКОГО ТРАНСПОРТНОГО ОПЕРАТОРА Специальность 05.13.10 – Управление в социальных и экономических системах Автореферат диссертации на соискание ученой степени кандидата технических наук ПЕНЗА – 2014 Работа выполнена на кафедре информационных систем и технологий Федерального государственного бюджетного учреждения высшего профессионального образования Самарский...»

«Карпов Руслан Геннадиевич МЕТОД АНАЛИЗА И ОБРАБОТКИ ДАННЫХ ДЛЯ УСТРОЙСТВА ТРЁХМЕРНОЙ МАГНИТНОЙ ЛОКАЦИИ Специальность 05.13.01 – Системный анализ, управление и обработка информации (приборостроение) Автореферат диссертации на соискание учёной степени кандидата технических наук Москва – 2009 г. Работа выполнена в научно-исследовательской лаборатории сверхпроводниковой микроэлектроники Московского государственного института электронной техники (технического университета) Научный...»






 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.