Содержание
1 Уравнения Гамильтона-Якоби в задачах эволюционных дифференциальных игр 21
1 Постановки задач теории эволюционных и
дифференциальных игр ..................... 21
2 Терминальная и стационарная задачи для
уравнений типа Гамильтона-Якоби .......... 31
2 Конечно-разностные операторы для уравнения Гамильтона-Якоби 40
3 Выпуклые, вогнутые оболочки и п-мерные
плоскости кусочно-линейных функций .... 41
4 Среднеквадратичные конструкции в конечных разностях ................................ 46
5 Модификация линейного оператора для стационарной задачи.............................. 49
6 Операторы на несимметричных областях
достижимости.............................. 55
3 Синтез оптимального управления при пространственно-временной дискретизации задачи 57
7 Оптимальные процедуры управления .... 58
1
8 Синтез стационарных стратегий ............ 62
9 Соотношения между шагами аппроксимаци-
онной сеточной схемы...................... 65
Квазивыпуклые аппроксимационные схемы 72
10 Оптимальный синтез для квазивыпуклых
аппроксимационных функций................. 73
11 Дифференциальная игра с дисконтированием ....................................... 78
Динамические модели и вычислительные эксперименты 80
12 Управляемые уравнения Колмогорова ... 80
13 Динамика неоднородных коалиций ........... 86
14 Управляемая репликаторная модель.......... 90
2
Введение.
Диссертационная работа посвящена разработке вычислительных методов построения равновесных стратегий управления в эволюционных играх. Теория эволюционных игр является активно исследуемым направлением прикладной математики. Создание этой теории было вызвано актуальностью выявления закономерностей развития и возможностей управления в экономических, социологических, биологических системах.
Развитие теории эволюционных игр тесно связано с такими направлениями как дифференциальные игры, оптимальное управление, математическое програмирование, негладкий и выпуклый анализ.
Становление теории дифференциальных игр относится к началу 60-х годов и связано с именами российских и зарубежных математиков H.H. Красовского, Л.С. Понтря-гина, Р. Айзекса, У. Флеминга. В качестве решения эволюционной игры в диссертации рассматривается совокупность позиционных управлений, ориентированных на гарантированную оптимизацию выигрышей один из классических подходов теории дифференциальных игр. Равновесные управления конструируются на основе решений вспомогательных задач гарантированого управления. Базисным элементом решения этих задач является функция цены, для построения которой применяются сеточные схемы аппроксимации обобщенных решений уравнений Гамильтона-Якоби. В этом аспекте материал диссертации опирается на результаты теории уравнений Гамильтона-Яко-
з
би, разработанных в работах А.И. Субботина для обобщенных минимаксных решений. Используются также конструкции вязкостных решений, предложенных в работах М.Дж. Крэндалла, П.-Л. Лионса. В частности, особое внимание уделяется конечно-разностным операторам. Аппро-ксимационные решения сеточных схем (аппроксимацион-ные функции цены) и информация об их обобщенных градиентах позволяют строить гарантированные управления методом экстремального сдвига, предложенным в работах H.H. Красовского. Равновесные решения (динамические равновесия по Нэшу) синтезируются на базе построенных гарантированных управлений в рамках конструкции, разработанной А.Ф. Клейменовым.
Основные целями работы являются.
1. Разработка и обоснование конструкций для эффективного вычисления позиционных управлений, реализующих динамическое рановесие по Нэшу в эволюционных играх.
2. Построение конечно-разностных операторов со среднеквадратичными градиентами, повышающих эффективность процесса вычисления фунции цены и оптимальных гарантированных управлений.
3. Синтезирование равновесных траекторий и исследование их свойств.
Теоретическая и практическая ценность.
Изложенные в диссертации методы носят конструктивный характер и применимы к достаточно широкому кругу задач. Предлагаемые конструкции и процедуры могут быть положены в основу разработки эффективных алго-
4
ритмов и программ, реализуемых на ЭВМ и позволяющих не только прогнозировать эволюционный процесс, но и вносить управляющие коррективы для достижения определенных параметров.
Диссертация состоит из введения и пяти глав. Нумерация параграфов сквозная. Список литературы включает 84 наименования. Объем работы составляет 116 страниц машинописного текста.
В первой главе описывается постановка эволюционной игры для двух игроков на бесконечном промежутке времени. Предполагается, что игрок представляет собой группу (коалицию, популяцию) участников (индивидумов) с общими интересами и одинаковыми стратегиями. Для группы определены две стратегии и в каждый момент времени их представители могут придерживаться только одной из них. Считается, что предствители разных групп встречаются (образуют игровые пары) случайным образом. Выигрыши участников определяются матрицами выигрышей. Локальные (краткосрочные) выигрыши групп задаются как соотвествующие математические ожидания (средние выигрыши). Глобальные (долгосрочные) интересы коалиций представляются как интегралы от математических ожиданий на бесконечном промежутке времени с подходящим коэффициентом дисконтирования [1],[78]. Действия участников могут корректироваться информационными сигналами.
Эволюционная динамика поведения игроков описывается стационарной системой дифференциальных уравнений
5
с управляющими параметрами (сигналами). Предполагается, что управления могут строиться по принципу обратной связи на основе информации о игровой ситуации. Цель каждой коалиции состоит в максимизации своих глобальных интересов.
Рассматривается задача поиска динамического равновесия по Нэшу в классе позиционных стратегий. Динамическое равновесие синтезируется [19] из решений двух вспомогательных задач гарантированного управления (антагонистических игр с интегральными функционалами платы). Задачи являются однотипными и исследуются в рамках формализации позиционных дифференциальных игр [24], [25].
Задачу управления с интегральным функционалом качества при наличии коэффициента дисконтирования можно привести [1] к задаче с терминальным функционалом, путем добавления к системе уравнения, задающего в дифференциальной форме функционал качества. В результате на единицу увеличивается размерность системы и в явном виде проявляется временная зависимость правой части от дисконтирующей экспоненты.
Таким образом, равновесное решение эволюционной игры тесно связано с исследованием задачи гарантированного управления с терминальным функционалом платы и соответствующей терминальной задачи для уравнения Гамильтона-Якоби. Следует отметить, что специфика терминальной краевой задачи позволяет рассматривать эквивалентную задачу со стационарным уравнением Гамиль-
б
тона-Якоби, в которой краевое условие заменяется условием ограниченности решения.
В теории позиционных дифференциальных игр [24],[25] одной из основных конструкций является функция цены (функция оптимального гарантированного результата), которая каждой начальной позиции ставит в соответсвие оптимальный гарантированный результат.
Функция цены в точках дифференцируемости удовлетворяет уравнению в частных производных типа Гамильтона-Якоби. Известно, что во многих задачах функция цены является недифференцируемой функцией. В работах
А.И.Субботина [53],[51] было предложено определение недифференцируемого обобщенного решения уравнения Гамильтона-Якоби, доказаны теоремы существования и единственности. Знание функции цены обеспечивает решение задачи управления, т.к. оптимальные позиционные процедуры управления могут быть построены, например, методом экстремального сдвига [24] на сопутствующие точки локальных экстремумов функции цены.
Во второй главе предлагается конечно-разностный оператор для уравнения Гамильтона-Якоби, в котором несуществующие градиенты решений заменяются градиентами локальных линейных аппроксимаций. Доказывается, что соответствующие этому конечно-разностному оператору аппроксимационная схема минорируется и мажорируется аппроксимационной схемой с конечно-разностными операторами, основанными на конструкциях су б- и супердифференциалов локальных выпуклых и вогнутых обо-
7
лочек. Это позволяет обосновать сходимость апроксима-ционных схем с линейными конструкциями. Конечно-разностные операторы, основанные на конструкциях локальных выпуклых (вогнутых) оболочек и локальных линейных аппроксимаций (локальных линейных оболочек) модифицируются для стационарной задачи с дисконтирующим функционалом. Доказывается сходимость аппрокси-мационных схем в этой задаче с бесконечным временным горизонтом.
Рассматриваются модификации конечно-разностных операторов, которые учитывают расположение локальных областей достижимости динамической системы.
В параграфе три, решается вспомогательная задача об отношениях, связывающих выпуклые и вогнутые оболочки /Н(у), дЬ(у) со среднеквадратичными плоскостями Ь(у).
Оболочки рассматриваются локально в окрестности 0Р1(х,г\) для функции, заданной таблично на сетке в п-мерной области определения.
Среднеквадратичной названа локальная линейная аппроксимация, построенная по методу наименьших квадратов, на основе информации о значении функции в узлах окрестности 0Р1(х,г\). (Величина ^-определяет количество узлов на координатной оси.)
Основным результатом является утверждение.
Теорема 3.1 Пусть радиусы гх, 7*2 окрестностей Орг(х, гх). 0Р1(х,Г2) выбраны таким образом, что
— = Зп(1-----—)
Г2 4 N + 1'
8
- Киев+380960830922