<<

стр. 3
(всего 4)

СОДЕРЖАНИЕ

>>

xk = PX (?k ? ?(F (?k ) + ?k xk )) ?? > 0.
? x x ?
xk ? xk > 0 при k > ?. В самом деле, по лемме 3.1
Покажем, что ?
xk+1 ? xk+1 ? xk+1 ? xk + xk ? xk+1 ?
? ? ? ?
? xk+1 ? xk + x (?k ? ?k+1 )/?k ,
? ?
где x — нормальное решение V I(X, F ). По лемме 3.2 и свойствам операции проек-
?
тирования
xk+1 ? xk =
?
= PX (xk ? ?k (F (xk ) + ?k xk )) ? PX (?k ? ?k (F (?k ?) + ?k xk )) ?
x x ?
? xk ? ?k (F (xk ) + ?k xk ) ? xk + ?k (F (?k ) + ?k xk ) ?
? x ?
? (1 ? r(?k , ?k )) xk ? xk .
?
В итоге
?k ? ?k+1
xk+1 ? xk+1 ? (1 ? r(?k , ?k )) xk ? xk +
? ? x.
?
?k
Остается воспользоваться леммой 3.3 и предположениями (3.6), (3.7) относительно
параметров шага и регуляризации.
Класс последовательностей, для которых условия приведенной теоремы верны,
достаточно широк. В частности, в него входят последовательности вида ?k = (1 +
k)?1/2 , ?k = (1 + k)?1/3 .
Альтернативой методу регуляризации с его сложными правилами согласования
шаговых параметров может служить экстраполяционный метод проекции, в кото-
ром в процесс вычислений вовлечены сразу две последовательности. Одна из них

50
является основной, а вторая играет роль своеобразного поводыря. Рекуррентные со-
отношения экстраполяционного метода имеют вид

xk+1 = PX (xk ? ?F (?k )), xk = PX (xk ? ?F (xk )),
x ?
(3.8)
где k = 0, 1, 2, . . . ,

здесь xk — точки основной последовательности; xk — точки вспомогательной после-
?
довательности; x0 ? X — произвольное начальное приближение; PX (·) — операция
проектирования на множество X; ? > 0 — параметр.
Условия сходимости экстраполяционного метода дает
Теорема 3.4. Пусть X — непустое выпуклое замкнутое подмножество Rn ,
отображение F монотонно и удовлетворяет на X условию Липшица с кон-
стантой L, т. е.
F (x) ? F (y) ? L x ? y ?x, y ? X.
Если задача V I(X, F ) разрешима и 0 < ? < 1/L, обе последовательности из
(3.8) сходятся к одному из ее решений.
Д о к а з а т е л ь с т в о. Пусть x — произвольное решение V I(X, F ). Восполь-
?
зуемся свойством операции проектирования:
2 2 2
?u ? Rn ,
u?v ? u ? PX (u) + v ? PX (u) ?v ? X.
Подставляя сюда v = x, u = xk ? ?F (?k ) и учитывая (3.8), получаем неравенство
? x
xk+1 ? x 2
? xk ? ?F (?k ) ? x 2
? xk ? ?F (?k ) ? xk+1 2
? x ? x =
= xk ? x 2
? xk ? xk+1 2
+ 2?F (?k ) (? ? xk+1 ).
? x x
Поскольку x — решение V I(X, F ), то последнее слагаемое можно оценить так:
?
F (?k ) (? ? xk+1 ) = F (?k ) (? ? xk ) + F (?k ) (?k ? xk+1 ) ?
x x x x? x x
? F (?k ) (?k ? xk+1 ).
x x
С учетом этого продолжим основную цепочку:
xk+1 ? x 2
? xk ? x 2
? xk ? xk+1 2
+ 2?F (?k ) (?k ? xk+1 ) =
? ? x x
= xk ? x 2
? xk ? xk 2
? xk ? xk+1 2 ?
? ? ?
?2(xk ? xk ) (?k ? xk+1 ) + 2?F (?k ) (?k ? xk+1 ) =
? x x x
= xk ? x 2
? xk ? xk 2
? xk ? xk+1 2 +
? ? ?
+2(xk ? ?F (?k ) ? xk ) (xk+1 ? xk ).
x ? ?
Вновь обратимся к последнему слагаемому. Разложим его на сумму двух других
слагаемых, одно из которых по свойствам операции проектирования неположительно,
а другое оценивается сверху неравенством Коши—Буняковского:
(xk ? ?F (?k ) ? xk ) (xk+1 ? xk ) =
x ? ?
= (xk ? ?F (xk ) ? xk ) (xk+1 ? xk ) + ?(F (xk ) ? F (?k )) (xk+1 ? xk ) ?
? ? x ?
? ? F (xk ) ? F (?k ) · xk+1 ? xk .
x ?

51
Кроме того,
xk ? xk 2
+ xk ? xk+1 2
? 2 xk ? xk · xk ? xk+1 .
? ? ? ?
Возвращаясь к основной цепочке неравенств, ввиду липшицевости F, имеем
xk+1 ? x 2
? xk ? x 2
? xk ? xk 2
? xk ? xk+1 2 +
? ? ? ?
+2?L xk ? xk · xk+1 ? xk ? xk ? x 2
? xk ? xk 2
? xk ? xk+1 2 +
? ? ? ? ?
+?2 L2 xk ? xk 2
+ xk+1 ? xk 2 .
? ?
В итоге
xk+1 ? x 2
? xk ? x 2
? (1 ? ?2 L2 ) xk ? xk 2 . (3.9)
? ? ?
А так как по предположению 1??2 L2 > 0, то из (3.9) следует, что xk ? xk > 0 при
?
k
k > ? и что последовательность x ? x — невозрастающая, а значит, ограничена
?
и имеет предельные точки. Пусть x — одна из таких предельных точек. Поскольку
?
xk = PX (xk ? ?F (xk )) ?k
?
и xk ? xk > 0, то, переходя в последнем равенстве к пределу по сходящейся
?
подпоследовательности, получаем
x = PX (? ? ?F (?)),
? x x
т. е. x — решение задачи V I(X, F ). Отождествляя x с x из оценки (3.9), получаем
? ??
сходимость к x всей последовательности {xk }, а значит, и {?k }.
? x
Рассмотренная экстраполяционная вычислительная схема не является единствен-
но возможной. В частности, на каждой итерации можно использовать одно и то же
направление спуска, что уменьшает вычислительные затраты метода. Модифициро-
ванная схема вычислений имеет вид
xk+1 = PX (xk ? ?F (?k )), xk+1 = PX (xk+1 ? ?F (?k )),
x ? x
(3.10)
где k = 0, 1, 2, . . . ,

здесь xk — точки основной последовательности; xk — точки вспомогательной по-
?
0 0
следовательности; x , x ? X — произвольные начальные приближения; PX (·) —
?
операция проектирования на множество X; ? > 0 — параметр.
Приведем без доказательства условия сходимости модифицированной схемы.
Теорема 3.5. Пусть X — непустое выпуклое замкнутое подмножество Rn ,
отображение F монотонно и удовлетворяет на X условию Липшица с кон-
стантой L. Если задача V I(X, F ) разрешима и 0 < ? < 1/3L, обе последова-
тельности из (3.10) сходятся к одному из ее решений.
Заметим, что технику ведущей точки (поводыря) можно использовать и при ра-
боте с сильно монотонными отображениями. Сходимость метода от этого только
выигрывает.

§ 4. Методы решения второго порядка

Рассматриваемые ниже методы второго порядка решения вариационных нера-
венств и нелинейных задач о дополнительности привлекают своей квадратичной ско-
ростью сходимости, но требуют повышенной гладкости отображений, более сложны

