книги из ГПНТБ / Балакришнан, А. Введение в теорию оптимизации в гильбертовом пространстве

Выпуклые множества в гильбертовых пространствах

79

(т. е. множество последовательностей, все члены которых неположительны). Тогда рассматриваемую задачу молено сформулировать в следующем виде.

Минимизировать функционал /(х)

при ограничениях

х е С, где множество С (как и раньше) выпукло,

и

Р(х)е/Ѵ , где отображение Р (х) (по предположению) выпукло.

К сожалению, для этой новой задачи теорема Куна — Таккера уже не проходит. Повторяя ее доказательство, определим прежде всего множества

A = {{y>z): y ^ f ( x ) , z —Р(х)<=Р для некоторого х е С},

В = {(У, г): У < Ң х 0), zeA f),

где, как и раньше, х0 — минимизирующая точка. Но теперь, к сожалению, из того, что множества А и В не пересекаются, еще не следует, что их можно отделить. Ведь и у А и у В может не быть внутренних точек. Действительно, известно, что у N внутренних точек нет. Тем не менее возможно по крайней мере одно обобщение теоремы Куна — Таккера, хотя его содержа­ тельная ценность не слишком ясна. Обозначим через Y

гильбертово пространство, содержащее замкнутый										вы­
пуклый конус Р. Введем в Y						отношение	порядка:			для
любых двух		элементов х, у из Y
			X	у,	если X — у е Р.
(Это	действительно			отношение		порядка,	так		как	если
х ^ у	и y ^ z ,		то	X — г/е=Р, у — z е			Р,	а	в	силу
выпуклости		конуса		Р	элемент	(х — у) + (у — z) также
принадлежит		Р,	т.	е.	x ^ z .)	Далее, конус		Р теперь

можно охарактеризовать так:

Р = { х е Т х>0}.

Этот конус можно назвать положительным, а отрица­ тельным конусом N будет просто множество (— Р):

N = {х е Y: х < 0}.

80

Глава 2

Пользуясь введенным упорядочением, определяем обыч­ ным образом выпуклое отображение. Если внутренность конуса N не пуста, то можно теперь сформулировать обобщение теоремы Куна — Танкера на случай беско­ нечного числа ограничений [13].

Т е о р е м а 2.5. (Бесконечномерный вариант теоремы Куна — Танкера.) Пусть С — выпуклое множество в гиль­ бертовом пространстве Н, а f (х) — вещественный вы­ пуклый функционал, определенный на С. Обозначим через Y гильбертово пространство, содержащее замкну­

тый выпуклый конус Р с	непустой ' внутренностью,
а через F (х) — отображение	из Н в Y, выпуклое отно­

сительно упорядочения, индуцированного конусом Р. Пусть х0— точка минимума функционала f(x) на мно­ жестве С при ограничениях

F (x )< 0.
Тогда в двойственном конусе Р' найдется				такой эле­
мент о, что для любого х из С
f(x) + [о, £ (х )]> /(х 0) +	[о, F(x0)] > f{ x 0) +			[u, F(x0)],
где и — любой элемент	в	Р*, для	которого выполнено
условие допустимости, т.	е.	и ^ Р *	и х е С таковы, что
[и, F{x)} < 0.
Д о к а з а т е л ь с т в о .	Доказательство			проводится

так же, как и раньше. Прежде всего построим под­ множества А и В в пространстве £ , ХТ:

А = {(а, у):	a ^ f ( x ) ,	y ^ F ( x ) для некоторого х е С},
£ = { (« , У)-	a ^ f ( x Q),	0}.

Заметим, что в гильбертовом пространстве £, X У эти множества отделимы, так как внутренность множества В не пуста и не пересекается с А f| В. Поэтому найдутся такое число а0 и такой элемент оеК , что для любого хеС

а</ (*) + [»> F (*)] > a0f (*о) — [о. Р]

для всех р из Р.	А так	как левая часть этого нера­
венства не равна	-)- оо,	то [п, р ] ^ 0 для любого р
из Р, т. е. Vе Р*,

Выпуклые множества в гильбертовых пространствах

81

Оставшаяся часть доказательства в точности повто­ ряет ход рассуждений, использованных при доказатель­ стве теоремы Куна — Таккера в конечномерном случае, и потому мы ее не приводим.

Для случая бесконечного числа ограничений можно предложить и аналог теоремы Лагранжа о двойствен­ ности:

/(*o)+ sup		inf (f(x)-\-[v, F(x)]).
	te P '	x e C
