автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование динамики макросистем на основе концепции равновесия

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

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

Моделирование динамики макросистем на основе концепции равновесия

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

Автореферат

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

1 3 ДЕН 2012

Москва-2012

005057030

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

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

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

кандидат физико-математических наук, доцент Меньшиков Иван Станиславович

Доктор физико-математических наук, профессор

Бекларян Лёва Андреевич,

Центральный экономико-математический институт РАН, главный научный сотрудник

кандидат физико-математических наук Швецов Владимир Иванович, Институт системного анализа РАН, ведущий научный сотрудник

Институт прикладной математики им. М.В. Келдыша РАН

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

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

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

Защита состоится ^

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

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

ноября 2012 г.

Федько О.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Для этого решаются следующие задачи:

• отыскание достаточных условий существования и единственности равновесия;

• разработка эффективных вычислительных алгоритмов поиска равновесий макросистем путем сведения к задачам энтропийно-линейного программирования, разработка соответствующего комплекса программ;

• изучение наследования свойств динамической макросистемы при различных скейлингах (изменеииях масштаба), в частности, исследование

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

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

• оценки скорости сходимости к равновесию и плотности концентрации инвариантной меры в равновесии;

• анализ конкретных макросистем, рассматриваемых при математическом моделировании транспортных потоков; при ранжировании web-cтpaниц; в экономических и социальных моделях.

Методы исследования. В работе используются: эргодические теоремы для марковских процессов, формула Стирлинга, метод Дарвина-Фаулера, современные варианты неравенства Нигера, понятие дискретной кривизны Риччи, второй метод Ляпунова, термодинамический формализм, аппарат производящих функций, метод внутренних штрафных функций, метод стохастического квазиградиентного спуска.

Научная новизна выносимых на защиту результатов состоит в том, что впервые:

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

• выявлен характер связи функции Ляпунова макросистемы с инвариантной мерой этой макросистемы;

• показано, что при достаточно естественных условиях время сходимости к равновесию оказывается малым;

• приведена эволюционная интерпретация конструкции равновесия Нэша— Вардропа, отвечающая равновесному распределению потоков на графе транспортной сети, до этого использовавшаяся только стационарно. Это позволило, в том числе, усилить парадокс Браесса (1968), а также объяснить эвристический способ отбора Бар-Гира-Швецова (2010) единственного

равновесия Нэша-Вардропа в случае, когда имеет место неединственность равновесий.

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

В диссертации в рамках макросистемного подхода предложена модель, обобщающая известную на практике энтропийную модель расчета матриц корреспонденции. Эта известная модель была использована для анализа данных по транспортным потокам г. Москвы. Предложенная в диссертации модель позволила более адекватно описать имеющиеся данные. Сейчас предложенная модель тестируется в Научно-исследовательском и проектном институте Генерального плана города Москвы, как структурный блок общей четырехстадийной транспортной модели.

Диссертация выполнялась при поддержке Лаборатории структурных методов анализа данных в предсказательном моделировании, МФТИ, грант правительства РФ договор 1Ш34.31.0073, а также при поддержке грантов РФФИ 11-01-00494-а, мол_а_вед 12-01-33007.

Апробация и публикации. По материалам диссертации опубликовано 30 печатных работ, в том числе, три - в изданиях, рекомендованных ВАК РФ [6, 12, 13].

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

Результаты работы докладывались, обсуждались и получили одобрение специалистов на 16 конференциях (в том числе, пяти международных), научных семинарах по экспериментальной экономике Вычислительного центра РАН (20092012), семинаре-конференции РАН под рук. акад. В.В. Козлова (2010), на

семинарах кафедр математических основ управления и анализа систем и решений ФУПМ МФТИ (2009-2011), на семинарах по транспортным потокам в Независимом Московском Университете (2011-2012).

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

Задача 1. Обобщение энтропийной модели А.Дж. Вильсона расчета матрицы корреспонденции.

Пусть в некотором городе имеется и районов, Ц > 0 — число жителей ¡' -го

района, 1¥;>0 - число работающих в ) -м районе. При этом М = = , -