52
в реализации и сходятся, вообще говоря, лишь локально (начальное приближение
должно быть близко к искомому решению задачи).
Общая схема методов второго порядка имеет вид
xk+1 ? Arg V I(X, F k ), (4.1)
k = 0, 1, 2, . . . ,
где F k (x) = F (xk ) + A(xk ) (x ? xk ) — линейная аппроксимация F (x) в точке xk ;
A(xk ) — (n ? n) -матрица. Существует множество конкретных реализаций общей
схемы, различающихся выбором A(xk ) :
A(xk ) = F (xk ) — метод Ньютона,
A(xk ) ? F (xk ) — квазиньютоновские методы,
A(xk ) = D(xk ) — линеаризованный метод Якоби
и др. Здесь D(xk ) — диагональная часть якобиана F (xk ).
Приведем несколько теорем, обосновывающих сходимость методов второго поряд-
ка.
Теорема 4.1. Пусть X — непустое выпуклое замкнутое подмножество Rn и
отображения F и A непрерывны. Пусть x — решение V I(X, F ). Если существу-
?
ют такие ? > ? > 0, что матрица A(?) ? ?E положительно полуопределена и
x
для всех x, y из некоторой окрестности N1 точки x выполнены неравенства
?
F (x) ? F (y) ? A(y) (x ? y) ? b x ? y , (4.2)
то при условии близости начального приближения x0 к x процесс (4.1) опреде-
?
лен и сходится к x.
?
Д о к а з а т е л ь с т в о. Как следует из условия, матрица A(?) положительно
x
определена, и, ввиду непрерывности A, существует окрестность N2 точки x такая,
?
что A(y) положительно определена при всех y ? N2 . Отсюда следует, что задача
V I(X, F y ), где F y (x) = F (y)+A(y)(x?y), разрешима и имеет единственное решение
при всех y ? N2 .
Выберем ? > 0 такое, что 0 < r = b/(? ? ?) < 1. Пусть N3 — окрестность точки
x, в которой
?
A(?) ? A(y) ? ? ?y ? N3 .
x
3
Ni . Пусть x0 ? N.
· . Возьмем N =
Все окрестности определены относительно
i=1
1 0
Тогда x — решение V I(X, F ) — существует и единственно. Оно удовлетворяет
неравенству
(? ? x1 ) (F (x0 ) + A(x0 ) (x1 ? x0 )) ? 0,
x
так как x ? X. Аналогично, так как x — решение исходной задачи и x1 ? X,
? ?
(x1 ? x) F (?) ? 0.
? x
Складывая эти два неравенства и перегруппировывая слагаемые, получаем
(x1 ? x) A(x0 )(x1 ? x) ? (x1 ? x) (F (?) ? F (x0 ) ? A(x0 ) (? ? x0 )).
? ? ? x x
Оценим левую часть этого неравенства:
(x1 ? x) A(x0 ) (x1 ? x) = (x1 ? x) A(?) (x1 ? x)+
? ? ? x ?

53
+(x1 ? x) (A(x0 ) ? A(?)) (x1 ? x) ? ? x1 ? x 2
? ? x1 ? x 2
? x ? ? ? =
= (? ? ?) x1 ? x 2 .
?
Теперь оценим правую часть:
(x1 ? x) (F (?) ? F (x0 ) ? A(x0 ) (? ? x0 )) ?
? x x
? x1 ? x · F (?) ? F (x0 ) ? A(x0 ) (? ? x0 ) ? b x ? x0 · x1 ? x .
? x x ? ?
В итоге получаем, что
x1 ? x ? r x ? x0 .
? ?
По определению r приближение x1 остается в окрестности N. Поэтому мы
можем повторить все рассуждения и установить, что
xk+1 ? x ? r xk ? x ?k.
? ?
Это и означает сходимость {xk } к x, так как r < 1.
?
Теорема 4.1 сформулирована в весьма общих предположениях. Приведем более
конкретные условия, обеспечивающие неравенство (4.2).
Следствие 4.1. Пусть X, F, A и x — те же, что и в теореме 4.1, причем отоб-
?
ражение F непрерывно дифференцируемо в окрестности x. Если существует
?
? > 0 такое, что матрица A(?) ? ?E положительно полуопределена и в неко-
x
торой окрестности N точки x выполнены неравенства
?
A(x) ? F (x) ? ? < ? ?x ? N, (4.3)
то заключение теоремы 4.1 верно.
Д о к а з а т е л ь с т в о. По теореме о среднем
F (x) ? F (y) ? A(y) (x ? y) = (B(x, y) ? A(y)) (x ? y) =
= (B(x, y) ? F (y)) (x ? y) + ( F (y) ? A(y)) (x ? y),
Fi (x + ti (y ? x)) при некоторых
где B(x, y) — матрица, строки которой есть
ti ? (0, 1). В силу (4.3) и непрерывной дифференцируемости F, отсюда вытекает
условие (4.2) теоремы 4.1.
Преимуществом методов второго порядка является то, что при определенных пред-
положениях они демонстрируют квадратичную скорость сходимости. Пример таких
предположений дает следующая теорема.
Теорема 4.2. Пусть X, F, x — те же, что и в теореме 4.1, причем отображе-
?
ние F непрерывно дифференцируемо, а матрица F (?) положительно определе-
x
на. Тогда существует окрестность точки x такая, что если точка x0 выбрана
?
из N, то последовательность (4.1) при A(x) = F (x) определена и сходится
к x. Более того, если F (x) локально удовлетворяет условию Липшица, т. е.
?
существует L > 0 такое, что
F (x) ? F (y) ? L x ? y ?x, y ? N,
то при некотром > 0 имеем
xk+1 ? x ? xk ? x 2
?k,
? ?
что и означает квадратичную скорость сходимости процесса.

54
Д о к а з а т е л ь с т в о. При доказательстве теоремы 4.1 нами было получено
неравенство
?(1 ? ?) xk+1 ? x 2
? (xk+1 ? x) (F (?) ? F (xk ) ? F (xk ) (? ? xk )),
? ? x x
где ? = min y F (?)y > 0, ? — некоторая величина, меньшая 1. Отсюда, по
x
y =1
теореме о среднем, вытекает оценка
?(1 ? ?) xk+1 ? x ?
?
F (xk + t(? ? xk )) ? F (xk ) · xk ? x ? L xk ? x 2 .
? sup x ? ?
0?t?1

Из нее мы и заключаем, что скорость сходимости процесса (4.1) квадратичная с
= L[?(1 ? ?)]?1 .
Заметим, что каждый шаг методов второго порядка требует решения вспомога-
тельного вариационного неравенства. Если текущее приближение близко к решению
F (?) положительно определен, отображение F k вспомогательной за-
и якобиан x
дачи сильно монотонно. Таким образом, для ее решения можно опираться на рас-
смотренные ранее проекционные методы.

§ 5. Проксимальное отображение и его свойства

Пусть X — непустое замкнутое выпуклое подмножество Rn , F — непрерывное
и монотонное отображение X в Rn . Отображение, любому y ? Rn ставящее в
соответствие вектор x(y) ? X такой, что
( F (x(y)) + x(y) ? y ) (x ? x(y)) ? 0 ?x ? X, (5.1)
называется (относительно F) и обозначается через
проксимальным
n
RF (·) : R > X.
Теорема 5.1. Пусть X — непустое замкнутое выпуклое подмножество Rn ,
F — непрерывное и монотонное отображение X в Rn . Тогда проксимальное
отображение RF определено и однозначно на всем Rn .
Д о к а з а т е л ь с т в о вытекает из сильной монотонности отображения в
задаче (5.1).
Изучим свойства проксимального отображения.
Теорема 5.2. Проксимальное отображение является монотонным и нерасши-
ряющим, т. е.
?x, y ? Rn .
RF (x) ? RF (y) ? x ? y
Д о к а з а т е л ь с т в о. Пусть x, y ? Rn . По определению проксимального
отображения
( F (RF (x)) + RF (x) ? x ) (u ? RF (x)) ? 0 ?u ? X,
( F (RF (y)) + RF (y) ? y ) (v ? RF (y)) ? 0 ?v ? X.
Подставим сюда u = RF (y), v = RF (x) и сложим полученное. После перегруппи-
ровки слагаемых, ввиду монотонности F, получаем
(RF (x) ? RF (y)) (x ? y) ? RF (x) ? RF (y) 2 +

