close

Вход

Забыли?

вход по аккаунту

?

Вычисление неподвижных точек симметричных экстремальных отображений.

код для вставкиСкачать
1997
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ
МАТЕМАТИКА
Є 12 (427)
УДК 519.853
А.С. АНТИПИН
ВЫЧИСЛЕНИЕ НЕПОДВИЖНЫХ ТОЧЕК
СИММЕТРИЧНЫХ ЭКСТРЕМАЛЬНЫХ ОТОБРАЖЕНИЙ
1. Постановка проблемы
Рассмотрим задачу вычисления неподвижной точки v 2 экстремального отображения
[1], [2]
v 2 Argminf(v; w) j w 2 g;
(1.1)
где функция (u; v) определена на произведении пространств Rn Rn. Переменная v играет
роль параметра, w | переменная оптимизации. Множество Rn выпуклое замкнутое. Предполагается, что экстремальное (маргинальное) отображение w(v) argminf(v; w) j w 2 g
определено для всех v 2 , а множество решений исходной задачи непусто.
Как следует из (1.1), любая неподвижная точка удовлетворяет неравенству
(v ; v ) (v ; w) 8w 2 :
(1.2)
Это неравенство можно рассматривать как эквивалентное определение неподвижной точки.
Известно, что линейное пространство квадратных матриц имеет два линейных подпространства симметричных и кососимметричных матриц. При этом любая квадратная матрица может
быть разложена в сумму двух проекций на эти подпространства. Проводя аналогию между
квадратными матрицами и целевыми функциями (v; w) задачи (1.1), выделим в линейном
пространстве этих функций два линейных подпространства, которые характеризуются соотношениями
(w; v) + (v; w) = 0 8w 2 ; 8v 2 ;
(1.3)
(w; v) ; (v; w) = 0 8w 2 ; 8v 2 :
(1.4)
Функции первого класса будем называть кососимметричными, а второго | симметричными.
В случае, если область определения этих функций представляет собой квадратную сетку, мы
имеем дело с обычными классами кососимметричных и симметричных матриц.
Напомним, что пара точек с координатами w; v и v; w расположена симметрично относительно диагонали квадрата . Это дает нам возможность ввести понятие транспонированной
функции [3]. Если каждой точке с координатами v; w поставить в соответствие значение функции ( ; ), вычисленной в точке w; v, то получим транспонированную функцию T (v; w). В
терминах этой функции условия (1.3) и (1.4) имеют вид
(v; w) = ;T (v; w); (v; w) = T (v; w):
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований
(код проекта Є 96-01-01046) и по программе государственной поддержки ведущих научных школ (код
проекта Є 96-15-96124).
3
Используя очевидные соотношения: (v; w) = (T (v; w))T , (1 (v; w) + 2 (v; w))T = T1 (v; w) +
T2 (v; w), нетрудно проверить, что вещественную функцию (v; w) всегда можно представить в
виде суммы
(v; w) = S (v; w) + K (v; w);
где функция S (v; w) симметричная, а K (v; w) кососимметричная. Это разложение единственно,
причем S (v; w) = 21 ((v; w) + T (v; w)), K (v; w) = 21 ((v; w) ; T (v; w)).
В данной работе ограничимся симметричными функциями. Кососимметричный случай рассматривался в [1]{[3].
2. Симметричные функции
Рассмотрим характеристические свойства симметричных функций и их возможные обобщения. Сначала укажем два примера таких функций, которые хорошо известны в экономических приложениях. Первая из них | это функция Кобба-Дугласа, а вторая | функция с
постоянной эластичностью замены ресурсов. Они имеют вид соответственно: (v; w) = Av w
и (v; w) = A[v;! + w;! ];=! , где A > 0, > 0, > 0, ! > 0, > 0| параметры. Если
параметры и равны, то эти функции симметричны.
Свойство 1. Частные производные симметричных функций на диагонали квадрата равны.
Пусть v; v 2 , тогда в некоторой окрестности этой точки возьмем две другие с координатами v + "h; v ; "h и v ; "h; v + "h, где " > 0, а h | некоторый фиксированный вектор такой,
что любая из этих двух точек принадлежит внутренности квадрата . Для каждой из этих
точек выпишем разложение функции (v; w) по формуле конечных приращений вида
f (x + h) ; f (x) = hrf (x + #h); hi;
(2.1)
где 0 # 1, тогда получим
(v + "h; v ; "h) = (v; v) + "hrv (v + "#1 h; v ; "#1 h); hi ; "hrw (v + "#1 h; v ; "#1 h); hi
и
(v ; "h; v + "h) = (v; v) ; "hrv (v ; "#2 h; v + "#2 h); hi + "hrw (v ; "#2 h; v + "#2 h); hi:
Подставим левые части полученных разложений в (1.3) и, переходя к пределу при " ! 0,
получим
hrv (v; v); hi = hrw (v; v); hi 8h 2 Rn:
Поскольку равенство (2.1) верно для всех h 2 Rn , то имеем
rv (v; v) = rw (v; v):
(2.2)
Свойство 2. Оператор rw (v; v ) является потенциальным на диагонали квадрата .
По определению дифференцируемости функции (v; w) имеем
(v + h; w + h) = (v; w) + hrv (v; w); hi + hrw (v; w); ki + !(v; w; h; k);
(2.3)
где !(v; w; h; k)=(jhj2 + jkj2 )1=2 ! 0 при jhj2 + jkj2 ! 0. Пусть w = v и h = k, тогда с учетом (2.2)
и (2.3) получим
(v + h; v + h) = (v; v) + 2hrw (v; v); hi + !(v; h);
(2.4)
где !(v; h)=jhj ! 0 при jhj ! 0. Поскольку формула (2.4) является частным случаем (2.3), то
она означает, что сужение частного градиента rw (v; w) на диагональ квадрата является
градиентом функции (v; v), т.е.
2rw (v; w)jv=w = r(v; v):
(2.5)
4
Как следствие из этого факта вытекает справедливость формулы Лагранжа
(v + h; v + h) = (v; v) + 2
Z
1
0
hrw (v + th; v + th); hi dt:
Свойство (2.5) является ключевым, т.к. из него фактически следует, что неподвижные точки
задачи (1.1) являются точками минимума функции (v; v) на диагонали квадрата .
Если градиент функции (v; w) удовлетворяет условию Липшица, то выполняется неравенство
j(v + h; w + k) ; (v; w) ; hrv (v; w); hi ; hrw (v; w); kij 21 L(jhj2 + jkj2 ) 8(v + h; w + k) 2 ; (2.6)
где L | константа Липшица. Пусть h = k, v = w в (2.6), тогда с учетом (2.5) получим
j(v + h; v + h) ; (v; v) ; hr(v; v); hij Ljhj2 8v + h 2 :
(2.7)
2
Свойство 3. Вторая смешанная производная r wv (v; w )jv =w симметричной функции (v; w )
на диагонали квадрата симметрична, т.е.
r2wv (v; v) = r2Twv (v; v) 8v 2 :
(2.8)
Воспользуемся формулой Тейлора ([4], гл. 2, x 3, с. 92)
f (x + h) ; f (x) = hrf (x); hi + 12 hr2f (x + #h)h; hi;
где 0 # 1, и выпишем разложение симметричной функции (v; w) в точке (v + "h; v ; "h),
" > 0, а h | вектор, определенный выше,
(v + "h; v ; "h) = (v; v) + "hrv (v; v); hi ; "hrw (v; v); hi +
+ 12 "2 hr2 vv (v + #1 "h; v ; #1 "h)h; hi ; "2 hr2 wv (v + #1 "h; v ; #1 "h)h; hi +
+ 12 "2 hr2 ww (v + #1 "h; v ; #1 "h)h; hi:
Разложение этой функции в точке (v ; "h; v + "h) имеет тот же самый вид, но константа # 1
будет иметь другое значение. Оба разложения приравняем согласно (1.3). Учитывая (2.2) и
соотношение hAh; hi = hh; AT hi, получим
hr2vv (v + #1"h; v ; #1"h)h; hi ; 2hr2 wv (v + #1"h; v ; #1"h)h; hi +
+ hr2 ww (v + #1 "h; v ; #1 "h)h; hi = hr2 vv (v ; #2 "h + #2 "h)h; hi ;
; 2hh; r2 Twv (v ; #2"h; v + #2"h)hi + hr2ww (v ; #2"h; v + #2"h)h; hi:
Переходя к пределу при " ! 0 и учитывая непрерывность второй производной, получим
hr2wv (v; v)h; hi = hr2Twv (v; v)h; hi 8v 2 :
Отсюда имеем (2.8). Доказанное утверждение используем, чтобы вычислить явный вид второй
производной функции (v; v).
Если функция (v; w) дважды дифференцируема, то по определению выполняется условие
(v + h; w + k) = (v; w) + hrv (v; w); hi + hrw (v; w); ki + 21 fhr2 vv (v; w)h; hi +
+ 2hr2 wv (v; w)h; ki + hr2 ww (v; w)h; hig + !(v; w; h; k); (2.9)
5
где !(v; w; h; k)=(jhj2 + jkj2 ) ! 0 при jhj2 + jkj2 ! 0. Пусть w = v и h = k, тогда с учетом (2.2) из
(2.9) имеем
(v + h; v + h) = (v; v) + 2hrw (v; v); hi +
+ 12 hfr2 vv (v; v) + 2r2 wv (v; v) + r2 ww (v; v)gh; hi + !(v; h);
где !(v; h)=jhj2 ! 0 при jhj ! 0. Здесь матрицы r2 vv (v; v), r2 ww (v; v) симметричны как
диагональные подматрицы симметричной матрицы r2 (v; w), матрица r2 wv (v; v) симметрична
по доказанному, следовательно, матрица
r2(v; v) = r2vv (v; v) + 2r2wv (v; v) + r2ww (v; v)
также симметрична и представляет собой вторую производную функции (v; v).
Покоординатная оптимизация. Рассмотрим класс функций (v; w), каждая из которых
является симметричной и нормализованной функцией (v; w) = L1 (z; p) + L2 (x; y), где v = x; p
и w = z; y, для игры двух лиц вида
x 2 argminfL1(x; p ) j x 2 Qg; p 2 argminfL2(x ; p) j p 2 P g:
Пусть функция (v; w) обладает свойством симметрии (1.3), тогда согласно свойству (2.2) при
w = v имеем
@L2(x; p) = @L1 (x; p) ; @L1(x; p) = @L2 (x; p) :
(2.10)
@x
@x
@p
@p
Эти условия означают, что функции L1 (x; p) и L2 (x; p) с точностью до константы совпадают, т.е.
L1(x; p) = L2(x; p) + C , а неравенство (1.2) принимает вид
L(x ; p) L(x; p) 8x 2 Q; L(x; p ) L(x; p) 8p 2 P;
(2.11)
где L(x; p) = L1 (x; p) = L2 (x; p) и C = 0.
Таким образом, неподвижная точка x ; p обладает свойством: ее первая компонента является точкой минимума функции L(x; p) по первой координате при p = p , а вторая компонента |
точкой минимума этой функции по второй координате при x = x . Эта ситуация полностью ана-
логична седловой задаче [5] и различие состоит лишь в том, что в седловом случае по одной из
переменных осуществляется операция максимизации. В содержательном плане седловая задача
описывает антагонистическое взаимодействие двух игроков. Задача покоординатной оптимизации, наоборот, моделирует максимально доброжелательное взаимодействие участников.
Если функция L(x; p) выпуклая по совокупности переменных x; p, то нетрудно проверить,
что точка x ; p будет минимумом этой функции по всем своим переменным. Действительно, в
силу выпуклости имеем
hrL(v); v ; vi L(v ) ; L(v) hrL(v ); v ; vi 8v; v 2 ;
(2.12)
где v = x; p, v = x ; p и = Q P . Представим также систему неравенств (2.11) в эквивалентной форме
hrLx(x; p); x ; xi 0 8x 2 Q; hrLp(x ; p); p ; pi 0 8p 2 P:
(2.13)
Учитывая (2.13) в правой части системы (2.12), получим
L(v ) L(v) 8v 2 ;
т.е. в выпуклом случае равновесное решение является точкой минимума.
Потенциальные игры. Введем следующее определение. Равновесную задачу (1.1) назовем
потенциальной, если существует функция P (v) такая, что
rP (v) = rw (v; w)jv=w 8v 2 :
(2.14)
6
Класс потенциальных задач не пуст, т.к. равновесные задачи со свойством (1.3) удовлетворяют
условию потенциальности. Совершенно ясно, что равновесные решения этих задач являются
точками минимума функции P (v) на .
В работе [6] на примере игры Курно было введено понятие потенциальной игры следующим
образом. Если для игры n лиц с равновесием по Нэшу
xi 2 Argminffi(xi ; x;i ) j xi 2 Xi g;
где fi (xi ; x;i ) | платежная функция i-го игрока, i 2 I = f1; 2; : : : ; ng, xi 2 Xi = (xi )i2I , x;i 2
X;i = (xj )j2I ni , (xi ; x;i ) = x 2 X = X1 X2 Xn , существует функция p(x1 ; x2; : : : ; xn)
такая, что
@p(x1 ; x2; : : : ; xn ) = @fi (x1; x2 ; : : : ; xn ) ; i 2 I;
(2.15)
@xi
@xi
то игра называется потенциальной. Другими словами, частные производные платежных функций по собственным переменным игроков в совокупности образуют градиент некоторой функции
p(x1; x2 ; : : : ; xn ), которая называется потенциалом. Перепишем условие (2.15) в форме
@p(xi ; x;i ) = @fi (xi ; x;i) ; i 2 I;
@xi
@xi
и будем рассматривать несобственные переменные x;i 2 X;i как параметры. Тогда полученное
условие означает, что при всех значениях параметра x;i 2 X;i производные двух функций
совпадают, т.е.
p(xi ; x;i ) = fi (xi ; x;i) + ci (x;i ):
(2.16)
Таким образом, целевые функции потенциальной игры с точностью до константы ci (x;i ) равны
между собой.
Из (2.16) получим
n
n
n
X
X
X
p(xi; x;i ) = fi(xi ; x;i ) + ci (x;i);
т.е.
i=1
i=1
i=1
p(v; w) = (v; w) + C (v);
(2.17)
где P (v; w), (v; w) и C (v) | соответствующие суммы из предыдущего равенства. При этом,
если v = w, то
P (v; w)jv=w = np(v) = np(x1; x2 ; : : : ; xn ):
(2.18)
Нормализованная функция (v; w) и функция P (v; w), порожденная потенциалом p(v), различаются на C (v), которую можно рассматривать как константу, т.к. ее присутствие не влияет
на минимум функции (v; w) по переменной w 2 . Отбросив константу C (v), можно считать,
что P (v; w) и (v; w) совпадают.
Из (2.18) следует
rPw (v; w)jv=w = nrp(v):
(2.19)
Сопоставляя (2.17) и (2.19), имеем
nrp(v) = rw (v; w)jv=w :
Таким образом, потенциальные игры в смысле (2.15) являются потенциальными играми и в
смысле (2.14). Если потенциал есть функция двух переменных p(x1 ; x2 ) для игры двух лиц, то,
как показано в (2.10){(2.11), функция P (v; w) будет симметричной.
7
3. Прогнозный метод проекции градиента
Рассмотрим равновесную задачу (1.1). Неподвижная точка v 2 этой задачи является
решением как вариационного неравенства
hrw (v ; v ); w ; v i 0 8w 2 ;
(3.1)
так и операторного уравнения
v = (v ; rw (v ; v ));
(3.2)
где (: : : ) | оператор проектирования некоторого вектора на множество . Оба соотношения
эквивалентны и являются необходимым условием минимума функции (v ; w) на множестве .
Так как оператор правой части уравнения (3.2) нерасширяющийся, возникает вопрос о сходимости метода
vn+1 = (vn ; rw (vn ; vn ))
(3.3)
к решению уравнения (3.2) или, что то же самое, к решению вариационного неравенства (3.1).
Проделав несложные вычисления по традиционной схеме, убедимся, что процесс (3.3) сходится к равновесному решению симметричной задачи. Однако область применимости этого метода ограничивается задачами минимизации. Известно, что в седловом варианте [5] этот метод
не сходится к седловой точке, в то же время градиентный метод прогнозного типа (экстраградиентный [7], [8]) сходится к этому решению. Последнее обстоятельство представляет для
нас значительный интерес. Имея сказанное в виду, рассмотрим градиентный метод прогнозного
типа
un = (vn ; rw (vn ; vn )); vn+1 = (vn ; rw (un; un ))
(3.4)
и покажем, что в классе симметричных целевых функций (v; w) метод сходится к решению
исходной задачи.
Выпишем некоторые оценки и неравенства. В (2.7) поменяем местами значения аргументов
(это можно сделать, поскольку неравенство верно для любых пар v + h; v + h и v; v), а затем
полученное неравенство прибавим к (2.7), в итоге получим
jr(v + h; v + h) ; r(v; v)j 2Ljhj 8(v + h; v + h) 2 :
(3.5)
Из (3.4) и (3.5) с учетом (2.5) имеем
jun ; vn+1j 2 jr(vn ; vn ) ; r(un; un )j Ljvn ; unj:
(3.6)
Представим уравнения (3.4) в форме вариационных неравенств
hun ; vn + rw (vn ; vn ); w ; un i 0 8w 2 ;
(3.7)
hvn+1 ; vn + rw (un ; un ); w ; vn+1 i 0 8w 2 и докажем теорему.
Теорема 1. Если дифференцируемая целевая функция (v; w ) удовлетворяет условию симметрии (1.3), градиент функции (v; v) удовлетворяет условию Липшица (2.7), 2 Rn |
выпуклое замкнутое ограниченное множество, то последовательность vn , порожденная методом (3.4) с параметром 0 < < 1=L, имеет непустое множество предельных точек, каждая из которых является стационарной точкой задачи (1.1).
Если дополнительно к перечисленным условиям функция (v; w) выпукла по переменной w,
то любая стационарная точка является неподвижной точкой задачи (1.1).
8
Положим w = vn в первом неравенстве (3.7) и w = un | во втором, тогда
с учетом (2.5) будем иметь
Доказательство.
hvn+1 ; vn; vn+1 ; uni + 2 hr(un ; un); vn+1 ; uni 0;
jun ; vnj2 + 2 hr(vn ; vn ); vn+1 ; vn i ; 2 hr(vn; vn ); vn+1 ; uni 0:
Сложим оба неравенства
hvn+1 ; vn ; vn+1 ; uni + jvn ; unj2 + 2 hr(vn ; vn ); vn+1 ; vn i +
+ 2 hr(un ; un ) ; r(vn ; vn ); vn+1 ; un i 0: (3.8)
Используя тождество
jx1 ; x3 j2 = jx1 ; x2j2 + 2hx1 ; x2; x2 ; x3i + jx2 ; x3j2 ;
(3.9)
разложим скалярное произведение в левой части (3.8) на сумму квадратов. Затем, применяя
неравенство (2.7) и оценки (3.5) и (3.6), получим
jvn+1 ; vnj2 + jvn+1 ; unj2 ; jvn ; unj2 + 2jun ; vnj2 +
+ 2 ((vn+1 ; vn+1 ) ; (vn ; vn )) ; 2 Ljvn+1 ; vn j2 ; (L)2 jvn ; un j2 0:
Отсюда
(vn+1 ; vn+1 ) + d1jvn+1 ; vn j2 + jvn+1 ; un j2 + d2 jvn ; unj2 (vn ; vn );
(3.10)
где d1 = 1 ; (=2)L > 0 и d2 = 1 ; (L)2 > 0, т.к. < 1=L. Из этого неравенства следует
монотонное убывание последовательности по функционалу.
Просуммируем полученную систему неравенств от n = 0 до n = N
(vN +1; vN +1 ) + d1
Отсюда
1
X
k=0
N
X
k=0
jvk+1 ; vk j2 +
jvn+1 ; vnj2 < 1;
и, следовательно,
1
X
k=0
N
X
k=0
jvk+1 ; uk j2 + d2
jvn+1 ; unj2 < 1;
N
X
k=0
1
X
k=0
jvk ; uk j2 (v0 ; v0):
jvn ; unj2 < 1
jvn+1 ; vnj ! 0; jvn+1 ; unj ! 0; jvn ; unj ! 0; n ! 1:
(3.11)
Так как последовательность vn ограничена, то существует элемент v0 такой, что vn ! v0
при ni ! 1, и при этом
jvn +1 ; vn j ! 0; jvn +1 ; un j ! 0; jvn ; un j ! 0:
Переходя к пределу по подпоследовательности ni ! 1 в (3.7) (или, что то же самое в (3.4)),
i
i
получим
i
i
i
i
hrw (v0 ; v0 ); w ; v0 i 0 8w 2 :
i
(3.12)
Поскольку это соотношение совпадает с (3.1), то любая предельная точка последовательности vn
является стационарной точкой равновесной задачи (1.1). Очевидно, множество решений задачи
(1.1) составляет подмножество (может быть, пустое) множества стационарных точек.
Если целевая функция (v; w) выпукла по w при любом фиксированном значении v, то
выполняется неравенство
(v0 ; w) ; (v0 ; v0 ) hrw (v0 ; v0 ); w ; v0 i 8w 2 :
(3.13)
9
С учетом (3.12) имеем
(v0 ; v0 ) (v0 ; w) 8w 2 :
Полученное неравенство, очевидно, совпадает с (1.2). Последнее означает, что v0 = v 2 , т.е.
любая предельная точка является равновесным решением задачи. Поскольку величина (vn ; vn )
согласно (3.10) убывает монотонно, то во всех предельных точках последовательности значение
функции одно и то же и равно (v0 ; v0 ).
Доказанное утверждение можно рассматривать как теорему существования неподвижной
точки для многозначных симметричных экстремальных отображений. Действительно, ее содержательный смысл состоит в следующем: если функция (v; w) симметрична, дифференцируема
и выпукла по второй переменной, а | компакт, то неподвижная точка задачи (1.1) всегда
существует.
4. Монотонная сходимость
Если функция (v; w) симметрична и одновременно выпукла по w, то в силу условия симметрии (1.3) она будет выпуклой и по переменной v. Таким образом, в этом случае функция
является выпукло-выпуклой, т.е. выпуклой как по одной переменной, так и по другой. Однако,
сужение выпукло-выпуклой симметричной функции S (v; w) на диагональ квадрата (т.е.
v = w) может не быть выпуклым. Действительно, пусть S (v; w) = hv; Awi, где v 2 R2, w 2 R2, а
матрица A имеет размерность 2 2. Эта функция линейна по своим переменным и, следовательно, выпукла по ним. Будет ли функция
hv; Avi выпукла на R2? Это зависит от вида матрицы
;1 0
A. Если матрица
имеет тип A = 0 1 , то функция выпуклая, если же матрица имеет структуру
;
0
1
вида A = 1 0 , то функция не выпуклая.
Для монотонной по норме сходимости градиентного метода к решению задачи ключевым
свойством является выпуклость целевой функции на диагонали квадрата, а не по переменной
w. Будем предполагать, что (v; w) выпукла на диагонали квадрата и необязательно выпукла
по переменной w. Тогда ее частный градиент rw (v; w) не обязательно монотонный оператор
при любом v, но его сужение на диагональ квадрата согласно (2.5) будет градиентом выпуклой
функции (v; v), т.е. 2r(v; w)jv=w = r(v; v), и потому монотонным оператором. Последнее
означает, что для него выполняется неравенство
hr(v + h; v + h) ; r(v; v); hi 0 8v 2 ; 8h 2 Rn:
(4.1)
Теорема 2. Если целевая функция (v; w ) симметрична, а ее сужение на диагональ квадрата представляет собой выпуклую и дифференцируемую функцию, причем градиент этого
сужения удовлетворяет условию Липшица (3.5), 2 Rn | выпуклое замкнутое множество,
то последовательность vn , порожденная методом (3.4) с параметром 0 < < 1=L, монотонно
но норме пространства сходится к минимуму функции (v; v) на . Этот минимум является
по крайней мере стационарной точкой задачи (1.1).
Если дополнительно к перечисленным условиям функция (v; w) выпукла по второй переменной w при любом значении v 2 , то найденный минимум является равновесным решением
задачи (1.1).
Положим w = v 2 во втором неравенстве (3.7) и w = vn+1 | в первом,
в (3.1), затем с учетом (2.5) сложим все неравенства, тогда получим
Доказательство.
а также w
= un
E
vn+1 ; vn + 2 r(un; un ); v ; vn+1 +
E
D
+ un ; vn + 2 r(vn ; vn ); vn+1 ; un + hr(v ; v ); u ; v i 0:
D
10
Отсюда имеем
hvn+1 ; vn ; v ; vn+1i + hun ; vn ; vn+1 ; uni + 2 hr(un; un ) ; r(vn ; vn ); un ; vn+1i +
+ 2 hr(un ; un ) ; r(v ; v ); v ; un i 0: (4.2)
Два первых скалярных произведения в полученном неравенстве разложим в сумму квадратов с
помощью тождества (3.9), третье слагаемое оценим, используя (3.5), (3.6), и, наконец, последнее
слагаемое оценим с помощью (4.1), тогда получим
jvn+1 ; vj2 + jvn+1 ; vnj2 + jvn ; unj2 + jun ; vn+1 j2 ; (L)2 jun ; vn j2 jvn ; v j2 + jvn+1 ; vnj2 :
Поэтому
jvn+1 ; v j2 + djvn ; unj2 + jun ; vn+1 j2 jvn ; v j2;
(4.3)
где d = 1 ; (L)2 > 0, т.к. < 1=L. Отсюда при < 1=L следует монотонность убывания
величины jvn ; v j2 при n ! 1. Просуммируем неравенства (4.3) от n = 1 до n = N , тогда
jvN +1 ; v j2 + d
N
X
n=1
jvn ; unj2 +
N
X
n=1
jun ; vn+1j2 jvn ; vj2 :
1
P
1
P
Из последнего неравенства вытекает сходимость рядов jvn ; un j2 , jun ; vn+1 j2 и соответn=1
n=1
ственно стремление к нулю величин
jvn ; unj2 ! 0; jun ; vn+1 j2 ! 0; n ! 1:
(4.4)
1 jx ; x j2 jx ; x j2 + jx ; x j2 ;
1
3
3
2
2 1 2
(4.5)
jvn+1 ; vnj2 ! 0; n ! 1:
(4.6)
Используя оценку
из (4.4) имеем
Так как последовательность vn ограничена, то существует элемент v0 такой, что vni ! v0
при ni ! 1, и при этом jvni +1 ; vni j2 ! 0, juni ; vni j2 ! 0.
Рассмотрим неравенства (3.7) для всех ni ! 1 и, перейдя к пределу с учетом (2.5), получим
hr(v0 ; v0 ); w ; v0 i 0 8w 2 :
Поскольку это соотношение совпадает с (3.1), то любая предельная точка последовательности
vn является минимумом (v; v) на . Условие монотонности убывания величины jvn ; v0j обеспечивает единственность предельной точки, т.е. сходимость vn ! v0 при n ! 1.
Если целевая функция (v; w) выпукла по w при любом фиксированном значении v, то
согласно (3.13) имеем
(v0 ; v0 ) (v0 ; w) 8w 2 :
Следовательно, v0 = v 2 , т.е. единственная предельная точка является равновесным решением задачи.
11
5. Конечная сходимость
Оценки скорости сходимости прогнозного метода проекции градиента (3.4) для симметричной функции полностью зависят от поведения этой функции на диагонали квадрата .
Будем предполагать, что минимум функции (v; v) на удовлетворяет условию остроты ([9],
гл. 5, x 2, с. 127)
(v; v) ; (v ; v ) jv ; v j 8w 2 ;
(5.1)
где 0 константа. Кроме того, предполагается, что градиент r(v; v) удовлетворяет условию
Липшица (3.5).
Заметим, что седловая точка невырожденной задачи линейного программирования, которая всегда является неподвижной точкой задачи (1.1) с нормализованной функцией (v; w),
удовлетворяет перечисленным выше условиям [2].
Теорема 3. Если множество решений задачи (1.1) не пусто и удовлетворяет условию
остроты (5.1), функция (v; w) | симметричная, выпуклая на диагонали квадрата ,
дифференцируема, причем ее градиент на диагонали квадрата удовлетворяет условию
Липшица (3.5), | выпуклое замкнутое множество, то последовательность vn , порожденная методом (3.4) с параметром 0 < < 1=L сходится к минимуму (v; v) на за конечное
число итераций, т.е. существует такой номер n0, при котором vn0 = v 2 .
Если дополнительно к перечисленным условиям функция (v; w) выпукла по w при любом
v 2 , то метод сходится за конечное число итераций к равновесному решению исходной
задачи.
n+1 | в первом,
Доказательство. Положим w = v во втором неравенстве (3.7), а w = v
затем с учетом (2.5) сложим оба неравенства, при этом получим неравенство типа (4.2), но в
нем отсутствует слагаемое вида (3.1)
hvn+1 ; vn ; v ; vn+1i + hun ; vn ; vn+1 ; uni +
+ 2 hr(un ; un ) ; r(vn ; vn ); un ; vn+1 i + 2 hr(un ; un ); v ; un i 0: (5.2)
В полученном неравенстве, следуя (4.2), преобразуем два первых скалярных произведения, третье слагаемое оценим с помощью (3.5), (3.6), а последнее | с учетом выпуклости, тогда
hvn+1 ; vn; v ; uni ; jvn+1 ; unj2 + 12 (L)2 jun ; vnj2 + 2 ((v ; v ) ; (un; un )) 0:
Второе слагаемое jvn+1 ; un j2 преобразуем с помощью тождества (3.9), а последнее оценим с
помощью (5.1)
jun ; v j + jvn+1 ; vn j2 + 2hvn+1 ; vn; vn ; uni + djun ; vnj2 hvn+1 ; vn ; v ; uni;
2
где d = 1 ; 21 (L)2 > 0, т.к. < 1=L.
Из третьего и четвертого слагаемых выделим полный квадрат
jun ; vj + p1 (vn+1 ; vn) + pd(vn ; un)2 + 1 ; 1 jvn+1 ; vn j2 hvn+1 ; vn ; v ; uni:
2
d
d
Отсюда
jun ; v j jvn+1 ; vn j jv ; unj + 1 ; 1jvn+1 ; vn j2:
2
d
Предполагая, что jun ; v j 6= 0 для всех n, получаем
jvn+1 ; vn j + 1 1 ; 1 jvn+1 ; vn j2 :
(5.3)
2
2 d
jun ; vj
12
Заметим, что неравенство (4.3) в условиях теоремы также справедливо. Поэтому в силу (4.3) и
используя оценку (4.5) имеем jvn+1 ; v j2 + d2 jvn+1 ; vn j2 jvn ; v j2 . Отсюда
(jvn+1 ; v j ; jvn ; v j)(jvn+1 ; v j + jvn ; v j) + d2 jvn+1 ; vn j2 0:
Разделим левую и правую части этого неравенства на величину (jvn+1 ; v j + jvn ; v j) и затем,
учитывая монотонность jvn+1 ; v j jvn ; v j, получим
n+1
n2
jvn+1 ; v j ; jvn ; v j + d4 jvjvn ;;vv jj 0:
(5.4)
N
k+1
k2
X
jvN +1 ; vj2 + d4 jvjvk ;;vvjj jv0 ; vj2 :
(5.5)
Просуммируем (5.4) от n = 0 до n = N
k=0
Из (5.5) следует
Таким образом,
1
X
jvk+1 ; vk j2 1:
k
k=0 jv ; v j
jvn+1 ; vn j2=jvn ; vj ! 0 при n ! 1:
Используя неравенство треугольника, получаем
jv+1 ; vnj2
jvn+1 ; vnj2 ! 0 при n ! 1:
jvn ; unj + jun ; v j jvn ; vj
(5.6)
С учетом (4.4) отсюда имеем
jvn+1 ; vnj2 =jun ; v j ! 0 при n ! 1:
(5.7)
Действительно, если это не так, то существует подпоследовательность vni такая, что jvni +1 ;
vni j2=juni ; v j a > 0 для всех ni ! 1. Так как jvni ; uni j ! 0, ni ! 1, то всегда можно
выбрать такой номер ni0 , что для всех ni ni0 выполняется оценка jvni0 +1 ; vni0 j2 =(jvni0 ; uni0 j +
juni0 ; v j) 12 a > 0. Но это противоречит (5.6).
Возвращаясь к неравенству (5.3), видим, что правая часть этого неравенства согласно (4.6)
и (5.7) с ростом номера n стремится к нулю, с другой стороны, эта правая часть ограничена
величиной =2 для всех n ! 1. Выход из этого противоречия состоит в том, что утверждение
jun ; vj 6= 0 для всех n неверно, поэтому существует такой номер nf , что unf = v 2 .
6. Сходимость со скоростью геометрической прогрессии
В этом разделе будем предполагать, что функция (v; v) на диагонали квадрата имеет
квадратичный порядок остроты минимума, т.е.
(v; v) ; (v ; v ) jv ; v j2 8w 2 ;
(6.1)
где 0 константа [9]. Квадратичная функция вида (v; v) = hAv ; b; Av ; vi с невырожденной
матрицей A и вектором b 2 Rn удовлетворяют этому условию [1].
Покажем, что градиентный метод может сходиться со скоростью геометрической прогрессии
к минимуму функции, которая не является сильно выпуклой, но имеет квадратичный порядок
остроты минимума.
13
Теорема 4. Если множество решений задачи (1.1) не пусто и удовлетворяет условию
(6.1), целевая функция (v; w) | симметричная, выпуклая на диагонали квадрата и
дифференцируема, причем ее градиент удовлетворяет условию Липшица (3.5), | выпуклое
замкнутое множество, то последовательность vn , порожденная методом (3.4) с параметром
0 < < 1=L, сходится к минимуму (v; v) на со скоростью геометрической прогрессии, т.е.
jvn+1 ; vj2 q()n+1 jv0 ; v j2 при n ! 1;
где q() = 1 + ( )2 =d1 ; < 1, d1 = 1 + ; (L)2 .
Если дополнительно к перечисленным условиям функция (v; w) выпукла по w при любом
v 2 , то метод сходится к равновесному решению со скоростью геометрической прогрессии.
Доказательство. Используя соотношения (3.9) и (3.5), (3.6), а также (2.12), представим
неравенство (5.2) в форме
jvn ; vj2 ; jvn+1 ; vj2 ; jvn+1 ; unj2 ; jun ; vn j2 +
+ (L)2 jun ; vn j2 + ((v ; v ) ; (un ; un )) 0:
Отсюда с учетом (6.1)
jvn+1 ; vj2 + jvn+1 ; unj2 + djun ; vn j2 + jun ; vj2 jvn ; vj2 ;
(6.2)
2
где d = 1 ; (L) > 0, т.к. 0 < < 1=L. С помощью тождества
jun ; vj2 = jun ; vnj2 + 2hun ; vn; vn ; vi + jvn ; v j2
преобразуем (6.2)
jvn+1 ; vj2 + jvn+1 ; unj2 + djun ; vnj2 + jun ; vn j2 +
+ 2 hun ; vn ; vn ; v i + jvn ; v j2 jvn ; v j2
или
jvn+1 ; vj2 + jvn+1 ; unj2 + d1 jun ; vnj2 + 2 hun ; vn ; vn ; v i (1 ; )jvn ; vj2 ;
где d1 = 1 + ; 2 L. Из третьего и четвертого слагаемых выделим полный квадрат
p
2
jvn+1 ; vj2 + jvn+1 ; unj2 + d1(un ; vn) + pd (vn ; v) ;
1
)2 jvn ; v j (1 ; )jvn ; v j2 :
; (
d1
Отсюда
jvn+1 ; vj2 [1 + ( )2 =d1 ; ]jvn ; v j2:
Поскольку < 1=L, то величина q() = 1 + ( )2 =d1 ; < 1.
Таким образом,
откуда
jvn+1 ; v j2 q()jvn ; v j2;
jvn+1 ; v j2 q()n+1 jv0 ; vj2 :
Знаменатель прогрессии q() зависит от параметра . Минимизируя его на отрезке (0; 1=L),
можно выбрать наилучшее значение знаменателя прогрессии.
Таким образом, доказано, что в случае симметричных экстремальных отображений градиентный метод прогнозного типа сходится:
| к множеству стационарных решений в невыпуклом случае,
| монотонно по норме к одной из неподвижных точек в выпуклом случае,
| за конечное число шагов к острому равновесию,
14
| со скоростью геометрической прогрессии к квадратичному равновесию.
Литература
1. Антипин А.С. О сходимости и оценках скорости сходимости проксимальных методов к неподвижным точкам экстремальных отображений // Журн. вычисл. матем. и матем. физ.
{ 1995. { Т.35. { Є 5. { С.688{704.
2. Антипин А.С. Вычисление неподвижных точек экстремальных отображений с помощью
методов градиентного типа // Журн. вычисл. матем. и матем. физ. { 1997. { Т.37. { Є 1. {
С. 42{53.
3. Антипин А.С. О дифференциальных градиентных методах прогнозного типа для вычисления
неподвижных точек экстремальных отображений // Дифференц. уравнения. { 1995. { Т.31.
{ Є 11. { С.1786{1795.
4. Васильев Ф.П. Численные методы решения экстремальных задач. { М.: Наука, 1988. { 549 с.
5. Антипин А.С. Седловые градиентные процессы, управляемые с помощью обратных связей //
Автоматика и телемеханика. { 1994. { Є 3. { С.12{23.
6. Monderer D., Shapley L.S. Potential games // Games and economic behavior. { 1996. { Є 14. {
C.124{143.
7. Корпелевич Г.М. Экстраградиентный метод для отыскания седловых точек и других задач
// Экономика и матем. методы. { 1976. { Т.12. { Є 4. { С.747{756.
8. Антипин А.С. Об одном методе поиска седловых точек модифицированной функции Лагранжа // Экономика и матем. методы. { 1977. { Т.13. { Є 3. { С.560{565.
9. Поляк Б.Т. Введение в оптимизацию. { М.: 1973. { 382 с.
Вычислительный Центр
Российской Академии Наук
Поступила
27.01.1997
15
Документ
Категория
Без категории
Просмотров
6
Размер файла
207 Кб
Теги
симметричные, вычисления, экстремальных, точек, отображений, неподвижную
1/--страниц
Пожаловаться на содержимое документа