<<

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

СОДЕРЖАНИЕ

>>

26
и i = k — номер, на котором этот минимум достигается. Тогда ? ? 0, w = z ? ?b =
(w1 , . . . , wn ) ? 0 и wk = 0.
Заметим, что
M w = M z ? ?M b = M z ? ?e1 ? 0
?
(здесь e1 = (1, 0, . . . , 0) — орт пространства Rn ). Обозначим через M главную
подматрицу, получаемую из M путем удаления k -й строки и столбца, а через w —?
(n ? 1) -вектор, получаемый из w удалением его k -й компоненты. Имеем
??
M w ? 0, w ? 0.
?
?
Поскольку M есть ((n?1)?(n?1)) -матрица и все ее главные миноры положительны
(совпадают с таковым у M ), то по предположению индукции w = 0. Это вместе с
?
равенством wk = 0 дает w = 0, так что M z = ?e1 ? 0. Следовательно, M z = 0, и,
ввиду невырожденности M, имеем z = 0, что и требовалось.

Следствие 7.1. Если M — P -матрица, то система
(7.2)
M z > 0, z > 0,
совместна.
Д о к а з а т е л ь с т в о. В силу однородности системы (7.2) ее совместность
эквивалентна совместности системы
M z ? e, z ? e, где e = (1, 1, . . . , 1) .
Последняя же совместна тогда и только тогда, когда система
M w ? 0, w ? 0, (7.3)
не имеет отличных от нуля решений (следует из двойственности в линейном про-
граммировании). Но по только что доказанной лемме система (7.3) действительно
не имеет ненулевых решений, так как матрица M принадлежит классу P вместе
с матрицей M.
Доказанная лемма и ее следствие позволяют установить конечность метода Лемке
для P -матриц.
Теорема 7.1. Если все главные миноры матрицы M положительны, то ме-
тод Лемке при любом q завершается на допустимом базисном решении (5.1),
удовлетворяющем условиям дополнительности, т. е. дает решение LCP (q, M ).
Д о к а з а т е л ь с т в о. Мы уже видели, что завершение на луче подразумевает
существование ненулевого вектора z ? 0, удовлетворяющего неравенствам (6.1).
?
Однако по только что доказанной лемме в случае P -матриц это невозможно. Значит,
для P -матриц невозможно и завершение метода Лемке на луче.
Приведем еще одну важную характеризацию P -матриц, для чего нам потребуется
два вспомогательных утверждения.
Пусть векторы z, w связаны соотношением w = M z. Будем говорить, что M
меняет знак z, если zi wi ? 0 для всех i = 1, . . . , u.
Лемма 7.2. Матрица M принадлежит классу P в том и только в том случае,
когда она не меняет знак ни у одного вектора, кроме нулевого.

27
Д о к а з а т е л ь с т в о. Прежде всего, доказывая необходимость, заметим,
что можно ограничиться случаем z ? 0. В самом деле, если L = {i : zi < 0} = ?,
определим D — диагональную матрицу, получаемую из единичной матрицы сменой
знака у тех ее строк, номера которых входят в L. Матрица M = DM D снова
оказывается P -матрицей, поскольку мы просто сменили знаки у строк и столбцов
M, номера которых входят в L. Кроме того, матрица M меняет знак у вектора
Dz ? 0.
Итак, пусть 0 = z ? 0 и M меняет знак z. Определим множество K = {i : zi >
?
0}. Предполагая, что K = ?, выделим M — главную подматрицу M, получаемую из
нее удалением тех строк и столбцов, номера которых не входят в K. Пусть также
?
z — вектор, получаемый из z аналогичным образом. Матрица M — также P -
?
матрица и меняет знак z . Поскольку все zi > 0, то должно выполняться неравенство
? ?
??
M z ? 0. В силу леммы 7.1 это отвергает гипотезу о принадлежности M классу P.
Необходимость доказана.
?
Перейдем к обоснованию достаточности. Пусть M = (aij ) — произвольная глав-
ная подматрица матрицы M, K — множество номеров входящих в нее строк и
?
столбцов. Если ее определитель не положителен, M должна иметь хотя бы одно
неположительное вещественное собственное значение и соответствующий ему нену-
левой вещественный собственный вектор z (это следует из того, что определитель
?
матрицы есть произведение всех ее собственных значений, причем комплексные зна-
чения образуют сопряженные пары). Если теперь дополнить вектор z до размерности
?
n нулями в позициях вне K, мы получим вектор z, знак которого меняется над
действием матрицы M. Полученное противоречие доказывает достаточность.
Напомним, что элементарным преобразованием системы линейных уравнений
называют разрешение ее относительно одной из своих неизвестных (т. е. опера-
цию исключения этой неизвестной из всех уравнений, кроме некоторого). Поскольку
элементарное преобразование не меняет множества решений системы, простым след-
ствием доказанной леммы является следующий факт.

Следствие 7.2. Пусть имеется система уравнений

w = q + M z,

где M — P -матрица. Тогда элементарное преобразование этой системы, меня-
ющее ролями переменные любой дополнительной пары (zi , wi ), снова приводит к
P -матрице.

Такое преобразование возможно, так как все mii > 0(= 0).

Теорема 7.2. Линейная задача о дополнительности LCP (q, M ) имеет един-
ственное решение при всех q тогда и только тогда, когда M — P -матрица.

Д о к а з а т е л ь с т в о. Пусть M — P -матрица. По теореме 7.1 задача
LCP (q, M ) разрешима при всех q, причем ее решение является некоторым допусти-
мым базисным решением системы ее уравнений. Переходя в случае необходимости
к преобразованной задаче, матрица которой также P -матрица, можно, не ограни-
чивая общности, считать, что q ? 0 и решение, получаемое методом Лемке, имеет
вид (q; 0) (т. е. z = 0, w = q ? 0 ). Пусть оно не единственно и (w, z ) — другое
??
решение. Тогда не трудно видеть, что M меняет знак z , т. е. по лемме 7.2 не может
?
принадлежать P.

28
Обратно, пусть LCP (q, M ) имеет единственное решение при всех q, но M —
не P -матрица. Тогда по лемме 7.2 существует ненулевой вектор z такой, что все
?
zi · wi ? 0, где w = M z .
?? ? ?
Определим q = (w) ? M (?)+ , где плюс над вектором означает его положитель-
+
? ? z
ную срезку, т. е. замену отрицательных координат нулями. Поскольку zi+ · wi = 0,
?+
?
пара (w+ , z + ) ? 0 является, очевидно, решением LCP (?, M ). Другим очевидным
?? q
решением LCP (?, M ) будет пара (w? , z ? ) ? 0, где минус над вектором означает
q ??
положительную срезку противоположного ему вектора. При проверке всех условий
опираемся на равенства w = M z , w = w+ ? w? , z = z + ? z ? , zi? · wi = 0.
? ??
? ?? ? ? ?? ?
В общем случае линейная задача о дополнительности не всегда разрешима, даже
если ее ограничения совместны.

Упражнения
1. Задача LCP (q, M ) имеет единственное решение для всех q > 0 тогда и только
тогда, когда матрица M полумонотонна. Докажите.
2. Убедитесь, что для задачи LCP (q, M ), где

?1 01
q= , M= ,
0 00

метод Лемке завершается на луче, хотя задача имеет решение (какое?).
3. Проверьте, что при использовании стандартного выбора ведущей строки метод
Лемке на задаче LCP (q, M ), где
? ? ? ?
?1 120
q = ? ?1 ? , M = ? 0 1 2 ? ,
?1 201
зацикливается.
4. Докажите, что для задач с полумонотонными матрицами значение искусствен-
ной переменной в методе Лемке никогда не превышает своего начального значения,
а для задач с P0 -матрицами оно или остается неизменным, или убывает.
5. Разберите ход вычислений в методе Лемке с искусственной переменной приме-
нительно к паре двойственных задач линейного программирования.
6. Дайте содержательную интерпретацию метода Лемке в применении к поста-
новкам, возникающим в квадратичном программировании.
7. Матрица M = ( mij )n?n называется Z-матрицей, если все ее внедиагональные
элементы неположительны. Покажите, что всякая допустимая линейная задача о
дополнительности с Z-матрицей разрешима.
8. Используя Бэйсик, Паскаль или другой язык программирования, опишите ал-
горитм пересчета таблиц в методе Лемке.




