ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2009, том 45, № 4, с. 97-104
МЕТОДЫ ОПТИМИЗАЦИИ
ОБ ОДНОЙ ЗАДАЧЕ РАВНОВЕСИЯ, СВЯЗАННОЙ С БЕСКОАЛИЦИОННЫМИ ИГРАМИ*
© 2009 г. Е.Г. Гольштейн
(Москва)
Рассматривается задача равновесия, частным случаем которой является задача отыскания точки Нэша бескоалиционной игры многих лиц. Приводится численный алгоритм решения этой задачи. При определенных требованиях к задаче получена оценка скорости сходимости алгоритма. Отмечена связь между задачей равновесия и определяемым ею вариационным неравенством.
1. Пусть E - евклидово пространство; G - непустой выпуклый компакт, содержащийся в E; Ф(м, w), u d G, w d G, - функция с вещественными значениями. Рассмотрим задачу Р(Ф, G) определения точки равновесия u* d G, такой, что
Ф(u*, u*) = maxФ(u, u*). (1)
u d G
В дальнейшем будем анализировать задачу Р(Ф, G) при различных допущениях относительно функции Ф. Наиболее слабыми из них являются следующие.
Условие R1. Функция Ф непрерывна на G # G и вогнута по u d G при любом фиксированном
w d G.
Если функция Ф удовлетворяет условию R1, то задача Р(Ф, G) разрешима, т.е. множество точек ее равновесия U * непусто. Это следует из теоремы Какутани о неподвижной точке. Вместе с тем соблюдение одного лишь условия R1 делает задачу Р(Ф, G) сопоставимой по сложности с задачей поиска неподвижной точки точечно-множественного отображения в условиях теоремы Какутани, решение которой весьма трудоемко. Ниже будет установлено, что задача Р(Ф, G) связана с некоторой антагонистической игрой и поэтому допускает достаточно эффективный численный метод решения, если функция удовлетворяет следующему условию.
Условие R2. Функция Ф - липшицева на G # G, вогнута по u d G при любом фиксированном w d G, выпукла по w d G при любом фиксированном u d G, и, кроме того, Ф(u, u), u d G, является вогнутой функцией.
Ниже будут указаны некоторые другие требования к функции Ф, при соблюдении которых задача Р(Ф, G) оказывается менее сложной, чем в общем случае.
2. Анализ задачи Р(Ф, G) при Ф, удовлетворяющей условию R2, основан на двух вспомогательных утверждениях.
Лемма 1. Если fx), x d G - вогнутая (выпуклая) функция, dfx) - супердифференциал (субдифференциал) f в точке x d G, то при любом x d G множество df(x) Ф 0 и содержит такие элементы l, что ||/|| < L, где L - постоянная в условии Липшица, которому удовлетворяет функция f.
Доказательство. Ограничимся случаем вогнутой функции f
1. Пусть int G Ф 0. Если x d int G, l d df(x), x(s) = x - sl, где s > 0 выбрано таким, чтобы x(s) d G, то f(x(s)) # f(x) + G l, x(s) - x H = f(x) - s || 1112, откуда, используя условие Липшица для функцииf, приходим к неравенству ||l|| < L. Итак, при x d intG норма каждого элемента супердифференциала dfx) не превышает L.
* Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 09-01-00156).
7
97
Рассмотрим произвольную граничную точку x компакта G. Выберем последовательность {xs} точек xs d int G, сходящуюся к x. Пусть ls d df(xs), || ls ||< L, s = 1, 2, ... Очевидно, что любая предельная точка l ограниченной последовательности {ls} содержится в dfx), причем ||l ||< L. Тем самым лемма доказана в случае int G Ф 0.
2. Предположим теперь, что int G = 0 и E - подпространство евклидова пространства E, некоторый сдвиг которого является линейной оболочкой G. Обозначим df (x) проекцию супердифференциала dfx) на E. Очевидно, что df (x) f df(x). Пусть ri G - относительная внутренность множества G. Рассуждения, аналогичные случаю int G ! 0, позволяют установить, что при x d ri G все элементы df (x) имеют норму, не превышающую L, а при x g ri G, x d G, df (x) содержит такие элементы l, что 11111 < L.
Лемма 2. Пусть Ф (u, w), (u, w) d G X G - такая липшицева функция с постоянной L, вогнутая по u при любом фиксированном w d G, выпуклая по w при любом фиксированном u d G, что
U(u, u) / 0, u d G. (2)
В таком случае при любом u d G
duф(u, u) = -dwф(u, u)! 0, (3)
где d^(u, w) - супердифференциал Ф по u в точке (u, w), а d^(u, w) - субдифференциал Ф по w в точке (u, w).
Доказательство. Для каждой точки u d G введем конус возможных направлений K(u) = {s d E: u + es d G3s >0}. Пусть u d G, l d duФ(u, u)(duФ(u, u) ! 0 в силу леммы 1), s d K(u). Для достаточно малых положительных e имеем
Ф(u + es, u)< Ф(u, u) + e (l, s >, (4)
U(u + es, u) > Ф(u + es, u + es) - e (l(e, s), s >,
где l(e, s) - некоторый элементдwФ(u + el, u + el), причем в силу леммы 1 можно считать, что
Ill(e, s)||<L.
Поскольку согласно (2) Ф(u, u) = Ф(u + es, u + es) = 0, то в силу (4) имеем
(l + l(e, s), s > >0, (5)
где l(e, s) d dwФ(u + es, u + es), || l(e, s) || < L.
Устремляя в (5) e > 0 к нулю, получаем при любых u d G, l d дмФ(u, u) и s d K(u)
(l +1(s), s > >0, (6)
где l(s) d dwФ(u, u), || l(s)||< L.
Из равномерной ограниченности векторов l(s) и замкнутости d„^(u, u) следует, что (6) имеет место для любых l d дмФ(u, u) и s d cl K(u) (cl K(u) - замыкание конуса K(u)). Итак, для произвольных l d дмФ(u, u) и s d cl K(u) справедливо неравенство
(l +1(s), s > >0, (7)
где l(s) - некоторый элемент множества d„^(u, u). Докажем, что из неравенства (7) вытекает включение
duФ(u, u) f -дwФ(u, u). (8)
Действительно, если (8) неверно, т.е. существует такой вектор l0 d дuФ(u, u), что l0 g -дwФ(u, u), то в силу выпуклости и замкнутости множества -d„^(u, u) существует вектор s0, удовлетворяющий требованиям
(l0, s0 ><0, (l, s0 >>0 6l d -дwФ(u, u). (9)
Проверим, что s0 d cl K(u). Если Г d -дwU(u, u), то очевидно, что l +1' d -дwU(u, u) при любом l d K*(u), где K*(u) = {l d E: (l, s ) >0 6 s d K(u)} - конус, сопряженный с K(u). Поэтому согласно правому неравенству (9) имеем
(l, s0 ) >0 6l d K*(u). (10)
Соотношения (10) означают, что s0 d (K*(u))* = K**(u). Но, как известно, K**(u) = clK(u). Следовательно,
s0 d cl K(u). (11)
Из (9) и (11) вытекает, что
(10 + l, s0 ) <0 6l d дwФ(u, u), s0 d clK(u). (12)
Но (12) входит в противоречие с (7). Следовательно, включение (8) верно. Если повторить рассуждения, использованные для доказательства (8), поменяв местами u и w, то получим противоположное включение: дwU(u, u) f дuU(u, u), которое совместно с (8) и эквивалентно (3).
Рассмотрим антагонистическую игру Г(Ф, G), в которой первый игрок выбирает стратегию u d G, второй игрок - стратегию w d G, а выигрыш первого игрока определяется функцией выигрышей Ф(^ w), u,w d G. Положим Ф1(u, w) = Ф(u, w) - Ф(w, w), u, w d G. Очевидно, что U1(u, u) = 0, u d G.
Теорема 1. Пусть функция Ф удовлетворяет требованиям R2. В таком случае седловое множество антагонистической игры Г(Ф, G) имеет вид U* х U*, где U* - множество решений (точек равновесия) задачи Р(Ф, G), а цена v* игры Г(Ф, G) равна нулю.
Доказательство. Пусть u* d U*. Тогда согласно (1) и определению функции Ф1 имеем
maxФ^, u*) = Ф1(и*, u*)=0. (13)
u d G
Следовательно, 0 d дuФ1(u*, u*). Тогда 0 d дwФ1(u*, u*) по лемме 2, откуда вытекает
minФ1(u*, w) = Ф1(u*, u*). (14)
w d G
Соотношения (13), (14) означают, что v* = 0, а (u*, u*) является седловой точкой функции Ф^, w), u d G, w d G.
Допустим теперь, что (u*, w*) - седловая точка функции Ф^, w), u d G, w d G. Поскольку Ф1(и*, w*) = v* = 0, Ф^*, w*) = 0, то
maxФ1(u, w*) = Ф1(и*, w*) = Ф^*, w*)
u d G
и согласно (1) точки u*, w* d U*. Таким образом, (u*, w*) d U* х U*.
3. Согласно теореме 1 задача Р(Ф, G) при Ф, удовлетворяющей требованиям R2, оказывается эквивалентной антагонистической игре с нулевой ценой игры и симметричным седловым множеством. Поэтому для численного решения задачи Р(Ф, G) можно воспользоваться достаточно эффективным методом отыскания седловых точек выпукло-вогнутых функций, содержащимся в (Гольштейн, Немировский, Нестеров, 1995).
Описание и анализ численного метода решения задачи Р(Ф, G) основан на соответствующих результатах работы (Гольштейн, Немировский, Нестеров, 1995) и отмеченной в теореме 1 специфике игры Г(Ф, G).
Метод решения задачи Р(Ф, G) является итерационным и зависит от параметра А, выбираемого из интервала (0, 1). Перед началом итерации q предполагается, что точки ui d G и векторы
Iг е диФ(и, иг), 1 < г < д, уже найдены. В качестве и1 может быть выбрана любая точка множества G. Введем задачу Лд с переменными и, х, имеющую вид:
х " тах, (I, и - и1) > х, 1 < г < д, и е G. (15)
Предположим, что выпуклый компакт G является многогранником. В этом случае Л - задача линейного программирования. Пусть Дд - максимальное значение переменной х задачи Л ; Ач -задача, двойственная Лд; пг - оптимальное значение переменной задачи Лд, отвечающей ограничению (I, и - иг ) > х задачи Лд, 1 < г < д. Из вида задачи Лд вытекает справедливость следующих двух соотношений:
q
max/n G h, u - u ) = A (16)
= 1
/ р,- =1, П,- >0, 1< i < q. (17)
i =1
Выберем произвольное s > 0. Итерация q начинается с решения двойственной пары задач линейного программирования Aq, Aq, в результате чего вычисляются Aq и р., 1 < i < q. Если Aq < s,
q
то в качестве приближенного решения задачи Р(Ф, G) принимается точка u*q = /pu,-, которая в
i=1
силу (17) содержится в G. В этом случае итерация q является последней. Если же Aq > s, то множество точек{и1, ... ,uq} пополняется новой точкой uq+1. Эта точка находится из решения задачи квадратичного программирования
||u - uq ||2 " min, и d Mq(AAq), (18)
где Mq(x) - многогранник, определяемый условиями задачи (15) при фиксированном значении x < Aq, а А е (0, 1) - параметр метода. Таким образом, точка uq+1 - проекция точки uq на многогранник Mq(AAq). На этом итерация q заканчивается.
Прежде чем приступить к обоснованию данного метода, уточним понятие приближенного решения задачи Р(Ф, G). Под s-решением задачи Р(Ф, G) при любом фиксированном s > 0 условимся понимать такую точку us е G, для которой верно неравенство
max Ф(и, ue)- Ф(ueue)< е. (19)
и d G
Из (1) и (19) следует, что е-решение задачи Р(Ф, G) при е = 0 совпадает с решением этой задачи. Обоснование метода основано на двух вспомогательных леммах. q
Лемма 3. Если функция Ф удовлетворяет условию R2, то точка «*q = /n,-«,- d G является Dq-р
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.