Файл: Балакришнан, А. Введение в теорию оптимизации в гильбертовом пространстве.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 24.10.2024

Просмотров: 107

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

Смотрите также файлы