55
+(F (RF (x)) ? F (RF (y))) (RF (x) ? RF (y)) ?
? RF (x) ? RF (y) 2 .
Отсюда сразу следует монотонность проксимального отображения, а также его нерас-
ширяемость, поскольку левая часть последнего неравенства оценивается как
(RF (x) ? RF (y)) (x ? y) ? RF (x) ? RF (y) · x ? y .
Утверждение доказано.
Заметим, что из свойства нерасширяемости проксимального отображения следует
его непрерывность.
Теорема 5.3. Пусть X — непустое замкнутое выпуклое подмножество Rn ,
F — непрерывное и монотонное отображение X в Rn . Если задача V I(X, F )
разрешима и x — ее решение, то x — неподвижная точка проксимального
? ?
отображения RF .
Д о к а з а т е л ь с т в о. Достаточно подставить x в неравенство (5.1) вместо
?
y и убедиться, что оно выполняется при x(y) = x.
?
Рассмотрим итерационный процесс, порождаемый проксимальным отображением,
а именно пусть
xk+1 = RF (xk ), k = 0, 1, 2, . . . , x0 ? Rn ; (5.2)
здесь x0 ? X — произвольная начальная точка. Процесс представляет собой метод
простой итерации для нахождения неподвижной точки проксимального отображения.
Хотя последнее не обязательно сжимающее, верна
Теорема 5.4. Пусть X — непустое выпуклое замкнутое множество, отобра-
жение F : X > Rn непрерывно и монотонно. Тогда процесс (5.2) сходится к x
?
— некоторому решению V I(X, F ), если только последние существуют.
Д о к а з а т е л ь с т в о. По построению [см.(5.1), (5.2)]
( F (xk+1 ) + xk+1 ? xk ) (x ? xk+1 ) ? 0 ?x ? X.
Это значит, что hk+1 = ?F (xk+1 ) + xk ? xk+1 ? NX (xk+1 ) при всех k. Отсюда
xk = xk+1 + F (xk+1 ) + hk+1 , и если x — произвольное решение V I(X, F ), то
?

xk ? x 2
= xk+1 ? x 2
+ F (xk+1 ) + hk+1 2 +
? ?
+2(F (xk+1 ) + hk+1 ) (xk+1 ? x) ?
?
(5.3)
? xk+1 ? x 2
+ F (xk+1 ) + hk+1 2
+ 2(F (?), xk+1 ? x) ?
? x ?
? xk+1 ? x 2
+ F (xk+1 ) + hk+1 2 ;
?

здесь использовались монотонность F, включение hk+1 ? NX (xk+1 ) и то, что x —
?
решение V I(X, F ).
Неравенство (5.3) устанавливает монотонное убывание xk ? x по k и сходи-
?
k k k k+1
мость к нулю F (x ) + h , т. е. x ? x > 0. Ограниченность последова-
k
тельности {x } влечет существование хотя бы одной ее предельной точки x ? X.
?
Предельным переходом по сходящейся подпоследовательности в (5.1) получаем, что
F (?) (x ? x) ? 0 ?x ? X,
x ?

56
т. е. x — решение V I(X, F ). Отождествляя x с x из (5.3), получаем монотонную
? ? ?
k
сходимость к x всей последовательности {x }.
?
Заметим, что итерационный процесс (5.2) относится к разряду двухуровневых:
на каждой его итерации нужно решить вспомогательное вариационное неравенство,
требующее своего, вообще говоря, бесконечного вычислительного процесса. Как и в
методах второго порядка, мы опускаем здесь анализ влияния погрешности решения
вспомогательной подзадачи на сходимость основного процесса.

§ 6. Метод оценочных функций

Пусть дано множество C ? Rn . Оценочной функцией, или функцией оценки
задачи V I(X, F ) (соответственно N CP (F ) ), называется неотрицательная функция
M : C > R, удовлетворяющая условию: точка x будет решением V I(X, F ) (соот-
?
ветственно N CP (F ) ) в том и только в том случае, когда x ? C и M (?) = 0, т. е.
? x
когда точки глобального оптимума задачи

min{ M (x) : x ? C } (6.1)
совпадают с решениями V I(X, F ) (N CP (F )) в предположении разрешимости по-
следней.
Построить функцию оценки не так сложно. Например, для задачи N CP (F ) та-
кой функцией является функция M (x) = F (x) x, неотрицательная на C = {x :
F (x) ? 0, x ? 0}, а для задачи V I(X, F ) — обычная функция скачка g(x) =
max F (x) (y ? x), заданная на C = X. Соответствующие теоремы эквивалентности
y?X
были приведены в главе 2 §1, 2.
Гораздо сложнее построить оценочную функцию, которая обладала бы рядом
свойств, полезных в вычислительном отношении. В частности, только что приведен-
ные в качестве примера функции такими свойствами не обладают, — уже отмеча-
лось, что g(x), вообще говоря, не является гладкой и даже не имеет конструктивно
очерченной области определения; вторая из приведенных функций, хотя и может
считаться гладкой, порождает задачу, найти точки глобального оптимума которой
достаточно сложно.
Свойства, которые выглядят привлекательно с вычислительной точки зрения, та-
ковы:
— M является гладкой функцией;
— любая ее стационарная относительно C точка является точкой глобального
минимума в (6.1);
— множества уровня L(?) = {x ? C : M (x) ? ?} ограничены
и т.п.
Рассмотрим некоторые из известных оценочных функций, обладающих перечис-
ленными свойствами.
Пусть имеется задача V I(X, F ), где X — непустое выпуклое замкнутое под-
множество Rn , отображение F : X > Rn непрерывно. При этих предположениях
множество решений V I(X, F ) совпадает, как уже отмечалось выше, с множеством
неподвижных точек отображения
H(x) = PX (x ? ?F (x)), ? > 0.



57
Нетрудно видеть, что точка y = H(x) будет единственным решением задачи
?
1
y ? x 2.
min ?(y), где ?(y) = F (x) (y ? x) + (6.2)
2?
y?X

В самом деле, функция ?(y) выпукла и дифференцируема, а ее градиент ?(y) =
1
F (x) + ? (y ? x), вычисленный в точке y = H(x), удовлетворяет условиям
?

?(?) (y ? y ) ? 0 ?y ? X.
y ?
Очевидно, что оптимальное значение задачи (6.2) не положительно.
Теперь мы подготовлены к описанию свойств функции оценки, называемой функ-
цией Фукушимы. Она определена формулой
1
H(x) ? x 2 .
M0 (x) = ?F (x) (F (x) ? x) ? (6.3)
2?
Эта функция задана при всех x ? X и принимает на X неотрицательные значения,
так как отличается от оптимального значения задачи (6.2) только знаком.
Рассмотрим задачу
min{ M0 (x) : x ? X }. (6.4)
Следующая теорема устанавливает эквивалентность этой задачи задаче решения
вариационного неравенства V I(X, F ).

Теорема 6.1. Пусть функция M0 (x) определена в соответствии с (6.3). Тогда
M0 (x) ? 0 при всех x ? X и M0 (x) = 0 тогда и только тогда, когда x —
решение задачи V I(X, F ).

Д о к а з а т е л ь с т в о. Функцию M0 (x) можно переписать в виде
1 2 2
? H(x) ? x + ?F (x)
M0 (x) = ?F (x) .
2?
Так как ?F (x) совпадает с расстоянием между x и x??F (x), а H(x)?x+?F (x)
— с расстоянием между x ? ?F (x) и проекцией этой точки на X, то M0 (x) ? 0
при всех x ? X. Более того, определение H(x) подразумевает, что эти расстояния
равны, только если x = H(x). Последнее имеет место в случае, когда x — решение
задачи V I(X, F ).
Заметим, что в случае X = Rn , т. е. когда задача V I(X, F ) превращается в
+
задачу о дополнительности N CP (F ), функция Фукушимы приобретает форму
1
( (x ? ?F (x))+ 2
? x 2 ).
M0 (x) = F (x) x +
2?
(x ? ?F (x))+ (x ? ?F (x)) H(x)
В самом деле, здесь и
H(x) = =
= H(x) 2 . Поэтому
1
H(x) ? x 2 =
?F (x) H(x) ?
2?
1
= ?F (x) (x ? ?F (x))+ ? (x ? ?F (x))+ ? x 2 =
2?
1 1 1
= (x ? ?F (x)) (x ? ?F (x))+ ? (x ? ?F (x))+ 2 ? 2
x =
? 2? 2?