29
Глава 2

НЕЛИНЕЙНЫЕ ЗАДАЧИ О
ДОПОЛНИТЕЛЬНОСТИ И
ВАРИАЦИОННЫЕ НЕРАВЕНСТВА

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

§ 1. Постановка задач и их взаимосвязь

Пусть X — непустое подмножество пространства Rn и F — некоторое отоб-
ражение X в Rn . Задача решения вариационного неравенства, обозначаемая в
дальнейшем V I(X, F ), состоит в отыскании вектора x ? X такого, что
?
F (?) (x ? x) ? 0 при всех x ? X. (1.1)
x ?
Обычно полагают, что множество X замкнуто и выпукло; в приложениях оно
часто оказывается полиэдральным.
Геометрически условие (1.1) требует, чтобы вектор F (?) составлял острый угол
x
со всеми допустимыми векторами – направлениями, исходящими из x. Более строго
?
x ? X есть решение V I(X, F ) в том и только в том случае, когда ?F (?) лежит в
? x
нормальном (к множеству X в точке x ) конусе NX (?), где
x
{z ? Rn : z (y ? x) ? 0 ?y ? X}, если x ? X;
NX (x) =
? — в противном случае.
Поэтому любое решение x задачи V I(X, F ) будет одновременно и решением задачи
?
min{ F (?) x : x ? X }, (1.2)
x
и наоборот, если x ? Arg (1.2), то x ? Arg V I(X, F ).
? ?
Простейший пример задачи решения вариационного неравенства дает обычная
система нелинейных уравнений
F (x) = 0,

30
где F (x) — отображение Rn в себя. В самом деле, при X = Rn вектор x будет
?
решением V I(X, F ), только если F (?) = 0, так как нуль-вектор — единственный
x
вектор, составляющий острый угол сразу со всеми векторами из Rn .
Другой наглядный пример задачи решения вариационного неравенства дает диф-
ференцируемая оптимизация. Если F (x) = f (x) — градиент вещественной диффе-
ренцируемой функции f : Rn > R и множество X выпукло, то V I(X, F ) представ-
ляет собой просто перезапись необходимых условий оптимальности первого порядка
для задачи
min{ f (x) : x ? X }. (1.3)
В самом деле, если x — решение задачи V I(X, f ), то в задаче (1.3) не суще-
?
ствует допустимого направления спуска из x. Если же f (x) — псевдовыпукла (т. е.
?
f (x) (y ? x) ? 0 влечет за собой неравенство f (y) ? f (x) при всех
неравенство
x, y ? X ), то любое решение V I(X, F ) будет также точкой глобального минимума
в (1.3).
Третий пример связан с поиском седловых точек выпукло-вогнутых функций (и
теми задачами из теории игр и математического программирования, которые сводятся
к такому поиску). Пусть X и Y — непустые замкнутые выпуклые подмножества
Rn и Rm соответственно, f : Rn ? Rm > R — дифференцируемая числовая функция
двух векторных аргументов. Седловой точкой функции f (x, y) относительно области
X ? Y называется пара (?, y ) ? X ? Y, удовлетворяющая неравенствам
x?

f (?, y) ? f (?, y ) ? f (x, y ) ?x ? X, ?y ? Y.
x x? ?

Как известно, необходимые условия того, что точка (?, y ) является седловой, имеют
x?
вид
x ? X, x f (?, y ) (x ? x) ? 0 ?x ? X,
? x? ?
(1.4)
y ? Y, y f (?, y ) (y ? y ) ? 0 ?y ? Y.
? x? ?
Если функция f (x, y) выпукла по x при всех фиксированных y ? Y и вогнута по
y при всех фиксированных x ? X, условия (1.4) носят также достаточный характер.
Их можно переписать в виде вариационного неравенства V I(X ? Y, F ), где F =
( x f, ? y f ).
Известно, что непрерывно дифференцируемое отображение F является градиен-
том некоторой функции f : Rn > R тогда и только тогда, когда его якобиан F
симметричен при всех x ? Rn . В этом случае
1

F (? + t(x ? x)) (x ? x)dt,
f (x) = x ? ?
0

где x — произвольный фиксированный вектор из Rn . Таким образом, симметрич-
?
ность F является тем ключом, который позволяет переформулировать V I(X, F )
как обычную оптимизационную задачу.
В общем случае указанная выше переформулировка является редким исключени-
ем, пример которого дают задачи математического программирования и связанные с
ними задачи поиска седловой точки ассоциированных с ними функций Лагранжа с
необязательно симметричными матрицами вторых производных.
Важным частным случаем V I(X, F ) является нелинейная задача о дополни-
тельности.


31
Пусть F (x) — отображение Rn в Rn . Нелинейная задача о дополнительности,
+
обозначаемая N CP (F ), состоит в отыскании вектора x ? Rn такого, что
?
x ? 0, F (?) ? 0, F (?) x = 0. (1.5)
? x x?
Если отображение F аффинно, т. е. F (x) = q +M x для некоторого q ? Rn и мат-
рицы M ? Rn?n , задача (1.5) превращается в линейную задачу о дополнительности
LCP (q, M ).
Геометрически нелинейная задача о дополнительности состоит в поиске неотри-
цательного вектора x такого, что образ F (?) также неотрицателен и ортогонален
? x
x.
?
Заменяя Rn на произвольный выпуклый конус X, приходим к обобщенной за-
+
даче о дополнительности. Последняя заключается в поиске x ? Rn такого, что
?
x ? X, F (?) ? X ? , F (?) x = 0; (1.6)
? x x?
здесь X ? обозначает конус, двойственный к X, т. е.
X ? = {y ? Rn : y x ? 0 ?x ? X}.
Эту задачу будем обозначать GCP (X, F ).
Между обобщенной (а значит, и нелинейной) задачей о дополнительности и за-
дачей решения вариационного неравенства существует следующая простая связь.
Теорема 1.1. Пусть X — выпуклый конус. Тогда множества решений задач
V I(X, F ) и GCP (X, F ) совпадают
Д о к а з а т е л ь с т в о. 1) Пусть x — решение V I(X, F ), т. е. x ? X и
? ?
F (?) (x ? x) ? 0 ?x ? X. (1.7)
x ?
Покажем, что F (?) ? X ? и F (?) x = 0. Для этого заметим, что конус X вместе
x x?
с любой своей точкой x содержит и все точки вида tx, t ? 0. Подставляя в (1.7)
вместо x вектор tx, получаем
F (?) x ? t?1 F (?) x ?x ? X, t > 0.
x x?
Переходя здесь к пределу по t > ?, имеем F (?) x ? 0 ?x ? X, т. е. F (?) ?
x x
?
X . Чтобы убедиться в равенстве F (?) x = 0, достаточно в последнее неравенство
x?
подставить x = x, а в неравенство (1.7) — точку x = 0.
?
2) Обратно, пусть x — решение GCP (X, F ), т. е. x ? X, F (?) ? X ? и F (?) x =
? ? x x?
0. Тогда
F (?) (x ? x) = F (?) x ? F (?) x ? 0 ?x ? X,
x ? x x?
т. е. x — решение и V I(X, F ).
?
Из теоремы 1.1 следует, что любая обобщенная (и, в частности, нелинейная) зада-
ча о дополнительности есть задача решения некоторого вариационного неравенства.
Обратное в общем случае не верно. Тем не менее в случае, когда X определяется
как множество решений некоторой системы неравенств, т. е.
X = {x ? Rn : gi (x) ? 0, i = 1, . . . , m}, (1.8)
задача V I(X, F ) может быть конвертирована в некоторую обобщенную задачу о
дополнительности.

