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

Выпуклые множества в гильбертовых	пространствах	69
Тогда, как уже отмечалось, если	h( - ) обращается

в нуль на множестве ненулевой меры Лебега, опорная плоскость, соответствующая h (•), не единственна.

Теорема отделимости

Следующий результат является основной теоремой отделимости для выпуклых множеств в конечномерном пространстве.

Т е о р е м а 2.2. Пусть А и В — выпуклые множества в конечномерном (вещественном гильбертовом) простран­ стве. Если выполняется одно из условий:

(i)А П В пусто,

(ii)внутренность множества А непуста и не пересе­ кается с В, то А и В можно отделить (друг от друга) некоторой гиперплоскостью. Другими словами, найдется такой ненулевой вектор ѵ, что

■ sup [о, х ]< с <	inf [ѵ, у]]
х^А	у&В

отделяющая гиперплоскость определяется тогда уравне­ нием

[о, х] = с.

Д о к а з а т е л ь с т в о . Обозначим через А — В мно­ жество

{х — у: X ^ А, у ^ В}.

Очевидно, что оно выпукло. Далее, нуль (начало коор­ динат) не является внутренней точкой для А — В. Это нужно доказать только для случая (іі). Поэтому будем считать, что условие (іі) выполнено. Пусть начало коор­ динат принадлежит внутренности множества А — В. Тогда очевидно, что объединение

ІИ ^ - я )

о

должно совпадать со	всем	пространством. Пусть
х0 — внутренняя точка	для А,	а у — произвольная

70 Глава 2

точка из В. Тогда
y — xQ= t{u — v),	і > 0,	и е А, V е В,
или •	х0 +	іи
у + іѵ
1+ t ~	1+	t '

Но калсдая точка на прямолинейном отрезке, соеди­ няющем х0 и и (кроме, быть может, точки и), является внутренней для А, в чем легко убедиться непосред­ ственно. С другой стороны, прямолинейный отрезок, соединяющий у и ѵ, принадлежит множеству В в силу выпуклости последнего. Таким образом, В пересекается с внутренностью мнолсества А, что противоречит усло­ вию (іі).

Итак, нуль не принадлелшт внутренности мнолсества А — В. Предпололсим сначала, что нуль принадлел<ит внутренности его дополнения. Тогда, согласно те'ореме 1.1, нуль молено спроектировать на замыкание

мнолеества Л — В.	Обозначив		эту	проекцию	через z,
получим, что для любого элемента				у из А — В
или	[ — 2 , 2 — 1/ ] > 0 ,
	[z, у] > [z ,		z] > 0
и, следовательно,
inf		[г, х\ > sup [z, у],			(2.1)
X е	А	у е	В

что и требовалось доказать.

Далее, если нуль не принадлелеит внутренности дополнения мнолеества А — В, то он доллсен быть гра­ ничной точкой мнолсества А — В и, значит, найдется сходящаяся к нулю последовательность точек хп, не принадлелеащих замыканию мнолсества А — В. Обозна­ чим проекции точек хп на замыкание множества А — В через z„; тогда

[хп— 2„, Zn — у] > 0, у 6= А — В.

(2.2)

Очевидно, можно полол<ить

	еп =	(х , і — Zn) '
		II Хп—г„ II ’

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

71

каждый вектор	еп является единичным.				А так как
	\гп	хп,	^п]	О,
то неравенство (2.2) можно переписать в виде
[%п Хщ У] \хп		Хп, Zn] УУ' [z n			Хп, Хп],
т. е.	[®п> £/] ^	[®ni ^/t]	[®п>		(2*3)
				Xn]
для всех у из	А — В.

Таким образом, мы показали, что для любой задан­ ной точки zn из сходящейся к нулю последовательности граничных точек существует опорная плоскость, прохо­ дящая через эту точку. Сходимость к нулю следует из того, что

II 0 — Zn ІКІІ 0 — Хп II + II Хп — ІКІІ о — Хп II + II О — Хп ||—>0.