58
1 1
(x ? ?F (x))+ 2 ? x 2.
=
2? 2?
Теорема 6.1 не накладывает особых условий на то, какими должны быть отобра-
жение F и функция M0 . Однако практические соображения требуют, чтобы послед-
няя обладала рядом полезных вычислительных свойств. К счастью, оказывается, что
если X — непустое выпуклое замкнутое множество, то функция M0 непрерывно
дифференцируема, если дифференцируемо отображение F.
Теорема 6.2. Если отображение F непрерывно, а множество X непусто, вы-
пукло и замкнуто, то функция M0 , определяемая соотношениями (6.3), непре-
рывна также. Далее, если отображение F непрерывно дифференцируемо, то
функция M0 также непрерывно дифференцируема и ее градиент равен
1
M0 (x) = F (x) ? F (x) ? E (H(x) ? x). (6.5)
?
Д о к а з а т е л ь с т в о. Если отображение F непрерывно, функция M0 непре-
рывна как суперпозиция непрерывных функций. Чтобы доказать вторую часть утвер-
ждения, рассмотрим функцию
n
h : R ? X > R, определенную формулой
1
y ? x 2.
h(x, y) = F (x) (y ? x) +
2?
Если отображение F — непрерывно дифференцируемо, функция h также будет
непрерывно дифференцируемой по x и ее градиент равен
1
x g(x, y) = F (x) ? ( F (x) ? E)(y ? x). (6.6)
?
По определению
M0 (x) = ? min h(x, y),
y?X

причем минимум достигается в единственной точке y = H(x). В соответствии с
?
классическими теоремами о производных функции оптимума параметрических задач
оптимизации это обеспечивает дифференцируемость M0 и равенство
M0 (x) = ? x h(x, H(x)).
Формула (6.5) следует отсюда с учетом (6.6).
Взглянем на связь задачи (6.4) с задачей решения вариационного неравенства
V I(X, F ) более пристально. Теорема 6.1 говорит, что решение V I(X, F ) сводится к
отысканию точек глобального оптимума в (6.4). Но поскольку функция M0 , вообще
говоря, не выпукла, задача (6.4) может иметь точки локального минимума и ста-
ционарные точки, которые не являются точками глобального минимума. К счастью,
перечисленные трудности исчезают в случае, когда отображение F непрерывно диф-
F (x) положительно определена при всех x ? X, т. е.
ференцируемо и матрица
F (x)y > 0 ?y ? Rn , ?x ? X.
y
Теорема 6.3. Пусть X — непустое выпуклое замкнутое подмножество Rn ,
отображение F : Rn > Rn непрерывно дифференцируемо и матрица Якоби
F (x) положительно определена при всех x ? X. Если x — стационарная
?
точка в задаче (6.4), т. е.
M0 (?) (y ? x) ? 0 ?y ? X, (6.7)
x ?

59
то она является также точкой ее глобального оптимума и, следовательно, ре-
шением задачи V I(X, F ).
Д о к а з а т е л ь с т в о. Пусть x удовлетворяет условиям (6.7). Подставляя
?
в эти условия формулу (6.6) и полагая y = H(?), получаем после перегруппировки
x
слагаемых, что
1
F (?) + (H(?) ? x) (H(?) ? x) ? (H(?) ? x) F (?) (H(?) ? x).
x x ? x ? x ? x x ?
?
Левая часть этого неравенства неположительна. Это следует из соотношения
(? ? ?F (?) ? H(?)) (y ? H(?)) ? 0 ?y ? X,
x x x x
которому H(?) удовлетворяет как проекция точки x??F (?) на выпуклое множество
x ? x
X. Полагая здесь y = x, получаем искомое неравенство
?
1
F (?) + ? (H(?) ? x) (H(?) ? x) =
x x ? x ?

1?
= ? x ? ?F (?) ? H(?) (? ? H(?)) ? 0.
x x x x

Таким образом, (H(?) ? x) F (?) (H(?) ? x) ? 0, что, в силу положительной
x ? x x ?
определенности матрицы Якоби, влечет равенство x ?H(?) = 0, т. е. x действитель-
? x ?
но оказывается решением V I(X, F ), а значит, по теореме 6.1 и точкой глобального
оптимума в задаче (6.4).
Пусть X — непустое выпуклое замкнутое подмножество Rn , отображение F :
Rn > Rn непрерывно дифференцируемо. По теореме 6.2 целевая функция M0 за-
дачи (6.4) также непрерывно дифференцируема и ее градиент может быть найден
из (6.5). Поэтому для решения задачи (6.4) можно применять любой из существую-
щих алгоритмов градиентного типа. Ниже, однако, мы остановимся на возможности
использования в качестве направления спуска вектора
d = H(x) ? x = PX (x ? ?F (x)) ? x, (6.8)
? > 0.
Поскольку соотношение (6.8) не содержит F (x), вектор d может быть опреде-
лен с гораздо меньшими вычислительными затратами по сравнению с градиентным
направлением M0 , особенно в случаях, когда вычисление матрицы F затруд-
нено. Следующее утверждение показывает, что при условии монотонности F вектор
d, задаваемый соотношениями (6.8), действительно является направлением спуска
функции M0 в точке x.
Теорема 6.4. Пусть X — непустое выпуклое замкнутое подмножество Rn ,
отображение F : Rn > Rn непрерывно дифференцируемо и матрица Якоби
F (x) положительно определена при всех x ? X. Тогда при любом x ? X
вектор d = H(x) ? x удовлетворяет условию
(6.9)
M0 (x) d < 0,
если только d = 0. Более того, если отображение F сильно монотонно на X с
константой ? > 0, т. е.
2
(F (x) ? F (y)) (x ? y) ? ? x ? y
при всех x, y ? X, то при всех x ? X также
M0 (x) d < ?? d 2 . (6.10)