32
Теорема 1.2. Пусть X определено соотношением (1.8), где все функции gi (x)
непрерывно дифференцируемы. Тогда при выполнении некоторых стандартных
условий регулярности любое решение x задачи V I(X, F ) можно дополнить век-
?
тором ? ? R до решения (?; ? ) задачи GCP (Rn ? Rm ; H), где отображение H
m
? x? +
: Rn+m > Rn+m задается формулой
m
? ?
F (x) + ?i gi (x)
H(x, ?) = ? ?.
i=1
?g(x)

Обратно, если все gi (x) выпуклы и пара (?; ? ) есть решение задачи GCP (Rn ?
x?
m
R+ ; H), то x — решение V I(X, F ).
?
Д о к а з а т е л ь с т в о опирается на уже отмечавшийся простой факт: любое
решение x задачи V I(X, F ) будет одновременно и решением задачи
?

min{ F (?) x : gi (x) ? 0, i = 1, . . . , m}, (1.9)
x
и наоборот, если x — решение задачи (1.9), то x ? Arg V I(X, F ), где X определено
? ?
соотношением (1.8). Поэтому утверждение теоремы есть просто другая формулиров-
ка необходимых условий Куна—Таккера оптимальности точки x в задаче (1.9):
?
m
?F (?) =
x ?i gi (?),
? x
i=1
? = (?1 , . . . , ?m ) ? 0, ?g(?) = (?g1 (?), . . . , ?gm (?)) ? 0,
? ? ? x x x
g(?) ? = 0.
x?

В случае выпуклости функций gi (x), i = 1, . . . , m, эти условия приобретают
также и достаточный характер.
Перечислим несколько простых условий регулярности, обеспечивающих справед-
ливость теоремы Куна—Таккера:
1) все функции gi (x) аффинны;
2) градиенты активных ограничений gi (x) в точке x линейно независимы;
?
3) все функции gi (x) выпуклы, и существует точка x такая, что все gi (?) < 0
? x
(точка Слейтера).
Обобщенная задача о дополнительности из теоремы 1.2 весьма специфична: толь-
ко часть ее переменных неотрицательна, а компоненты H -отображения, соответ-
ствующие остальным переменным, должны равняться нулю. Такие задачи называют
смешанными нелинейными задачами о дополнительности.
Заметим, что все предположения теоремы 1.2 относятся только к функциям gi (x) ;
никаких условий на отображение F не было наложено. Недостатком рассмотренного
приведения V I(X, F ) к задаче о дополнительности является рост числа неизвестных
с n до n + m. С вычислительной точки зрения это может привести к росту затрат
на нахождение искомого решения. Тем не менее такое приведение дает полезный
инструмент анализа V I(X, F ).
Для вывода ряда теорем существования решения V I(X, F ) и развития многих
итерационных методов их отыскания полезно переформулировать задачу решения ва-
риационного неравенства как классическую задачу о неподвижной точке. Для этого
напомним понятие проекции точки на непустое выпуклое замкнутое множество.


33
Пусть X — непустое выпуклое замкнутое подмножество Rn . Под проекцией
точки y ? Rn на множество X, обозначаемой в дальнейшем PX (y), понимают
решение (оптимальный вектор) задачи
min (x ? y) (x ? y).
x?X

Нетрудно убедиться, что неравенство
(PX (x) ? x) (y ? PX (x)) ? 0 ?y ? X (1.10)
является характеристическим свойством введенной таким образом операции проекти-
рования. Из него, в частности, вытекает, что отображение PX (·) — не расширяющее,
т. е.
?x, y ? Rn .
PX (x) ? PX (y) ? x ? y
Кроме того, верно включение
x ? PX (x) ? NX (PX (x)).
Опираясь на понятие проекции, легко установить следующий результат.
Теорема 1.3. Пусть X — непустое выпуклое замкнутое подмножество Rn , ? >
0. Тогда любое решение x задачи V I(X, F ) удовлетворяет условию
?
x = PX (? ? ?F (?)), (1.11)
? x x
и обратно, любая точка x, удовлетворяющая условию (1.11), есть решение
?
V I(X, F ).
Несмотря на свою простоту, это утверждение носит важный характер.
Следствие 1.1. Множество решений V I(X, F ) совпадает с множеством непо-
движных точек отображения H : Rn > Rn , определяемого формулой
H(x) = PX (x ? ?F (x)), ? > 0. (1.12)
В случае нелинейной задачи о дополнительности N CP (F ), т. е. при X = Rn ,
+
отображение (1.12) принимает вид
H(x) = (x ? ?F (x))+ ,
где + над вектором означает замену его отрицательных координат нулями (операция
положительной срезки).
Вернемся к обсуждению вопроса о сведении задач о дополнительности и решении
вариационного неравенства к обычным задачам оптимизации. Как уже отмечалось
для последних, предположение о симметричности F играет критическую роль.
Однако для нелинейных задач о дополнительности имеет место следующий простой
факт.
Теорема 1.4. Пусть F — некоторое отображение Rn в себя. Вектор x ? Rn
?
решает N CP (F ) тогда и только тогда, когда он оптимален для задачи
min{ F (x) x : F (x) ? 0, x ? 0 } (1.13)
и оптимальное значение последней равно нулю.

34
Вообще говоря, допустимая область задачи (1.13) необязательно выпукла. Однако
в случае аффинности F (т. е. в случае линейной задачи о дополнительности) поста-
новка (1.13) есть просто задача квадратичного программирования (необязательно
выпуклого).
Для представления V I(X, F ) в виде оптимизационной задачи большую роль иг-
рает так называемая функция скачка.
Функция скачка (или разрыва) g(x), ассоциированная с V I(X, F ), определяется
формулой
g(x) = max F (x) (x ? y). (1.14)
y?X

Заметим, что g(x) ? 0 при всех x ? X, причем равенство имеет место только на
решениях V I(X, F ). Таким образом, верна
Теорема 1.5. Вектор x ? X есть решение V I(X, F ), если и только если он
?
оптимален для задачи
min g(x) = min max F (x) (x ? y) (1.15)
x?X x?X y?X

и g(?) = 0.
x
Нетрудно видеть, что в случае нелинейной задачи о дополнительности задача
(1.15) сводится к (1.13).
Итак, функция скачка позволяет сформулировать V I(X, F ) как некоторую мини-
максную задачу. К сожалению, подобно большинству задач такого рода, последняя,
вообще говоря, не является гладкой, что затрудняет применение к ней численных
методов решения.
Другие, более привлекательные в вычислительном отношении функции скачка
будут рассмотрены в конце данной главы.

Упражнение
Введем в рассмотрение двойственную задачу решения вариационного неравенства
DV I(X, F ), состоящую в поиске y ? X такого, что
?
F (x) (x ? y ) ? 0 ?x ? X. (1.16)
?
Для этой задачи можно определить свою функцию скачка f (y) по формуле
f (y) = min F (x) (x ? y).
x?X

Покажите, что вектор y ? X есть решение DV I(X, F ), если и только если он
?
оптимален для задачи
max f (y) = max min F (x) (x ? y) (1.17)
y?X y?X x?X

и f (?) = 0.
y
Покажите также, что вектор x ? X есть решение задачи V I(X, F ), а вектор
?
y ? X — задачи DV I(X, F ) в том и только в том случае, когда
?
F (?) (? ? y ) = min max F (x) (x ? y) = max min F (x) (x ? y),
xx?
x?X y?X y?X x?X

т. е. когда пара (?, y ) образует седловую точку функции
x?
?(x, y) = F (x) (x ? y)
относительно декартова произведения X ? X. Воспользуйтесь тем, что значения
минимакса и максимина в задачах (1.15), (1.17) в общем случае различаются знаком.

35
§ 2. Теоремы существования и единственности решения