общее число жителей города. Обозначим через х(/ (г) > 0 - число жителей, живущих в ;'-м районе и работающих в у'-м в момент времени /. Со временем жители могут только меняться квартирами, поэтому во все моменты времени [

хДО^О, ¿Х(у (/) = /,., ;,у=11«л2«М. (А)

¡-\ .=1

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

хорошую работу. Будем считать, что компромисс между этими двумя неприятностями описывается эффективной функцией затрат R{l) = {alp-т где / > 0 - расстояние от дома до работы, а а > 0, /) > 0,

<о> 0 - настраиваемые параметры модели.

Теперь опишем саму динамику. Пусть в момент времени / > 0 г-й житель живет в к-м районе и работает в ш-м, а ,?-й житель живет в р-м районе и работает в q-u. Тогда \m.pq(t)At + o(At) — есть вероятность того, что жители с номерами /- и s (1 <r<s<M) поменяются квартирами в промежутке времени (/,í+Aí). Вероятность обмена местами жительства зависит только от мест проживания и работы обменивающихся:

суммарные зэтраты суммарные затраты

до обмена * после обмена

где коэффициент Л>0 характеризует интенсивность обменов. Согласно эргодической теореме для марковских цепей:

V Ы":",.,е(Л) ¡jm Р(хДг) = у =1,...,«) =

где статсумма Z находится из условия нормировки получившейся "пуассоновской" вероятностной меры. Отметим, что стационарное распределение

ч) Удовлетворяет условию детального равновесия:

~ ХрЛ„р[{Х„ м ) Лр.т,к,ч ■ При М» 1 распределение _J сконцентрировано на множестве (А) в

окрестности наиболее вероятного значения которое находится, как

решение задачи энтропийно-линейного программирования (см. теорему 1 ниже):

-MMm J~ S хМХч!е) + Ё [a\lui-üAnl.)x.i~>, min . . Решение этой задачи можно представить как

х, = ехр(^ + Л; + ® Ы,-а • (/.У ),

где множители Лагранжа (двойственные переменные) {Л^}", и {^Г}" , определяются из равенств системы (А). На практике мы имеем информацию о и Из системы ограничений (А), мы найдем

M^fccC--

Такой способ расчета матрицы корреспонденции с а = 0 в литературе часто называют (энтропийной) гравитационной моделью:

где {Л,}"^ и ^ определяются из соотношений:

4 =

В классической статической энтропийной модели (второй половины 60-ых годов XX века) А.Дж. Вильсона а> = 0. Однако по Москве наблюдается заметно лучшее соответствие реальных данных рассматриваемой модели, если допускать а > 0, и оптимально его подбирать.

Приведем теперь оценку концентрации стационарного распределения

^| в окрестности наиболее вероятного значения Для этого,

предварительно, введем такую перестановку (/'(■), что дс*^ >х'^ а

затем введем обозначение иДг) = к = 1,...,п2.

Утверждение. V д = 0,...,п2 Э Л?>0, Тцп = 0(Л/1пА/): V

хт

Л„п

.....9

>0.99.

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

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

(химические реакции). Пусть й->«-« + /?, еJ - все возможные типы

реакций (конечный набор). Введем, следуя М.А. Леонтовичу (1935), интенсивность реакции:

у ' у ' га<> О

где Ка- > 0 - константа реакции (в общем случае Щ («) - функция, см. например, теорему 2). При этом часто считают X!,'?, (')М. Таким образом ^(й) -

вероятность осуществления в единицу времени перехода й—>-й-а+Д На макроуровне все это соответствует принципам химической кинетики (закон действующих масс Гульдберга-Вааге, 1864).

Определение. Условием унитарности (условием Штюкельберга-Батищевой-Пирогова) называется следующее соотношение:

3 £>б: V а—> X А^ПС = Е ■ (ШБГТ)

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

Теорема 1. а) (/2,й(г)) = (/},й(0)) (ту)

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

б) Пусть выполняется условие (ШБП). Тогда

¡.мера v(»j) = J"J .¿¡"'е где Л, = £м, а - произвольное решение

(ШБП), будет инвариантной относительно предложенной стохастической марковской динамики.

2. на множестве (inv) эта мера экспоненциально быстро концентрируется, с ростом М, в окрестности наиболее вероятного состояния, которое и принимается за положение равновесия макросистемы.

3. задача поиска наиболее вероятного макросостояния асимптотически эквивалентна задаче максимизации энтропийного функционала (воспользовались формулой Стирлинга

In v(n) я nf ■ (in (и, /Л,)-1) на множестве, задаваемом условием (inv). /

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

V а„Де{0,1}, К*=К|,

i i

к; (Я)=к» ехр(Х,:д,ч (*,-и) -Е,:«,.,". (",)). ч ('г)^о.

Тогда справедливо утверждения п. б) теоремы 1 с

I

Путь, по которому мы до сих пор приходили к равновесию макросистемы, состоял из следующей последовательности предельных переходов: lim и lim .

f-ЮО А/-+О0

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

Пусть теперь dim Я и число реакций |j| не зависят от числа агентов М, ив начальный момент времени / = 0 для любого i существует предел c,(0)=Jimn((0)/A/>0. Тогда в произвольный момент времени />0 для

ПН.

любого i существует не случайный предел с,(7) = lim n,(t)/M. Описанный выше предельный переход называется каноническим скейлингом.

В результате такого скейлинга приходим к «динамике квазисредних» (терминология В. Вайдлиха):

= I сдю

си 1

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

Систему (ДК) можно получить и по-другому. А именно, как приближенную динамику средних с((*) = £[и,-(?)/Л/]. Приближенную в том смысле, что при

выводе (ДК) используется приближение: /''(с, (г))к(7)/Л/)] для «достаточно хороших» функций F (например, полиномов). Это верно в случае пикообразного распределения п:(г).

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

Н(с) = ^с,{НсЛ)-1),

I

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

Теорема 3. Пусть инвариантная вероятностная мера представляется в виде:

у(й) = Мехр(-М-(#(й/М) + о(1))), А/з>1, где Я(с) строго вогнутая функция.

Тогда Я (с) — функция Ляпунова системы (ДК).

Естественно теперь задаться вопросом: А что будет, если условия (ШБП) не выполняются, однако система (ДК) имеет на внутренности пересечения неотрицательного ортанта и инвариантного аффинного многообразия (¡пу)

единственную неподвижную точку (пример такой макросистемы имеется в докторской диссертации СЛ. Пирогова)? Оказывается, имеет место

Теорема 4. Если эта точка экспоненциально глобально устойчива, то 1) все инварианты (законы сохранения) системы (ДК) определяются (inv); 2) около положения равновесия инвариантная мера будет экспоненциально быстро концентрироваться (с ростом М); 3) скорость сходимости к равновесию (mixing time) оценивается как O(MltiM); 4) элементы корреляционной матрицы случайного вектора n{t) равномерно ограничены по времени; 5) предельные переходы lim и lim перестановочны: lim lim* = lim lim*.

Л/ —*ac ОС M > t ; if: f-MM-W

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

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

Во второй главе исследуется способы численного решения задачи энтропийно-линейного программирования. Согласно главе 1 именно к таким задачам часто сводятся задача поиска равновесия макросистемы.

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

max; А: А(х) = g - Тх = б„ F(x) = d-Gx>Öw. (ЭЛП)

iea п r+

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

др.:

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

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

1)3 г>0т: ¡7-75 = 0,, 3-Сг>0п;

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

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

(ИП)

где шага Т = (, й = , у > 0, а > 0 - достаточно маленькие, а дважды

гладкие функции ]5 ^ - монотонно возрастают и равны нулю в

пуле. Например, часто выбирают

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

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