Все приведенные выше соображения никак не исполь­ зовали конечномерность основного пространства, и, зна­ чит, они справедливы в бесконечномерном случае. Сле­ дующий шаг доказательства потребует использования конечномерной конструкции (а на самом деле, как выяснится в дальнейшем, в бесконечномерном случае он просто неверен). Итак, по теореме Больцано — Вейерштрасса ограниченное множество точек еп должно иметь

предельную	точку. Обозначим ее	через е0. Ясно,	что
е0— единичный вектор. Переходя		в неравенстве	(2.3)
к пределам,	получаем
	[е0, У] > [е0, 0], уе=А — В.		(2.4)

Это неравенство характеризует опорную плоскость, про­ ходящую через граничную точку нуль. Из условия (2.4) находим

inf [е0, х\ > с >	sup [е0, у].	(2.5)
J e A	у е В

Теорема доказана.

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

72

Глава 2

С л е д с т в и е 2.1. В любом гильбертовом простран­ стве множество опорных точек выпуклого множества плотно в множестве граничных точек.

П р и м е р 2.8. Приведем пример, показывающий, что этот результат нельзя улучшить. А именно мы построим такое выпуклое множество, что для некоторых его граничных точек не существует опорных плоскостей, проходящих через них (Кли, см. [2]). В качестве Н возьмем пространство квадратично суммируемых после­ довательностей вещественных чисел. Рассмотрим в нем положительный конус, т. е. множество С таких после­ довательностей, все члены которых неотрицательны.

Ясно,		что	С выпукло и замкнуто. Легко убедиться
в том,		что	С не содержит внутренних точек: каждая
точка	в С является граничной.

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

	Действительно,	пусть	z — такая			последовательность.
	Предположим, что для		некоторого элемента h из Н
		[,h, х] <		[/г, г]		(2.6)
	для всех X из С.	Но тогда для любого числа Я > О
		Я [h, z]		[h, г].
	Переходя к пределу при Я—>оо, получаем
	а при Я —>0		[/г, z] <		О,
		[[/г, z		]	>	0 .
	Отсюда
			[h,z\ = 0.			(2.7)

Согласно неравенству (2.6), последовательность h, оче­ видно, не может содержать положительных членов, так что в силу (2.7) она должна состоять из одних нулей, ибо ни один из членов последовательности z не равен нулю. Заметим, что для каждой последовательности из С, имеющей хотя бы один нулевой член, проходящая

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

73

через нее опорная плоскость существует, и множество этих последовательностей, очевидно, плотно в С.

З а д а ч а		2.1. Пусть	# = L2(О, I)9 и
C =		{f(-)€Etf: II / (t) II ^ 1 почти всюду}.
Покажите,	что каждая		точка в С является граничной
и f ( - ) e C	оказывается		опорной точкой тогда и только
тогда, когда		множество
		{/е [0 ,	Ц: 11/(011=1)

имеет ненулевую меру Лебега. При этом соответствую­ щая опорная плоскость не обязательно единственна.

Сильная отделимость

Два множества А и В гильбертова пространства Н называются сильно отделимыми, если для некоторого элемента н е й

inf [ѵ, х]	с + sup [о, у], с > 0.	(2.8)
X е А	у ^ В

Согласно рассуждениям, использованным при дока­ зательстве теоремы 2.2, сильно отделимы, например, два замкнутых выпуклых множества А и В, расстояние между которыми конечно в том смысле, что

inf II л-— y\\ = d > 0.

ж е Л

уев

Действительно, в этом случае нуль является внутренней точкой дополнения множества А — В. Если z — проекция нуля на замыкание множества А — В, то [— z, z — q ] ^ 0 для каждого q из А — В, или

[z,	q] > [г, г].
Тогда		х ^ А , ij£ В,
[z, х] — [х, у] > [z, г],
откуда	[z, z] +	sup [z, у].
inf [z, х) >
X e А		у e В

З а м е ч а н и е 2.1. Теорему 2.2 интересно сформули­ ровать так, чтобы она была верна в любом гильбертовом

74 Глава 2

пространстве. Очевидно, что она верна при выполнении условия (іі), так как тогда внутренность множества А — В не пуста, а нуль является его граничной точкой. Как уже было показано, в этой ситуации существует опорная

плоскость,		проходящая через			начало координат. Одна
из	более	общих		формулировок первой части теоремы
такова: Пусть			А и В — два		выпуклых множества в Н
и выполняется			одно из условий:
из	(i) пересечение			А П В пусто и по крайней мере одно
	множеств А		я	В имеет непустую внутренность,
	(ii) внутренность множества А не пуста и не пере­
секается с В.
	Наконец, контрпримером к теореме 2.2 в гильбертовом

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

З а д а ч а 2.2. Пусть Р — замкнутый выпуклый конус в Н. Обозначим через Р* множество

Р' — {х: [х, р ] ^ 0 для всех р из Р}.

Тогда Р* — также замкнутый выпуклый конус. Он назы вается двойственным по отношению к первому. С по­ мощью теоремы сильной отделимости покажите, что если внутренность множества Р не пуста, то из того, что для каждого у из Р*

[х, у] > О,

следует, что х принадлежит Р. (Другими словами, конус Р является двойственным по отношению к Р \)

Указание. Если х не принадлежит Р, можно найти такой элемент е, что для всех р е Р

[е, х] < [е, р]

и, следовательно, [е, р ] ^ 0, откуда ееР * . Тогда [е, х]<0 т. е. пришли к противоречию.

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

75

Приложения к задачам выпуклого программирования

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

Т е о р е м а 2.3. Непрерывный выпуклый функционал, определенный на гильбертовом пространстве, достигает своего минимума на любом выпуклом замкнутом огра­ ниченном множестве.

Д о к а з а т е л ь с т в о . Если пространство конечно­ мерно, то очевидно, что условие выпуклости множества, на котором ищется минимум, не обязательно. В случае же бесконечной размерности пространства из минимизи­ рующей последовательности {х„} в силу ее ограничен­ ности можно выделить слабо сходящуюся подпоследо­ вательность (обозначим ее предел через х). Согласно следствию 1.6, функционал / ( • ) должен быть полу­ непрерывен снизу,

lim f(xn) ^ f ( x ) .

Таким образом, минимум функцио-нала f( - ) равен f(x). Так как сильно замкнутое выпуклое множество всегда слабо замкнуто, точка х должна принадлежать данному замкнутому выпуклому множеству.

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

Т е о р е м а 2.4. (Кун — Таккер.) Пусть f (х) и ft (х) —

выпуклые функционалы, определенные на выпуклом подмножестве С гильбертова пространства Н (на самом деле Н может быть любым линейным пространством).

Пусть требуется минимизировать / ( • ) на С при огра­ ничениях

f i i x X 0, і= 1 , .... п.

76

Глава 2

Обозначим через х0 точку, в которой достигается иско­ мый минимум {по предположению конечный). Предпо­ ложим, что для каждого отличного от нуля вектора и из Еп с неотрицательными компонентами найдется такая точка X из С, что

П

2I Ukfk М < о,

где uk — компоненты вектора и. (Очевидное, но тем не менее полезное достаточное условие для этого состоит в том, чтобы нашлась точка х из С, в которой все

функционалы	/,•(•)	( і = 1 ,	... , п) были бы строго
меньше нуля.)	Тогда	существует такой вектор ѵ с не-
'отрицательными компонентами vk, что
min (/ (х) +	2 о*/* (*)) =		/ (*о) + Ѣ °kfk (хо) = / (*о)-
лес V	1	/	1

Более того, для каждого неотрицательного вектора и из Еп

f{x) + 2 ) vkfk (X) > / (х0) + 2 о*/* (х0) >
1	I
	> f{ x 0) +	21u kfk(xo). (2.9)
(Другими словами,	(дг0, ѵ) — седловая	точка функции
	п
ф(х,	и) = f (х) + 2 ЫJfe (х),
	1

где и принадлежит положительному конусу в Еп,

аX <— выпуклому множеству С.)

До к а з а т е л ь с т в о . Определим в Еп+1 следующие множества:

А = {у — {у0, уі........	уп) е= £«+,: уй > f ( x 0),	уі >U{x),
i = l ........	п, для некоторого х е С );
В = {у — іу0, Уі........	уп) es En+l: у0 < f {х0),	yt < О,
	і = 1, ■• я}.

Выпуклые множества в	гильбертовых	пространствах	77
Нетрудно проверить, что	множества	А и В выпуклы

и не пересекаются. Согласно теореме 2.2, их можно отделить. Следовательно, можно найти такие числа vk,

k =	0, 1, .... п,	что
	inf { v0f (х) -f 2		vkfk(X) } >	o0f (x„) — 2 о* I Уk I- (2-10)
	лес I	1	J	I
Но	так как это	неравенство должно выполняться для

любых I yk I, все коэффициенты vk должны быть неотри­

цательными.		В частности, полагая			| | = 0 для	всех
k = \ , .... п,		получаем
		vof (-«о) +	2 vkfk (х0) >		Oof (х0).
			1
Так как,	согласно ограничениям			задачи, fft(x0) ^ 0		для
всех к =	1........ п, то
		2	Vkfk М =	0.
		1

Покажем теперь, что о0 строго больше нуля. Действи­

тельно,		если		все	числа	vk (k = \ , ... ,		п) равны нулю,
то	ѵ0=£0,		а	из	неравенства		v0Z o ^ v 0y0		для	всех
у0<	f (х0) ^		z0 вытекает,			что ѵ0> 0.		Если	же не	все
числа		vk ( к =		1 ,	п) равны нулю, то по условию
существует такая					точка ^ е С ,		что
					2 Vkfk ( х) <		0.
					1

Но для любого zQ^ f ( x 0) должно быть

п

ѵ0(Z0 — f (xq)) > — 2 Vkfk (X) > 0, 1

а значит, v0>	0. Разделив	неравенство		(2.10) на v0
и обозначив vk/v0 снова через vk, k = 1,			... , п, получим
f (Х) + 2	Vkfk (Х) > f (Х 0)	= f (Хо) +	2	Vkfk (х0),
1			1

78 Глава 2

откуда легко вывести все остальные утверждения теоремы.

С л е д с т в и е	2.2.	В условиях теоремы 2.4
f (*о) =	sup	inf (f (а ) +	2 ЧІк	/	.	(2.11)
	и>0	xmC \	1

Д о к а з а т е л ь с т в о .				Равенство		(2.11)	непосред­
ственно следует		из неравенства			(2.9). Действительно,
Д Л Я Л Ю б Ы Х U f e j X )
in f ( f (A') +	S	Ukfk(A')) <		f (Aq) +	2	(a0) <	/ (a0).
x e C \,	1	/			I
Подстановка	uk — vk дает
	in f	( / (A) +	2	Vkfk(A)) >		f (A'o).
	j e C \		1		J

Это следствие полезно тем, что оно определяет про­ цедуру поиска оптимального решения задачи.

Заметим, что если все коэффициенты vk из нера­ венства (2.9) положительны, то а 0 — граничная точка выпуклого множества, определенного ограничениями задачи. Если же ѵк = 0 для всех k = l, 2........ п, то ограничения вообще не оказывают влияния на решение задачи и функционал имеет тот же минимум, что и в „свободном“ случае, т. е. когда не наложены никакие ограничения.

Приведенное следствие известно под названием тео­ ремы Лагранжа о двойственности.

Обобщение на случай бесконечного множества ограничений

Рассмотрим ситуацию, когда число ограничений бесконечно. Один из подходов состоит в следующем. Обозначим через F (х) отображение из Я в простран­ ство /2 квадратично суммируемых последовательно­ стей, через Р — положительный конус в /2 (т. е. мно­ жество последовательностей, все члены которых не­ отрицательны), а через Я — отрицательный конус в /2