Основной результат о существовании решений вариационного неравенства V I(X, F )
требует компактности и выпуклости множества X и непрерывности отображения F.
Ряд следствий может быть получен из него путем замены требования компактности
X на дополнительные условия относительно F. Сам результат получается приме-
нением к непрерывному H -отображению из (1.12) теоремы Брауэра о неподвижной
точке. Он формулируется следующим образом.
Теорема 2.1. Пусть X — непустое компактное и выпуклое подмножество Rn ,
F — непрерывное отображение X в Rn . Тогда задача V I(X, F ) разрешима.
В случае неограниченности X (как это имеет место, например, в нелинейной
задаче о дополнительности) можно опираться на условия, заведомо обеспечиваю-
щие ограниченность самого множества потенциальных решений для того, чтобы га-
рантировать наличие хотя бы одного из них. Это достигается различными путями.
Например, можно пытаться указать внутри X такое ограниченное множество D,
вне которого ни одна точка не может быть искомым решением. Строгий результат
выглядит так.
Теорема 2.2. Пусть X — непустое замкнутое и выпуклое подмножество Rn ,
F — непрерывное отображение X в Rn . Если существует такое непустое огра-
ниченное подмножество D множества X, что
?x ? X\D ?y ? D : F (x) (x ? y) > 0, (2.1)
то задача V I(X, F ) разрешима.
Д о к а з а т е л ь с т в о. Пусть B = {x ? Rn : x ? 1} — единичный шар
? ?
в Rn . По предыдущей теореме разрешима задача V I(X, F ), где X — замыкание
множества (D+B)?X — компакт. В силу (2.1), ее решение x лежит в D. Покажем,
?
что оно является и решением V I(X, F ).
В самом деле, по построению
?
F (?) (x ? x) ? 0 ?x ? X.
x ?
?
Пусть теперь x ? X\X. В этом случае ? = x ? x > 1 и вектор y = x + ??1 (x ?
? ?
?
x) ? X. Поэтому также
?
F (?) (x ? x) = ?F (?) (y ? x) ? 0,
x ? x ?
что и требовалось.
В общем случае указать заранее нужное множество D трудно. Однако, если отоб-
ражение F обладает некоторыми дополнительными свойствами, то такое указание
делается возможным. Введем ряд определений.
Отображение F : Rn > Rn называется
а) монотонным на X, если
(F (x) ? F (y)) (x ? y) ? 0 ?x, y ? X;
б) псевдомонотонным на X, если
F (y) (x ? y) ? 0 влечет F (x) (x ? y) ? 0 ?x, y ? X;

36
в) строго монотонным на X, если
(F (x) ? F (y)) (x ? y) > 0 ?x, y ? X, x = y;
г) сильно монотонным на X, если найдется такая константа ? > 0, что
2
(F (x) ? F (y)) (x ? y) ? ? x ? y ?x, y ? X;
д) коэрцитивным по отношению к X, если найдется вектор x ? X такой, что
?
F (x) (x ? x)/ x = ?.
lim ?
x?X, x >?

Заметим, что если отображение F сильно монотонно на X, то оно коэрцитивно
относительно X. Если F (x) = q + M x и X = Rn , то F коэрцитивно только в слу-
чае своей сильной монотонности, что, в свою очередь, эквивалентно положительной
определенности матрицы M. В общем случае, если отображение F непрерывно диф-
ференцируемо, его различные свойства монотонности связаны с положительной по-
луопределенностью и положительной определенностью матриц F. Среди перечис-
ленных свойств наиболее слабым является, очевидно, свойство псевдомонотонности,
затем следуют в порядке усиления свойства монотонности, строгой монотонности и
сильной монотонности.
Хорошо известно, что оптимальное множество задачи выпуклого программирова-
ния выпукло. Следующее утверждение распространяет этот результат на вариацион-
ные неравенства псевдомонотонного типа.
Теорема 2.3. Пусть X — непустое замкнутое выпуклое подмножество Rn
и F — непрерывное псевдомонотонное отображение X в Rn . Точка x решает
?
задачу V I(X, F ) в том и только в том случае, когда x ? X и
?
F (y) (y ? x) ? 0 ?y ? X. (2.2)
?
В частности, множество решений задачи V I(X, F ) выпукло (если не пусто).
Д о к а з а т е л ь с т в о. 1) Пусть x — решение V I(X, F ), т. е. x ? X и
? ?
F (?) (y ? x) ? 0 ?y ? X.
x ?
Эти соотношения, в силу псевдомонотонности отображения F, влекут искомое
F (y) (y ? x) ? 0 ?y ? X.
?
2) Обратно, пусть имеет место (2.2). Зафиксируем произвольно вектор y ? X и
рассмотрим точки вида y? = ?? + (1 ? ?)y, ? ? [0, 1]. Эти точки лежат в X, в силу
x
выпуклости последнего. Отсюда и из (2.2) следует, что
1
F (y? ) (y ? x) = F (y? ) (y? ? x) ? 0
? ?
1??
при всех ? ? [0, 1]. Переходя в левой части к пределу по ? > 1 ? 0, в силу
непрерывности F получаем искомое
F (?) (y ? x) ? 0 ?y ? X.
x ?
Обе части теоремы доказаны.
В общем случае задача V I(X, F ) может иметь более одного решения. Если, од-
нако, отображение F строго монотонно, такое решение единственно (если вообще
существует).

37
Теорема 2.4. Если отображение F строго монотонно на X, то задача V I(X, F )
не может иметь более одного решения.
Д о к а з а т е л ь с т в о. Пусть x и y — два различных решения задачи
V I(X, F ). Тогда
F (x) (y ? x) ? 0 и F (y) (x ? y) ? 0.
Складывая эти два неравенства, получаем
(F (x) ? F (y)) (y ? x) ? 0,
что противоречит предположению о строгой монотонности F.
Ни одно из приведенных утверждений 2.3, 2.4 не гарантирует еще существования
решения задачи V I(X, F ). Общим приемом при выводе такого существования яв-
ляется опора на свойство коэрцитивности отображения F. Это свойство позволяет
выбрать в качестве компакта D, требуемого в теореме 2.2, просто шар достаточно
большого диаметра, пересекающийся с X. Таким образом, существование решения
будет следовать из этой теоремы, и, более того, легко показать, что множество ре-
шений будет компактным.
Теорема 2.5. Пусть X — непустое замкнутое выпуклое подмножество Rn и
F — непрерывное отображение X в Rn . Если F коэрцитивно относительно X,
то задача V I(X, F ) имеет непустое компактное множество решений.
Следующий результат показывает, что условие коэрцитивности можно несколько
ослабить.
Теорема 2.6. Пусть X — непустое замкнутое выпуклое подмножество Rn и
F — непрерывное отображение X в Rn . Если существует вектор x ? X такой,
?
что множество
D0 = {x ? X : F (x) (x ? x) ? 0}
?
ограничено, то множество решений V I(X, F ) не пусто и компактно.
Д о к а з а т е л ь с т в о. Достаточно сослаться на теорему 2.2, взяв в качестве
множества D множество D0 , а в качестве y — вектор x. ?
Поскольку сильная монотонность отображения влечет как коэрцитивность, так
и строгую его монотонность, то, комбинируя теоремы 2.4 и 2.5, можно получить
следующий результат.
Следствие 2.1. Пусть X — непустое замкнутое выпуклое подмножество Rn
и F — непрерывное отображение X в Rn . Если F сильно монотонно на X, то
решение задачи V I(X, F ) существует и единственно.
В случае, когда отображение F монотонно или псевдомонотонно, задача V I(X, F )
может не иметь решения. Однако псевдомонотонности F хватает, если дополнитель-
но для X выполняются условия регулярности (типа Слейтера). Их точная форму-
лировка дана ниже и опирается на понятие двойственного конуса к произвольному
множеству X, который определяется точно так же, как и для выпуклого конуса.
Теорема 2.7. Пусть X — непустое выпуклое замкнутое подмножество Rn
и F — непрерывное отображение X в Rn . Предположим, что F псевдомоно-
тонно на X и существует вектор x ? X такой, что F (?) ? int (X ? ), где
? x
int (·) означает внутренность множества. Тогда задача V I(X, F ) имеет непу-
стое компактное выпуклое множество решений.

