Методы поиска точки равновесия в седловых играх двух лиц тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

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

Артемьева Людмила Анатольевна

МЕТОДЫ ПОИСКА ТОЧКИ РАВНОВЕСИЯ В СЕДЛОВЫХ ИГРАХ ДВУХ ЛИЦ

01.01.09 — Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 2013

005051476

Работа выполнена на кафедре оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Научные руководители: доктор физико-математических наук,

профессор Васильев Федор Павлович

доктор физико-математических наук, профессор Антипин Анатолий Сергеевич

Официальные оппоненты: доктор физико-математических наук,

профессор Васин Александр Алексеевич

кандидат физико-математических наук, доцент Молоствов Виталий Серафимович

Ведущая организация: Институт проблем управления

им. В.А. Трапезникова РАН

Защита диссертации состоится " 15 " марта 2013 года в 11 часов на заседании совета Д 501.001.44 при факультете вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. (495) 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» - «Работа диссертационных советов» - «Д 501.001.44».

Автореферат разослан " " февраля 2013 года.

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

Н.П. Трифонов

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

Актуальность работы. Теория игр, говоря кратко, это математическая теория принятия решений в конфликтных ситуациях. Усилиями многих ученых к настоящему времени исследованы широкие классы математических моделей конфликтных ситуаций различного характера (антагонистические, кооперативные, иерархические, динамические и.т.д.), имеется огромное количество монографий, учебных пособий, журнальных публикаций, посвященных теории игр (см. библиографию [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 страниц.

Содержание работы

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

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

В §1.1 формулируется постановка седловой игры. Пусть Ет - евклидово

ТП

пространство размерности тп, {а, Ь) = £ - скалярное произведение век-

г=1

торов а = (а1,...,ат)Т> Ь = (Ь1.....Ьт)т 6 Е™, Т - знак транспонирования;

N = хИ2)172 - норма в Ет- Е™ = {а е Ет : а > 0} - неотрицательный ортант в Ет\ функции ^(ад), Д(ш) = (/¿Н. ■••> /Г1 И) > 9\Ь») = (511Н,->5Г(и'))Т определены на ТУ0; функции й2(у), /2(у) = (/¿Ы.-. /™2 (у))Т > М = ЫМ.-.Л))7 определены на У0, гдеЖо С Етз, У0 С Ет1 - заданные множества; векторы г, г„ е Е+1, р, р* €

Рассмотрим задачу, в которой требуется найти точку (ги*,р*,у*,г*) £

Шо х Етг х У0 х Ет\ удовлетворяющую следующим условиям [2-4]:

<= Аг^пф (ш) + Л (ад)) \weWo, 31О) + /2(у») < 0}, (1)

(р-^йМ+ЛЫХО Ур&Е™', (2)

у, 6 Аг5тт{52(2/) + <р„ /2(у)> \ у е У0> 5г(у) + ЛК) < 0}, (3) ^-'•„йЫ + ЛЫХО УгеЯГ, (4)

где Аг^т{/(,г) | г € С}} - множество точек минимума функции /(г) на множестве <3.

Задачу (1)-(4) можно истолковать, как следующую игру двух лиц. А именно, будем предполагать, что поведение первого игрока описывается условиями (1), (2), поведение второго игрока - условиями (3), (4). Параметры (ш«,Р*) первого игрока, входящие в условия (3), (4) и параметры (у„г„) второго игрока, входящие в условия (1), (2), связывают эти условия в единую систему (1)-(4). Взаимодействие игроков происходит по следующей схеме. Сначала игроки сообщают друг другу какой-то набор своих параметров: первый игрок получает от второго игрока набор (у*, г*) € 1о х Е+1, второй получает от первого набор (ги,,р„) 6 х Е+2. Далее, первый игрок, рассматривая условия (1), (2) как задачу математического программирования с уже известными параметрами (у», г»), составляет функцию Лагранжа:

£ч{ю,р,у.,и) =5,1Н + (г<,,/1(ги)) + (р,51И+/2(2/,))1 ги 6 \У0, р е (5)