60
Д о к а з а т е л ь с т в о. Из (6.6) и (6.8) вытекает, что
1
(H(x) ? x) (H(x) ? x)?
M0 (x) d = F (x) +
?
? (H(x) ? x) F (x) (H(x) ? x). (6.11)
Но поскольку H(x) = PX (x ? ?F (x)), то
(x ? ?F (x) ? H(x)) (y ? H(x)) ? 0 ?y ? X.
Отсюда
1
(H(x) ? x)) (H(x) ? x) ? 0. (6.12)
(F (x) +
?
Комбинируя (6.12) и (6.11), получаем
M0 (x) d ? ?(H(x) ? x) F (x) (H(x) ? x) = ?d F (x)d.
Таким образом, если матрица Якоби F (x) положительно определена, то M0 (x) d <
0 при d = 0. Если же отображение F сильно монотонно с константой ? > 0, то
F d ? ? d 2.
условие (6.10) просто следует из того, что d
Следующая теорема устанавливает глобальную сходимость алгоритма, использу-
ющего направление спуска d = H(x)?x вкупе с точным правилом линейного поиска.
Теорема 6.5. Пусть {xk } — последовательность, порождаемая рекуррентны-
ми соотношениями
xk+1 = xk + tk d k , k = 0, 1, 2, . . . ,
где d k = H(xk ) ? xk , а шаговые параметры tk ? [0, 1] определены из условия
M0 (xk + tk d k ) = min {M0 (xk + td k ) : 0 ? t ? 1}. (6.13)
Предположим также, что X — выпуклый компакт и отображение F : Rn > Rn
непрерывно дифференцируемо, причем матрица F (x) положительно определе-
на при всех x ? X. Тогда независимо от начального приближения x0 ? X по-
следовательность {xk } лежит в X и сходится к x — единственному решению
?
задачи V I(X, F ).
Д о к а з а т е л ь с т в о. Заметим вначале, что непрерывность отображения
F вместе с условием компактности X гарантирует разрешимость задачи V I(X, F ),
а условие положительной определенности матрицы F (x) — единственность ее
решения.
Далее, так как tk ? [0, 1] и множество X — выпукло, то из включений xk ?
X, H(xk ) = xk + d k ? X следует, что xk+1 ? X. Но x0 ? X, и потому вся после-
довательность {xk } лежит в X. Следовательно, любая предельная точка x этой
?
последовательности также лежит в X.
? ?
Предположим теперь от противного, что d = H(?)?? = 0. Тогда d — направление
xx
спуска функции M0 в точке x. Поэтому
?
? x ??
? = M0 (? + td) ? M0 (?) < 0,
x
?
где величина t определена из условия
x ?? ?
M0 (? + t d) = min {M0 (? + t d) : 0 ? t ? 1}.
x

61
Воспользуемся теперь свойством непрерывности отображений F и H, а также функ-
ции M0 и отображения, ставящего каждой паре (x, d) величину шага t по правилу
(6.13). Для сходящейся к x подпоследовательности {xkS } имеем
?

?
lim M0 (xkS + tkS d kS ) ? M0 (xkS ) = ? < 0.
(s)

Полученное строгое неравенство и очевидная монотонность последовательности зна-
чений M0 (xk ) противоречит ограниченности последней снизу.
Рассмотренный метод тесно связан с методом простой итерации из §3 данной
главы, поскольку и там и здесь участвует одно и то же направление d = H(x) ?
x. Однако в методе простой итерации параметр ? > 0 постоянен и не связан с
минимизацией какой бы то ни было функции.
В заключение раздела приведем (без подробного анализа вычислительных свойств)
две другие функции оценки, предназначенные для сведения нелинейной задачи о до-
полнительности N CP (F ) к обычной задаче безусловной оптимизации типа min M (x).
x
Первая известна как функция Мангасарьяна—Солодова. Она имеет вид
1
( (x ? 2F (x))+ 2 ?
M1 (x) = F (x) x + 4
2
+ (F (x) ? 2x)+ 2
? F (x) 2 ) .
?x

Эта функция непрерывно дифференцируема и, если якобиан F (x) отображения
n
F положительно определен при всех x ? R , любая стационарная точка функции
M1 относительно всего пространства является ее точкой глобального минимума и
решением задачи N CP (F ), если последняя разрешима.
Вторая функция, функция Фишера, имеет вид
n
?(xi , Fi (x))2 ,
M2 (x) =
i=1
v
a2 + b2 ? (a + b). Нетрудно заметить, что
где ?(a, b) =

?(a, b) = 0 ?? a ? 0, b ? 0, ab = 0.

Функция M2 также непрерывно дифференцируема и в случае, когда отображение
F представляет собой P0 — функцию, т. е. когда для любых x и y ? Rn , таких,
что x = y, существует индекс i такой, что

xi = yi , (xi ? yi ) (Fi (x) ? Fi (y)) ? 0,

любая стационарная точка функции M2 относительно всего пространства дает точку
ее глобального минимума и соответственно решение задачи N CP (F ).




62
Глава 3

ПОИСК ЭКОНОМИЧЕСКОГО
РАВНОВЕСИЯ

Перейдем к обсуждению важнейшей области приложения теории и методов реше-
ния конечномерных вариационных неравенств и задач о дополнительности — зада-
чам поиска равновесия в бескоалиционных играх n лиц (сторон). В математической
экономике этому соответствуют задачи поиска общего экономического равновесия,
прогнозирование транспортных потоков и тарифов на грузоперевозки и многие дру-
гие.

§ 1. Равновесие по Нэшу в играх n лиц

Рассмотрим бескоалиционную игру n лиц, в которой каждый из участников с
номером i ? {1, . . . , n} характеризуется своим множеством допустимых стратегий
n
mi
Xi ? R , mi ? 1, и своей функцией полезности ui (x1 , . . . , xn ) : Xi > R,
i=1
значение которой он стремится максимизировать.
Обозначим
n
N = {1, . . . , n}, xN \{i} = (xj : j ? N, j = i), X = Xi .
i=1

Точка x = (?1 , . . . , xn ) ? X называется точкой равновесия по Нэшу в бескоалици-
? x ?
онной игре n лиц N E(X, u), если для всех ее участников
ui (?i , xN \{i} ) ? ui (xi , xN \{i} ) ?xi ? Xi ,
x? ?
т. е. ни один из них не может в одиночку улучшить значение своей функции полез-
ности.
Следующий результат о сведении задачи поиска равновесия по Нэшу к некоторо-
му вариационному неравенству может быть легко установлен суммированием необ-
ходимых условий оптимальности первого порядка для задач максимизации функции
полезности каждого из участников игры. При этом полное допустимое множество в
задаче решения вариационного неравенства представляет собой декартово произве-
дение множеств допустимых стратегий участников игры.
Теорема 1.1. Если все Xi — непустые замкнутые выпуклые подмножества
mi
R , где mi ? 1, и функции полезности всех игроков ui : X > R непрерыв-

63
но дифференцируемы и псевдовогнуты по xi , то точка x ? X будет точкой
?
равновесия по Нэшу в том и только в том случае, когда
n
Fi (?) (xi ? xi ) ? 0 ?x ? X,
x ?
i=1

т. е. когда эта точка является решением вариационного неравенства V I(X, F ),
определяемого множеством X и отображением
n
Rm ,
F = (Fi : i ? N ), F : X >
i=1

где Fi : X > Rmi , Fi (x) = ? xi ui (x).

Таким образом, задача поиска равновесия по Нэшу весьма естественно форму-
лируется в терминах теории вариационных неравенств. Существование и единствен-
ность равновесия по Нэшу может быть установлена при помощи результатов раздела
2. В частности, наиболее известный результат для бескоалиционных игр является
простым следствием теоремы 2.1.

Теорема 1.2. Пусть Xi — непустые компактные выпуклые подмножества
mi
R , mi ? 1, и функции полезности ui : X > R непрерывно дифференцируемы и
псевдовогнуты по xi , i = 1, . . . , n. Тогда решение задачи N E(X, u) существует.

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

§ 2. Прогнозирование потоков в транспортных сетях

Задача прогнозирования грузовых потоков в транспортной сети дает сильный по-
будительный мотив к развитию алгоритмов решения вариационных неравенств боль-
шой размерности. Модель, лежащая в основе этой задачи, использует понятие рав-
новесия по Вардропу. Последнее есть просто поведенческий принцип, утверждаю-
щий, что пользователи сети (водители автомашин) ведут некооперативное соревно-
вание за сетевые ресурсы с целью минимизации индивидуальных дорожных расхо-
дов. В итоге задача прогнозирования грузовых потоков может рассматриваться как
частный случай поиска равновесия по Нэшу в некоторой игре n лиц.
Дадим обозначения, необходимые для постановки рассматриваемой задачи:
G(V, A) — транспортная сеть, описываемая множествами своих вершин V и дуг
A;
W — множество выделенных пар вершин поставщик—потребитель , т. е. пар
w = (i, j) ? W ;
Pw — множество путей, соединяющих пару w ? W ;
Pw — совокупность всех путей Pw в сети;
P=
w?W
f = (fa : a ? A), где fa — грузовой поток вдоль дуги a ? A;
h = (hp : p ? P ), где hp — грузовой поток вдоль пути p ? P ;

64
1, если путь p ? P содержит дугу a ? A;
?ap =
0 — в противном случае;
M = ( ?ap ) — матрица инцидентности дуг и путей;
c(f ) = (ca (f ) : a ? A), где ca (f ) — функция средних транспортных расходов для
дуги a ? A;
C(h) = (Cp (h) : p ? P ), где Cp (h) — функция средних транспортных расходов
для пути p ? P ;
u = (uw : w ? W ), где uw —минимальные транспортные расходы на перевозку
груза для пары вершин поставщик—потребитель w ? W, т. е. uw = min {Cp (h)} ;
p?Pw
T (u) = {Tw (u) : w ? W }, где Tw (u) — функция спроса на транспортировку груза
для пары вершин поставщик—потребитель w ? W.
Очевидно, что потоки и затраты вдоль дуг связаны с потоками и затратами вдоль
путей транспортной сети линейно:
f = Mh, C(h) = M c (f ).

Принцип равновесия Вардропа постулирует, что водители автомашин, перевозя-
щие груз от источника к потребителю, выбирают пути, вдоль которых их индивиду-
альные затраты на перевозку груза минимальны. Таких путей может быть несколько,
но пути с затратами, превосходящими минимальные, не используются.
??
Пара поток–затраты (f , u) образует точку равновесия по Вардропу, если вы-
полнены следующие условия:

hp (Cp (h) ? uw ) = 0, Cp (h) ? uw ? 0, hp ? 0 ?w ? W, p ? Pw ;

hp ? Tw (u) = 0, uw ? 0 ?w ? W.
p?Pw

Задачу поиска равновесия по Вардропу обозначим U E(c, T ).
Если бы не условия неотрицательности для uw , задача U E(c, T ) являлась бы
просто смешанной нелинейной задачей о дополнительности.
Предполагая, однако, транспортные расходы вдоль всех путей и дуг строго по-
ложительными, а функции спроса — неотрицательными, задачу U E(c, T ) можно
переформулировать как чистую нелинейную задачу о дополнительности.
??
Теорема 2.1. Пусть ca (f ) > 0 при всех a ? A и Tw (u) ? 0. Пара (f , u) будет
??
решением задачи U E(c, T ) в том и только в том случае, когда (f , u) решает
следующую задачу N CP (F ) :

Fp (h, u)hp + Fw (h, u)uw = 0,
p?P w?W

Fp (h, u) ? 0, hp ? 0, Fw (h, u) ? 0, uw ? 0,
где
Fp (h, u) = Cp (h) ? uw , Fw (h, u) = hp ? Tw (u),
p?Pw

f = Mh, C(h) = M c(f ).




65
Таким образом, нелинейная задача о дополнительности есть весьма естествен-
ная формулировка равновесия по Вардропу, а введенные выше необходимые условия
этого достаточно слабые. Однако задача имеет очень большую размерность и, в
частности, требует перенумерации всех путей в транспортной сети.
Последнюю проблему можно решить в случае, когда функция T (u) имеет об-
ратную, которую обозначим u = ?(T ). Теперь задачу U E(c, T ) можно записать
как задачу решения вариационного неравенства на полиэдральном множестве X, в
котором переменные, характеризующие пути, трактуются как скрытые.
??
Теорема 2.2. Пусть функция T (u) обратима. Пара (f , T ) есть решение задачи
??
U E(c, T ) в том и только в том случае, когда (f , T ) решает следующую задачу
V I(X, F = (c, ??)) :
? ? ? ?
c (f ) (f ? f ) ? ? (T ) (T ? T ) ? 0 ?(f, T ) ? X,
где
X = (f, T ) : f = Mh, ?w ? W, h ? 0, T ? 0 .
hp = Tw
p?Pw

Определенное здесь множество X является полиэдральным конусом. В случае
фиксированного спроса (т. е. при T (u) = T ) обратная функция ? исчезает из
постановки вообще, а множество X обращается просто в многогранник (т. е. огра-
ниченное полиэдральное множество). Сама задача превращается при этом просто в
серию задач поиска кратчайшего пути в сети.
Существование и единственность равновесия в U E(c, T ) можно установить, при-
меняя различные теоремы из главы 2 §2. В частности, справедливо следующее
утверждение.

Теорема 2.3. Пусть все ca (f ), a ? A, — строго положительные и непрерывные
функции, отделенные от нуля, и пусть Tw (u) — строго положительные, непре-
рывные функции, ограниченные сверху при всех w ? W. Тогда решение N CP (F )
из теоремы 2.1 существует и единственно.
??
Заметим, что единственной является пара (f , u) ; что касается потоков h, то они
редко являются единственными в задаче определения грузовых потоков.
Важным расширением рассмотренной выше задачи является задача развития транс-
портной сети. В последней оптимизируется некоторая мера производительности транс-
портной сети, пользователи которой подчиняются поведенческому принципу Вар-
дропа. Важность задачи развития можно проиллюстрировать известным парадоксом
Браеса: при неудачном добавлении в сеть новой дуги ее производительность мо-
жет снизиться(!). Поэтому следует аккуратно подходить к вопросу о включении в
транспортную сеть новых и удалению из нее старых дуг.

§ 3. Пространственное равновесие цен

Другое обобщение задачи определения грузовых потоков в сети можно полу-
чить, если заменить функции спроса Tw (u) на более базовые понятия спроса—
предложения товара в каждой из ее вершин. Введем необходимые обозначения:
? = (?i : i ? V ), где ?i — цена некоторого однородного товара в вершине i ? V ;
D(?) = (Di (?) : i ? V ), где Di (?) — спрос на этот товар в вершине i ? V ;

66
S(?) = (Si (?) : i ? V ), где Si (?) — предложение этого товара в вершине i ? V.
Принцип пространственного равновесия цен утверждает, что конкуренция при
перевозке товаров между регионами приводит к отсутствию положительной прибыли
при перевозках; если же эта прибыль отрицательна, движение товаров отсутствует.
Приведем точное математическое определение.
??
Пара поток—цена (f , ? ) описывает пространственное равновесие цен, если
Si (?) ? Di (?) + hp ? hp = 0, ?i ? 0, ?i ? V,
w=(k,i)?W p?Pw w=(i,j)?W p?Pw

(?i + Cp (h) ? ?j ) hp = 0, ?i + Cp (h) ? ?j ? 0, hp ? 0,
?w = (i, j) ? W, p ? Pw .
Задачу поиска пространственного равновесия цен будем обозначать через SP E(c, S, D).
Предполагая, что функции затрат строго положительны, а функции спроса и пред-
ложения удовлетворяют условию
?i = 0 ? Di (?) ? Si (?), ?i ? V, (3.1)
задачу SP E(c, SD) можно переформулировать как нелинейную задачу о дополни-
тельности.
Теорема 3.1. Пусть функции ca (f ), a ? A, строго положительны и выполнены
??
условия (3.1). Пара (f , ? ) будет решением SP E(c, S, D) в том и только в том
??
случае, когда (f , ? ) решает следующую задачу N CP (F ) :
Fi (h, ?)?i + Fp (h, ?)hp = 0,
i?V w?W p?Pw

Fi (h, ?) ? 0, ?i ? 0, Fp (h, ?) ? 0, hp ? 0,
где
f = Mh, C(h) = M c(f ),
Fi (h, ?) = Si (?) ? Di (?) + hp ? hp ,
w=(k,i)?w p?Pw w=(i,j)?w p?Pw

Fp (h, ?) = ?i + Cp (h) ? ?j при всех p ? P(i,j) .
Как и в случае задачи определения грузовых потоков, при предположении об
обратимости функций S(?) и D(?) задачу SP E(c, S, D) можно представить как
задачу решения некоторого вариационного неравенства относительно полиэдрально-
го множества.
Теорема 3.2. Пусть функции S (?) и D(?) обратимы, причем обратные к
ним функции ?(S) и ?(D) соответственно существуют и неотрицательны.
?? ?
Тройка (f , S, D) порождает равновесие в задаче SP E(c, S, D) тогда и только
тогда, когда она решает следующую задачу V I(X, F = (?, c, ??)) :
? ?
? ? ? ?
?(S) (S ? S) + c (f ) (f ? f ) ? ?(D) (D ? D) ? 0 ?(f, S, D) ? X,
где
X = (f, S, D) : Si ? Di + hp ? hp = 0
w=(k,i)?W p?Pw w=(i,j)?W p?Pw

?i ? V, f = Mh, S ? 0, D ? 0, h ? 0 .


67
Приведем один из результатов о существовании и единственности решения SP E(c, S, D).
Он получается как следствие теоремы 2.6 из главы 2.

Теорема 3.3. Пусть функции ca (f ), a ? A, строго положительны, непрерыв-
ны и отделены от нуля, а функции S(?) и D(?) непрерывны, удовлетворяют
условию (3.1) и следующему условию: существует вектор цен ? такой, что
?
?i ? ?i ? Si (?) ? Di (?).
?

Тогда решение задачи N CP (F ) из теоремы 3.1 существует и единственно.

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

§ 4. Общее экономическое равновесие по Вальрасу

Модель, к рассмотрению которой мы переходим, предназначена для прогнози-
рования экономической активности в замкнутой экономике, т. е. для вычисления
равновесных цен и объемов производства различного вида товаров и услуг, которые
ее составляют. Эта хорошо известная модель является основой большинства совре-
менных экономико-математических исследований и доказала свою пригодность для
изучения вопросов ценообразования, для анализа международной торговли, энерге-
тической политики и др. Она имеет весьма богатую историю теоретических иссле-
дований и приложений.
Из различных математических формализаций модели общего экономического рав-
новесия остановимся на следующей, предложенной Масиесеном. Пусть
M — множество различных продуктов (товаров), производимых в рамках неко-
торой экономики;
N — множество технологических способов (отраслей, предприятий и т.п.), ее
составляющих;
xj — интенсивность использования i -го технологического способа (отрасли, пред-
приятия), x = (xj : j ? N ) ;
?i — цена i -го продукта, ? = (?i : i ? M ) ;
bi — начальный запас i -го продукта, b = (bi : i ? M ) ;
cj — затраты на реализацию единичной интенсивности i -го технологического
способа (оплата труда и т.д.), c = (cj : j ? N ) ;
di (?) — функция спроса на i -й продукт, d(?) = (di (?); i ? M ) ;
A(?) = (aij (?)) — технологическая матрица Леонтьева, ее положительные эле-
менты aij (?) равны объему выпуска i -го продукта при единичной интенсивности
реализации j -го технологического способа, а отрицательные — объему его затрат.
При помощи этих обозначений модель общего экономического равновесия опре-
деляется следующим образом.
Пара цена—интенсивности (? , x) образует точку общего экономического рав-
??
новесия GE(b, c, d, A), если она удовлетворяет следующим соотношениям:
1) c ? A(?) ? ? 0 — бесприбыльность всех технологических способов;
2) b + A(?)x ? d(?) ? 0 — обеспечение спроса на все виды продуктов;
3) ? ? 0, x ? 0 — неотрицательность всех цен и интенсивностей реализации всех
технологических способов;