38
Д о к а з а т е л ь с т в о. Снова воспользуемся теоремой 2.2. В качестве D
возьмем множество
D1 = {x ? X : F (?) (x ? x) ? 0}. (2.3)
x ?
Это множество не пусто, поскольку содержит x, и ограничено, поскольку F (?) ?
? x
?
int (X ), т. е. ?? > 0 такое, что
x
(F (?) ? ? ) x ? 0 ?x ? X,
x
x
что дает после преобразования F (?) x ? ? x ?x ? X. Выполнимость остальных
x
требований теоремы 2.2 к множеству D1 следует из (2.3) и псевдомонотонности F.

В случае нелинейной задачи о дополнительности приведенные выше результаты
можно усилить, благодаря специфике постановки последней.
Теорема 2.8. Пусть отображение F : Rn > Rn непрерывно и
+ +

F (x) x ? 0 ?x ? CR , (2.4)
n
Rn
где CR = { x ? xi = R }, R > 0. Тогда задача N CP (F ) разрешима.
:
+
i=1 n
Rn
Д о к а з а т е л ь с т в о. Обозначим CR = { x ? xi ? R }. В силу
:
+
i=1
ограниченности, замкнутости и выпуклости этого множества существует x ? CR
?
такое, что
F (?) (x ? x) ? 0 ?x ? CR . (2.5)
x ?
Поскольку CR содержит ноль, то
F (?) x ? 0. (2.6)
x?
Далее, существует ? > 0 такое, что x = ?ei ? CR при всех i = = 1, . . . , n (здесь
ei — i -й единичный орт). Подставляя эти векторы в (2.5), получаем
1
Fi (?) ? при всех i = 1, . . . , n. (2.7)
x x F (?)
? x
?
Рассмотрим два случая.
1) Пусть x ? CR . Из условия (2.4) и из (2.6), (2.7) вытекает F (?) x = 0, F (?) ?
? x? x
0, т. е. x — решение N CP (F ).
?
2) Пусть x ? CR . Для каждого i = 1, . . . , n существует t > 0 такое, что x =
?/
x + tei ? CR . Подставляя эти точки в (2.5), получаем неравенства Fi (?) ? 0 ?i.
? x
Снова из (2.6) следует, что x — решение задачи N CP (F ).
?
Заметим, что в качестве множества CR в только что доказанной теореме можно
использовать пересечение Rn с шаром радиуса R. Доказательство не изменится.
+
Перейдем к рассмотрению обобщенной задачи о дополнительности.
Конус X называется острым, если X ?(?X) = {0}, и телесным, если int (X) =
?.
Допустимым множеством обобщенной задачи о дополнительности GCP (X, F )
называется множество
?(X, F ) = {x ? X : F (x) ? X ? }.
Векторы из ?(X, F ) называются допустимыми; допустимой называется и задача
GCP (X, F ), если ее множество ?(X, F ) не пусто.

39
Лемма 2.1. Пусть X — острый замкнутый выпуклый телесный конус в Rn
и d ? Rn . Тогда включение d ? int (X ? ) эквивалентно любому из следующих
условий:
1) x d > 0 при всех 0 = x ? X ;
2) множества S(d; ?) = {x ? X, 0 ? d x ? ?} ограничены при всех ? > 0.
Д о к а з а т е л ь с т в о. 1) Пусть от противного d ? int (X ? ), но существует
0 = x ? X такой, что d x = 0. Поскольку d — внутренняя точка X ? , то при малом
? ?
? > 0 точка d??? также лежит в X ? , что приводит к противоречивому неравенству
x
2
0 ? (d ? ??) x = d x ? ? x
x? ? ? < 0.
Обратно, если x d > 0 при всех 0 = x ? X, но d — граничная точка X ? , то
найдется последовательность точек {d k } > d такая, что выполняются неравенства
d k ? X ? , т. е. при некоторых xk ? X
/
(d k ) xk < 0. (2.8)
Поскольку X — замкнутый конус, то, не теряя общности, можно считать, что
x = 1 ?k, причем {xk } > x, x = 1, x ? X. Поэтому при переходе в (2.8) к
k
?? ?
пределу по k > ?, имеем d x ? 0, что противоречит постулированному в условии
?
свойству вектора d. Следовательно, d ? int (X ? ).
2) Пусть от противного d ? int (X ? ), но множество S(d; ?) не ограничено, т. е.
существует последовательность его точек {xk } такая, что {xk } > ?. Определим
?1
y k = xk xk ? X.
Для точек этой последовательности имеем
?1 ?1
d y k = xk d xk ? ? xk (2.9)
.
Поскольку y k = 1 ?k, то существует подпоследовательность {y kS }, сходящаяся
к некоторому y ? X, и для этого y предельным переходом в (2.9) получаем нера-
? ?
венство d y ? 0. По первой части доказываемой теоремы это и означает, что d —
?
граничная точка X ? .
Обратно, пусть все множества S(d; ?) — компактны. Предположим от противного,
что d ? int (X ? ). По первой части теоремы существует 0 = x ? X такой, что
/ ?
d x = 0. Но тогда, как легко видеть, ?? ? S(d; ?) при всех ? > 0, что противоречит
? x
условию ограниченности множеств S(d; ?).
Монотонное отображение F : X > Rn назовем правильным в точке x ? X, если
?
множество
B(?) = {x : x ? x ? X, F (x) ? F (?) ? X ? , (x ? x) (F (x) ? F (?)) = 0}
x ? x ? x
ограничено.
Теорема 2.9. Пусть X — острый выпуклый замкнутый и телесный конус в
Rn , отображение F непрерывно и монотонно на X. Если задача GCP (X, F )
имеет допустимую точку x, в которой F правильно, то она имеет и решение.
?
Д о к а з а т е л ь с т в о. Возьмем любую точку d ? int (X ? ). Определим
множества
S k = {x : x ? x ? X, (x ? x) d = k}, k = 1, 2, . . . .
? ?

40
Так как все эти множества не пусты, выпуклы и компактны, а отображение F (x) =
F (x) ? F (?) непрерывно на них, то по теореме 1.1 разрешимы задачи V I(S k , F ), т. е.
x
существуют xk ? S k такие, что

(F (xk ) ? F (?)) x ? (F (xk ) ? F (?)) xk ?x ? S k .
x x

Вычитая из обеих частей этого неравенства значение (F (xk ) ? F (?)) x, в силу моно-
x?
тонности F получаем
(F (xk ) ? F (?)) (x ? x) ? (F (xk ) ? F (?)) (xk ? x) ? 0 ?x ? S k .
x ? x ?

Последнее означает, что F (X k ) ? F (?) ? X ? . Но поскольку F правильно в точке
x
k
x, а последовательность {x } не ограничена по построению, то найдется номер m
?
такой, что

(F (xm ) ? F (?)) (x ? x) ? (F (xm ) ? F (?)) (xm ? x) > 0 ?x ? S k .
x ? x ?

Поэтому по предыдущей теореме F (xm ) ? F (?) ? int (X ? ), что, ввиду выпуклости
x
конуса X ? , означает F (xm ) ? int (X ? ). А так как всякое монотонное отображение
псевдомонотонно, то осталось сослаться на теорему 2.7.

Следствие 2.2. Пусть X — острый выпуклый замкнутый телесный конус
в Rn , отображение F непрерывно и строго монотонно на X. Если задача
GCP (X, F ) допустима, то она имеет решение, и оно единственно.
Аналогично обобщенной задаче о дополнительности допустимым
множеством нелинейной задачи о дополнительности N CP (F ) называется множе-
ство
?(F ) = {x ? Rn : F (x) ? Rn }.
+ +

Векторы из ?(F ) называются допустимыми; допустимой называется и задача
N CP (F ), если ее множество ?(F ) не пусто.
Следующее утверждение является следствием теоремы 2.9, но и его прямое дока-
зательство не лишено интереса.

