ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2011, том 51, № 9, с. 1588-1593
УДК 519.626
ЧИСЛЕННОЕ РЕШЕНИЕ ОДНОЙ ЗАДАЧИ РАВНОВЕСИЯ, ОСНОВАННОЕ НА ОБОБЩЕННОМ МЕТОДЕ УРОВНЕЙ1
© 2011 г. Е. Г. Гольштейн
(117418Москва, Нахимовский пр-т, 47, ЦЭМИРАН) e-mail: golshtnv@cemi.rssi.ru Поступила в редакцию 01.11.2010 г.
Исследуется некоторая задача равновесия, частным случаем которой является задача отыскания точки Нэша бескоалиционной игры многих лиц. Описан численный алгоритм решения этой задачи. Сформулированы требования к задаче, при соблюдении которых получена оценка скорости сходимости алгоритма к единственному решению задачи. Результаты использованы для численного анализа бескоалиционных игр. Библ. 6.
Ключевые слова: точка равновесия, бескоалиционная игра, точка Нэша, метод уровней.
1. Пусть G — непустой выпуклый компакт, содержащийся в евклидовом пространстве E, Ф(и, w), и е G, w е G, — функция с вещественными значениями. Рассмотрим задачу P(Ф, G) определения такой точки и* е G (точки равновесия), что
ф(и*, и*) = max Ф(и, и*). (1)
Если предположить, что функция Ф непрерывна на G х G и вогнута относительно и е G при любом фиксированном w е G, то из известной теоремы Какутани вытекает разрешимость задачи
P (Ф, G), т.е. непустота множества U *(Ф, G) точек равновесия этой задачи. Однако класс разрешимых задач P(Ф, G) сопоставим по сложности с классом всех задач поиска неподвижной точки точечно-множественного отображения в условиях теоремы Какутани. Поэтому не приходится рассчитывать на возможность построения эффективного численного алгоритма решения всех разрешимых задач P (Ф, G). В [1], [2] описан класс задач P (Ф, G), для численного решения которых использован сходящийся алгоритм градиентного типа. Другой класс задач P (Ф, G), допускающих эффективное решение, рассмотрен в [3]. Численный анализ этих задач основан на обобщенном методе уровней (см. [4]). Настоящая работа посвящена выделению еще одного класса сформулированных выше задач равновесия, которые поддаются численному решению при помощи обобщенного метода уровней.
2. Сформулируем три условия на функцию Ф, определенную на выпуклом компакте G х G, которые будут использованы в дальнейшем (обозначим их через Q:, Q 2, Q 3).
Условие Qj. Функция Ф(и, w) определена и непрерывна на G х G и вогнута относительно и е G при любом фиксированном w е G, где G — открытое выпуклое множество, содержащее G.
Пусть диФ(и, w) — супердифференциал Ф относительно u в точке (и, w). Из Qi вытекает, что д иФ(и, w) Ф 0, если (и, w) е G х G, причем
sup ||/|| < L < да. (2)
геЭ иФ (и, w), (и, v)e Gx G
Условие Q2. Функция Ф(и, w) сильно вогнута относительно и е G с постоянной сильной вогнутости у > 0 при любом фиксированном w е G.
1) Работа выполнена при финансовой поддержке РФФИ (код проекта 09-01-00156).
1588
Условие Q 2 означает, что при произвольных и1, и2, w е О имеет место неравенство
/ 1 2 1 2\ II 1 2||2
(I -1 , и - и ) < -у и - и , (3)
где 11 и 12 — любые элементы множеств диФ(и1, м>) и д„Ф(и2, соответственно. Для любых двух компактов О1,02 с Е положим
p(Gb G2) = max {max minimi - x2||,maxmin|| x1 - x2|}• (4)
IxieQ Х2е02 x2^G2 x^ )
Величину p(G1, G2) принято называть расстоянием между компактами G1 и G2 в смысле Хау-сдорфа. Если G1 и G 2 являются точками x1 и x2, то p(G1, G2) = ||x1 - x2||.
Пусть N — точечно-множественное отображение точек компакта G с E в компакты, содержащиеся в E. Условимся говорить, что отображение N удовлетворяет обобщенному условию Липшица с постоянной L, если для любых x1, x2 е G имеет место неравенство
р№ДN(x2)) < L\\xx - x^|, (5)
где p(v) определяется соотношением (4).
В случае точечно-множественного отображения N обобщенное условие Липшица (5) переходит в обычное условие Липшица.
Условие Q3. При любом фиксированном и е G отображение N(w) = диФ(и, w), w е G, удовлетворяет обобщенному условию Липшица с постоянной L, т.е.
р(диФ(и, W1), диФ(и, W2)) < LW1 - w^l, W1, W2 e G. (6)
В случае дифференцируемости функции Ф(и, w) по u неравенство (6) переходит в обычное условие Липшица для Ф 'u(u, w):
Фи(и, w1) -фU(u, w2))
< L|w1 - w2||, wb w2 e G. (7)
3. Численный метод решения задачи P (Ф, G), описываемый ниже, основан на результатах работы [5], в которой обобщенный метод уровней применен для численного анализа вариационных неравенств, порождаемых монотонными отображениями. Метод является итерационным и зависит от параметра А, выбираемого из интервала (0,1). Перед началом итерации n предполагается, что уже найдены точки us е G и векторы ls е диФ(и5, us), 1 < s < n. В качестве u1 может быть выбрана любая точка множества G.
Введем экстремальную задачу Ы n с переменными и,т, имеющую следующий вид:
т ^ max, (ls, и - us) > т, 1 < s < n, и е G. (8)
Пусть A n — максимальное значение переменной т задачи Ы n, ц s — оптимальное значение переменной задачи Ыn, двойственной задаче Ыn, отвечающей ограничению (ls,и - us) > т задачи Ыn, 1 < s < n. Из вида задачи Ы n вытекают следующие два соотношения:
n
max X ^s(ls, и - и) =Д n, (9)
UeG
s=1
n
X Иs = 1, Иs > 0, 1 < s < n. (10)
s =1
Выберем произвольное 5 > 0 (о величине 5 будет сказано ниже). Итерация n начинается с решения двойственной пары задач Ы n, Ы „, в результате определяются A n и ц s для s = 1,2, ..., n. Если
An <8, то в качестве приближенного решения задачи P(Ф, G) принимается точка и* = Еn^sus, которая в силу (10) содержится в G.
1590
ГОЛЬШТЕЙН
Если же Аn >5, то к точкам щ, ..., un добавляется еще одна точка un+i е G. Эта точка совпадает с решением экстремальной задачи ^ n вида
||u - Un\\2 ^ min, u е Mn(kA „), (11)
где Mn (т) — выпуклый компакт, определяемый ограничениями задачи (8) при фиксированном значении т < Аn, а X е (0,1) — упомянутый выше параметр метода. На этом итерация n заканчивается. Заметим, что в случае, если G — выпуклый многогранник, то задачи (8) и (11) являются, соответственно, задачами линейного и квадратичного программирования.
4. Для доказательства сходимости описанного метода нам понадобятся три вспомогательных утверждения, формулировки и обоснования которых приведены ниже.
Точечно-множественное отображение T, определенное на множестве G с E со значениями T(u) с E, T(u) ф 0, называют сильно монотонным, если для произвольных u1, u2 е G, l1 е T(u1), l2 е T(u2) справедливо неравенство
(li - 12, u - щ) >a|| ui - u^|2, (12)
где а > 0 — постоянная сильной монотонности.
Лемма 1. Если соблюдаются условия Q1, Q2 и Q3, причем у > L, где постоянные у и L содержатся в соотношениях (3) и (6) соответственно, точечно-множественное отображение T (u) = -дu^(u, u), u е G, является сильно монотонным с постоянной сильной монотонности а = у - L > 0.
Доказательство. В силу Q1 множество д^(u, w) непусто при любых значениях u, w е G. Пусть u1, u2 е G, l1 е дUФ(u1, u1), l2 е дuO(u2, u2). Выберем l е öUФ(u1, u2) из условия
||li - l|| = min ||li -11. (13)
ГеЭ u<b(uh щ)
Имеем
(li -12, u - щ) = (li - l, Щ - u^ + (l -12, u - щ). (14)
Согласно (3),
(l - 12, u - щ) <-^|ui - u^|2, (15)
а в силу (13) и (6) имеем
|(li -1,u - < p(duФ(Ul,u&duФ(Ul,щ))\\щ - u^ < L||ui - u2f. (16)
Из (14)—(16) следует, что
(li - l2,u - щ) < -(у - L)\\ui - u^|2. (17)
Соотношение (17), верное для произвольных ui, u2 e G и li e дUФ(u1, ui), l2 e дuO(u2, u2), эквивалентно сильной монотонности отображения -дUФ(u, u) с постоянной сильной монотонности
а = у - L > 0.
Лемма 2. Пусть соблюдаются все допущения, перечисленные в формулировке леммы 1. В таком случае имеет место оценка
||u* - u*||2 <Аn/а, n = i,2,..., (18)
где точка u* = 2n=i^sus e G вычисляется на итерации n описанного выше метода, u* — единственное решение задачи Р(Ф, G), а = у - L > 0.
Доказательство. При сделанных предположениях задача P (Ф, G) имеет единственное решение. Действительно, из условия Qi вытекает разрешимость этой задачи. Если бы задача P (Ф, G) имела
два различных решения uf и uf, то нашлись бы такие lf е дuO(uf, uf) и lf е дuO(uf, uf), что
(lf, u - uf^ < 0, (lf, u - uf^ < 0 Vu e G. (19)
Из (19) следует, что
(/*, u* - u?) > 0, (/*, u* - u?) < 0. Неравенство (20) в силу леммы 1 приводит к невозможному соотношению
0 < ^1* -1*, u* - < -а и* - u* 2 < 0.
Для произвольных u е G и 1 е диФ(и, u) получаем
n n n
(l, u* - ^ = X Иs (l, us - u) = X Hs (l - ls, us - u) + X us - u).
s=1 s=1
В силу леммы 1 и (10) получаем
n n
X И s(l - ls, us - u > aX И s Ik - ui2 > a
(20)
s=1
u* - u
s=1
s =1
Согласно (9) имеем
X ^s (¡s, us - u) >-Дn
s =1
Из (21)—(23) вытекает соотношение
11,u* - u) + A„ > a
u* - u2
(21)
(22)
(23)
(24)
верное для произвольных и е С, I е 5„Ф(и,и). Используя (24) при и = и* и таком I* е д„Ф(и*,и*), что (I*,и - и*) < 0 Vи е С, получаем (18).
Лемма 3. Пусть выполняется условие Q1. В таком случае члены последовательности {Ап} допускают оценку
А „ <
dL
-1/2
X(1 - X 2)1/2
n = 1,2,
(25)
где й — диаметр компакта G, Ь определено соотношением (2), (0,1) — параметр метода, который входит в формулировку задачи (11).
Лемма 3 не требует доказательства, поскольку вытекает из леммы 4 работы [6] при 0 = С,
Ь = Ч-, вк = р, = (/„ , ь = ь.
5. Уточним понятие приближенного решения задачи Р (Ф, С) в предположении, что эта задача
имеет единственное решение и *. Под е -решением задачи Р(Ф, С) при любом е > 0 условимся понимать такую точку иЕ е С, что ||иЕ - и* < 6.
Следствием лемм 1—3 является следующее утверждение о сходимости описанного выше численного метода решения задачи Р (Ф, С).
Теорема 1. Пусть соблюдаются условия Q1, Q2, Q3, а = у - Ь > 0, 5 = аг2. В таком случае отмеченный метод позволяет при любом е > 0 найти е -решение задачи Р(Ф, С) за п(г) итераций, причем
и(е) < ]а-2Х"2(1 - X2)-1й2Ь2е-4[. (26)
Смысл величин Ь, у, Ь определен, соответственно, в условиях Q1, Q2, Qз, А е (0,1) — параметр метода, й — диаметр выпуклого компакта G, под ] а [ при любом вещественном а понимается наименьшее целое число, большее либо равное а.
6. Применим полученные результаты к анализу игр многих лиц.
Пусть Х( — выпуклый компакт, расположенный в евклидовом пространстве Е,, 1 < г < к, — функция
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.