и определяет множество седловых точек Ащ8(И£1(ю,Р,У„,Гф), состоящее из точек (гй,р) 6 И^о х Еудовлетворяющих условиям:

£1(й,р,2/*,т-,) < ¿1 (гУ,р,г/.,г„) ^ £ч(и>,Р,У*,г,) Уги-е Ур <= Е™2 (6)

Аналогично второй игрок, рассматривая условия (3), (4) как задачу математического программирования с известными параметрами (ги„,р*), составляет свою функцию Лагранжа:

-СаК.р., у, г) = 5а(») +(р.,/2(»)) + <г,й(1/)+ /!(«;,)>, г/е У0, г € Я?1 (7)

и определяет множество седловых точек АгрсП^г^^р^у, г), состоящее из точек (у, г) е 1о х удовлетворяющих условиям:

¿2(™*,р*,у,г) ^ £2(у>*,Р*,У,г) < £,2(т„р„у,г) Уу € У0, Уг 6 Е?1 (8)

Таким образом определено седловое отображение, которое каждому набору точек (ш*,р„ у», г») 6 У/о х Е™2 х У0 х Е^1 ставит в соответствие множество точек:

(й),р,у,г) е А^всП£!(ш,р, у*, г*) х Argsdl£2(w<„p»,г/,r) (9)

6

Может случиться так, что это отображение будет иметь неподвижную точку (го„р„1/*,г,), то есть:

(гу,,р*,2/,,г») € Аг^Ш,£1(1и,р,2/„,г,) х Аг^сП£2{™*,р*,У,г) (10)

Такую точку называют точкой равновесия игры (1)-(10), и она является решением задачи (1)-(4) [2-4]. Если же условие (10) не выполняется, то игроки продолжают обмен информацией: они сообщают друг другу новые точки (ш,р), {у,г), взяв их из условия седла (6), (8), определяют значение сед-лового отображения (9), соответствующее точке (й),р,у,Г) - это множество АгрсИ/^ (и),р,у,г) х А^8с11£2(й>,р,у,г), проверяют, будет ли принадлежать точка (й),р,у,г) этому множеству и.т.д. Таким образом, на каждом шаге стратегией каждого из игроков является седловая точка соответствующей функции Лагранжа или Целью игры является нахождение точки равновесия, являющейся неподвижной точкой седлового отображения. Поэтому, описанную игру (1)-(Ю) принято называть седловой игрой [2-4, 13, 14].

Заметим, что седловая игра (1)-(10) сочетает в себе идеи равновесия как по Нэшу, так и по Парето: с одной стороны игроки при поиске седловых точек (6), (8) с известными параметрами (и)*,р*), (у*,г*) преследуют свои цели по правилам характерным для игры Нэша, с другой стороны у них есть совпадающие интересы заключающиеся в совместном согласованном поиске точки равновесия путем специального выбора коэффициентов свертки при формировании целевой функции, что соответствует равновесиям по Парето.

Переформулируем седловую игру (1)-(10) в более удобной для исследования форме. Для этого введем следующие обозначения:

1п — единичная матрица пх п,

(И)

и определим функцию:

£(х, А) = S(x) + (B\,f{x)) + (A,g(x)), х е Х0, \ е Е™ (12)

Переменную х будем называть прямой переменной, А - двойственной переменной седловой игры.

Теорема 1.1.1. Точка (itf*,p*,y»,r*) = (а;», Л») G Хо х Е™ является точкой равновесия седловой игры (1)-(10) тогда и только тогда, когда она является седловой точкой функции (1^2) в следующем смысле:

С(х„ А) < Z(xt, А,) < £(js, А») Va; € Х0, VA € Е™ (13)

Таким образом, согласно этой теореме, поиск точки равновесия седловой игры (1)-(10) можно свести к поиску седловой точки функции (12).

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

Во второй главе предлагаются и исследуется сходимость экстраполя-ционного градиентного и проксимального (или, короче, экстраградиентного и экстрапроксимального) методов.

В §2.1 рассматриваются различные варианты итерационного экстраградиентного метода (симметричный, прямой и двойственный) [13] в предположении, что множество Хо выпукло и замкнуто, функции S(x), f(x), g(x) дифференцируемы на Xq. Тогда функция £(х,\) (12) имеет частные градиенты:

^^ = &{х) + mTf(x) + А Тд'(х),

яг( \\ (14)

= BJf(x) + g(x), х е Хо, А 6 Л0 ^

где S'(x), f'(x), g'(x) - градиенты функций S(x), f(x), g(x), x e Хо соответственно.

Итерационный симметричный экстраградиентный метод тогда описывается следующим образом. Пусть хо € -АГо, Ао £ Ло - некоторая начальная точка процесса. Если известно к- ое приближение хк € Xq, А * € Ло, к ^ 0, то сначала делаем прогнозный шаг, на котором определяем экстраполяционную точку по правилу:

( а д£,(хк,\к)\ х ( , д д£(хк,\к)\

Хк = 1Тх0 1хк - Рк--I, лк = 7ГЛо I Afc + Рк-- I, (15)

где ттга - проекция точки а на множество Z, fa > 0 - длина шага метода. Затем, в полученной точке {хк, вычисляем градиенты , и

делаем основной шаг:

= Aj.+i = тгЛэ (a. + A^I^), (16)

где к = 0,1,.... Так как в метод (15), (16) прямые переменные х* = (гик, Ук)т и двойственные переменные А*, = (рк,Гк)т входят симметрично, то этот метод называется симметричным экстраградиентным методом.

Сходимость метода (15), (16) исследуется в предположении, что выполнены следующие условия:

I Множество Х0 = ]¥0 х Уо выпукло, замкнуто.

II Функции 5(х), /(а;), д(х) выпуклы и непрерывно-дифференцируемы на Х0.

III На любом ограниченном подмножестве с Хо функции Б(х), /(ж), д(х) и их градиенты Б'(х), }'{х), д'(х) удовлетворяют условию Липшица:

тах{|5(а;1) - 3(х2)\] \/(хг) - /(х2)|; \gixi) - £?С^2>|> ^ Ь0\х1~х2\, та^'(х,) - 5'(х2)|; |/'(*х) - /'(х2)|; |</(*1) - д'(х2)|} < Ь0\Х1 - х2\,

УХ\,Х2 €

(17)

где постоянная Ьо > 0 зависит от Хх.

IV Множество 5* точек равновесия седловой игры (1)-(10) непусто.

V Начальная точка (хо, Ао) € Хо х Ло выбрана произвольным образом.

VI Длина шага /Зк экстраградиентного метода такова, что:

О < Апт < & ^ Апах < тш ^ } , (18)

где Ь\ - константа Липшица для частных градиентов ¿х ¿А , соответствующая шару 5о достаточно большого радиуса, содержащему начальную точку (хо, Ао) и какую-либо точку из 5»; шар £о строится в процессе доказательства сходимости экстраградиентного метода.

Метод (15), (16) был впервые предложен в [7] для поиска седловых точек выпукло-вогнутых функций и его сходимость была доказана в предположении, что градиенты В£^, удовлетворяют условию Липшица по совокуп-

ности переменных на множестве Хо х Ло- Однако, в седловой игре (1)-(10) множество Л0 = неограничено и, как видно из формул (14), даже с учетом условий (17), градиент может не удовлетворять условию Липшица. Это значит, что сходимость метода (15), (16) в седловых задачах (13) не будет

вытекать из работы [7], поэтому нужно развивать технику исследования сходимости этого метода для седловых игр. Проведенный в диссертации анализ метода^(15), (16) показал, что траектория {(я*,Ай), к = 0,1,...}, порождаемая этик методом, принадлежит некоторому множеству 5о С Х^ х Е™, на котором градиенты , удовлетворяют условию Липшица:

тах <

dZ(zUfj,i) dL(z2,ß2)

d£(zUß i) d£(z2>ß2)

дХ дХ

€

(19)

дх дх

< Li(| Zi - Z21 + l/Líl - Ц2\), V(zi,fll), (z2,fl2) eSoCljX^

Заметим, что постоянна Li из (19) входит в условие (18).

Теорема 2.1.1. Пусть выполнены условия I-VI. Тогда последовательность {uk} = {(хк, Ajc)T}, порождаемая методом (15), (16), монотонно сходится к некоторой точке равновесия s» игры (1)-(10):

|ujfe+i - s«| < - s«|, А; = 0,1,..., lim - s»| = 0

k-t oo

Наряду с симметричным экстраградиентным методом (15), (16) в §2.1 рассматриваются методы, в которых прогнозный шаг дедается лишь по одной из переменных х или Л. В результате получаются еще два варианта итерационного экстраградиентного метода - прямой и двойственный.

В прямом экстраградиентном методе прогнозный шаг делается по прямым переменным х = (w,y)T:

= (20)

основной шаг:

Afc+i = я-А к + ßk

д£>{хк,Хк) дх

д£(хк,Хк)

«г í-r. я dC(xk,\k+i)\ Хк+1 = 7ГХ„ I хк - ßk-Q^-I

дх

, fc = 0,l,...

(21)

В двойственном экстраградиентном методе прогнозный шаг делается по двойственным переменным А = (р, г)т:

= + (22)

основной шаг:

г (г я . , Л . я д£(хы,~Хк)\

Хк+1 = Кх0 I Хк - Рк-о^-I , Хк+1 = I хк + Рк-дд-I,

где к = 0,1,.... При выполнении условий 1-У и достаточно малом параметре метода > 0, к = 0,1,..., методы (20), (21) и (22), (23) монотонно сходятся к одной из точек равновесия седловой игры (1)-(10) [13]. В диссертации доказываются соответствующие теоремы сходимости.

В §2.2 предлагаются и исследуются различные варианты дифференциального экстраградиентного метода при тех же предположениях 1-У относительно седловой игры, что и в §2.1 [14]. В этом методе точка равновесия седловой игры (1)-(10) определяется как предел при £ —»■ оо решения задачи Коши для некоторой системы обыкновенных дифференциальных уравнений с обратной связью.

В случае симметричного дифференциального экстраградиентного метода эта задача Коши имеет следующий вид:

лед + лад = +

(24)

(25)

®(0) = хо, Л(0) = Л0 (26)

Функции х(¿), Л(<) определяемые формулами (24) являются аналогами прогнозных шагов в методе (15), (16), и в (25) выполняют роль обратной связи [9]. Заметим, что метод (15), (16) можно истолковать как разностный метод Эйлера для задачи Коши (24)-(26) [10]. Однако, дифференциальный метод

(24)-(26) привлекателен тем, что для приближенного решения задачи Коши может быть использован не только метод Эйлера, но и другие известные методы [10], которые, возможно, будут сходиться быстрее и будут лучше приспособлены для поиска седловой точки. Это обстоятельство оправдывает рассмотрение дифференциальных методов.

Теорема 2.2.1. Пусть выполнены условия 1-У. Тогда существует, притом единственное решение и(Ь) = {х(Ь), А^))т задачи Коши (24)-(26), определенное при всех £ ^ 0, которое принадлежит некоторому шару £о достаточно большого радиуса, содержащему начальную точку (хо, Ао) и какую-либо точку равновесия в, седловой игры (1)-(10), если параметр /3(£) в (24),

(25) непрерывен при всех Ь ^ 0 и удовлетворяет условию:

0<А„1п<^)<А11в<тш|1;^-| (27)

И 1 и

где постоянная L\ > О взята из условия Липшица (19).

Теорема 2.2.2. Пусть выполнены условия I-V. Длина шага ß(t) взята из (27). Тогда решение u(t) = (x(t),X(t))r задачи Коши (24)-(26) при t —ï оо монотонно сходится к некоторой точке равновесия s, седловой игры (1)-(10):

|к(т) - s,| < |u(f) - 5,1, Vt ^ t ^ О, lim \u(t) - s*| = О

Прямой дифференциальный экстраградиентный метод описывается задачей Коши:

(28)

i(l)+x(t)=n,(x(t)-mÊ£mrn±m), <29)

®(0) = во, А(0) = Ао (30)

Двойственный дифференциальный экстраградиентный метод описывается задачей Коши:

+ (31)

^^-^(äW + ^^M+J«), (32)

х(0) = х0, Л(0) = Л0 (33)

При выполнении условий I-V и достаточно малом параметре ß(t), t ^ 0 методы (28)-(30) и (31)-(33) монотонно сходятся к одной из точек равновесия седловой игры (1)-(10).

В §2.3 рассматриваются три варианта экстрапроксимального метода [15]. Симметричный экстрапроксимальный метод состоит из прогнозного шага:

хк = argmin{i|z - хк\2 + ßk£(x, Хк)\х е Х0}, (34)

Äfc = argmin{i|A - А*| - ßk£(xk, A)|A 6 E™} (35)

12

и основного шага:

Zfc+i = argmin{^|x - хк\2 + fa£(x, ЛОк 6 Х0}, (36)

At+i = argmin{i|A - Afc| - fa£(xk, А)|А 6 В™} (37)

Сходимость метода (34)-(37) исследуется в предположении, что выполнены следующие условия:

VII Множество Х0 = W0 х Y0 выпукло, замкнуто.

VIII Функции S(x), f(x), д(х) определены и выпуклы на Х0, непрерывны на Х0. Кроме того, функции f(x), д(х) на Хо удовлетворяют условию Липшица:

max{|/(xi) - f(x2)I; \д{х{) - £(х2)|} < Цхi - х2\, Чхих2 6 Х0

IX Множество S* точек равновесия седловой игры (1)-(10) непусто. X Начальная точка (жо,Ао) S Х0 х Л0 выбрана произвольным образом. XI Параметры fa таковы, что:

О < Anin < fa ^ Ana* < fe = 0,1,...

При выполнении этих условий в каждой из задач минимизации (34)-(37) целевая функция сильно выпукла, точки (¿6*, Хк)т, (хк,Хк)т определяются однозначно и для их определения могут быть использованы известные методы [И]. В частности, имея ввиду линейность функции L(x, А) (12) по переменой А и, пользуясь характеристическим свойством проекции, условия (35), (37) часто заменяют эквивалентными легко вычислимыми равенствами:

i Л l0dC(xk,\k)\ ( дЦхк,Щ h = ке? I h + fa--- I , Afc+i = тгву I Ак + Рк-дд-I

соответственно. Заметим также, что метод (34)-(37), как и экстраградиентные методы допускает распараллеливание.

Теорема 2.3.1. Пусть выполнены условия VII-XI. Тогда последовательность {и*} = {(хк, A¡t)}T, порождаемая методом (34)-(37), монотонно сходится к одной из точек равновесия седловой игры (1)-(10).

Также в §2.3 рассматриваются прямой и двойстенный экстрапроксимальные методы, показывается, что при выполнении условий УН-Х1 эти методы монотонно сходятся к одной из точек равновесия седловой игры (1)-(10).

В §2-4 исследуется дифференциальный экстрапроксимальный метод [16]. Симметричный дифференциальный экстрапроксимальный метод выглядит следующим образом:

х{£) = аг^пД - х(*)|2 + А(£))|х е Х0},

2 (38)

Щ = ацрпш{-|А - А(*)| - /?(«)£(*(*), А)|А е КУ

х{г) + х(Ь) = ах^шфх - х(г)|2 + /?(*)£(х, А(«))|х €

Щ + Аф = агршпфА - А(4)| - /?(*)£(х(*), А)|А € Е%}, % > О, (ЗЭ) х(0) = х0, А(0) = А0

Теорема 2.4.1. Пусть выполнены условия УП-Х, параметр ¡3(Ь) метода непрерывен при всех £ ^ 0 и удовлетворяет условию:

О < йпш < /?(<) ^ Ртах < V« >0 (40)

Пусть система (38)-(39) имеет единственное решение и(£) = (х(£),А(£))т при всех Тогда это решение монотонно сходится к некоторой точке

равновесия .9» седловой игры, (1)-(10).

Также рассматривается прямой дифференциальный экстрапроксимальный метод и двойственный дифференциальный экстрапроксимальный метод, доказывается, что при выполнении условий УН-Х эти методы монотонно сходятся к одной из точек равновесия седловой игры (1)-(10).

Третья глава посвящена методам поиска точки равновесия седловой игры (1)-(10), в случае когда входные данные Б(х), /(ж), д(х) и их градиенты £"(х), /'(х), д'(х) заданы неточно и в нашем распоряжении имеются лишь их приближения Бк(х), /к(х), дк(х), $'к(х), Д(х), д'к(х), х 6 Х0, к = 0,1,.... Казалось бы, в этом случае по аналогии с (12) можем составить приближенную функцию Лагранжа:

£к(х, А) = Бк{х) + (А, ВТ/к(х) + дк(х)), х е Х0, А € Е?, к = 0,1,..., (41)

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

14

пути точки (хк„ А*»), к = 0,1,... могут сильно отличаться от точки равновесия седловой игры (1)-(10) [11, 12]. Поэтому для поиска седловых точек при неточных входных данных нужно разрабатывать специальные устойчивые методы. Такие методы могут быть получены путем регуляризации методов главы 2.

В §3.1 расматривается регуляризованный экстраградиентный метод [17] в предположении, что выполнены условия ¡-V и приближенные входные данные таковы, что:

max{|S*(z) - S(x)|, \fk{x) - f(x)\,\gk(x) - <?(z)|} < 4(1 + M), x e

(42)

max{|Si(a;) - 5'(x)|,\f'k(x) - f(x)\, \g'k(x) - g'(x)|} ^ Sk, x e X0, k = 0,1,...,

где Sk ^ 0 - параметр, характеризующий погрешность. Введем функцию:

которую будем называть функцией Тихонова игры (1)-(10). Здесь ак > 0 -параметр регуляризации, lim ak = 0. В качестве приближений для частных

градиентов этой функции = + акх, = ^ - ак\,

(43)

Тк(х, А) - £i(x,X) + \ак(\х\2 - |А|2), х Q Х0, X € (44)

к—о

Регуляризованный симметричный экстраградиентный метод: прогнозный шаг:

** = (*, - Ä^g^) , А^ = (А, + , (45)

Zfc = T^Xi

основной шаг:

где ßk > 0 - параметр метода.

Теорема 3.1.1. Пусть выполнены условия I-V, погрешности входных данных седловой игры (1)-(10) удовлетворяют условиям (42), (43), параметры {аь}, {ßk}, {4} таковы, что:

S 1

otk > 0, 5к > 0, к = 0,1,..., lim ак = 0, lim 5к = О, sup — < —,

к-*оо к-*оо к> Oik 28

00 г

УЧ = +ос, = lim — = О,

^ ак Ь^00 ак

(47)

О < 4афк + 16/3kök < 1, ßk [2Li + 12 sup 6k + 4 sup ak ) <1,

V k£0 fc»0 /

О < \akßk{l ~ 56^ + ±akßk - UßkSk) < 1, (4g)

О < \akßk{ 1 - 28—) < 1, 2 oik

О < Anin «S Ä < ßmax. < ß, к = О, 1, ..,

где постоянная Li взята из условия (19). Тогда последовательность {ик = (хк, А^)т}; порождаемая методом (45), (46), сходится к нормальной точке равновесия и*, |и„| = inf |s*| седловой игры (1)-(10), причем сходимость равномерная относительно выбора приближенных входных данных из условий (42), (43).

В прикладных задачах входные данные, как правило, известны с некоторой фиксированной погрешностью. В частности, в седловой игре (1)-(Ю) вместо условий (42), (43) где {¿¡t} -» 0, более реальным представляется следующее условие: вместо точных входных данных:

h=(S(x),f(x),g(x),S'(x)J'(x),g'(x)), х е Х0, известны приближения:

hs = (S6{x)Js(x),g6{x),S'5(x),fs{x),g'ö(x)), х е Х0,

такие, что:

тах{|ЗД - S(x)|, |/,(г) - f(x)|, \g5{x) - g(x)\} < S( 1 + |®|), x 6 X0, (49)

шах{|ад-5(®)|,№)-/(®)|,Ш®)-<7(а;)|}<5, x e XQ, (50)

где 5 > 0 - фиксированное число. Возникает вопрос, как распорядиться набором Ні и построить оператор Н$, который каждому набору из (49), (50) ставит в соответствие точку = и(5) = (х(5),\(6))т, которая близка к множеству й» точек равновесия игры (1)-(10) при достаточно малых 5 > 0. Такой оператор, следуя [11, 12] будем называть регуляриаующим. Оказывается, для построения такого оператора можно воспользоваться методом (45), (46) и соответствующей теоремой о сходимости. Точнее, рассмотрим метод:

( о дт6(хк,Хк)\ ^ ( дт6(хк,Хк)\

хк = пХо I Хк- рк-^-I , Хк = 7ГЕ? I А* + рк-^- I ,

( о дт6{хк,Хк)\

Хк+1 = ТГЛГо ( Хк - Рк-^- ) , (51)

+ к = 0,1,...,

Метод (51) получен из метода (45), (46) заменой функций дп^, дпна:

^^ = + (ВХ)т/'5(х) +

ох ^52)

дТб(£Х) = ВтМх) + 96{х), х Є Хо, X є Е™

Начальная точка (яо, Ао) и параметры {ак}, {Дь}, удовлетворяющие

условиям (47), (48), считаются фиксированными и не зависят от 5 > 0. Процесс (51) продолжается до такого наибольшего номера к = к(6), при котором выполняются неравенства:

5к>5, Л = 0,1,-.*:(*)■ (53)

йеі

Если 8 ^ ¿о, то полагаем к(5) = 0.

Оператор В,5 определяется следующим образом:

Щкц = и{8) = (хед, Аад)т, 5> 0 (54)

Теорема 3.1.3. Пусть выполнены все условия теоремы 3.1.1 сходимости метода (45), (46), кроме условий (42), (43). Приближения /іг удовлетворяют условиям (49), (50), и известна оценка Я ^ для какой-либо точки равновесия з» Є й1*. Пусть оператор В,$ определен согласно (51), (54). Тогда:

Нтр(и(<5), 5») = 0, р{и,8*)= Ы \u-sl (55)

<5—>0

причем сходимость в (55) равномерна относительно выбора приближений из (49), (50).

Также в §3.1 рассматривается регуляризованный прямой экстраградиентный метод, доказывается теорема сходимости этого метода, по аналогии с регуляризованным симметричным экстраградиентным методом строится ре-гуляризующий оператор.

В §3.2 рассматривается регуляризованный дифференциальный экстраградиентный метод [18] в предположении, что выполнены условия I-V и приближенные входные данные S(x, t), f(x, t), g(x, t), S'(x, t), f'(x, t), g'(x, t), x € Xo, таковы, что:

шах{|S(x,t) - S(x)\, |f(x,t) - f(x)I, \g(x,t) - g(x)\} < S(t)( 1 + |z|), г £ X0,

(56)

max{|S'(M)-S'(z)l, \f'(x,t) - f'(x)\, \g'(x,t) - g'(x)\} < 6(t), x 6 X0, t > 0,

. (57)

где 6(t) > 0 - параметр, характеризующий погрешность. Подчеркнем, что в (57) функции S'(x,t), f'(x,t), g'(x,t) необязательно являются градиентами функций S(x,t), f(x,t), g(x,t), это лишь приближения для градиентов функций S(x), f(x), g(x).

Для описания регуляризованного дифференциального экстраградиентного метода введем следующую функцию:

Т(®А <)=£(*, A)+ |a(t)(|z|a-|A|l). х е Х0, А е Е™, (58)

которую будем называть функцией Тихонова игры (1)-(10). Здесь a(t) > 0, t ^ 0 - параметр регуляризации.

В качестве приближений функции (58) и ее частных градиентов возьмем следующие функции:

r(x,X,t) = L(x,X,t) + ^a(t)(\x\2 ~\Х\2), хеХ0, А € Я?, dr(x,x,t) дЩ(х,х) |

дх дх

dr(x,X,t) _ dZ{t)(x, А)

дХ ~ дХ

- a{t)A, t > 0

Регуляризованный симметричный дифференциальный экстраградиентный метод описывается следующей задачей Коши:

2(0 = тгхо - ß

dT(x(t),X(t)tt) дх

m-m- (л«+,t>0

s(0) = A(0) = A0, x0 6 X0, A0 € E?

Теорема 3.2.1. Пусть выполнены условия I-V, приближенные входные данные удовлетворяют условиям (56), (57) и, кроме того, на любом ограниченном подмножестве Х\ с Хо выполняются условия Липшица:

шах{|S(xbt) - S(x2,t)|f(xut) - f(x2,t)\, \g(xut) - g(x2,t)\} ^ L2\xi - x2\, Vxi,x2eXi, 0

max{| SW)-SW)U/W)-/W)I, (61)

\g'(xut)-g'(x2,t)\} <La|®i-ia|, Vxltx2 e Xu tè 0, Пусть параметры a(t), ¡3(t), 5(t), t ^ 0 метода (59) непрерывны, a(t), @(t) непрерывно-дифференцируемы и a(t) выпукла при t ^ 0, и, кроме того:

a(t)> 0, â(t)>0, 0 Vi^O, sup Ш <

(62)

inf /?(i) > 0, /3'(i) ^ 0, lim = 0, t^o 4 ' «-юо a(t)

0</3(^min{l;2i.i + 12^)+4Q(J V^O

Тогда существует, притом единственное решение u(t) — (x(t),\(t))T задачи Коши (59), определенное при ecext ^ 0, которое принадлежит некоторому шару So достаточно большого радиуса, содержащему начальную точку (яо, Ао) и какую-либо точку равновесия s, седловой игры (1)-(10).

Теорема 3.2.2. Пусть выполнены условия I-V, (56), (57), (60), (61), (62). Тогда решение u(t) = (x(t), A(i))T, t ^ 0 задачи Коши (59) сходится к нормальной точке равновесия щ седловой игры (1)-(10), причем эта сходимость равномерная относительно выбора приближенных входных данных S{x,t), f(x,t), g(x,t), S'(x, t), f'(x,t),J(x,t), xeX0 из условий (56), (57).

Аналогично тому, как это сделано в §3.1 на базе теоремы о сходимости строится регуляризующий оператор Ду в случае, когда приближенные входные данные ¡11 удовлетворяют условиям (49), (50). Далее в работе рассматривается регуляризованный прямой дифференциальный экстраградиентный метод, доказывается теорема сходимости, строится регуляризующий оператор.

В §3.3 рассматривается регуляризованный экстрапроксималъный метод [19] в предположении, что выполнены условия УН-Х и приближенные входные данные удовлетворяют условию (42).

Регуляризованный симметричный экстрапроксимальный метод: прогнозный шаг:

xk = argmin{^|a; - xk\2 + ßkrk(x, Xk) \ x e X0}, Xk = argmin{i|A - Afc|2 - ßkTk{xk, А) | А € E

основной шаг:

xk+i = argmin{^|a; - а^2 + ßkrk(x, Xk) \ x e ^o}, Afc+i = argmin{i|A - Xk\2 - ßkTk(xk, А) | А € E™}, ßk > 0, k = 0,1,...

(63)

(64)

Теорема 3.3.1. Пусть выполнены условия VII-X, (42). Пусть параметры {ak}, {ßk}, {¿¡ь} метода (63), (64) таковы, что:

ак > 0, 5к > 0, к — 0,1,..., lim ак — 0, lim 6к = 0,

к-Уоо к->оо

f>fc = oo, um K±LZ£»l = о, f-t к^>оо ai

x (65)

V ak ^ n r ö*

lim-= ao > 0, hm — =0,

&-»oo Ctk+l Ä:—>oo Oik

Тогда последовательность = {(xk, А^)т}; порождаемая методом (63), (64), сходится к нормальной седловой точке и« равномерно относительно выбора функций Sk(x), fk(x), gk(x) из условий (42).

Если приближенные входные данные hs удовлетворяют условию (49), то регуляризующий оператор Rs можно строить на базе метода (63), (64) также как и в случае регуляризованного экстраградиентного метода.

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

В §3-4 рассматривается регуляризованный дифференциальный экстрапроксимальный метод [20] в предположении, что выполнены условия VII-X, приближенные входные данные S(x, t), f(x, t), g(x, t) удовлетворяют условию (56).

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

x{t) = argmin{^|a; - x(t)\2 + ß(t)r(x, X(t),t) | x e X0},

X(t) = argmin{^|A - A(i)|2 - ß(t)T(x{t), A,i) | A €

x(t) + x{t) = argmin{±|z - x(t)\2 + ß(t)r(x, X(t), t) | x S X0}, (66)

X(t) + A(t) = argmin{^|A — A(i)|2 — ß(t)r(x(t), A,í) | A 6 E™}, i > 0,

ж(0) = xq, A(0) = A0

Теорема 3.4.1. Пусть выполнены условия VII-X, (56), параметры a (t), ß(t), ö(t), í ^ 0 метода таковы, что a(t), ß(t) - непрерывно-дифференцируемы, ó(t) - непрерывна при t >0, и, кроме того:

a(t) > 0, 5(t) > 0, a'{t) < 0, ß\t) ^ 0,

г ( (A i тл , , i ^ п

hm («(t) + 5(t) + W)+ ^щщ + щщ^) = 0,

1 -supß(t)(L + 245(t)) > 0 о

Пусть система (66) имеет единственное решение u{t) = (x(t), X(t))T, t ^ 0, тогда:

lim |m(í) — u»| = 0, (67)

Í-+ 00

где и, - нормальная седловая точка функции (12), причем сходимость в (67) равномерна относительно выбора приближенных входных данных S(x,t), f{x,t), g{x,t) из условий (56).

Если приближенные входные данные h¡ удовлетворяют условию (49), то

регуляризующий оператор R¡ можно строить на базе метода (66) также, как и

в случае регуляризованного дифференциального экстраградиентного метода.

21

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

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

Основные результаты, выносимые на защиту

1) Разработаны экстраградиентные и экстрапроксимальные методы поиска точки равновесия седловой игры в итерационной и дифференциальной формах, доказана их сходимость, развита техника исследования сходимости таких методов.

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

Список литературы

1. Васин A.A., Морозов В.В. Теория игр и модели математической экономики. М.: МАКС-Пресс, 2005.

2. Антипин А. С. Равновесное программирование: модели и методы решения.// Известия Иркутского государственного университета. Серия «Математика». 2009. 2. №1. С.8-36.

3. АнтипинА. С. Седловые игры двух лиц: модели и методы решения.// Материалы IV всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск. 2009. С. 10-15.

4. Антипин А. С., Попова О. А. О равновесной модели кредитного рынка: постановка задачи и методы решения.// ЖВМиМФ. 2009. 49. №3. С.465-481.

5. Демьянов В. Ф., ПевныйА. Б. Численные методы разыскания седловых точек.// ЖВМиМФ. 1972. 12. №5. С. 1099-1127.

6. Гольштейн Е. Г., Третьяков Н. В. Модифицированные функции Лагранжа. М.: Наука. Физматлит. 1989.

22

7. Корпелевич Г. М. Экстраградиентный метод для отыскания седловых точек и других задач. // Экономика и математические методы. 1976.12. вып. 9. С. 747-756.

8. Антипин А. С. Об одном методе отыскания седловой точки модифицированной функции Лагранжа. // Экономика и математические методы. 1977. 13. №3. С.560-565.

9. АнтипинА. С. Седловые градиентные процессы, управляемые с помощью обратных связей.// Автоматика и телемеханика. 1994. №3. С.12-23.

10. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. М.: Наука, 1987.

11. Васильев Ф. П. Методы оптимизации. Т. 1,11. М.: МЦНМО, 2011.

12. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1986.

Публикации автора по теме диссертации

13. Артемьева JI. А. Экстраградиентный метод поиска точки равновесия в седловых играх двух лиц. // ЖВМиМФ. 2011. 51. №12. С. 2143-2157.

14. Артемьева Л. А. Дифференциальный экстраградиентный метод поиска точки равновесия в седловых играх двух лиц. // Дифференциальные уравнения. 2012. 48. №1. С.79-92.

15. Васильев Ф.П., Антипин A.C., Артемьева Л.А. Экстрапроксимальный метод решения седловых игр двух лиц. // ЖВМиМФ. 2011. 51. №9. С. 1576-1587.

16. Васильев Ф.П., Антипин A.C., Артемьева Л. А. Дифференциальный экстрапроксимальный метод поиска точки равновесия в седловых играх двух лиц. // Дифференциальные уравнения. 2011. 47. №11. С. 1551-1563.

17. Артемьева Л. А. Регуляризованный экстраградиентный метод поиска точки равновесия в седловых играх двух лиц. // ЖВМиМФ. 2012. 52. №4. С. 585-601.

18. Артемьева Л. А. Регуляризованный дифференциальный экстраградиентный метод поиска точки равновесия в седловых играх двух лиц. //

ЖВМиМФ. 2012. 52. №9. С. 1582-1600.

23

19. Васильев Ф.П., Антипин A.C., Артемьева JI. А. Регуляризован-ный экстрапроксимальный метод поиска точки равновесия в седловых игр двух лиц. // ЖВМиМФ. 2012. 52. №7. С. 1231-1600.

20. Васильев Ф.П., Антипин A.C., Артемьева JI.А. Регуляризо-ванный дифференциальный экстрапроксимальный метод поиска точки равновесия в седловых игр двух лиц. // Вычислительные методы и программирование. 2012. 13. С. 149-160.

21. Васильев Ф.П., Антипин A.C., Артемьева J1. А. Экстрапроксимальный метод поиска точки равновесия в седловых играх двух лиц, // Тихоновские чтения. Тезисы докладов. М: Макс Пресс. 2011. С.19-20.

22. Артемьева JL А. Непрерывный экстраградиентный метод поиска точки равновесия в седловых играх двух лиц. // Сборник тезисов XVIII международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2011». М.: Макс Пресс. 2011. С.29-30.

23. Васильев Ф.П., Антипин A.C., Артемьева JI.А. Дифференциальный экстрапроксимальный метод поиска точки равновесия в седловых играх двух лиц. // Ломоносовские чтения. Тезисы докладов. М: Макс Пресс. 2011. С.86.

24. Артемьева Л. А. Экстраградиентный метод в седловых играх двух лиц с неточно заданными входными данными. // Сборник тезисов XIX международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2012». Издательский отдел ВМК МГУ имени М.В. Ломоносова. 2012. С.55-56.

25. Васильев Ф.П., Антипин A.C., Артемьева Л.А. Регуляризо-ванный экстрапроксимальный метод поиска точки равновесия в седловых играх двух лиц. // Тихоновские чтения. Тезисы докладов. М: Макс Пресс. 2012. С.29.

Напечатано с готового оригинал-макета

Подписано в печать 31.01.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 110 экз. Заказ 025.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Введение

Глава 1. Седловые игры двух лиц.

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

1.2. Содержательный смысл седловой игры двух лиц.

Глава 2. Методы поиска точки равновесия в седловых играх двух лиц.

2.1. Итерационный экстраградиентный метод.

2.2. Дифференциальный экстраградиентный метод.

2.3. Итерационный экстрапроксимальный метод.

2.4. Диферснциальный экстрапроксимальный метод.

Глава 3. Методы поиска точки равновесия в седловых играх двух лиц в случае неточно заданных входных данных.

3.1. Регуляризованный экстраградиентный метод.

3.2. Регуляризованный дифференциальный экстраградиентный метод.

3.3. Регуляризованный экстрапроксимальный метод.

3.4. Регуляризованный дифференциальный экстрапроксимальный метод.

Теория игр, говоря кратко, это математическая теория принятия решений в конфликтных ситуациях. Усилиями многих ученых к настоящему времени исследованы широкие классы математических моделей конфликтных ситуаций различного характера (антагонистические, кооперативные, иерархические, динамические и.т.д.), имеется огромное количество монографий, учебных пособий, журнальных публикаций, посвященных теории игр [18, 2736, 38-40, 47-52, 54, 57-59, 61-80, 83-86].

В настоящей работе рассматривается относительно новый класс задач теории игр, которые можно назвать седловыми играми двух лиц, предлагаются и исследуются методы поиска точки равновесия таких игр [11-13]. В таких играх каждый игрок распоряжается функцией двух векторных переменных, выбирает седловую точку своей функции и свой выбор (свою стратегию) сообщает другому игроку. Предполагается, что функция каждого игрока зависит от седловой точки другого игрока как от параметра, поэтому седловая точка, выбираемая каждым игроком, влияет на выбор седловой точки другого игрока. Такой взаимозависимый выбор ссдловых точек каждым игроком в совокупности порождает седловое отображение. Неподвижная точка этого отображения называется точкой равновесия рассматриваемой седловой игры. Игроки, последовательно обмениваясь седловыми точками, согласуя свои действия, ищут эту неподвижную точку. Такая точка выгодна каждому игроку и определить ее - это цель седловой игры. Точное описание математической модели этой игры дается ниже. Пока мы лишь скажем, что седловые игры возникают при моделировании различных экономических ситуаций, таких как, например, равновесная модель кредитного рынка, равновесная модель взаимодействия двух предприятий, использующих продукцию друг друга как сырье, модель равновесной поставки ресурсов, равновесная модель фирмы, равновесный выбор весовых коэффициентов в задачах многокритериальной оптимизации и другие [4, 11-13].

Каждой седловой игре можно сопоставить некоторую функцию, такую, что всякая точка равновесия седловой игры является седловой точкой этой функции. Можно сказать, что такая функция в седловой игре выполняет такую же роль, как и функция Лагранжа в обычной задаче математического программирования. Это значит, что задача поиска точки равновесия седловой игры может быть сведена к седловой задаче, и здесь, казалось бы, можно использовать известные методы поиска седловой точки [37, 41]. Однако, сходимость таких методов доказывается при весьма жестких требованиях на входные данные (условия типа сильной выпуклости целевой функции, компактности допустимого множества ссдловых параметров). Развитые позднее экстраполяционныс методы поиска ссдловых точек (экстраградиентныс, экстрапроксимальныс методы [1, 55, 56]) сходятся при традиционных требованиях (например, условия Липшица для градиентов функции Лагранжа). Однако, как выяснилось, в ссдловых играх эти традиционные условия не всегда выполняются. Поэтому разработка новых вариантов экстраполяциопных методов поиска седловой точки, развитие техники доказательства сходимости этих методов при умеренных требованиях на входные данные задачи, является актуальной проблемой. Кроме того, важно заметить, что седловые задачи, вообще говоря, неустойчивы к погрешностям задания входных данных и для поиска ссдловых точек нужно использовать специальным образом регуляризованные экстраполяционныс методы. Таким образом, разработка устойчивых методов поиска точек равновесия в ссдловых играх является актуальной задачей теории игр.

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

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

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

Краткое содержание работы.

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

В §1.1 формулируется постановка седловой игры. Пусть Еш - евклидот во пространство размерности га, (а, Ь) — ^ агЬг - скалярное произведение г=1 векторов а = (а1,., ат)т, Ь = (Ь1,.,Ьт)Т е Ет, Т - знак транспонирования; \а\ = (Тл=\(а1)2)1/2 ~ н°Рма в Е+ = (а е Ет : а ^ 0} - неотрицательный ортант в Ет-, функции ¿^(-ш), /1(10) = (/^(ги),., /]П1(и;))Т, 01М = ЫЫ'-^Г2^))7" определены на функции 52(у), /2(у) = (Я(У)> - ч ¿ТЧу))7, 02 (у) = (р2(у),-,рГ(г/))Т определены на У0, где С Етз, 1о С - заданные множества; векторы г, г* е Е1™1, р, р* € Е™2.

Рассмотрим задачу, в которой требуется найти точку у*, г*) е

И^о х Е7П2 х Г0 х , удовлетворяющую следующим условиям [11-13]: ги, е А^гшп-^О) + (г*, /1(10)) | гу е И'0) 51И + /2Ы ^ 0}, (1) р-Р^1М + Ш)<О Уре^2, (2)

У* е Агётт{52(у) + /2(у)) | у Е У0, Рг(у) + ЛК) ^ 0}, ■ (3) г-г„йЫ + /1Ы<0 Угедр, (4) где А^тт{/(,г) | 2 £ <3} - множество точек минимума функции /(г) на множестве (3.

Задачу (1)-(4) можно истолковать, как следующую игру двух лиц. А именно, будем предполагать, что поведение первого игрока описывается условиями (1), (2), поведение второго игрока - условиями (3), (4). Параметры (ги*,р*) первого игрока, входящие в условия (3), (4) и параметры (у*, г*) второго игрока, входящие в условия (1), (2), связывают эти условия в единую систему (1)-(4). Взаимодействие игроков происходит по следующей схеме. Сначала игроки сообщают друг другу какой-то набор своих параметров: первый игрок получает от второго игрока набор (у*, г*) 6 Уо х Е™1, второй получает от первого набор е х -Е+2. Далее, первый игрок, рассматривая условия (1), (2) как задачу математического программирования с уже известными параметрами (у*, г*), составляет функцию Лагранжа: хКр^г*) = + + т е \¥0, р е £+2 (5) и определяет множество седловых точек Аг£В(И£1(ги,р,у*,г*), состоящее из точек (;ш, р) Е И/ц х Е'^2, удовлетворяющих условиям:

1 (го,р,у*,г*) ^ (й>,р,у*,г*) ^ £1 (ъи,р,у*,г*) Уги е И^о, Ур 6 Е™2 (6)

Аналогично второй игрок, рассматривая условия (3), (4) как задачу математического программирования с известными параметрами составляет свою функцию Лагранжа:

2К,р*,у,г) = 52(») + (р*,/2(у)) + + ЛК)). ге^1 (7) и определяет множество седловых точек А^бс11£2(и>*,Р*,У,'г), состоящее из точек (у, г) Е Уо х Е1™1, удовлетворяющих условиям:

2{ы*,Р*,у,г) < £2{и)*,р*,у,г) ^ \/у Е У0, Vr е Е+1 (8)

Таким образом, определено седловое отображение, которое каждому набору точек у*, г*) Е И^о х .Ё+2 х Уо х .Е1™1 ставит в соответствие множество точек: й),р,у,г) Е Argsdl£ 1 (ги, р, у*, ) х Argsdl ^С2,, У, г) (9)

Может случиться так, что это отображение будет иметь неподвижную точку г/*,г*), то есть: г/;*,р*,;г/*,г*) Е Avgsd\Ll(w,p, у*, г*) х А^сИ^О-и*,.??*, 2/, О (Ю)

Такую точку называют точкой равновесия игры (1)-(10), и она является решением задачи (1)-(4) [11-13]. Если же условие (10) не выполняется, то игроки продолжают обмен информацией: они сообщают друг другу новые точки (й),р), (у, г), взяв их из условия седла (6), (8), определяют значение сед-лового отображения (9), соответствующее точке (ш, р, у, г) - это множество Ат£3(1\£1('ш,р,у,г) х А^сП/^С^Р, ?/,г), проверяют, будет ли принадлежать точка (и>,р,у,г) этому множеству и.т.д. Таким образом, на каждом шаге стратегией каждого из игроков является седловая точка соответствующей функции Лагранжа £1 или £2- Целью игры является нахождение точки равновесия, являющейся неподвижной точкой седло во го отображения. Поэтому, описанную игру (1)-(10) принято называть седловой игрой [11-13].

Заметим, что седловая игра (1)-(10) сочетает в себе идеи равновесия как по Нэшу, так и по Парето: с одной стороны игроки при поиске седловых точек (6), (8) с известными параметрами (у*, г*) преследуют свои цели по правилам характерным для игры Нэша, с другой стороны у них есть совпадающие интересы заключающиеся в совместном согласованном поиске точки равновесия путем специального выбора коэффициентов свертки при формировании целевой функции, что соответствует равновесиям по Парето.

Переформулируем седловую игру (1)-(10) в более удобной для исследования форме.

Введем обозначения: х X у>*,Р*,У*,г*) = (ж*, А*), 5(ж) = 51(7«) +52{у), Х0 = Ж0 х У0, К = ЕТ х Е+\ гп = т1+ т2, 1п — единичная матрица п х п,

В =

И) и определим следующую функцию: х,\) = 8(х) + (В\Лх)) + (\,д(х)), х е Х0) X Е Е™ (12)

Переменную х будем называть прямой переменной, Л - двойственной переменной седловой игры.

Теорема 1.1.1. Точка = (ж*, Л*) € Х0 х Е™ является точкой равновесия седловой игры (1)-(10) тогда и только тогда, когда она является седловой точкой функции (12) в следующем смысле:

УжеХо, УХеЕ™ (13)

Таким образом, согласно этой теореме, поиск точки равновесия седловой игры (1)-(10) можно свести к поиску седловой точки функции (12).

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

Во второй главе предлагаются и исследуется сходимость экстраполя-ционного градиентного и проксимального (или, короче, экстраградиентного и экстрапроксимального) методов.

В §2.1 рассматриваются различные варианты итерацио7того экстраградиентного метода [14] (симметричный, прямой и двойственный) в предположении, что множество Хо выпукло и замкнуто, функции 3(х), /(х), д(х) дифференцируемы на Xо - Тогда функция -С(ж, Л) (12) имеет частные градиенты: = + (ВХ)ТГ(х) + ХТд'(х), Вт/(х) + д(х), х е Х0, X е А0 ^ Е™, где /'(ж), д'(х) - градиенты функций 8(х), /(ж), д(х), х Е Хо соответственно.

Итерационный симметричный экстраградиентный метод описывается следующим образом. Пусть гг0 е Хо, Ло € Ад - некоторая начальная точка процесса. Если известно к-ое приближение хк £ Хо, А^ £ Ло, к ^ 0, то сначала делаем прогнозный шаг, на котором определяем экстраполяционную точку по правилу: д£(хк,\к)\ - ( д£(хк,\к)\ Хк = тгхо ( хк - Рк-о^- ) , Ай = тгЛо I ЛА. + /3*-—-) , (15) где 7г^а - проекция точки а на множество Z, 0к > 0 - длина шага метода. хк,Хк) д£(хку дх ' дХ

Затем, в полученной точке (хк,Хк) вычисляем градиенты дД-^А); d^O^fc) и делаем основной шаг: тгхо ( хк ~ ßk-Ö-] ,

V - J (16) ( dL{xk,\k)\ V ;

Afc+1 = 7ГЛ0 I Afc + Pfc-^д- )■ « = 0.1,.

Так как в метод (15), (16) прямые переменные Хк — (wk, ук)Т и двойственные переменные Хк = (рк, гк)т входят симметрично, то этот метод будем называть симметричным экстраградиент,ным методом.

Сходимость метода (15), (16) исследуется, в предположении, что выполнены следующие условия:

I Множество Хо = Wq х Yq выпукло, замкнуто.

II Функции S(x), f(x), g{x) выпуклы и непрерывно-дифференцируемы на Х0.

III На любом ограниченном подмножестве Х\ С Хо функции S(x), f(x), g{x) и их градиенты S'(x), f'(x), g'{x) удовлетворяют условию Липшица: тах {|5(ж1) - 5(х2)|;\fixi) - /(ж2)|; \д(хг) - д(х2)\} < Ь0\х1 - х2\, тах{|5'(Ж1) - 5"(х2)|; \/'(Х1) - /'{х2)\] \4(х{) - д'(х2)|} < Ь0\Х1 - х2\, жьж2 € Хи (17) где постоянная Ьу > 0 зависит от Х\. IV Множество точек равновесия седловой игры (1)-(10) непусто. V Начальная точка (ж0, Ао) Е х Д0 выбрана произвольным образом. VI Длина шага /3^ экстраградиентного метода такова, что: соответствующая шару 5о достаточно большого радиуса, содержащему начальную точку (жо,Ао) и какую-либо точку из 51*; шар ¿о строится в процессе доказательства сходимости экстраградиентного метода.

Метод (15), (16) был впервые предложен в [55] для поиска седловых точек выпукло-вогнутых функций и его сходимость была доказана в предположении, что градиенты , удовлетворяют условию Липшица по совокупности переменных на множестве Хо х До- Однако, в седловой игре (1)-(10) множество До = Е™ нсограничено и, как видно из формул (14), даже с учетом (17), градиент может не удовлетворять условию Липшица. Это значит, что сходимость метода (15), (16) в седловых задачах (13) не будет вытекать из работы [55], поэтому нужно развивать технику исследования сходимости этого метода для седловых игр. Проведенный в диссертации анализ метода (15), (16) показал, что траектория {(ж/с, Ак — 0,1,.}, порождаемая этим процессом, принадлежит некоторому множеству ¿о С Хо х Е™, на котором

18) где ¿а - константа Липшица для частных градиентов д£{х,\) д£{х,\) дх ' д\ градиенты д,СдХх^ , удовлетворяют условию Липшица: тах дх дх дХ дХ Ь^гх - 221 + - /х2|), N/(21,^1), (2:2,^2) € 50 С Х1 х Е. т

Заметим, что постоянна Ь\ из (19) входит в условие (18). Справедлива следующая теорема:

Теорема 2.1.1. Пусть выполнены условия 1-У1. Тогда последовательность {щ} = {(а^-, А*;)7}, порождаемая методом (15), (16), монотонно сходится к некоторой точке равновесия я* игры (1)-(10): щ+1 - 5*1 < \щ, - 5*1, /г = 0,1,., Нт |ик — з*! = 0 к—^оо

Наряду с симметричным экстраградиентным методом (15), (16) в §2.1 рассматриваются методы, в которых прогнозный шаг делается лишь по одной из переменных х или А. В результате получаются еще два варианта итерационного экстраградиентного метода - прямой и двойственный.

В прямом экстраградиентном методе прогнозный шаг делается по прямым переменным х = (ъи,у)Т: г* = - Л^^1) , (20) основной шаг: д£(хк,\к)\

21)

А/г+1 = ( Хк + Рк- ^

Хк+1 = тг^о ( хк - (Зк-—- I , к = 0,1,.

В двойственном экстраградиентном методе прогнозный шаг делается по двойственным переменным А = (р,г)Т:

Хк = 7гЕш ^А*; + рк—^д ^ ^ , (22) основной шаг: к = 0,1,.

В §2.1 доказываются соответствующие теоремы сходимости (теорема 2.1.2, теорема 2.1.3), показывающие, что при выполнении условий 1-У и достаточно малом параметре >0, к = 0,1,. методы (20), (21) и (22), (23) монотонно сходятся к одной из точек равновесия ссдловой игры (1)-(10).

Каждый из приведенных вариантов (15), (16) или (20), (21) или (22), (23) экстраградиентного метода может иметь определенные преимущества перед другими вариантами в зависимости от сложности структуры множества Х0 — И^о х >о, от размерностей прямой и двойственной переменных. Отмстим, что проекция любой точки а = .,ат)т на Е™ легко вычисляется:

А£,., А^)Т, Ц. = тах{0; Х{ + /Зк(Вт/(хк) + </(.х,))*}, г = 1,., гп. Таким же образом распараллеливается выичеление Ад;+1. Аналогично можно распараллелить вычисление если множество Хц имеет вид = Zl х Z2 х . х Zl, а функции 5(ж), /(ж), д(х) представимы в виде суммы функций, каждая из которых зависит лишь от одной из переменных , ., 2/.

В §2.2 предлагаются и исследуются различные варианты дифференциального экстраградиентного метода [15] при тех же предположениях 1-У относительно ссдловой игры, что и в §2.1. В этом методе точка равновесия седловой игры (1)-(10) определяется как предел при £ —>• оо решения задачи Коши для некоторой системы обыкновенных дифференциальных уравнений с обратной связью [6, 42, 45].

В случае симметричного дифференциального экстраградиентного меттЕта = тах{0; а} = (тах{0; ах},., тах{0; ят}) Кроме того, согласно (14) градиент не зависит от А, поэтому Ад moda эта задача Коши имеет следующий вид: т+x(t) = пЕТ (л (о+mdm¡l )' d£(.x(¿),A(¿)) дх дХ

25) ж(0) = х0, Л(О) = Л0

26)

Функции х(Ь), А(£) определяемые формулами (24) являются аналогами прогнозных шагов в методе (15), (16), и в (25) выполняют роль обратной связи [6]. Заметим, что метод (15), (16) можно истолковать как разностный метод Эйлера для задачи Коши (24)-(26) [21]. Однако, дифференциальный метод

24)-(26) привлекателен тем, что для приближенного решения задачи Коши может быть использован не только метод Эйлера, но и другие известные методы [21], которые, возможно, будут сходится быстрее и будут лучше приспособлены для поиска ссдловой точки. Это обстоятельство оправдывает рассмотрение дифференциальных методов.

Теорема 2.2.1. Пусть выполнены условия 1-У. Тогда существует, притом единственное решение и(£) = (х(Ь), А(£))т задачи Коши (24)-(26), определенное при всех которое принадлежит некоторому шару ¿о достаточно большого радиуса, содержащему начальную точку (жо, Ао)т и какую-либо точку равновесия я* седловой игры (1)-(10), если параметр ¡3(1) в (24),

25) непрерывен при всех £ ^ 0 и удовлетворяет условию: где постоянная Ь1 > 0 взят,а из условия Липшица (19).

Теорема 2.2.2. Пусть выполнены условия ТУ. Длина шага /?(£) взята из (27). Тогда решение и(1) = (ж(£), А(£))т задачи Коши (24)-(26) при £ —>

Vi ^ О,

27) оо монотонно сходится к некоторой точке равновесия s* седловой игры (1)-(10): и(т) - К \u{t) - Vr^i^O, lim |u(t) — s*| = 0 t—» c»

Прямой дифференциальный экстраградиентный метод описывается задачей Коши: <28>

29) х(0) = 10, А(0) = А0 (30)

Двойственный дифференциальный экстраградиент,ный метод описывается задачей Коши:

V ох / С32)

А(4)+л« = (л(0+>{>0< а;(0) = ж0| Л(0) = А0 (33)

В §2.2 приводятся соответствующие теоремы, которые показывают, что при выполнении условий 1-У и достаточно малом параметре /3(£), £ ^ 0 методы (28)-(30) и (31)-(33) монотонно сходятся к одной из точек равновесия седловой игры (1)-(10).

В §2.3 рассматриваются три варианта итерационного экстрапроксимального метода [23]. Симметричный вариант, метода состоит из прогнозного шага: хк = argm.ini- хк\2 + рк£(х, Аа)|ж € Х0}, (34)

Afc = argmin{-[A - A*| - pk£(xk, A)|A G E™}

35) и основного шага: xk+l = argmin{-|a; - xk\2 + /Зк£(х, Afc)|a? € X0}, 1

36)

Afc+i = argmin{i|A - Afc| - pkL(xk, A)|A G E™}

37)

Сходимость метода (34)-(37) исследуется в предположении, что выполнены следующие условия:

VII Множество Xq = Wq х Yq выпукло, замкнуто.

VIII Функции S(x), f(x), д(х) определены и выпуклы на Хо, непрерывны на Xq. Кроме того, функции f(x), д(х) на Хо удовлетворяют условию Липшица: max{|/(xi) - f(x2)|; - д{х2)|} ^ L\xx - х2\, Ухих2 £ Х0

IX Множество S* точек равновесия ссдловой игры (1)-(10) непусто. X Начальная точка (.то- Ао) G Х0 х Ао выбрана произвольным образом. XI Параметры /Зк таковы, что:

При выполнении этих условий в каждой из задач минимизации (34)-(37) целевая функция сильно выпукла, точки (хк,Хк)т, (хк, Хк)т определяются однозначно и для их определения могут быть использованы известные методы [22]. В частности, с учетом линейности функции £(ж,А) (12) и, пользуясь характеристическим свойством проекции, условия (35), (37) можно заменить эквивалентными легко вычислимыми равенствами: соответственно. Заметим также, что метод (34)-(37), как и экстраградиентные методы допускает распараллеливание.

О < Аши Апах < ^Т, к = 0, 1, . 1

Теорема 2.3.1. Пусть выполнены условия УП-Х1. Тогда последовательность {7^} = порождаемая методом (34)-(37), монотонно сходится к одной из точек равновесия седловой игры (1)-(10).

В прямом экстрапроксимальном мет,оде прогнозный шаг делается по переменной х: хк = а^гтп-фа; - хк\2 + АХ (ж, Хк)\х Е Х0}, (38) основной шаг:

Хк+\ = агётт{^|Л - А,.|2 + /Зк£,{хк, А)|Л € Щ,

I (39) хш = ащтт{-|ж - хк\2 + Л^)^ е Х0},

Двойственный экстраградиентный метод: прогнозный шаг:

А* = а^тт{^|А - А,| - 0кЦхк, А)|А £ ЕД, (40) основной шаг: хк+х = - хк\ - /Зк£(х, Ай)|ж е Х0},

I (41)

Хк+1 = а^тт{-|А - Ал| - /Зк£(хк+Ъ А)|А е Е™}

При выполнении условий УН-Х1 методы (38)-(39), (40)-(41) монотонно сходятся к одной из точек равновесия седловой игры (1)-(10). Соответствующие рассуждения приведены в теореме 2.3.2 и теореме 2.3.3 соответственно.

В §2-4 исследуется дифференциальный экстрапроксимальный метод [24]. Симметричный дифференциалышй экстрапроксимальный метод выглядит следующим образом: х{£) = жётт{1\х - хЩ2 + А(*))|я € Х0},

2 (42)

Щ = аг§гшп{-|А - А(*)| - А)|А е + х(Ь) = а^гшпЛх - х{Ь)\2 + /?(*)£ (ж, Щ)\х <= Х0}:

АI

А(*) + А(£) - а^ттД|А - А(*)| - (3{1Щх(г), А)|А е Е™}, í ^ 0, (43) х(0) = х0, А(0) = А0

Теорема 2.4.1. Пусть выполнены условия УП-Х, параметр /3(£) метода непрерывен при всех £ ^ О и удовлетворяет условию: о < А„т < т ^ ртах < V£ ^ 0 (44)

Пусть система (42)-(43) имеет единственное решение м(£) = (х(£), А(£))т при всех £ ^ 0. Тогда это решение монотонно сходится к некоторой точке равновесия б* седловой игры (1)-(10).

Прямой дифференциальный экстрапроксимальный метод: х{€) = а^гшпД|х - х(£)|2 + /3(£)£(х, А(£))|х 6 Х0}, и 1

Л(£) + А(£) = агётт{-|А - А(£)|2 + /?(£)£(х(£), А)|Л 6

2 (45) х(£) + х(£) = аг§гшп{-|х - х(£)|2 + /3(£)£(х, Л(£) + А(£))|х € Х0}, х(0) = х0, А(О) = Л0, £ ^ О

Двойственный дифференциальный экстрапроксимальный метод:

Л(£) = а^тт{^|А - Л(£)| - /?(£)£(х(£), Л)|Л е 1 х(Ь) + х(£) = а^тт{-|ж - х(£)| - /3(£)£(х, А(£))|х € Х0},

Л(£) + А(£) = агётт{^|Л - Л(£)| - /3(£)£(±(£) + х(£), А)|А € Е™}, х(О) = х0, Л(0) = А0, £ ^ О

46)

При выполнении условий УП-Х методы (45), (46) монотонно сходятся к одной из точек равновесия седловой игры (1)-(10) (теорема 2.4.2, теорема 2.4.3).

Третья глава посвящена методам поиска точки равновесия седловой игры (1)-(10) в случае, когда входные данные 5(х), /(х), д{х) и их градиенты 5"(:с), /'(ж), д'(х) заданы неточно и в нашем распоряжении имеются лишь их приближения /к(х), 9к(х), ^(х), /¿(х), д'к(х), х Е Х0, к = 0,1,.

Казалось бы, в этом случае по аналогии с (12) можем составить приближенную функцию Лагранжа: к{х,\) = Зк(х) + (\,ВТ/к(х)+дк(х)), хеХ0, \еЕ?, к = 0,1,. (47) и, с помощью методов главы 2, искать седловую точку (хк*,Хфункции Lк(х, А). Однако, простые примеры показывают, что седловые игры, вообще говоря, неустойчивы к возмущениям входных данных и полученные на этом пути точки (xk*, Afc*), к = 0,1,. могут сильно отличаться от точки равновесия седловой игры (1)-(10) [22, 81, 82]. Поэтому для поиска седловых точек при неточных входных данных нужно разрабатывать специальные устойчивые методы. Такие методы могут быть получены путем регуляризации методов главы 2.

В §3.1 расматривается регуляризованный экстраградиентный метод [16] в предположении, что выполнены условия I-V и приближенные входные данные таковы, что: max {\Sk{x) - ¿'(ж)!, \fk(x) - f(x)|, \gk(x) - g(x)\} ^ 6k( 1 + |ar|), ж e XQ,

48) max{|S'k(x) - S'{x)\, \f'k(x) - f'(x)|, |g'k(x) - g\x)|} < Sk, x E X0, k = 0,1,.,

49) где 6k ^ 0 - параметр, характеризующий погрешность. Введем функцию:

Tk(x, А) = А) + ^ак(\х\2 - |А|2), х е Х0, А е Е™, (50) которую будем называть функцией Тихонова игры (1)-(10). Здесь о/к > 0 -параметр регуляризации, lim ак = 0. В качестве приближений для частных к—too градиентов этой функции = ^ + о^, = ^ - акХ, к = 0,1,. возьмем: дтк{х, A) dLk{x,X) дх дх дтк{х, А) д&к{х,Х) акх, ox ах ~акХ• к = ол-

Регуляризованный симметричный экстраградиентный метод: прогнозный шаг: о дтк(хк1Хк)\ - ( дтк{хк,Хк)\ Хк = Кх0 ( Хк - ßk-- I , Хк = f Хк + ßk-—-j , (51) основной шаг: о дтк(хк,Хк)\ Хк+1 = 7ГХо I Хк - ßk--- I , дтк{хкХ)\ (52)

Afc+i = -кЕш ( \к + ßk---J, к = 0,1,., где ßk > 0 - параметр метода.

Теорема 3.1.1. Пусть выполнены условия I-V, погрешности входных данных седловой игры (1)-(10) удовлетворяют условиям (48), (49), параметры {ак}, {ßk}, {5/J таковы, что:

6к 1 ак > 0, 0к > 0, к = 0,1,., lim ак = 0, lim 6к = 0, sup—< —, к—>оо к—too k^ СИк ¿о сю

Е, «fc+i - «fc п r h п a.k = +оо, lim -ö-- = U, lim — = 0, к—>оо /т- /-v, к=0 к-^оо Oi^ к^-оо ак

53)

О < + 16/3*4 <1, ßk 2Li + 12 sup 4 + 4supafc < 1,

V fc^o /cäo /

О < - 56— + - 14/ЗД < 1,

4 а/. 2 (54)

О < \афк{1 - 28—) < 1, 2 а*;

О < Агпп < Рк ^ Р тах <Р, к = 0,1,., где постоянная Ь\ взята из условия (19). Тогда последовательность {ик = (хк,Хк)Т}, порождаемая методом (51), (52), сходится к нормальной точке равновесия и*, |и*| = inf |з*| седловой игры (1)-(10), причем сходимость равномерная относительно выбора приближенных входных данных из условий (48), (49).

В прикладных задачах входные данные, как правило, известны с некоторой фиксированной погрешностью. В частности, в седловой игре (1)-(10) вместо условий (48), (49) где {4} —>■ 0, более реальным представляется следующее условие: вместо точных входных данных: h=(S(x),f{x),g(x)tS'(x)J'(x),gr{x)), х е Х0, известны приближения: hs = {Ss(x), fs(x),gs{x), S's(x), fi(x),g'5(x)), x € X0, такие, что: тах{|ЗД - S(x)\fs{x) - f(x)|, \gs{x) - < 5(1 + |.т|), ж € X0, (55) max{\S's(x) - 5(^)1,\f'5(x) - f(x)|, \g>(x) - я(ж)|} ^ 6, x e X0, (56) где S > 0 - фиксированное число. Возникает вопрос, как распорядиться набором hs и построить оператор который каждому набору hs из (55), (56) ставит в соответствие точку Rshs = и(5) = (х(5), А(5))т, которая близка к множеству точек равновесия игры (1)-(10) при достаточно малых 5 > 0. Такой оператор, следуя [22, 81] будем называть регуляризующим. Оказывается, для построения такого оператора можно воспользоваться методом (51), (52) и соответствующей теоремой о сходимости. Точнее, рассмотрим метод: о дтб(хкЛк)\ т Л . п дтд(хк,Хк)\

Хк = ТГ^о \хк- Рк-—- 1 , Ак = 7ГEm I Хк + Рк-- I ,

Хк+1 = пХо I Хк - рк-—- I , (57)

Afc+i = 7ГЕШ ^Afc + Ас^^д , к = 0,1,.,

Метод (57) получен из метода (51), (52) заменой функций ; дт^д.А) на drs(x, А) т т дх S's{x) + (ВХ) f's(x) + А д'6(х), дт6(х, А) = ^^ + ^ ж е Л е Егп

58) дх

Начальная точка (ж0, А0)т и параметры {а^}, {Рк}, удовлетворяющие условиям (53), (54), считаются фиксированными и не зависят от 5 > 0. Процесс (57) продолжается до такого наибольшего номера к = к (5), при котором выполняются неравенства: k = 0,l,.,k{5). (59) def

Если <5 ^ ¿о, то полагаем k(S) — 0.

Оператор Rs определяется следующим образом:

Rfihs = и{5) = (xKS), Лед)т, 5 > 0 (60)

Теорема 3.1.3. Пусть выполнены все условия теоремы 3.1.1 сходимости метода (51), (52), кроме условий (48), (49)- Приближения h$ удовлетворяют условиям (55), (56), и известна оценка R ^ |s*| для какой-либо точки равновесия s* Е S*. Пусть оператор Rs определен согласно (57), (60). Тогда: limp{u{6),S>) = 0, p{u,S*) = inf \u-s\, (61)

6-+0 6-65» причем сходимость в (61) равномерна относительно выбора приближений hs из (55), (56).

Также в §3.1 рассматривается регуляризованный прямой экстраградиентный метод, доказывается теорема сходимости этого метода, по аналогии с регуляризованным симметричным экстраградиентным методом строится ре-гуляризующий оператор.

В §3.2 рассматривается регуляризованный дифференциальный экстраградиентный метод [17] в предположении, что выполнены условия I-V и приближенные входные данные S(x,t), /(ж, £), g(x,t), S'(x,t), f'(x,t), g'(x,t), x E Xq, таковы, что: max{\S(x,t) - 5(x)|, |f{x,t) - f(x)|, |g(x,t) - g{x)|} < 1 + |x|), ж E X0,

62) msx{\S'(x, t) - 5#(ar)|, \f(x, t) - f'(x) |, \g'(x, t)-g'{x) |} < S(t), x E X0, t > 0,

63) где S(t) > 0 - параметр, характеризующий погрешность. Подчеркнем, что в (63) функции S'(x,t), f'(x,t), g'(x,t) необязательно являются градиентами функций S(x,t), /(ж, £), g(x,t), это лишь приближения для градиентов функций S(x), f{x), g(x).

Для описания регуляризованного дифференциального экстраградиентного метода введем следующую функцию:

Т(х) А, £) = £(х, А) + ^а(Ь)(\х\2 — |А|2), хбХ0, А е Е™, (64) которую будем называть функцией Тихонова игры (1)-(10). Здесь а(Ь) > О, Ь ^ 0 - параметр регуляризации. В качестве приближений функции (64) и ее частных градиентов возьмем: 1

2"|А|2 т(х, А,¿) = А, г) + -а(Щх\2 - |А|2), х <Е Х0, А е Е™, дх дх а(Ь)х,

-а(£) А, ¿^0

9А дА

Регуляризованный симметричный дифференциальный экстраградиентный мет,од описывается следующей задачей Коши: дт(х(Ь), A(í),¿)^ = - Р

Щ = ттЕш ( А(£) + /3

Эж дХ

А(£) + А(£) = ^ (лад + , ^ о ж(0) = а*, А(0) = А0, х0 е Х0, А0 6 Е™

Теорема 3.2.1. Пусть выполнены условия 1-У, приближенные входные данные удовлетворяют условиям (62), (63) и, кроме того, на любом ограниченном подмножестве Х\ С выполняются условия Липшица: тах{|5(£1,£) - 5(я2,*)|, 1/(^1,0 - ¡(х2,01,

66) аМ) - д(х2лЬ)\} ^ Ь2\хг -х2\, Ух1,х2 в Хи г^о тах{|5'(:гь ¿) - З'(а:2,1% - /'{х2, д\хъг) - д'(х2,1)\} ^ Ь2\х1 - х2\, Ухъх2еХъ £ > 0,

Пусть параметры ot(t), ß(t), ö(t), t ^ О метода (65) непрерывны, a(t), ß(t) непрерывно-дифференцируемы и a(t) выпукла при t ^ 0, и, кроме того: a(t)> 0, ад>0, а'(0<0 Vi ^ 0, Sup^<i

О a^t; Zö lim fa(i) + S(t) + + = 0, з'т ( j

Тогда существует, притом единственное решение u{t) = (îc(î), Л(£))т за-àw Коши (65), определенное при всех t ^ 0, которое принадлежит некоторому шару So достатючно большого радиуса, содеро/салцему начальную точку (жо,Ао) и какую-либо точку равновесия s* седловой игры (1)-(10).

В качестве параметров ß(t), S(t) в (68) можно, например, взять a(t) = + S(t) = (i + l)2; ß(t) = ß0 = const > 0 - достаточно малое число.

Теорема 3.2.2. Пусть выполнены условия I-V, (62), (63), (66), (67), (68). Тогда решение u(t) = (x(t), X(t))T, t ^ 0 задачи Коши (65) сходится к нормальной точке равновесия и* седловой игры (1)-(10), причем эта сходимость равномерная относительно выбора приближенных входных данных S(x,t), f(x,t), g(x.t), S'(x,t), f'(x.t), g'(x,t), x G Xq из условий (62), (63).

Аналогично тому, как это сделано в §3.1 на базе теоремы о сходимости можно построить регуляризующий оператор Rs в случае, когда приближенные входные данные h$ удовлетворяют условиям (55), (56). Для этого нужно перейти к задаче Коши, которая получается после замены в (65) , на Функции ^ dn{x,x,t) соотвстствешЮ) определить решение us(t) = (x(t), A(i))T на отрезке 0 ^ t ^ t(ô), где момент £($) определяется из условия: t) Vi, 0 < t < t(â), 23 аналогичного (59), и положить, как в (60): щы (Хт),\(1(б)))т

Для таким образом определенного оператора справедлива теорема аналогичная вышеприведенной теореме, то есть Щ - регуляризующий оператор.

Далее в работе рассматривается регуляризованный прямой дифференциальный экстраградиентный метод, который описывается следующей задачей Коши: - - Р

Щ = 7гет (А(£) + р дх дХ

Щ + А(0 = ^ (лм + ^УММ) , ^ о, ж(0) = ж0, Л(0) = Ао, Ж0е4 А 0еЕ%

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

В §3.3 рассматривается регуляризованный экстрапроксимальный мет,од [26] в предположении, что выполнены условия УП-Х и приближенные входные данные удовлетворяют условию (48). В качестве приближения функции Тихонова Тк(х,Х) (50) возьмем: тк(х, А) = £к(х, А) + Ц(\х\2 - |А|2), X 6 Х0, А € (70) где функция Лк{х,Х) определена согласно (47).

Регуляризованный симметричный экстрапроксимальный метод: прогнозный шаг:

1, хк = а^тт{^|:г - хк\2 + Рктк(х, Хк) | х е Х0}, Хк = а^тт{^|А - А*!2 - Рктк(хк, А) | А е Е™}, основной шаг: хк+г = argmin{i|a; - хк\2 + ßkrk(x: Хк) | х G Х0};

2 (72)

Л*+1 = argmin{-|A - А*|2 - ßkrk(xk, А) | А <= Е™}, ßk > 0, к = 0,1,.

Теорема 3.3.1. Пусть выполнены условия VII-X, (48)- Пусть параметры {ак}, {ßk}, {<У метода (71), (72) таковы, что: ак > 0, 5к >0, к = 0,1,., lim ак — 0, lim 6к = 0, к-^-оо к—> оо r \ak+i ~ Ы п ак = оо, lim -^-= 0, fc-» оо аг fc=° ак 4 (73) lim -= üq > 0, lim — = 0, к >оо ОСк±\ к->оо ак

1 S 1 1

О < ßmin < ßk < ог , — + Т ßkök < к = 0, 1, .

2L + 24 дк ак 4 56

Тогда послеовательность {г^} = {(^ьА/г)7}, порожденная методом (71), (72), сходится к нормальной седловой точке и* равномерно относительно выбора функций Sk(x), fk(x), gk{x) из условий (48).

Если приближенные входные данные удовлетворяют условию (55), то регуляризующий оператор Rs можно строить на базе метода (71), (72) также как и в случае регуляризованного экстраградиентного метода.

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

В §3-4 рассматривается регуляризованный дифференциальный экстрапроксимальный метод в предположении, что выполнены условия VII-X, приближенные входные данные S(x,t), f(x,t), g(x,t) удовлетворяют условию (62). В качестве приближения функции T(x,X,t) (64) возьмем: r(x,A,i) = (a:,A,t) + ^)(|a:|2-|A|2), х е XQ> X в Е™, t > О

Симметричный регуляризованный дифференциальный экстрапроксимальный метод: x(t) = argmin{i|a: - x(t)|2 + ß{t)r(x, A(t),t) | x G X0},

Щ = argmin{i|A - A(i)|2 - ß(t)r(x(t), A, t) | A G E™}, x(t) + x(t) = argmin{î|a; - x{t)|2 + ß(t)r(x, Â(£), t) \ x G X0}, (74) + A(i) = argmin{^|A - A(£)|2 - ß(t)r(x(t), A, t) | A G t ^ 0, x(0) = XQ, A(0) = A0

Теорема 3.4.1. Пусть выполнены условия VII-X, (62), параметры oc(t), ß(t), S(t), t ^ 0 метода таковы, что cx(t), ß(t) - непрерывно-дифференцируемы, 6(t) - непрерывна при t ^ 0, и, кроме того: a{t) > 0, ¿О) > 0> <*'(*) ^ 0, ß'(t) ^ 0,

Si«'»0' lim (ait) + ô(t) + M + + Ж1 о lim + ад + a(t) + ^ЩЩ + a{t)ß2{t)) - °>

1 -supß(t)(L + 246(t)) > 0 t^ о

Пусть система (74) имеет единственное решение u(t) = (x(t), A(t))J; t ^ О, тогда: lim \u(t) — uj = 0, (75) t—>00 где щ - нормальная седловая точка функции (12), причем сходимость в (75) равномерна относительно выбора приближенных входных данных S(x, t), f(x,t); g(x,t) из условий (62).

Если приближенные входные данные 1ц удовлетворяют условию (55), то регуляризующий оператор R$ можно строить на базе метода (74) также, как и в случае регуляризованного дифференциального экстраградиентного метода.

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

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

Основные результаты работы.

1) Разработаны экстраградиентные и экстрапроксимальные методы поиска точки равновесия седловой игры в итерационной и дифференциальной формах, доказана их сходимость, развита техника исследования сходимости таких методов.

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

1. АнтипинА. С. Об одном методе отыскания седловой точки модифицированной функции Лагранжа. // Экономика и математические методы. 1977. 13. №3. С.560-565.

2. АнтипинА. С. Об одной задаче равновесия и методах ее решения. // Автоматика и телемеханика. 1986. №9. С. 75-82.

3. АнтипинА. С. Методы решения систем задач выпуклого программирования.// ЖВМиМФ. 1987. 27. №3. С. 368-376.

4. АнтипинА. С. О моделях взаимодействия предприятий-производителей, предприятий-потребителей и транспортной системы// Автоматика и телемеханика. 1989. №10. С. 105-113.

5. АнтипинА. С. Управляемые проксимальные дифференциальные системы для решения седловых задач. // Дифференциальные уравнения. 1993. 28. №11. С.1846-1861.

6. АнтипинА. С. Седловые градиентные процессы, управляемые с помощью обратных связей.// Автоматика и телемеханика. 1994. №3. С.12-23.

7. Антипин А. С. Итеративные методы прогнозного типа для вычисления неподвижных точек экстремальных отображений. // Известия вузов. Математика. 1995. №11. С.1-8.

8. АнтипинА. С. Экстрапроксимальный метод решения равновесных и игровых задач. // ЖВМиМФ. 2005. 45. №11. С.1969-1990.

9. АнтипинА. С. Экстрапроксимальный метод решения равновесных и игровых задач со связанными переменными. // ЖВМиМФ. 2005. 45. №12. С.2012-2111.

10. АнтипинА. С. Седловая задача и задача оптимизации как единая система. // Труды института математики и механики. 2008. 14. №2. С.5-15.

11. АнтипинА. С., Попова О. А. О равновесной модели кредитного рынка: постановка задачи и методы решения.// ЖВМиМФ. 2009. 49. №3. С.465-481.

12. АнтипинА. С. Равновесное программирование: модели и методы решения.// Известия Иркутского государственного университета. Серия «Математика». 2009. 2. №1. С.8-36.

13. АнтипинА. С. Седловые игры двух лиц: модели и методы решения.// Материалы IV всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск. 2009. С. 10-15.

14. Артемьева JI. А. Экстраградиентный метод поиска точки равновесия в седловых играх двух лиц. // ЖВМиМФ. 2011. 51. №12. С. 2143-2157.

15. Артемьева JI. А. Дифференциальный экстраградиентный метод поиска точки равновесия в седловых играх двух лиц. // Дифференциальные уравнения. 2012. 48. М. С. 79-92.

16. Артемьева JI. А. Регуляризованный экстраградиентный метод поиска точки равновесия в седловых играх двух лиц. // ЖВМиМФ. 2012. 52. №4. С. 585-601.

17. Артемьева JT. А. Регуляризованный дифференциальный экстраградиентный метод поиска точки равновесия в седловых играх двух лиц с приближенными входными данными. // ЖВМиМФ. 2012. 52. №9. С. 1582-1600.

18. Ашманов С. А. Введение в математическую экономику. М.: Наука, 1984.

19. Бакушинский А. Б., Гончарский А. В. Итеративные методы решения некорректных задач. М.: Наука, 1989.

20. Беленький В.З., Волконский В. А., Иванков С. А., Поман-ский А. Б., Шапиро А. Д. Итеративные методы в теории игр и программировании. М.: Наука, 1974.

21. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. М.: Наука, 1987.

22. Васильев Ф. П. Методы оптимизации. Т. 1,11. М.: МЦНМО, 2011.

23. Васильев Ф.П., Антипин A.C., Артемьева J1.А. Экстрапроксимальный метод решения седловых игр двух лиц. // ЖВМиМФ. 2011. 51. №9. С. 1576-1587.

24. Васильев Ф.П., Антипин A.C., Артемьева JI. А. Дифференциальный экстрапроксимальный метод поиска точки равновесия в седловых играх двух лиц. // Дифференциальные уравнения. 2011. 47. №11. С. 1551-1563.

25. Васильев Ф.П., Антипин A.C., Артемьева JI. А. Регуляризо-ванный дифференциальный экстрапроксимальный метод поиска точки равновесия в седловых игр двух лиц. // Вычислительные методы и программирование. 2012. 13. С. 149-160.

26. Васильев Ф.П., Антипин A.C., Артемьева JI. А. Регуляризован-ный экстрапроксимальный метод поиска точки равновесия в седловых игр двух лиц. // ЖВМиМФ. 2012. 52. №7. С. 1231-1241.

27. Васин А. А. Модели процессов с несколькими участниками. М.: Изд-во МГУ, 1983.

28. Васин В. В., Агеев А. JI. Некорректные задачи с априорной информацией. Екатеринбург. Уральская издательская фирма "Наука". 1993.

29. Васин А. А. Некооперативные игры в природе и обществе. М.: МАКС-Пресс, 2005.

30. Васин A.A., Морозов В.В. Теория игр и модели математической экономики. М.: МАКС-Пресс, 2005.

31. Васин A.A., Краснощеков П. П., Морозов В. В. Исследование операций. М.: Издательский центр «Академия», 2008.

32. Воробьев H. H. Основы теории игр. Бескоалиционные игры. М.: Наука, 1984.

33. Гермейер Ю. Б. Игры с ^противоположными интересами. М.: Наука, 1976.

34. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

35. Giblons R. Game theory for applicd économiste. Princeton University Press. Princeton, New gersey, 1992.

36. Гилл Ф., Мюррей У., Райт M. Практическая оптимизация. M.: Мир, 1985.

37. Голыптейн Е. Г., Третьяков Н.В. Модифицированные функции Лагранжа. М.: Наука. Физматлит. 1989.

38. Горелик В. А., Фомина Т.П. Основы исследования операций. М: МПГУ, 2004.

39. Григоренко H. JI. Дифференциальные игры преследования несколькими объектами. М.: Изд-во МГУ, 1983.

40. Григоренко H. JI. Математические методы управления несколькими динамическими процессами. М.: Изд-во МГУ, 1990.

41. Демьянов В. Ф., Певный А. Б. Численные методы разыскания сед-ловых точек.// ЖВМиМФ. 1972. 12. №5. С. 1099-1127.

42. Денисов А. М., Разгулин А. В. Обыкновенные дифференциальные уравнения. М.: Макс Пресс, 2009.

43. Дмитрук А. В. Выпуклый анализ: элементарный вводный курс. М.: Макс Пресс, 2012.

44. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

45. Емельянов C.B., Коровин С. К. Принцип построения и основные свойства замкнутых динамических систем с различными типами обратных связей. // Динамика неоднородных систем. Тр. сем. ВНИИСИ. М. 1982. С.5-27.

46. Жадан В. Г. Численные методы линейного и нелинейного программирования. М.: Изд-во ВЦ РАН, 2002.

47. Жуковский В. И. Конфликты и риски. М.: РосЗИТЛП, 2007.

48. Жуковский В. И. Риски при конфликтных ситуациях. М.: Ленанд, 2011.

49. Жуковский В. И., Молоствов В., С. Многокритерильое принятие решений в условиях неопределенности. М.: Междуародный НИИ проблем упралеиия, 1988.

50. Замков О. О., Толстопятенко A.B., Черемных Ю. Н. Математические методы в экономике. М.: Изд-во «Дело и Сервис», 2004.

51. Карлин С. Математические методы в теории игр, программировании и Экономикс. М.: Мир, 1964.

52. КармновВ.Г., Федоров В. В. Моделирование в исследовании операций. М.: Твема. 1996.

53. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. M : Наука. 1975.

54. Коннов И. В. Методы решения конечномерных вариационных неравенств. Курс лекций. Казань, 1998.

55. Корпелевич Г. М. Экстраградиентный метод для отыскания седловых точек и других задач. // Экономика и математические методы. 1976. 12. вып. 9. С. 747-756.

56. Корпелевич Г. М. Экстраполяционные градиентные методы и их связь с модифицированными функциями Лагранжа. // Экономика и математические методы. 1983. 19. вып. 4. С. 694-703.

57. Краснощеков П. С., Морозов В. В., Попов Н. М. Оптимизация в автоматизированном проектировании. М.: МАКС-Пресс, 2008.

58. Красовский H.H., Субботин А. И. Позиционные дифференциальные игры. М.: Наука, 1974.

59. Кукушкин Н. С., Морозов В. В. Теория неантогонистических игр. М: Изд-во МГУ, 1984.

60. Левитин Е. С., Поляк Б. Т. Методы минимизации при наличии ограничений. // ЖВМиМФ. 1966. 6. №5. С. 787-823.

61. Лотов А. В., Поспелова И. И. Многокритериальные задачи принятия решений. М: Изд-во МГУ ВМК. 2008

62. Mayerson R. В. Game theory. Analysis of Conflict. Harvard University Press. Cambridge, Massachusetts, London, Englan. 1991.

63. Морозов В. А. Регулярные методы решения некорректно поставленных задач. М.: Наука, 1987.

64. Myles G. Public economics. Cambridge. 1996.

65. Нейман Дж. фон., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.

66. Никольский М. С. Первый прямой метод Л.С. Понтрягина в дифференциальных играх. М.: Изд-во МГУ, 1984.

67. Новикова Н. М. Дискретные и непрерывные задачи оптимизации. М.: Изд-во ВЦ РАН, 1996.

68. Осипов Ю.С., Васильев Ф.П., Потапов М.М. Основы метода динамической регуляризации. М.: Изд-во МГУ, 1999.

69. Owen G. Game Theory. Second Edition. Acad. Press, 1982.

70. Панюков A.B. Математическое моделирование экономических процессов. M.: Книжный дом «Либроком», 2010.

71. Pareto V. Manuel d'economie politique. Paris: Geard, 1909.

72. Петросян Л. A., Зенкевич H.A., Семина Е. А. Теория игр. М.: Высш. шк., 1998.

73. Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М: Физматлит, 2007

74. Подиновский В. В. Введение в теорию важности криетриев в многокритериальных задачах принятия решений. М: Физматлит, 2007.

75. Полтерович В.М. Экономическое равновесие и хозяйственный механизм. М.: Наука, 1990.

76. Понтрягин Л. С. Обыкновенные дифференциальные уравнения. М.: ГИФМЛ, 1961.

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

78. Попов H. М. Приближенное решение многокритериальных задач с функциональными ограничениями. // ЖВМиМФ. 1986. 26. №10. С. 1468-1481.

79. Смольяков Э.Р. Теория конфликтных равновесий. М.: Едиториал УРСС, 2005.

80. Стронгин Р. Г. Численные методы в многоэкстремальных задачах управления. М.: Наука, 1978.

81. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1986.

82. Тихонов А. Н., Леонов A.C., Ягола А. Г. Нелинейные некорректные задачи. М.:Наука. Физматлит, 1995.

83. Федоров В. В. Численные методы максимина. М.: Наука, 1979.

84. Harsaniy J. С., Selten R., А. General Theory of Equilibrium Selection in Games. The MIT Press, Cambridge, Massachusetts, London, England. 1989.

85. Эрроу К.Дж., Гурвиц JI., Удзава X. Исследования по линейному и нелинейному программированию. М.: Изд-во иностр. лит., 1962.

86. Weibull J. W. Evolutionary Game Theory. MIT Press, Cambridge, Massachusetts, London, England. 1995.