Теорема 2.10. Если отображение F непрерывно и строго монотонно на Rn , +
а ?(X, F ) не пусто, то задача N CP (F ) разрешима, и ее решение единственно.
Д о к а з а т е л ь с т в о. По предположению найдется x ? 0 такое, что F (?) ? 0.
? x
Если F (?) > 0, то можно сразу воспользоваться теоремой 2.7. В противном случае
x
покажем, что можно от x перейти к точке x1 с меньшим числом нулевых компонент
?
в образе F (x1 ). Действительно, пусть Fk (?) = 0. Рассмотрим точки x? = x + ?ek ,
x ?
где ? > 0, ek — k -й единичный орт. В силу строгой монотонности F имеем

(F (x? ) ? F (?)) (x? ? x) = ?(Fk (x? ) ? Fk (?)) > 0,
x ? x

откуда Fk (x? ) > 0 при всех ? > 0. Остается выбрать ? > 0 настолько малым, чтобы
те Fi (x? ), что были положительны в точке x, остались бы таковыми. Найденную
?
точку обозначим через x1 . Если F (x1 ) > 0, обращаемся к теореме 2.7, в противном
случае повторяем описанную процедуру снова.
Приведем аналоги свойств монотонности, используемые при анализе нелинейных
задач о дополнительности.

41
Отображение F : R+ > Rn называется
N

а) коположительным, если
(F (x) ? F (0)) x ? 0 ?x ? Rn ;
+

б) строго коположительным, если
(F (x) ? F (0)) x > 0 ?x ? Rn , x = 0;
+

в) сильно коположительным, если существует число ? > 0 такое, что
2
?x ? Rn .
(F (x) ? F (0)) x ? ? x +

Поскольку сильно коположительное отображение коэрцитивно относительно Rn ,+
то по теореме 2.5 задача N CP (F ) с сильно коположительным отображением всегда
имеет непустое компактное множество решений. Если F лишь строго коположи-
тельно, то верен следующий результат.
Теорема 2.11. Пусть отображение F : Rn > Rn непрерывно и строго кополо-
+
жительно. Если существует числовая функция
c : R+ > R такая, что c(?) > ? при ? > ? и
(F (?x) ? F (0)) x ? c(?) (F (x) ? F (0)) x
при всех ? ? 1, x ? 0, то N CP (F ) имеет непустое компактное множество
решений.
(F (x) ? F (0)) x
Д о к а з а т е л ь с т в о. Обозначим ?1 = и
min ?2 =
x =1, x?0
F (0) x. В силу непрерывности и строгой коположительности отображения
max
x =1, x?0
F имеем ?1 > 0. Пусть x ? Rn , x = 0. По предположению
+

x x
(F (x) ? F (0)) x = F ? F (0) ?
x x
x x
x x
? c( x ) F ? F (0) ? c ( x ) x ?1 .
x
x x
Отсюда
x
F (x) x ? c( x ) x ?2 + F (0) x ? (c( x )?1 ? ?2 ) x .
x
Правая часть этого неравенства неограниченно растет при x > ?. Следовательно,
множество
{x ? Rn : F (x) (x ? 0) ? 0}
+

ограничено, и можно сослаться на теорему 2.6, полагая в ней x = 0.
?
Закончим раздел результатами о локальной единственности решений задач о до-
полнительности и вариационных неравенств, получаемых без предположений типа
монотонности.
Решение x задачи V I(X, F ) называется локально единственным (или изолиро-
?
ванным), если существует окрестность N точки x такая, что x — единственное
? ?
решение V I(X, F ) в N.
Следующий результат дает достаточные условия локальной единственности реше-
ния вариационного неравенства.

42
Теорема 2.12. Пусть F — непрерывно дифференцируемое отображение Rn
в себя и x — решение V I(X, F ). Если матрица Якоби F (?) положительно
? x
определена, это решение будет локально единственным.
Д о к а з а т е л ь с т в о. Выделим окрестность N точки x, в которой матрицы
?
F (x) положительно определены (такая окрестность существует, поскольку матри-
ца F (x) непрерывна и положительно определена в точке x ). В этой окрестности
?
x — единственное решение V I(X, F ).
?
В самом деле, пусть от противного y — другое такое решение из N. По опреде-
?
лению решения
F (?) (? ? x) ? 0 и F (?) (? ? y ) ? 0,
xy? yx?
откуда
(F (?) ? F (?)) (? ? y ) ? 0.
x y x?
Но, опираясь на функцию
?(t) = (? ? y ) F (x(t)), где x(t) = t? + (1 ? t)?, t ? [0, 1],
x? x y
и на ее производную, равную
? (t) = (? ? y ) F (x(t)) (? ? y ) > 0,
x? x?
легко получить противоположное неравенство
(F (?) ? F (?)) (? ? y ) =
x y x?
1
= ?(1) ? ?(0) = (? ? y ) F (x(t)) (? ? y )dt > 0.
x? x?
0
Это противоречие и завершает доказательство.
Теорема 2.12 не оговаривает специальных свойств множества X. Если, однако,
это множество задано системой неравенств типа (1.8), условия положительной опре-
деленности F (?) можно ослабить. Следующий результат обобщает достаточные
x
условия оптимальности второго порядка, известные для оптимизационных постано-
вок.
Теорема 2.13. Пусть отображение F : Rn > Rn непрерывно дифференци-
руемо, множество X определено как в (1.8), где все функции gi (x) дважды
непрерывно дифференцируемы, и x — решение задачи V I(X, F ). Предположим
?
также, что существует вектор ? ? Rn такой, что
?
m
F (?) +
x ?i
? gi (?) = 0,
x
(2.10)
i=1
?i ? 0, ?i gi (?) = 0 ?i = 1, . . . , m,
? ? x
и, кроме того,
m
2
(2.11)
z F (?) +
x ?i
? gi (?) z > 0
x
i=1
при всех z = 0 таких, что
?i ? I1 = {i : ?i > 0},
z gi (?) = 0
x ?
gi (?) ? 0 ?i ? I2 = {i : gi (?) = 0, ?i = 0}.
z x x ?
Тогда x —локально единственное решение V I(X, F ).
?

43
Д о к а з а т е л ь с т в о. Пусть от противного существует сходящаяся к x
?
k k k
последовательность {x }, где x ? X, x = x и
?
F (xk ) (x ? xk ) ? 0 ?x ? X. (2.12)
Определим последовательность векторов {y k } и чисел {?k } таких, что xk = x +?k y k ,
?
k k
где y = 1, ?k > 0. Поскольку x ? X, то
gi (xk ) ? gi (?) ? 0 ?i : gi (?) = 0; (2.13)
x x
F (?) (xk ? x) ? 0. (2.14)
x ?
Не ограничивая общности, можно считать, что ?k > 0, y k > y , причем y = 1.
? ?
Поделив обе части в (2.13) на ?k и перейдя затем к пределу по k > ?, получим
gi (?)? ? 0 ?i : gi (?) = 0.
xy x
Из (2.14) следует, что
F (?) y k ? 0 ?k, (2.15)
x
а из (2.12) — что
F (?) y k ? 0 ?k. (2.16)
x
Поэтому
F (?) y k = 0 ?k. (2.17)
x
Пусть найдется такой номер m, что ?m > 0 и gm (?)? > 0. Из (2.10) следует
? xy
m
F (?) y = ?
x?? g(?) y =
x? ?i
? gi (?) y > 0,
x?
i=1

что противоречит (2.17). Значит,
?i : ?i > 0. (2.18)
gi (?)? = 0,
xy ?
Далее по теореме о среднем
k
? ?
F1 (?1 )
F (xk ) = F (?) + ?k ? . . . ? yk . (2.19)
x
k
Fn (?n )
В силу (2.16), из (2.19) вытекает
k
? ?
F1 (?1 )
F (?) y k + ?k y k ? . . . ? y k ? 0,
x
k
Fn (?n )
откуда, ввиду (2.15), уже следует
k
? ?
F1 (?1 )
?k y k ? . . . ? y k ? 0.
k
Fn (?n )
Поделив обе части полученного неравенства на ?k > 0 и перейдя к пределу по
k > ?, получим
F (?)? ? 0,
y
? xy