З а д а ч а 2.3.	Пусть х0— фиксированный элемент
из Я и Р — конус,	натянутый на		множество
	II	* — х0II ^	пг < оо } .

Покажите, что двойственным конусом Р* будет множество

{о: [о, х0] > т || ѵ ||}.

С помощью теоремы Куна — Таккера найдите минимум функционала || x — h ||2, где h — фиксированный элемент из Я, при ограничении x ^ z (z — фиксированный эле­ мент из Я); роль положительного конуса играет Р.

Задача векторной максимизации

Пусть Р — положительный конус (в гильбертовом пространстве Y) с непустой внутренностью, а F(x) и G (х) — вогнутые функции относительно упорядочения, индуцированного конусом Р, отображающие гильбертово пространство X в Y. Требуется максимизировать „век­ торный критерий“ G(•) при ограничениях

х е С, F (x )^ 0 ,

где С — выпуклое множество в Y. Поскольку упорядо­ чение, индуцированное Р, является лишь частичным, прежде всего необходимо модифицировать само понятие максимума, Будем называть точку х0 эффективной, если она удовлетворяет ограничениям задачи и нет другой такой удовлетворяющей этим ограничениям точки х, что

Q (х) > G (х0).

82

Глава 2

Очевидно, что эффективных точек может быть много. Однако эффективные точки можно охарактеризовать как точки обычного максимума соответствующих число­ вых функций.

Т е о р е м а 2.6. Пусть С — выпуклое множество в Y, а х0— эффективная точка для G(x). Тогда в Р* найдется такой элемент о0, что при ограничении Н (х) ^ О

шах К , G ( x )] = [ü0, G(x0)].

хе С

До к а з а т е л ь с т в о . Обозначим через К замкнутое выпуклое множество

{G (х) — G (х0): X е С, F (х) ^ 0}.

Ясно, что К не может пересекаться с внутренностью конуса Р, и, следовательно, его можно отделить от Р. Поэтому найдется такой отличный от нулевого элемент е в Y, что

sup [е, G(х) — G( х 0)]<	inf [е, р],		р е . Р.
Отсюда, в частности, следует,	что е е		Р' и
[е, G(x)]<[e, G(х0)],	х е	С, Р ( х ) > 0,
что и требовалось доказать.
Основной результат теории игр.		Теорема о минимаксе
Посмотрим теперь, как с помощью теоремы сильной
отделимости для выпуклых множеств			можно	получить
основной результат теории игр.		Итак,	пусть	<р(х, у ) —

вещественная функция двух переменных х, у е Н, а А и В — выпуклые множества в Н. Говорят, что игра двух лиц с нулевой суммой и функцией платежа ф(х, у),

где один игрок выбирает стратегии (точки) из А и
старается максимизировать ср(х, у)	(минимизировать
— ф(х, у)), а второй выбирает стратегии из В и старается
минимизировать ф(х, у), имеет цену с,	если

sup inf ф(х, у) = с =	inf зирф(х, у).	(2.12)
хеА уеВ	yeß

Выпуклые

множества в гильбертовых

пространствах

83

Далее,

если для некоторой пары (х0,

у0)

ф(*о> Уо) = с,

то

(х0,

уQ)

называется оптимальной парой стратегий.

Если же, кроме того, выполняются неравенства