68
4) (c ? A(?) ?) x = 0 — технологические способы с отрицательной прибылью не
используются (используются с нулевой интенсивностью);
5) (b+A(?)x?d (?)) ? = 0 — закон Вальраса — товары, произведенные в избытке,
имеют нулевую цену.
Нетрудно видеть, что условия 1 – 5 прямо переводятся в нелинейную задачу о
дополнительности.
Теорема 4.1. Пара (? , x) является точкой общего равновесия в задаче GE(b, c, d, A)
??
в том и только в том случае, когда (? , x) решает следующую задачу N CP (F ) :
??
Fx (?, x) x + F? (?, x) ? = 0,
Fx (?, x) ? 0, ? ? 0, F? (?, x) ? 0, x ? 0,
где
Fx (?, x) = c ? A(?) ?, F? (?, x) = b + A(?)x ? d(?).
Приведенная формулировка включает в себя как цены, так и интенсивности при-
менения технологических способов. В случае когда технологическая матрица A(?)
не зависит от цен, т. е. A(?) ? A, можно дать сокращенную формулировку задачи
поиска точки общего экономического равновесия в виде некоторого вариационного
неравенства над полиэдральным множеством относительно только вектора цен.
Теорема 4.2. Вектор цен ? есть решение задачи V I(X, F ), где
?
X = {? : c ? A ? ? 0, ? ? 0}, F (?) = b ? d(?),
в том и только в том случае, когда существует вектор интенсивностей x та-
?
кой, что пара (? , x) образует точку общего экономического равновесия GE(b, c, d, A) ;
??
при этом есть вектор множителей
x
?
Лагранжа ограничений общего вида, определяющих множество X.
Литература по модели общего экономического равновесия содержит огромное чис-
ло результатов по существованию и единственности ее решения. Один простой ре-
зультат может быть получен как непосредственное следствие теоремы 1.1. Поскольку
функции спроса однородны степени ноль, то без потери общности можно нормали-
зовать все цены. Определим
?
X=X? ?: ?i = 1 .
i?M