44
что противоречит условию (2.11).
Два последних утверждения можно отнести и к нелинейной задаче о дополнитель-
ности. Но, благодаря специальной структуре последней, справедливо более сильное
утверждение (приводится без доказательства).
Теорема 2.14. Пусть отображение F : Rn > Rn непрерывно дифференцируемо
и x — решение N CP (F ). Определим индексные наборы I+ = {i : xi > 0} и I0 =
? ?
{i : xi = 0, Fi (?) = 0} и отвечающие им подвекторы
? x

xI+ = {xi : i ? I+ }, xI0 = {xi : i ? I0 },
FI+ (x) = {Fi (x) : i ? I+ } и FI0 (x) = {Fi (x) : i ? I0 }.
Если нет ненулевых векторов (xI+ , xI0 ), удовлетворяющих условиям

I+ FI+ (?) xI+
x + I0 FI+ (?) xI0
x = 0,

? 0,
I+ FI0 (?) xI+
x + I0 FI0 (?) xI0
x
xI0 ? 0 и xI0 ( I0 FI0 (?)xI+
x + I0 FI0 (?)xI0 )
x = 0,
то x — локально единственное решение N CP (F ). Здесь обозначает
? N FI (x)
I ? N –блок матрицы F.

Важный частный случай описывается равенством I0 = ?.
Говорят, что решение x задачи N CP (F ) удовлетворяет условию строгой допол-
?
нительности, если x + F (?) > 0. В этом случае решение x называют невырожден-
? x ?
ным.
Теорема 2.15. Пусть отображение F : Rn > Rn непрерывно дифференцируемо
и x — невырожденное решение N CP (F ). Пусть I+ = {i : xi > 0}. Если матрица
? ?
I+ FI+ (?) не вырождена, то x — локально единственное решение N CP (F ).
x ?

Д о к а з а т е л ь с т в о следует непосредственно из классической теоремы
о неявной функции, так как в условиях невырожденности нелинейная задача о до-
полнительности сводится к системе нелинейных уравнений в некоторой окрестности
решения.

Упражнения
1. Покажите, что функция расстояния dX (x) от точки x до выпуклого замкнутого
множества X выпукла и x ? PX (x) ? ?dX (x).
2. Покажите, что дифференцируемая функция f : Rn > R выпукла, псевдовы-
пукла, строго выпукла и сильно выпукла тогда и только тогда, когда отображение
F = f монотонно, псевдомонотонно, строго монотонно и сильно монотонно соот-
ветственно.
3. Покажите, что отображение F = ( 1 f, ? 2 f ), порождаемое дифференцируе-
мой функцией двух аргументов f : Rn ? Rm > R, будет монотонным тогда и только
тогда, когда функция f (x, y) при фиксированном значении второго аргумента выпук-
ла по первому аргументу и при фиксированном значении первого аргумента вогнута
по второму. Установите также связь между строгой и сильной монотонностью отоб-
ражения F и свойствами строгой и сильной выпуклости-вогнутости функции f по
ее аргументам.

45
4. Покажите, что аффинное отображение F (z) = q + M z всюду строго моно-
тонно (просто монотонно) тогда и только тогда, когда матрица M положительно
определена (полуопределена).
5. Покажите, что для аффинных отображений понятия строгой и сильной моно-
тонности совпадают.
6. Покажите, что дважды непрерывно дифференцируемая функция f : Rn > R
выпукла (сильно выпукла) тогда и только тогда, когда матрица ее вторых производ-
ных H(x) = (? 2 f (x)/?xi ?xj )n?n всюду положительно полуопределена (равномерно
положительно определена, т. е. удовлетворяет условию z H(x)z ? ? > 0 ?z, z = 1,
где ? не зависит от x ).
7. Пусть отображение F : S > Rn непрерывно на
n
S = {x ? Rn : x ? 0, xi = 1}.
i=1

Покажите, что существует точка x ? S, удовлетворяющая условиям:
?
a) F (?) (x ? x) ? 0 при всех x ? S ;
x ?
b) xk > 0 ? Fk (?) = mini Fi (?) = µ0 ;
? x x
c) Fk (?) > µ0 ? xk = 0.
x ?

§ 3. Проекционные методы решения

Обратимся к методам решения вариационных неравенств и нелинейных задач о
дополнительности. Начнем с итерационных методов первого порядка, т. е. методов,
не предполагающих дифференцируемости входящих в них отображений. Изложение
будем вести для более общей задачи — задачи решения вариационного неравенства
V I(X, F ).
Первым рассмотрим итерационный процесс, порождаемый следующими рекур-
рентными соотношениями:
xk+1 = PX (xk ? ?F (xk )), k = 0, 1, . . . , (3.1)
где x0 ? X — произвольное начальное приближение; PX (·) — операция проектиро-
вания на множество X; ? > 0 — параметр.
Операция проектирования на множество X относится к обычным оптимизаци-
онным задачам и подробно здесь не обсуждается. Ее реализация может оказаться
трудной, но часто оказывается и простой. В частности, в задачах о дополнительно-
сти N CP (F ), где X = Rn , она решается взятием положительной срезки координат
+
проектируемого вектора. На практике в сложных случаях проектирование осуществ-
ляется приближенно, а его точность согласуется с другими параметрами алгоритма.
Процесс (3.1) можно рассматривать как метод простой итерации для поиска непо-
движной точки проекционного отображения H из (1.12). Как показывает следующее
утверждение, он сходится глобально, но лишь при достаточно сильных предположе-
ниях относительно монотонности и непрерывности отображения F.
Теорема 3.1. Пусть X — непустое выпуклое замкнутое подмножество Rn и
пусть отображение F : X > Rn сильно монотонно с константой ? > 0, т. е.
2
(F (x) ? F (y)) (x ? y) ? ? x ? y ?x, y ? X,
и удовлетворяет условию Липшица с константой L > 0, т. е.
F (x) ? F (y) ? L x ? y ?x, y ? X.

46
Тогда вариационное неравенство V I(X, F ) разрешимо, и при любом 0 < ? <
2?L?2 последовательность, порожденная процессом (3.1), сходится к x — его
?
единственному решению, причем скорость этой сходимости линейна: найдется
< 1 такое, что
xk+1 ? x ? xk ? x
? ?
при всех k.

Д о к а з а т е л ь с т в о. По теореме 1.3 из данной главы точка x удовлетворяет
?
равенству
x = PX (? ? ?F (?)) ?? > 0.
? x x
Поэтому, в силу свойств нерасширяемости оператора проектирования и соотношений
(3.1),
xk+1 ? x 2 = PX (xk ? ?F (xk )) ? PX (? ? ?F (?)) 2 ?
? x x
? xk ? ?F (xk ) ? x + ?F (?) 2
? x =
= xk ? x 2
+ ?2 F (xk ) ? F (?) 2
? 2?(F (xk ) ? F (?)) (xk ? x).
? x x ?
Здесь, в силу липшицевости и сильной монотонности F, имеем

F (xk ) ? F (?) ? L xk ? x ,
x ?

?(F (xk ) ? F (?)) (xk ? x) ? ?? xk ? x 2 .
x ? ?
Поэтому окончательно

xk+1 ? x 2
? (1 + ?2 L2 ? 2??) xk ? x 2 ,
? ?