• для сильно разреженных матриц Т и (7;

• при 1+м><^т.

При этом время работы (число арифметических операций типа умножения двух чисел с плавающей точкой) детерминированного алгоритма (ИП) оценивается, соответственно, как 0{т+1 + у/) и О (/и •(/ + 11')). Как показывают

вычислительные эксперименты, стохастические варианты, о которых говорилось выше, работают заметно быстрее.

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

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

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

Пусть транспортная сеть города представлена ориентированным графом Г = (У,Е), где V - узлы сети (вершины), ЕсУхУ - дуги сети (рёбра графа).

Пусть Иг = {л\' = (/,у):г,у — множество корреспонденции, т.е. возможных пар

«исходный пункт» - «цель поездки»; р = — путь из V, в мт, если

(уиу*+[)е^> к = 1,...,т-\, т> 1; — множество путей, отвечающих

корреспонденции и' е IV, то есть если и' = (/,у), то — множество путей,

начинающихся в вершине / и заканчивающихся в _/'; Р =[] — совокупность всех путей в сети Г; х [автомобилей/час] — величина потока по пути р, х = [хр : р е /■}; уг [автомобилей/час] - величина потока по дуге е:

те{Уе) ~ удельные затраты на проезд по дуге е (как правило, возрастающие, выпуклые, гладкие функции).

Рассмотрим теперь Ор (х) - затраты временные или финансовые на проезд по пути р. Естественно считать, что Ср(х) = (х))^, где те(уе) — удельные

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

Пусть также известно, сколько перемещений в единицу времени с1№ осуществляется согласно корреспонденции \ve\V. Тогда вектор х, характеризующий распределение потоков, должен лежать в допустимом

множестве: X = х >0:

I е*Г. )

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

Рассмотрим игру, в которой каждому элементу ус е соответствует свой, достаточно большой (с/№»1), набор однотипных "игроков", осуществляющих передвижение согласно корреспонденции у>. Чистыми стратегиями игрока служат пути, а выигрышем - величина -Ор(х). Игрок "выбирает" путь следования ре.Р„, при этом, делая выбор, он пренебрегает тем, что от его выбора также "немного" зависят |Р№| компонент вектора х и, следовательно, сам выигрыш

-Ср (х). Можно показать, что отыскание равновесия Нэша-Вардропа х* е X

15

(макро описание равновесия) равносильно решению задачи нелинейной комплементарности (принцип Вардропа): для любых е IV, ре Ри, выполняется

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

такая функция Ч'(х) = ^ | ге(г)а!г, что д^'{х)/дхр = Ср(х) для любого

е&Е о

р е Р. Оказывается, что х' е X - равновесие Нэша-Вардропа тогда и только тогда, когда оно доставляет минимум 1Н(Зс) на множестве X.

Введем теперь в эту статическую модель динамику. Пусть на шаге п игрок, осуществляющий перемещение согласно корреспонденции выбрал путь р. Обозначим количество таких игроков через хр (л). Тогда на шаге и + 1 он с вероятностью 1 — уп выбирает тот же путь, а с вероятностью уп использует смешанную стратегию: выбирает путь р е Ри с вероятностью

РгоЬ;(» + 1)-ул-шах(хДй),1/»)ехр(-оДх(«))/г)/г;, где 2" определяется из условия нормировки. Множитель тах(^(и),1/п)

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

Как показали разнообразные численные эксперименты, часто вполне разумно выбирать уп~\/п. При таком выборе уп наблюдается сходимость к равновесию Нэша-Вардропа при наиболее общих условиях относительно Т (вне зависимости

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

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

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

Утверждение. Пусть 7" > О — достаточно мало, 5j(/„)2 <0°- Тогда

х(п)—> (*(<?)) - одно из равновесий. Если равновесие х' единственно, то *'(х(0))=.х\

П.И.

Случай 1

Случай 2

Рис. 1

Случай 1: хп4 =хп4 = 3. Полное время в пути Т = 83 мин

Случай 2: хт = х1324 = х134 = 2. Полное время в пути Т = 92 мин

Пример (парадокс Браеса, 1968). Пусть корреспонденция с114 = 6 (тысяч [автомобилей/час]). Вес ребра е (удельные затраты на проезд по этому ребру) есть время движения по ребру (в минутах) ге(уг), если поток через ребро есть уе (тысяч [автомобилей/час]). Значения функций тс{уе) приведены на рис. 1. Напомним, что потоки по ребрам можно рассчитать исходя из потоков по путям, например, в случае 2 на рис. 1: у24 = хПА + х132,. Оба равновесия Нэша-Вардропа (в случаях 1 и 2) являются «притягивающими» положениями равновесия описанной выше динамики.

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

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

В заключении приведены основные результаты диссертации.

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

18

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

3. Выявлен характер связи функции Ляпунова макросистемы с инвариантной мерой этой макросистемы.

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

5. Получено обобщение модели миграции населения В. Вайдлиха на случай более общих правил, описывающих возможности мигрирования.

6. Разработаны эффективные вычислительные алгоритмы поиска равновесий динамической макросистемы, сводящиеся к задачам энтропийно-линейного программирования. Полученные алгоритмы являются обобщением ранее известных алгоритмов Брэгмана-Шелейховского, MART, GISM, Ю.С. Попкова и др. Разработан соответствующий комплекс программ.

СПИСОК ПУБЛИКАЦИЙ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Гасникова ЕВ. Двойственные мультипликативные алгоритмы для задачи энтропийно-линейного программирования // Труды 50-й научной конференции МФТИ. Современные проблемы фундаментальных и прикладных наук. - М., Долгопрудный: Изд-во МФТИ, 2007 г. Ч. 7. Т. 1. С. 106-109.

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

3. Гасникова Е.В. Барьерно-мультипликативные алгоритмы для задач, двойственнх к задачам оптимизации энтропийно подобных функционалов на выпуклых множествах простой (аффинной) структуры // Труды 51-й научной конференции МФТИ. Современные проблемы фундаментальных и прикладных наук. - М., Долгопрудный: Изд-во МФТИ, 2008 г. Ч. 7. Т. 1. С. 2125.

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

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

6. Гасникова Е.В. Двойственные мультипликативные алгоритмы для задач энтропийно-линейного программирования // ЖВМ и МФ Т.49 № 3 Изд-во МАИК «Наука/Интерпериодика», 2009 г. С. 453-464.

7. Гасников A.B., Гасникова Е.В. О принципе максимума энтропии в сетевых моделях // Тезисы докладов IV Всероссийской научной конференции «Математическое моделирование развивающейся экономики и экологии» (ЭКОМОД-2009), Киров, 6-12 июля 2009. Киров: Изд-во ВятГУ, 2009. С. 38.

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

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

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

11. Гасникова Е.В. О равновесиях макросистем. Труды VI международной конференции по исследованию операций. М.: МАКС Пресс. 19-23 октября

2010. С. 139-140.

12. Гасников A.B., Гасникова Е.В. О возможной динамике в модели расчета матрицы корреспонденции (А.Дж. Вильсона) // Труды МФТИ, Т. 2. № 4(8). Изд-во МФТИ, 2010. С. 45-54.

13. Гасникова Е.В, Дорн IO.B. О стохастической марковской динамике, приводящей к равновесию Нэша - Вардропа в модели распределения потоков // Труды МФТИ, Т. 2. № 4(8). Изд-во МФТИ, 2010. С. 55-57.

14. Гасникова Е.В. О социально-экономических приложениях уравнений стохастической химической кинетики, динамике средних и динамике, полученной в результате скейлинга // Труды 53-й научной конференции МФТИ, - М., Долгопрудный: Изд-во МФТИ, 2010. Ч. 7. Т. 1. С. 88-90.

15. Гасникова Е.В. О стохастической марковской динамике наилучших ответов, приводящей к равновесию Нэша-Вардропа // Труды 53-й научной конференции МФТИ. - М., Долгопрудный: Изд-во МФТИ, 2010. Ч. 7. Т. 1. С. 106-107.

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

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

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

19. Гасников A.B., Гасникова Е.В., Колесников A.B., Нагапетян Т.А. О концепции равновесия макросистемы и сё приложении к модели равновесного распределения потоков // Труды Международной научной конференции "50 лет ИППИ РАН", - М.: Изд-во ИППИ РАН, 25 июля - 29 июля 2011. Москва,

2011. С. 53-61.

20. Gasnikov А. V., Gasnikova Е. V., Nagapetyan Т.А. On the convergence to one of the Nash-Wardrop's equilibriums // Traffic and granular flow'11. International conference. Moscow, 28 September - 1 October 2011. Изд-во МТУ СИ. P. 296298.

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

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

23. Гасникова КВ. Достаточные условия существования равновесия макросистем // Труды 54-й научной конференции МФТИ, - М., Долгопрудный: Изд-во МФТИ, 2011. Ч. 7. Т. 1. С. 64-65.

24. Гасникова КВ. Концепция равновесия макросистемы в модели распределения потоков // Труды 54-й научной конференции МФТИ, - М., Долгопрудный: Изд-во МФТИ, 2011. Ч. 7. Т. 1. С. 88-89.

25. Gasnikova E.V., Nagapetyan Т.А. 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, 2012. arXiv: 1112.1628v3

26. Gasnikov A. V., Gasnikova К 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.

27. Гасников A.B., Гасникова E.B., Петрашко Д.И. Макросистемный подход к ранжированию web-страниц // «Информационные технологии и системы — 2012» 35-я конференция молодых ученых и специалистов ИППИ РАН, ПреМоЛаб, СТРАДО. г. Петрозаводск: Изд-во ИППИ РАН. С. 423-429.

28.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.

29. 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.

30. Гасникова Е.В. О возможной динамике в модели расчета матриц корреспонденции // Приложение к монографии «Введение в математическое моделирование транспортных потоков» Под ред. А.В. Гасникова. М.: МЦНМО, 2012. С. 250-273.

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

Моделирование динамики макросистем на основе концепции равновесия

Автореферат

Подписано в печать 02.11.2012. Печать трафаретная Усл.п.л. -1,0 Заказ № 4893 Тираж: 100 экз. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ВВЕДЕНИЕ.

ГЛАВА 1. ВВЕДЕНИЕ ДИНАМИКИ В МАКРОСИСТЕМЫ. КОНЦЕПЦИЯ РАВНОВЕСИЯ МАКРОСИСТЕМЫ И ЕЁ ОКРЕСТНОСТИ.

1.1. Введение в теорию однородных дискретных марковских процессов и их приложения (PageRank, МСМС, алгоритм Григориадиса-Хачияна).

1.2. Парадокс Эренфестов.

1.3. Кинетика социального неравенства.

1.4. Энтропийная модель расчёта матрицы корреспонденции (обобщение).

1.5. Модель распределения WWW трафика (Дж.А. Томлин, IBM).

1.6. Общая схема.

ГЛАВА 2. ДВОЙСТВЕННЫЕ МУЛЬТИПЛИКАТИВНЫЕ АЛГОРИТМЫ ДЛЯ ЗАДАЧИ ЭНТРОПИЙНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

2.1. Двойственная задача.

2.2. Мультипликативно-барьерные итерационные алгоритмы решения двойственной задачи.

2.3. Исследование одного мультипликативного итерационного алгоритма минимизации строго выпуклой функции на неотрицательном ортанте.

2.4. Задача энтропийно-линейного программирования (случай регулярных ограничений).

2.5. Задача энтропийно-линейного программирования (общий случай).

2.6. Численные примеры решения задач энтропийно-линейного программирования

ГЛАВА 3. О ТЕОРЕТИКО-ИГРОВОЙ ИНТЕРПРЕТАЦИИ КОНЦЕПЦИИ РАВНОВЕСИЯ МАКРОСИСТЕМЫ.

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

3.2. Не единственность равновесия - макросистемный отбор.

3.3. Платные дороги и "цена анархии".

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

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

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

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

Для выполнения поставленной цели решаются следующие задачи:

• отыскание достаточных условий существования и единственности равновесия;

• разработка эффективных вычислительных алгоритмов поиска равновесий макросистем путем сведения их к задачам энтропийно-линейного программирования, разработка соответствующего комплекса программ;

• изучение наследования свойств динамической макросистемы при различных скей-лингах (изменениях масштаба), в частности, исследование перестановочности предельных переходов по времени и размерности макросистемы;

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

• оценки скорости сходимости к равновесию и плотности концентрации инвариантной меры в равновесии;

• анализ конкретных макросистем, рассматриваемых при математическом моделировании транспортных потоков; при ранжировании web-страниц; в экономических и социальных моделях.

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

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

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

Научная новизна выносимых на защиту результатов состоит в том, что впервые:

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

• выявлен характер связи функции Ляпунова макросистемы с инвариантной мерой этой макросистемы;

• показано, что при достаточно естественных условиях время сходимости к равновесию оказывается малым;

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

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

В диссертации в рамках макросистемного подхода предложена модель, обобщающая известную на практике энтропийную модель расчета матриц корреспонденций А. Дж. Вильсона. Эта известная модель была использована для анализа данных по транспортным потокам г. Москвы, полученным в Лаборатории прикладного моделирования транспортных систем ИПМ им. М.В.Келдыша РАН. Предложенная в диссертации модель позволила более адекватно описать имеющиеся данные. Сейчас предложенная модель тестируется в Научно-исследовательском и проектном институте Генерального плана города Москвы, как структурный блок общей четырехстадийной транспортной модели.

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

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

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

Публикации. По материалам диссертации опубликовано 35 печатных работ [1-35],, в том числе, четыре - в изданиях, рекомендованных ВАК РФ, приложение к монографии и один электронный препринт, выложенный на arxiv.org.

Апробация работы. Результаты работы докладывались, обсуждались и получили одобрение специалистов на 16 конференциях (в том числе, пяти международных), научных семинарах по экспериментальной экономике Вычислительного центра РАН (20092012), семинаре-конференции РАН под рук. акад. В.В. Козлова (2010), на семинарах кафедр математических основ управления и анализа систем и решений ФУПМ МФТИ (2009-2011), на семинарах по транспортным потокам в Независимом Московском Университете (2011-2012).

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Единообразно представлены многие известные алгоритмы решения задач энтропийно-линейного программирования (Брэгмана-Шелейховского, MART, GISM, Ю.С. Попкова и др.), возникающие при поиске равновесий макросистем.

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

2. Гасникова Е.В. Двойственные мультипликативные алгоритмы для задач энтропийно-линейного программирования // ЖВМ и МФ Т.49 № 3. Изд-во МАИК «Наука/Интерпериодика», 2009 г. С. 453-464.http://www.mathnet.ru/links/477d9abf29f4617e2884d66705be0b39/zvmmf22.pdf

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

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

5. Гасникова ЕВ О равновесиях макросистем. Труды VI международной конференции по исследованию операций. М.: МАКС Пресс. 19-23 октября 2010. С. 139-140.

6. Гасников А В, Гасникова Е.В О возможной динамике в модели расчета матрицы корреспонденции (А.Дж. Вильсона) // Труды МФТИ, Т. 2. № 4(8). Изд-во МФТИ 2010. С. 45-54.http://mipt.ru/nauka/trudv/N+4+%288%29/Pages 45-54 from Trud-8-7-arpgtk3kdie.pdf

7. Гасникова ЕВ О стохастической марковской динамике наилучших ответов, приводящей к равновесию Нэша-Вардропа // Труды 53-й научной конференции МФТИ. -М., Долгопрудный: Изд-во МФТИ, 2010. 4.7. Т. 1.С. 106-107.

8. Gasnikov A.V., Gasnikova E.V., Nagapetyan Т.А. On the convergence to one of the Nash-Wardrop's equilibriums // Traffic and granular flow' 11. International conference. Moscow, 28 September 1 October 2011. Изд-во МТУСИ P. 296-298.

9. Гасникова Е.В. Достаточные условия существования равновесия макросистем // Труды 54-й научной конференции МФТИ, М., Долгопрудный: Изд-во МФТИ, 2011. Ч. 7. Т. 1.С. 64-65.

10. Гасникова Е.В. Концепция равновесия макросистемы в модели распределения потоков // Труды 54-й научной конференции МФТИ, М., Долгопрудный: Изд-во МФТИ, 2011. Ч. 7. Т. 1. С. 88-89.

11. 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.

12. Гасникова Е.В. О платных дорогах и метаигровом синтезе // Труды 55-й научной конференции МФТИ. Современные проблемы фундаментальных и прикладных наук. -М., Долгопрудный: Изд-во МФТИ, 2012 г. Ч. 7. Т. 1. С. 55-56.

13. Гасникова Е.В. Оценка mixing time для макросистем с единственным равновесием // Труды 55-й научной конференции МФТИ. Современные проблемы фундаментальных и прикладных наук. М., Долгопрудный: Изд-во МФТИ, 2007 г. Ч. 7. Т. 1. С. 87-89.

14. Боровков А.А. Эргодичность и устойчивость случайных процессов. М.: УРСС, 1999.

15. Бупинский А.В., Ширяев A.H. Теория случайных процессов. М.: Физматлит; Лаборатория базовых знаний, 2003.

16. Кельберт М.Я., Сухов Ю.М. Вероятность и статистика в примерах и задачах. Т. 2. М.гМЦНМО, 2010.

17. Ширяев А.Н. Вероятность 1,2. М.: МЦНМО, 2007.

18. Соболь И.М. Численные методы Монте-Карло. М.: Наука, 1973.

19. Дынкин Е.Б., Юшкевич А.А. Теоремы и задачи о процессах Маркова. М.: Наука, 1967.

20. Motwani R., Raghavan P. Randomized algorithms. Cambridge Univ. Press, 1995.

21. Красносельский M.A., Лифшиц E.A., Соболев А.В. Позитивные линейные системы. Метод положительных операторов. М.: Наука, 1985.

22. Brin S., Page L. The anatomy of a large-scale hypertextual web search engine // Comput. Network ISDN Syst. 1998. V. 30(1-7). P. 107-117.

23. Langville A.N., Meyer C.D. Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 2006.

24. Baldi P., Frasconi P., Smyth P. Modeling the Internet and the Web: Probabilistic methods and algorithms. Published by John Wiley & Sons, 2003. http://ibook.ics.uci.edu/

25. Назин А.В., Поляк Б.Т. Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank // Автоматика и телемеханика, № 2, 2011. С. 131-141.

26. Nesterov Y.E. Subgradient methods for huge-scale optimization problems // CORE Discussion Paper; 2012/2, 2012. http://wvvw.uclouvain.be/32349.html

27. Ермаков C.M. Метод Монте-Карло в вычислительной математике. Вводный курс. М.: Бином, 2009.

28. Кнут Д., Яо Э. Сложность моделирования неравномерных распределений // Кибернетический сборник. Новая серия. Вып. 19. М.: Мир, 1983. С. 97-158.

29. Sinclair A., Jerrum М. Approximate counting, uniform generation and rapidly mixing Markov chains//Information and Computation. 1989. V. 82. № l.P. 93-133.

30. Dyer M., Frieze A., Kannan R. A random polynomial-time algorithm for approximating of the volume of convex bodies // Journal of ACM. 1991. V. 38. № 1. P. 1-17.

31. David Aldous and Jim Fill Reversible Markov Chains and Random Walks on Graphs, 2002. h tip: //sta t -u w vv. be r k с 1 e \ .edu/users/aldous/R WG/book.html

32. Fan Chung Laplacians and the Cheeger inequality for directed graphs // Annals of Combinatorics. 2005. no. 9. P. 1-19. http://math.ucsd.edu/~fan/

33. Diaconis P The Markov chain Monte Carlo revolution // Bulletin (New Series) of the AMS.2009. V. 49. № 2. P. 179-205.http://math uchicago.edu/~shmuel/Network-course-readings/MCMCRev.pdf

34. Spielman D. Lecture, 2009 http://www.cse.cuhk.edu.hk/~chi/csc5160/notes/L02.pdf

35. Jouhn A , Ollivier Y Curvature, concentration and error estimates for Markov chain Monte Carlo //Ann. Prob. 2010. V. 38. № 6. P. 2418-2442. http://www.vann-ollivier.org/rech/publs/survevcurvmarkov.pdf

36. Ledoux M. Concentration of measure phenomenon. Providence, RI, Amer. Math. Soc., 2001 (Math. Surveys Monogr. V. 89).

37. ХачиянЛГ Избранные труды / сост. С. П. Тарасов. М.: МЦНМО, 2009. С. 38-48.

38. Въюгин В.В Элементы математической теории машинного обучения. М.: МФТИ,2010. http://4\\w\ ■iitp.n.i/iipload/publieations/5759<vyu»inl .pdf62. http://www2.isve.gatech.edu/~nemirovs/63. http://www.core.ucl.ac.be/~nesterov/

39. Juditsky A , Lan G., Nemirovski A., Shapiro A Stochastic approximation approach to stochastic programming // SIAM Journal on Optimization. 2009. V. 19. № 4. P. 1574-1609.

40. Nesterov Y Primal-dual subgradient methods for convex problems // Math. Program. Ser. B.2009. V. 120. P. 221-259.

41. Кац M. Вероятность и смежные вопросы в физике. М.: Мир, 1965.

42. Dragulescu А , Yakovenko V. М. Statistical mechanics of money // The European Physical

43. Journal B. 2000. V. 17. P. 723-729. arXiv:cond-mat/0001432v4

44. Маслов В П Квантовая экономика. M.: Наука, 2006

45. Вильсон А Дж Энтропийные методы моделирования сложных систем. М.: Наука, 1978.

46. Попков Ю С Теория макросистем: равновесные модели. М.: УРСС, 1999.

47. Швецов В И Математическое моделирование транспортных потоков // Автоматика и телемеханика. 2003. № 11. С. 3^16.

48. Gongalves MB , Ulyssea-Neto I Equilibrium values and dynamics of attractiveness terms in production-constrained spatial-interaction models // Envir. & Plan. A. 1993. V. 25. P. 817-826.

49. Шредингер Э Статистическая термодинамика. M.: ИЛ, 1948.

50. Хуанг К Статистическая механика М Мир, 1966

51. Веденяпин В В , Орлов ЮНО законах сохранения для полиномиальных гамильтонианов и для дискретных моделей уравнения Больцмана // ТМФ 1999 Т 121, №2 С 307-315

52. Веденяпин В В Кинетическая уравнения Больцмана и Власова М Физматлит, 2001

53. Батищева Я Г, Веденяпин В В И-й закон термодинамики для химической кинетики // Мат мод 2005 Т 17, №8 С 106-110

54. Malyshev VA , Pirogov S А , Rybko А N Random walks and chemical networks // Mosc Math J 2004 V 42 P 441-453

55. Малышев В А , Пирогов С А Обратимость и необратимость в стохастической химической кинетике//УМН 2008 Т 63 № 1 С 3-36

56. Калинкин А В Марковские ветвящиеся процессы с взаимодействием // УМН 2002 Т 57, №2 (344) С 23-84

57. Гардинер К В Стохастические методы в естественных науках М Мир, 1986

58. Занг В -Б Синергетическая экономика время и перемены в нелинейной экономической теории М Мир, 1999

59. Castellano С, Fortunato S, Loreto V Statistical physics of social behavior // Review of modern physics 2009 V 81 P 591-646 arXiv 0710 3256v2

60. Николис Г, Пригожин И Самоорганизация в неравновесных системах М Мир, 1979

61. Хакен Г Информация и самоорганизация Макроскопический подход к сложным системам М УРСС, 2005

62. МарриДж Нелинейные дифференциальные уравнения в биологии М Мир, 1983

63. Свирежев Ю М Нелинейные волны, диссипативные структуры и катастрофы в экологии М Наука, 1987

64. Вайдпих В Социодинамика системный подход к математическому моделированию в социальных науках М УРСС, 2010

65. Jaynes Е Т Probability theory The logic of science Cambridge Cambridge University Press, 2003

66. Розоноэр ЛИ Обмен и распределение ресурсов (обобщенный термодинамический подход) I, II, III // Автоматика и Телемеханика. № 5, № 6, № 8, 1973

67. Опойцев В И Нелинейная системостатика М Наука, 1986, Равновесие и устойчивость в моделях коллективного поведения М Наука 1977

68. Сергеев В М Пределы рациональности М Фазис, 1999

69. Rybko А , Shlosman S. Poisson hypothesis for information networks I, II// e-prints http://arxiv.org/abs/math/04061 lOvl; http://arxiv.org/abs/math-ph/0410053v 1, 2004.

70. Stewart N. Ethier and Thomas G Kurtz Markov processes. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons Inc., New York, 1986.

71. ФедорюкМВ Метод перевала. M.: Наука, 1977.

72. Вентцель АД, Фрейдлин МИ Флуктуации в динамических системах под действием малых случайных возмущений. М.: Наука, 1979.

73. International workshops on Bayesian inference and maximum entropy methods in science and engineering. AIP Conf. Proceedings (holds every year from 1980).

74. Kapur J.N. Maximum entropy models in science and engineering. John Wiley & Sons, Inc., 1989.

75. Маслов ВП, Черный AC О минимизации и максимизации энтропии в различных дисциплинах // ТВП. 2003. Т. 48. № 3. С. 466-486.

76. Golan А , Judge G., Miller D Maximum entropy econometrics: Robust estimation with limited data. Chichester, Wiley, 1996.

77. Fang S.-C., Rajasekera J R, Tsao H.-SJ. Entropy optimization and mathematical programming. Kluwer's International Series, 1997.

78. Евтушенко ЮГ Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.105Жадан В Г Численные методы линейного и нелинейного программирования: вспомогательные функции в условной оптимизации. М.: ВЦ РАН, 2002.

79. Nesterov Y.E, Nemirovsky A.S. Interior-point polynomial algorithms in convex programming: Theory and algorithm. SIAM Publications, Philadelphia, 1994.

80. Магарил-Илъяев Г Г, Тихомиров В М Выпуклый анализ и его приложения. М.: УРСС, 2011.

81. Поляк Б Т Введение в оптимизацию. М.: Наука, 1983

82. Никайдо X Выпуклые структуры и математическая экономика. М.: Мир, 1972; Агима-нов С А Введение в математическую экономику. М.: Наука. 1984.

83. Ермольев Ю М Методы стохастического программирования. М.: Наука, 1976.

84. Wl.Shejfi Y Urban transportation networks: Equilibrium analysis with mathematical programming methods. N.J.: Prentice-Hall Inc., Englewood Cliffs, 1985.

85. S.Foster D., Young P Stochastic evolutionary game dynamics // Theoretical population biology. 1990. V. 38. № 2.

86. Cressman R Evolutionary game theory and extensive form games. Cambridge, Mass.: MIT Press, 2003.

87. Hojbauer J, Sigmund К Evolutionary game dynamics // Bulletin of the AMS. 2003. V. 40. №4. P. 479-519.121 .Васин A A , Краснощекое ПС, Морозов В В Исследование операций. М.: Издательский центр «Академия», 2008.

88. Easley D, Kleinberg J Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010 http://wvvw.cs.cornell.edu/home/kleinber/networks-book/

89. McKelvey R D, Palfrey TR Quantal response equilibria for extensive form games // Experimental economics. 1998. V. 1. P. 9-41.

90. Marsili M Toy models of markets with heterogeneous interacting agents // e-print www.unifr.ch/econophysics/. 2001.

91. Fogel D В Evolutionary Computation: Towards a New Philosophy of Machine Intelligence. New York: IEEE Press, 2000.

92. СтенбринкП А Оптимизация транспортных сетей. M.: Транспорт, 1981.

93. Patriksson М The traffic assignment problem. Models and methods. Utrecht, Netherlands: VSP, 1994.

94. Nesterov Y, de Palma A Static equilibrium in congested transportation networks // Networks Spatial Econ. 2003 № 3(3). P. 371-395.

95. Amnon Rapoport, Tamar Kugler, Subhasish Dugar, Eyran J. Gisches Choice of routes in congested traffic networks: Experimental tests of the Braess Paradox // Games and Economic Behavior. 2009. V. 65 P. 538-571.

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

97. Bar-Gera H. Origin-based algorithms for transportation network modeling. Univ. of Illinois at Chicago, 1999.

98. Sandholm W. Evolutionary Implementation and Congestion Pricing // Review of Economic Studies. 2002. V. 69. P. 667-689.

99. Roughgarden Т., Tardos E. How bad is selfish routing? // Journal of the ACM. 2002. V. 49. №2. P. 236-259.