Методы поиска точек равновесия в билинейной игре с ненулевой суммой

• Автор: Делавархалафи Али
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 79 с. : ил

Введение
Оглавление

Глава1. Итерационный метод поиска точки равновесия

1.1. Постановка игровой задачи

1.2. Постановка равновесной задачи

1.3. Существование решения

1.4. Градиентный подход с прогнозированием

Глава2. Методы регуляризации с расширением множества

2.1. Возмущенная задача. Примеры неустойчивых задач

2.2. Метод стабилизации

2.3. Метод невязки
2.4. Метод квазирешений
ГлаваЗ. Методы регуляризации в сочетании со штрафными функциями
3.1. Метод стабилизации со штрафами
3.2. Метод невязки со штрафами
3.3. Метод квазирешений со штрафами
Приложение. Численные эксперименты
на тестовых задачах
Список литературы

ВВЕДЕНИЕ
Исследование математических моделей многих сложных явлений экономики, естествознания, связанных с поиском компромисса и согласования частично (или полностью) противоположных интересов сторон конфликта составляет содержание области математики, которую называют равновесным программированием и которая охватывает ряд важных задач теории игр и экономического равновесия [1],
[2], многокритериального принятия решений в условиях неопределенности [3], обратных задач оптимизации [4], вариационных неравенств [5]. Основную задачу равновесного программирования можно сформулировать следующим образом. Пусть имеется некоторая функция Ф(г», гу), (v,w) £ W х W ,где W—заданное множество из п-мерного пространства Еп. Требуется найти точку £ W, для которой
Ф(гц,гц) < Ф(гц,гт) Vw £ W. (0.1)
Такую точку г>* называют точкой равновесия. Многие важные проблемы исследования операций, вычислительной математики и математической экономики сводятся к задаче (0.1). Если функция Ф(г/, го) не зависит от v, то задача (0.1) превращается в обычную задачу минимизации.
К настоящему времени достаточно хорошо изучена проблема существования точек равновесия, равносильная проблеме существования неподвижных точек v £ W{y) экстремального отображения w — w{y) функции Ф(г, w) на W, определяемого из условия min^gvK Ф(г>, w) = Ф(г>, w(v)), v £ W, w(v) £ W. Экстремальные отображение, как правило, является многозначным и при доказательстве существования неподвижной точки обычно пользуются теоремами Какутани [6], Fan К у [7], Oettli [8], обобщающие классические теоремы о неподвижных точках для многозначных отображений.
Что касается конструктивных методов поиска точек равновесия, пригодных для использования на компьютерах, то здесь значительные результаты получены лишь для отдельных классов задач (0.1), таких, как задачи оптимизации, седловых задач, вариационные нера-

венства. Однако эти методы в основном разрабатывались и исследовались при значительных ограничениях на функцию Ф(в,гв) (требования типа выпуклости по переменной w и вогнутости по v, нулевой суммы игры, сильной монотонности оператора в вариационних неравенствах и т.п). Между тем многие практически важные задачи математической экономики, теории игр не удовлетворяют этим ограничениям и ранее разработанные методы к таким задачам не вполне применимы. Поэтому можно считать, что разработка методов решения достаточно общих задач (0.1) практически только начинается, о чем свидетельствуют имеющиеся немногочисленные работы (Карпе-левич Г.М.[9], Антипин А.С [10], [20], [25],[27], [28], Шпирко С.В.[11], Васин А.А.[12], Богданов A.B. [13]).
При разработке методов решения задачи (0.1) следует ещё учитывать, что эта задача, вообще говоря, неустойчива к возмущениям функции Ф(гц'ш) и множества W, и для их решения нужно использовать специальные методы, называемые методами регуляризации. Имеется относительно небольшое число работ в которых предложены и исследованы методы регуляризации неустойчивых равновесных задач. (Васильев Ф.П, Антипин А.С[14], [15], [16]-[18], Шпирко С.В. [11])-
Из вышесказанного следует, что тема диссертации, в которой разрабатываются и исследуются методы решения билинейных задач вида (0.1), является актуальной.
Сформулируем основную задачу, которая изучается в диссертации — это задача поиска точки равновесия Нэша следующей игры двух лиц.
Пусть выигрыш (или расходы) первого игрока выражается функцией
fi(x 1, ж2) = (ж1, Cix2 + ci) + l/2(ßi*i, xi), (0.2)
его стратегии
х С Ад = {х Е Б1”1 : х > 0, Ах < =
{xi Е Ещ : Xi > O,0ii(®i) = (ац, Xi) - bu < 0,i = l,mi}, (0.3)

2.2. Метод стабилизации
Здесь возможно использование идей и методов регуляризации, применяемых для решения неустойчивых (некорректных) задач [29]-[31]. Отметим, что методы регуляризации в сочетании со штрафными функциями [15], [17], [18] или с расширением множества [16] уже использовались для решения неустойчивых задач равновесного программирования, однако рассмотренные в этих работах классы задач не охватывают задачу (1. 3). Ниже предлагается и исследуется модификация метода стабилизации А.Н.Тихонова [29] для решения задачи (1. 15), (1. 16) при услових (2. 1), основанные на идее расширения множества.
Для описания и исследования того метода нам удобнее переформулировать задачу (1. 3).
VI*,х2* — ^2*) -решение задачи (1. 3), и наоборот, если ж* = (ть,Ж2*)-
образом, множества решений задачи (1. 3) и (1. 13) совпадают. Далее, вместо функции (1. 12) возьмем функцию
и рассмотрим задачу поиска точки д* £ IV, удовлетворяющей условию
Убедимся, что при В > 0 задача (2. 4) равносильна задаче (1. 13) и, следовательно, исходной задаче (1. 3).
Беря за основу задачу (2. 4), опишем метод стабилизации для решения исходной задачи (1. 3). Введем функции
задачи (1. 13), то пара г* = (ад*
решение задачи (1. 3), то г*
решение задачи (1. 13). Таким
Ф(т, и>) = ((С + В)у, ги) + (с,ги), v,/w Е ¥ (2-3)
Ф(т*,г*) < Ф(г*,гг) Уад £ У.
(2.4)
Фй(и, ч>) = {(С(5) + В +
(2.5)
(2.6)