где 0 < 1 + ?2 L2 ? 2?? < 1 при 0 < ? < 2?L?2 . Это доказывает искомые свойства
сходимости с = (1 + ?2 L2 ? 2??)1/2 .
Метод проекции можно применять не только для решения вариационных нера-
венств и нелинейных задач о дополнительности, но и для решения линейных задач
о дополнительности, матрицы которых положительно определены. Действительно,
аффинное отображение F (x) = q + M x всегда является липшицевым, а в слу-
чае положительно определенной матрицы будет и сильно монотонным с константой
? = max x M x.
x =1
Заметим, что на практике константы ? и L редко известны заранее, и потому
шаговый параметр ? подбирают экспериментально, например, постепенным дробле-
нием некоторого начального ?0 > 0.
Если отображение F липшицево и монотонно, но не сильно монотонно (например,
матрица в линейной задаче о дополнительности только положительно полуопределе-
на, но не положительно определена), метод простой итерации не гарантирует получе-
ние искомого решения. В этом случае исходную задачу V I(X, F ) можно подвергнуть
так называемой регуляризации, т. е. заменить на некоторую близкую задачу, об-
ладающую предпочтительными вычислительными свойствами, например, на задачу
V I(X, F? ), где F? (x) = F (x) + ?x, ? > 0 — малый параметр. Очевидно, отображе-
ние F? не только наследует свойства липшицевости и монотонности отображения F,
но и приобретает свойство сильной монотонности, в силу чего сходимость процесса
(3.1) для регуляризованной задачи имеет место. Разумеется, предельная точка про-
цесса будет решать совсем другую задачу, а именно задачу V I(X, F? ). Обоснование
методу регуляризации дает

47
Теорема 3.2. Пусть X — непустое выпуклое замкнутое подмножество Rn ,
отображение F : X > Rn непрерывно и монотонно на X. Тогда для любого
? > 0 существует решение регуляризованной постановки, т. е. точка x(?) ? X
такая, что
(F (x(?)) + ?x(?)) (x ? x(?)) ? 0 ?x ? X, (3.2)
и если задача V I(X, F ) разрешима, то
(3.3)
lim x(?) = x,
?
?>+0

где x = arg — нормальное решение V I(X, F ).
? min x
x?Arg V I(X,F )

Д о к а з а т е л ь с т в о. Разрешимость задачи (3.2) вытекает из уже от-
мечавшегося свойства сильной монотонности отображения F? . Сосредоточимся на
обосновании соотношения (3.3).
Отметим вначале, что, в силу непустоты, выпуклости и замкнутости множества
Arg V I(X, F ), его минимальный по норме элемент x (нормальное решение) суще-
?
ствует и является единственным. Он удовлетворяет условию
F (?) (x ? x) ? 0 ?x ? X.
x ?
Подставим сюда x = x(?) и x = x — в соотношение (3.2). Складывая полученное,
?
приходим к неравенству
(F (x(?)) + ?x(?) ? F (?)) (? ? x(?)) ? 0.
x x
После перегруппировки слагаемых имеем
?x(?) (? ? x(?)) ? (F (?) ? F (x(?))) (? ? x(?)).
x x x
Далее, в силу монотонности F правая часть этого неравенства неотрицательна,
следовательно, неотрицательна и левая и потому
x(?) x ? x(?) 2 .
?
2
?x
Отсюда x(?) , т. е.
x(?) ?
x(?) ? x . (3.4)
?
Таким образом, последовательность {x(?)}, где ? > +0, является ограниченной
и имеет предельные точки. Последние являются решением V I(X, F ), в чем легко
убедиться путем перехода в соотношениях (3.2) к пределу по сходящимся подпосле-
довательностям. Но, в силу (3.4) и единственности минимального элемента x, все
?
такие предельные точки совпадают и равны этому элементу.
Процесс постепенного уменьшения параметра регуляризации можно и целесооб-
разно совместить с процессом решения регуляризованного неравенства. Это сообра-
жение реализуется в методе итеративной регуляризации А.Б.Бакушинского, соотно-
шения которого имеют вид
xk+1 = PX (xk ? ?k (F (xk ) + ?k xk )), (3.5)
k = 0, 1, 2, . . . ,
здесь x0 ? X — произвольное начальное приближение к решению, PX (·) — опера-
ция проектирования на множество X, положительные параметры ?k , ?k согласо-
ванно меняются в ходе вычислений.
Прежде чем сформулировать условия сходимости метода итеративной регуляри-
зации, докажем ряд вспомогательных утверждений.

48
Лемма 3.1. Пусть X — непустое выпуклое замкнутое подмножество Rn ,
отображение F : X > Rn непрерывно и монотонно на X и задача V I(X, F )
разрешима. Пусть x(?) — решение V I(X, F? ), где F? (x) = F (x) + ?x, ? > 0.
Тогда
x(? ) ? x(? ) ? x (? ? ? )/? ,
?
где x — нормальное решение V I(X, F ), ? > ? > 0 — любые.
?
Д о к а з а т е л ь с т в о. Точка x(? ) удовлетворяет неравенствам
(F (x(? )) + ? x(? )) (x ? x(? )) ? 0 ?x ? X,
а точка x(? ) — неравенствам
(F (x(? )) + ? x(? )) (x ? x(? )) ? 0 ?x ? X.
Подставляя x = x(? ) в первое из них и x = x(? ) — во второе и складывая
полученное, имеем
(F (x(? )) + ? x(? ) ? F (x(? )) ? ? x(? )) (x(? ) ? x(? )) ? 0.
Отсюда
(? x(? ) ? ? x(? )) (x(? ) ? x(? )) ?
? (F (x(? )) ? F (x(? ))) (x(? ) ? x(? )).
Правая часть этого неравенства неотрицательна ввиду монотонности F. Поэтому
левая часть также неотрицательна. Используем это в следующей оценке:
2
? x(? ) ? x(? ) =
= (? x(? ) ? ? x(? )) (x(? ) ? x(? )) + (? ? ? )x(? ) (x(? ) ? x(? )) ?
? (? ? ? ) · x(? ) · x(? ) ? x(? ) .
Остается применить соотношение (3.4).
Лемма 3.2. Пусть отображение F монотонно и удовлетворяет условию Лип-
шица с константой L > 0, т. е.
F (x) ? F (y) ? L x ? y ?x, y ? X.
x ??F? (x )?x +?F? (x ) ? (1?r(?, ?)) x ?x , где F? = F (x)+?x, ? >
Тогда
0, r(?, ?) = ?? ? ?2 (L + ?)2 /2.
Д о к а з а т е л ь с т в о. В силу монотонности и липшицевости отображения F
имеем
x ? ?F? (x ) ? x + ?F? (x 2 =
2
+ ?2 F? (x ) ? F? (x ) 2
= x ?x ? 2?(F? (x ) ? F? (x )) (x ? x ) ?
2
+ ?2 ( F (x ) ? F (x ) + ? x ? x )2 ? 2?? x ? x 2
? x ?x ?
? (1 + ?2 (L + ?)2 ? 2??) x ? x 2 .
v
Отсюда, ввиду неравенства 1 + a ? 1 + a/2, следует требуемое утверждение.

Следующее утверждение хорошо известно из теории оптимизации ([9], с.96) и
потому приводится без доказательства.

49
Лемма 3.3. Пусть числовая последовательность {?k } удовлетворяет соот-
ношениям
0 ? ?k+1 ? (1 ? ?k )?k + ?k (k = 0, 1, 2, . . .),
?
?1
где ?k ? (0, 1], ?k > 0, ?k = ?, lim ?k ?k = 0. Тогда lim ?k = 0.
(k) (k)
k=1

Сформулируем теперь основной результат сходимости для метода итеративной
регуляризации.
Теорема 3.3. Пусть X — непустое выпуклое замкнутое подмножество Rn ,
отображение F : X > Rn монотонно и удовлетворяет на X условию Липшица
с константой L > 0, т. е.
F (x) ? F (y) ? L x ? y ?x, y ? X.
Если задача V I(X, F ) разрешима, а параметры метода удовлетворяют услови-
ям ?
?k > +0, ?k > ?k+1 > 0, ?k > +0, ?k ?k = ?, (3.6)
k=1
?1
2
?0 = 1/L2 ,
?k = (?k ? ?k+1 )/(?k ?k ) > 0, 0 < (3.7)
?k ?k <
то последовательность (3.5) сходится к одному из ее решений.
Д о к а з а т е л ь с т в о. Обозначим через xk решения задач V I(X, Fk ), где
?
Fk (x) = F (x) + ?k x. Напомним, что по теореме 1.3 из данной главы

<<

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

СОДЕРЖАНИЕ

>>