Теорема 4.3. Пусть d (?) — непрерывная функция такая, что d (??) = d(?) ?? ?
Тогда существует решение задачи
R+ . ?
?
?
V I(X, F ), определенной в теореме 4.2.
Среди численных методов решения общей задачи о равновесии проекционные
методы выделяются своей интересной экономической интерпретацией. Переопреде-
ление итерационной точки в них ведется отдельно для вектора интенсивностей ис-
пользования технологических способов и отдельно для вектора цен на продукцию.
Нетрудно проверить, что направление смещения для первого из них дается вектором
A(?) ? ? c, а для второго — вектором d(?) ? b ? A(?)x. Таким образом, на каж-
дом шаге вычислительного процесса несколько возрастает интенсивность использо-
вания технологических способов, характеризующихся положительной прибылью (в

69
текущих ценах на продукцию), и снижается интенсивность использования техноло-
гических способов, прибыль которых отрицательна. Одновременно растут цены на
продукты, пользующиеся повышенным спросом, и падают цены на продукты, остаю-
щиеся в избытке. Жесткие условия на свойства отображений и шаговые параметры,
при которых имеет место сходимость итерационных последовательностей, являются
адекватным отражением известной и признаваемой в экономической науке неустой-
чивости классического рыночного механизма регулирования спроса и предложения
и необходимости дополнительных мер по его стабилизации (например, со стороны
государства).

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

§ 5. Многоуровневое принятие решений

Пусть заданы X — непустое подмножество пространства Rn и {F1 , F2 , . . . , Fm }
— конечный упорядоченный набор отображений X в Rn . Рассмотрим лексикогра-
фическую задачу решения вариационного неравенства LV I(X, F1 , . . . , Fm ), которая
заключается в поиске элементов множества Xm , последнего в следующем рекурсив-
ном ряду множеств
i = 0, 1, . . . , m ? 1; (5.1)
Xi+1 = Arg VI (Xi , Fi+1 ),
здесь, как и ранее, Arg VI — множество решений соответствующего вариационного
неравенства (обычного), X0 = X .
Лексикографические вариационные неравенства возникают как
естественное обобщение классических задач лексикографической (последователь-
ной) оптимизации, а также как обобщение аппарата, развитого разными авторами
при анализе обычных оптимизационных задач с ограничениями в форме вариацион-
ных неравенств, в задачах поиска аппроксимационных корней монотонных отображе-
ний, задачах оптимальной коррекции неразрешимых (несобственных) минимаксных
задач и ряде других.
Рассмотрим, например, проблематику двухуровневой технологии
принятия решений. Двухуровневое программирование изучает задачи принятия ре-
шений несколькими неравноценными партнерами, один из которых является лиде-
ром, а все прочие — ведомыми. Лидер оптимизирует свою целевую функцию (функ-
цию верхнего уровня) при ограничениях, включающих в себя реакцию ведомой сто-
роны (сторон) на его решения. Реакция ведомой стороны описывается задачей ма-
тематического программирования нижнего уровня, целевая функция и ограничения
которой параметрически зависят от переменных верхнего уровня. В более строгой
записи задача двухуровневого программирования выглядит следующим образом:
min{F (x, y) : (x, y) ? X, y ? Arg min f (x, z) },
x z?Y (x)

здесь F (x, y) — целевая функция лидера; x — вектор его переменных; y — вектор
переменных ведомой стороны; f (x, y) — ее целевая функция; X и Y (x) описывают
общие ограничения и ограничения на поведение ведомой стороны в зависимости от
поведения лидера.

70
Допустимую область и условия оптимальности в этой задаче можно описать вари-
ационными неравенствами. Сама задача возникает, например, при государственном
регулировании цен на энергетические носители. В этом случае переменные x ин-
терпретируются как цены на нефть, газ, электроэнергию и т.п., а переменные y
— как реакция промышленного сектора на их изменение. Целевая функция, опти-
мизируемая на верхнем уровне, формируется не только на основе финансовых со-
ображений, но также и на основе общеполитических, социальных, экологических
и других аспектов. На нижнем уровне промышленные предприятия, ориентируясь
на цены, предложенные государством, стремятся распорядиться своими ресурсами и
технологиями так, чтобы обеспечить себе максимальную прибыль.
Вернемся к лексикографической задаче LV I(X, F1 , . . . , Fm ). В прямой постановке
эта задача, являясь обобщением обычной задачи последовательного (лексикографи-
ческого) программирования, сохраняет свойства неустойчивости последней. Одним
из приемов преодоления указанной неустойчивости в последовательном программи-
ровании служит переход от векторного критерия к скалярному, представляющему
собой взвешенную сумму частных критериев. При этом упорядоченность частных
критериев находит свое отражение в выборе весовых множителей. Перенесем этот
прием на лексикографическую задачу решения вариационного неравенства.
Пусть ? = (?1 , ?2 , . . . , ?m ) — набор положительных весовых коэффициентов.
Определим взвешенное отображение F ? : X > Rn по правилу
F ? (x) = ?1 F1 (x) + ?2 F2 (x) + . . . + ?m Fm (x). (5.2)
Введем условия:
1. Множество X не пусто, выпукло и замкнуто.
2. Отображения F1 , F2 , . . . , Fm непрерывны и монотонны на X.
Следующий результат характеризует принципиальную связь лексикографической
задачи (5.1) с решениями вариационного неравенства, порождаемого отображением
(5.2) и множеством X при различном выборе весовых множителей ?i .
Теорема 5.1. Пусть выполнены условия 1 , 2 и при всех ? > 0 задача VI (X, F ? )
имеет единственное решение x (?). Если существует повторный предел
. . . lim x (?) = x? ,
lim lim
?m?1 >? ?m?2 >? ?1 >?