ф(*. і/оК ф ^ о . УоХ

ф (% У)’

xz=A,

у*=В,

(2.13)

то (х0,

у0) — седловая

точка.

и

Т е о р е м а

2.7.

Пусть множества А и В замкнуты

выпуклы

в

Н,

а А к тому же еще

и ограничено.

Пусть ф(х,

у) — вещественная

функция,

определенная

для X из

А

и у из В и такая, что

(i) ф(х,

(1 — Ѳ) у, +

Ѳу2) < (1 — Ѳ)ф(х, Уі) +

Ѳф (х, у2)

для всех

X

из

А,

у и у2 из В

и О ^ Ѳ ^ І (г.

е.

функ­

ция ф(х,

у)

выпукла по у при любом фиксированном х),

(ii) ф((1 — в)*, + Ѳх2, у)>{1 — Ѳ)ф(х„ у) + Ѳф(х2, у)

для	всех у из В, х,,	х2 из А и	1 (т. е. функция
ф(х,	у) вогнута по х	при любом	фиксированном у),

(iii) функция ф(х, у) непрерывна по х при любом у из В. Тогда соотношение (2.12) выполняется (т. е. игра

	имеет цену).
	Д о к а з а т е л ь с т в о .			Сначала освободимся от три­
	виальной части		доказательства:
		inf ф(х, г/)< ф{х, у) <				sup ф(х, у)
		у&В				х^А
	и, следовательно,
		sup	inf ф (х, у) ^		inf	sup ф (х, у).
		х ^ А у ^ В		у & В х ш А
	Далее,	так как	функция ф(лг,		у)	вогнута и непрерывна
	по х е	А, а множество		А выпукло, замкнуто и огра­
	ничено,	то	sup ф(х, у) < оо.
	Обозначим		хе= Л
			с — inf	sup ф(х, у).
			у(=в X

84 Глава 2

Предположим, что	существует элемент х0 е А, для
которого				всех у ^ В .
ф ( * о . У ) ~ ^ с			Д л я
Отсюда сразу следует,		что
i n f		ф ( л ' 0 , г / ) > с ,
у < = В
или
s u p	i n f		q > ( j c ,	г / ) > с ,
.ѵеЛ	у s		В

а это вместе с тривиальной частью доказательства дает утверждение теоремы.

Осталось доказать существование элемента х0. Опре­ делим. для каждого у из В множество

Ау= {х £= А: ф(х, у )> с).

Множество Ау замкнуто, ограничено и выпукло. Пред­ положим, что для некоторого конечного набора у ь .. .,уп

а

Г К , = 0 - 1=1

Зададим отображение из А в Еп равенством

f (х) = (ф (х, Уі) — с,

ф (х, уп) — с).

Обозначим через G замкнутую выпуклую оболочку мно­

жества f (А), а через Р замкнутый положительный ко­ нус в Еп. Тогда

• Pf ] G=0 .

Действительно, так как функция ф(лг, у) вогнута по х,

то для любого набора {xk} из A, k =			1,	п, 0 < Ѳ* < 1,
2 Ѳ * = 1 .	справедливо неравенство
п	ѳй(ф (хк, у) -	{ п	ekxk,	\
2		с ) < ф f s		у ] - с,

показывающее, что выпуклая оболочка множества f(A )

не пересекается ^с Р.	Пусть {хп} — последовательность
в А, для которой	сходится к ѵ ^ Е п. Поскольку
множество А замкнуто,	ограничено и выпукло, то в {хп}

Выпуклые множества в гильбертовых пространствах

85

можно выделить подпоследовательность (перенумеруем ее в {хш}), слабо сходящуюся к некоторому элементу х0 множества А. В силу вогнутости по х функции ср(х, z/J для любого Уі

1іпіф(хш, z/iK ф(х0) Уі),

или

f (х0) > Йш f (Xm) = V.

Отсюда следует, что пересечение Р Л G пусто.

Таким	образом,			множества Р и G сильно отделимы.
Другими	словами,			в Еп найдется	такой	вектор с ком­
понентами		ak,	что
		п		п
sup		2	а* (ф (х, Уі) — с) < 2		агРь	Рг > 0.
іеЛ		I		I

Из всего сказанного выше ясно, что все компоненты аг должны быть неотрицательны и не все одновременно

равняться нулю. Поэтому, поделив обе части послед-

П

него неравенства		на	2 аг.	положив		рг = 0 для всех
і = 1, ... , п	и учтя		1			функции ф(х, у),
			выпуклость по у
получим		sup ф (х,		у) — с < 0,
где	Xе А
		у == 2 Q-kUk			2 öfcj
			1	'	1
разумеется,	z/ е Д .	Иначе говоря,
		inf	sup ф(х,		у) < с,
	ае В ж1=л

что противоречит определениючисла с. Итак, для

любого конечного набора {z/„} пересечение пПАу не

£=І

пусто.

Покажем теперь, что на самом деле даже пересе­ чение

П Аи

у<^В

86	Глава 2
не	пусто. Заметим, что все множества Ау замкнуты
и	выпуклы и, следовательно, согласно теореме 1.6,

к тому же слабо замкнуты. Но так как они еще и ограничены, то они компактны в слабой топологии. Это относится также и к Л. Обозначим дополнение мно­ жества Ау через Gy. Тогда Gy открыто в слабой топо­

логии, и если бы пересечение (") Ау было пустым, то

IіеВ

было бы

U G y ^ H ^ A .

у<=В

Поскольку множество А компактно, его можно покрыть конечным числом множеств :

т

U °У, =>А-

і=і

Тогда

т

гГ=\1А У і = 0 ,

т. е. Пришли к противоречию. Обозначим теперь эле­ мент, принадлежащий всем множествам Ау ( у ^ В ) , черёз х0:

^ѵ&в АУП

Очевидно, что ф(х0, у ) ^ с , и теорема доказана.

С л е д с т в и е 2.3. Пусть функция ср(х, у) из тео­ ремы 2.7 непрерывна по каждой переменной и мно­ жество В ограничено. Тогда существует оптимальная пара стратегий, обладающая свойством седловой точки.

Д о к а з а т е л ь с т в о .	Мы уже		доказали, что най­
дется такой элемент х0, что
Ф (х0, у ) > с				(2.14)
для всех г /е В. Так как функция			ф(х0, у)	непрерывна
по у, а множество В ограничено,		то в силу теоремы 2.3
inf ф(*о,	у) = ф(х0,	Уо)^с		(2.15)

Выпуклые множества в гильбертовых пространствах

87

для некоторого у0 из В.		Но
	inf ер (л'0, у) <	sup	inf ф(х, у) = с,
так	у е В	х і= А у ^ В
	что
	ф(*0> Уо) = с,			(2.16)
что	и требовалось доказать.		Свойство седловой	точки

следует непосредственно из соотношений (2.14) — (2.16).

П р и м е р 2.9. В качестве	простого примера, в ко­
тором inf и sup можно найти	непосредственно (без по­

мощи теоремы 2.7), рассмотрим случай, когда ф(*> У) = [У. «/] — [*. х\ — 2[х, у],

А — шар IIX||^ 1 , а множество В, на котором ищется минимум, совпадает со всем пространством. Тогда

так	что	Ф (х, У) =				IIУ— XII2 — 2[х, х],
				inf ф(х, у) = — 2 [х, х],
откуда				У
		sup		inf ф {х, у) — 0 =				ф (0, 0).
		IIJCII <		I у
С другой		стороны,
sup	ф{х,	у )=	sup		2 [у, у] — \\х-{- у\¥ —
IIJEII <	1	II *		II < 1
	= 2 [у, у] —			inf		II х + у II2 =		2 \у, у] —	У
									II у II
откуда				\\Х\\<1
		inf		sup	ф(л:,		г/) = 0 =	ф(0, 0).
		У	II * II <		I
Несмотря на				простоту			этого	примера, заложенные

в нем идеи распространяются, как мы увидим, и ня случай функционалов типа разности неотрицательных квадратичных форм. Заметим, что в этом примере можно взять в качестве А все пространство и резуль* тат от этого не изменится.

П р и м е р 2.10. Другой столь же простой, но более содержательный результат — принцип двойственности по норме [13].

88 Глава 2

Т е о р е м а 2.8. Пусть С — замкнутое выпуклое мно­ жество в Н, а fs(-) — его опорный функционал. Тогда

inf II у ||=	sup	(— fs(x)).
У е С	II .V II < 1
Д о к а з а т е л ь с т в о .	Достаточно заметить, что
— fs № = — SUP [*. У] =		inf [(— 1) X, у].
і/е=С		!/е С

Поэтому, так как множество элементов, для которых IIX||^ 1 , симметрично (т. е. х принадлежит ему тогда и только тогда, когда ему принадлежит — х),

sup	(—/,(* ))=	sup	inf [х, у].
И* II <	I	II .VII <	I у <= С

Теперь можно непосредственно применить теорему 2.7, взяв в качестве А единичный шар с центром в начале координат, а в качестве В — выпуклое множество С, которое, естественно, не обязательно ограничено, т. е. можно изменить порядок операций sup и inf:

sup inf [х,	у] =	inf	sup [х, »1.
II -« II < I У e С		x <= C || x || < 1
Легко видеть, что	[x,	y] =	\\y II,
sup

II* I K I

итеорема доказана.

Сл е д с т в и е 2.4. Если множество С замкнуто и вы­

пукло, a fs{ ■) — его опорный функционал, то

inf II х0 — у II =	sup	{[х, x0] — fs(x)).	(2.17)
j e C	II д: II <	I

Равенство (2.17) дает еще одну характеризацию про­ екции на С.

Приложение. Теорема Фаркаша

В качестве последнего, но на самом деле непосред­ ственного примера применения теорем отделимости (в конечномерных пространствах) упомянем теорему Фаркаша, играющую фундаментальную роль в теории оптимизации потоков на сетях.