Введение к работе
Актуальность работы. Теория игр, говоря кратко, это математическая теория принятия решений в конфликтных ситуациях. Усилиями многих ученых к настоящему времени исследованы широкие классы математических моделей конфликтных ситуаций различного характера (антагонистические, кооперативные, иерархические, динамические и.т.д.), имеется огромное количество монографий, учебных пособий, журнальных публикаций, посвященных теории игр (см. библиографию [1]).
В настоящей работе рассматривается относительно новый класс задач теории игр, которые можно назвать седловыми играми двух лиц, предлагаются и исследуются методы поиска точки равновесия таких игр [2-4]. В таких играх каждый игрок распоряжается функцией двух векторных переменных, выбирает седловую точку своей функции и свой выбор (свою стратегию) сообщает другому игроку. Предполагается, что функция каждого игрока зависит от седловой точки другого игрока как от параметра, поэтому седловая точка, выбираемая каждым игроком, влияет на выбор седловой точки другого игрока. Такой взаимозависимый выбор седловых точек каждым игроком в совокупности порождает седловое отображение. Неподвижная точка этого отображения называется точкой равновесия рассматриваемой седловой игры. Игроки, последовательно обмениваясь седловыми точками, согласуя свои действия, ищут эту неподвижную точку. Такая точка выгодна каждому игроку и определить ее - это цель седловой игры. Точное описание математической модели этой игры дается ниже. Пока мы лишь скажем, что седловые игры возникают при моделировании различных экономических ситуаций, таких как, например, равновесная модель кредитного рынка, равновесная модель взаимодействия двух предприятий, использующих продукцию друг друга как сырье, модель равновесной поставки ресурсов, равновесная модель фирмы, равновесный выбор весовых коэффициентов в задачах многокритериальной оптимизации и другие [2-4].
Каждой седловой игре можно сопоставить некоторую функцию, такую, что всякая точка равновесия седловой игры является седловой точкой этой функции. Можно сказать, что такая функция в седловой игре выполняет такую же роль, как и функция Лагранжа в обычной задаче математического программирования. Это значит, что задача поиска точки равновесия сед- ловой игры может быть сведена к седловой задаче, и здесь, казалось бы, можно использовать известные методы поиска седловой точки [5, 6]. Однако, сходимость этих методов доказывается при весьма жестких требованиях на входные данные (условия типа сильной выпуклости целевой функции, компактности допустимого множества седловых параметров). Развитые позднее
экстраполяционные методы поиска седловых точек (экстраградиентные, экстрапроксимальные методы [7, 8]) сходятся при традиционных требованиях (например, условия Липшица для градиентов функции Лагранжа). Однако, как выяснилось, в седловых играх эти традиционные условия не всегда выполняются. Поэтому разработка новых вариантов экстраполяционных методов поиска седловой точки, развитие техники доказательства сходимости этих методов при умеренных требованиях на входные данные задачи, является актуальной проблемой. Кроме того, важно заметить, что седловые задачи, вообще говоря, неустойчивы к погрешностям задания входных данных и для поиска седловых точек нужно использовать специальным образом регуляри- зованные экстраполяционные методы. Таким образом, разработка устойчивых методов поиска точек равновесия в седловых играх является актуальной задачей теории игр.
Цель диссертационной работы. Разработать методы поиска точек равновесия седловых игр двух лиц, обладающих монотонной сходимостью к одной из точек равновесия при традиционных ограничениях на входные данные. Создать регуляризованные варианты этих методов, способные работать при неточно заданных входных данных.
Методы исследования. При выполнении диссертационной работы использовались аппарат выпуклого анализа, равновесного программирования, теория и методы некорректных (неустойчивых) задач, методы и подходы современного анализа численной оптимизации.
Научная новизна. В диссертации предложены и исследованы новые экстраградиентные и экстрапроксимальные методы поиска точек равновесия седловых игр, доказана их монотонная сходимость при традиционных ограничениях на входные данные. Предложены и исследованы новые регуляри- зованные экстраградиентные и экстрапроксимальные методы поиска точек равновесия в седловых играх с неточно заданными входными данными, построен регуляризующий оператор. Развита техника доказательства сходимости перечисленных методов.
Практическая значимость. Разработанные в диссертации методы могут быть использованы для поиска точек равновесия в реальных седловых играх, возникающих в теории равновесного кредитного рынка, равновесной модели развития производства, модели равновесной поставки ресурсов, при выборе равновесных коэффициентов скаляризации многокритериальной оптимизации.
Достоверность полученных в диссертации результатов обусловлена строгость математических доказательств, использованием апробированных научных методов и средств, подтверждена результатами вычислительных экспериментов.
Соответствие диссертации паспорту научной специальности. В
диссертации проведено исследование нового класса игр и разработаны методы их решения, что соответствует паспорту специальности 01.01.09.
Апробация работы Результаты полученные в диссертации докладывались и обсуждались на ежегодных конференциях «Ломоносовские чтения» (Москва, 2011,2012), на ежегодных научных конференциях «Тихоновские чтения» (Москва, 2011, 2012), на XVIII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2011» и XIX Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2012». Кроме того, результаты обсуждались на семинаре кафедры оптимального управления факультета ВМК МГУ.
Публикации. Материалы диссертации опубликованы в 13 печатных работах, из них 8 статей в рецензируемых журналах [13-20].
Структура и объем диссертации Диссертация состоит из введения, трех глав, одного приложения, списка литературы. Общий объем диссертации 207 страниц.