то x? — одно из решений лексикографической задачи (5.1).
Д о к а з а т е л ь с т в о. Заметим, что рассматриваемый повторный предел не
зависит от значения ?m , которое можно считать равным 1. Введем обозначения:

x1 (?) = lim x (?),
?1 >?
x2 (?) = lim x1 (?) = lim lim x (?),
?2 >? ?2 >? ?1 >?
...
. . . lim x (?) = x? .
xm?1 (?) = lim xm?2 (?) = lim lim
?m?1 >? ?m?1 >? ?m?2 >? ?1 >?

По условию отображения F1 , F2 , . . . , Fm монотонны и все ?i > 0. Поэтому отобра-
жение (5.2) также мотонно, и по теореме 2.3 из главы 2
(?1 F1 (x) + ?2 F2 (x) + . . . + ?m Fm (x), x ? x(?)) ? 0 ?x ? X. (5.3)

71
Деля обе части этого неравенства на ?1 > 0 и переходя к пределу по ?1 > ?,
получаем
(F1 (x), x ? x1 (?)) ? 0 ?x ? X = X0 ,
что, в силу той же теоремы, означает x1 (?) ? X1 = ?.
Если m > 1, перепишем неравенство (5.3) в виде

(?2 F2 (x) + ?3 F3 (x) + . . . + ?m Fm (x), x ? x(?)) ?
? (?1 F1 (x), x(?) ? x) ?x ? X0 .

Отсюда, с учетом неравенств ?1 > 0 и (F1 (x), x(?) ? x) ? 0 ?x ? X1 и включения
X1 ? X0 , вытекает

(?2 F2 (x) + ?3 F3 (x) + . . . + ?m Fm (x), x ? x(?)) ? 0 ?x ? X1 ,

или, после перехода к пределу по ?1 > ?,
(?2 F2 (x) + ?3 F3 (x) + . . . + ?m Fm (x), x ? x1 (?)) ? 0 ?x ? X1 . (5.4)

Деля обе части этого неравенства на ?2 > 0 и переходя к пределу по ?2 > ?,
получаем
(F2 (x), x ? x2 (?)) ? 0 ?x ? X1 ,
что, в силу все той же теоремы 2.3, означает x2 (?) ? X2 = ?.
Если m > 2, повторим все приведенные выше рассуждения применительно к
неравенству (5.4). Перепишем его в виде
(?3 F3 (x) + . . . + ?m Fm (x), x ? x(?)) ? (?2 F2 (x), x1 (?) ? x) ?x ? X1 .

С учетом того что ?2 > 0 и (F2 (x), x1 (?) ? x) ? 0 ?x ? X2 , а также включения
X2 ? X1 , имеем

(?3 F3 (x) + . . . + ?m Fm (x), x ? x1 (?)) ? 0 ?x ? X2 ,

или, после перехода к пределу по ?2 > ?,
(?3 F3 (x) + . . . + ?m Fm (x), x ? x2 (?)) ? 0 ?x ? X2 . (5.5)

Деля обе части этого неравенства на ?3 > 0 и переходя к пределу по ?3 > ?,
получаем
(F3 (x), x ? x3 (?)) ? 0 ?x ? X2 ,
что и означает x3 (?) ? X3 = ?.
Повторяя приведенные выше рассуждения снова и снова, будем получать аналоги
неравенств (5.3)–(5.5) вида

(?k Fk (x) + . . . + ?m Fm (x), x ? xk?1 (?)) ? 0 ?x ? Xk?1 , k = 4, . . . , m ? 1,

пока, наконец, не дойдем до неравенства

(?m Fm (x), x ? xm?1 (?)) ? 0 ?x ? Xm?1 .

Деля обе части этого неравенства на ?m > 0 и замечая, что xm?1 (?) = = x? , в
силу все той же теоремы 2.3, приходим к заключительному выводу: x? ? Xm = ?.


72
Ввиду сложности вычисления повторного предела доказанный результат носит
скорее принципиальный, чем практический характер. Поэтому перейдем к выясне-
нию условий, при которых можно ограничиться обычным пределом или даже ко-
нечными значениями весовых множителей. Хотя по прежнему веса более важных
критериев будут больше весов менее важных критериев, в оставшейся части пара-
графа нам удобнее будет считать эти веса сходящимися не к бесконечности, а к
нулю.
Итак, пусть значения весовых коэффициентов в (5.2) зависят от некоторого нату-
рального параметра k. Выпишем дополнительные условия:
3 . ?k = 1, lim ?k = 0 (i = 2, . . . , m).
1 i
k>?

4 . lim ?k /?k = 0 (i = 3, . . . , m).
i i?1
k>?

Введем также условие регулярности для промежуточных подзадач:
5 . ?(x, Xi ) ? Ci (Fi (x), x ? Pi (x)) при всех i < m и x ? Xi?1 .
Здесь Pi (x) — проекция точки x на множество Xi ; Ci > 0 — некоторые кон-
станты.

Теорема 5.2. Пусть выполнены условия 1 – 5 и последовательность, состав-
ленная из векторов xk = x(?k ) ? Arg VI (X, F?k ), ограничена. Тогда ее элемен-
ты при всех достаточно больших k будут решением лексикографической зада-
чи (5.1) .
Д о к а з а т е л ь с т в о. Вначале покажем, что xk ? X1 при всех достаточно
больших k . В самом деле, по самому способу определения точек xk имеем
m
1
k
?k Fi (xk ), xk ? x) ? 0 ?k ?x ? X = X0 . (5.6)
(F1 (x ) + k i
?1 i=2

Отсюда, в силу условия 5, следует
m
C1
?(xk , X1 ) ? C1 (F1 (xk ), xk ? P1 (xk )) ? k ?k (Fi (xk ), P1 (xk ) ? xk ) ?
i
?1 i=2

m
max {?k /?k } Fi (xk ) ?(xk , X1 )
? C1 ?k.
i 1
i
i=2

Поэтому
(1)
(1 ? µk ) ?(xk , X1 ) ? 0,
где
m
(1)
C1 max{?k /?k } Fi (xk ) > 0 при k > ?.
µk = i 1
i
i=2
(1)
При достаточно больших k имеем µk < 1, т. е. ?(xk , X1 ) = 0 .
Далее, по индукции, предполагая уже установленным включение xk ? Xi при
всех достаточно больших k для i = 1, . . . , n ? 1 < m, покажем, что при больших k
это включение верно также и для i = n .
Рассмотрим два случая.

73
1) Пусть n < m . В силу формул (5.6) и условия 4 и ввиду монотонности рас-
сматриваемых отображений, имеем

?k ?(xk , Xn ) ? ?k Cn (Fn (xk ), xk ? Pn (xk )) ?
n n

n?1 m
?k (Fi (xk ), Pn (xk ) ? xk ) + Cn ?k (Fi (xk ), Pn (xk ) ? xk ) ?
? Cn i i
i=1 i=n+1
n?1 m
?k (Fi (Pn (xk )), Pn (xk ) ? xk ) + Cn ?k (Fi (xk ), Pn (xk ) ? xk ) ?
? Cn i i
i=1 i=n+1
m
max{?k } Fi (xk ) ?(xk , Xn ),
? Cn i
i>n
i=n+1

здесь использовались неравенства (Fi (Pn (xk )), Pn (xk ) ? xk ) ? 0, которые верны
благодаря включениям Pn (xk ) ? Arg VI (Xi?1 , Fi ) при всех i = 1, . . . , n.
Из полученного неравенства следует
(n)
(1 ? µk ) ?(xk , Xn ) ? 0,
где
m
(n)
= Cn max{?k /?k } Fi (xk ) > 0 k > ?.
при
µk i n
i>n
i=n+1
(n)
Поэтому при достаточно больших k имеем µk < 1, что влечет ?(xk , Xn ) = 0 .
2) Пусть n = m . Как и выше, из формул (5.6) при достаточно больших k в силу
монотонности всех отображений следует

?k (Fm (xk ), xk ? x) ?
m

<<

стр. 3
(всего 4)

СОДЕРЖАНИЕ

>>