Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Теоремы о неотрицательных линейных функционалах.



Определение. Пусть К—выпуклый конус в линейном пространстве Е. Линейный функционал /, определенный на Е, называется неотрицательным, если {х, /> ^0 для всех х^К, т. е. для х ^ 0.

Теорема 1. Пусть линейное пространство Е полуупорядо­чено телесным выпуклым конусом К. Тогда всякий линейный неотрицательный функционал f, определенный на Е, необхо­димо ограничен.

Доказательство. Вследствие телесности конуса К су­ществует его внутренняя точка Хо. Но тогда найдется шар Sr(x0)czK. Возьмем в Е произвольный элемент х ф 0 и рас­смотрим элементы

Jfe± WV^5'^-

На этих элементах f неотрицателен, т. е.

(Xa±JJ7f'f)> 0-

По линейности f отсюда получаем

/> < < *, /> < 11£! <, 0| /).

Следовательно,

\{х, /Ж ^т^Н -г II. Это и означает ограниченность f, а также (см. п. 17.1) нера­венство ll/IK^^.

Нашей ближайшей целью будет доказательство теоремы, яв­ляющейся аналогом теоремы Хана — Банаха (см. § 16), для случая неотрицательного функционала. Как и в п. 16.1, рас­смотрим сначала простейший случай продолжения линейного неотрицательного функционала.


Лемма (об элементарном продолжении). Пусть Е — ее- щественное нормированное пространство, частично упорядочен­ное выпуклым телесным конусом К. Пусть L — линейное много­образие в Е, содержащее хоть одну внутреннюю точку конуса К. Пусть точка х0 ф L. Тогда любой определенный на L линейный неотрицательный функционал / можно продолжить с сохране­нием линейности и неотрицательности на линейное многообра­зие L\ элементов вида у + tx0, где у е L, a t е Ех.

Доказательство. Покажем сначала, что для любой точки хо < = Е, х0 ф. L найдутся в L точки у' и у" такие, что

у'< Хо< у".

Действительно, пусть хх— внутренняя точка К, принадлежащая L. Тогда существует шар Sr(jti)c: К, а тогда

± " 2^71 s Sr М И> ЗНаЧНТ' ± Щ^Л > Отсюда следует, что

Действительно, х\ eL, a L — линейное многообразие. Поэтому у' е L и у" е L, но тогда из неравенства у' ^ у" следует, что

< у", Г>.

Заметим теперь, что существует точная верхняя грань

с = sup {у\\). (1)

и' «а Хо

Ппи этом справедливо следующее неравенство:

(у', f)< C< {y", /).

Продолжим теперь f с L на Li следующим образом: для х = у -+- txо е L\ положим

{x, f) = (y, f)+tc. (2)

Докажем, что так определенный функционал будет линей­ным и неотрицательным. Если х\ = у\ + Лхо, а х2 = у2 + hxo, то

(aiXi -f а2х2, /> = (axyi + а2у2, /} + с (а^ + a2t2) =

~ «1 (у и /) + «2 (у2, f) + + ca2t2 =

= < *i [(^1. /> + ct\\ + а2 [< У2, f> + Ct2] = < *i (хь f> + а2 < х2, /).

Итак, / линеен на L\. Докажем, что { неотрицателен на L\. Пусть

y + txо> 0. •

Тогда

Хо> --упри/> 0 и Же< — 7- при /< 0. (3) Из первого неравенства следует, что

< *е, f)> (-T' f)-

Но < хо, f> < с вследствие неравенства (1). Значит, (--f. /)< с при / > 0.

Следовательно, ^-у-, + откуда по (2) имеем при < > 0

+ /хо, ^ 0. Аналогично, при t < 0 второе из неравенств (3)

дает с ^ -у, откуда < «/ + /х0, /> ^ 0. Таким образом, f

неотрицателен на L\. Лемма доказана.

Сформулируем теперь теорему М. Г. Крейна о продолжении линейного неотрицательного функционала.

Теорема 2. Пусть линейное пространство Е частично упо­рядочено выпуклым телесным конусом К. Пусть, далее, линей­ное многообразие L пространства Е содержит хоть одну внутрен­нюю точку конуса К. Тогда любой линейный неотрицательный, заданный на L функционал можно продолжить до линейного неотрицательного функционала, определенного на всем прост­ранстве Е.

Доказательство теоремы 2 проводится на основе доказанной леммы так же, как и доказательство теоремы Хана — Банаха (см. п. 16.1). Приведем теперь важное следствие.

Теорема 3. Пусть вещественное нормированное простран­ство Е упорядочено выпуклым телесным конусом К, не совпа­дающим со всем Е. Тогда существует хотя бы один ненулевой неотрицательный линейный функционал, определенный на Е.

Доказательство. Пусть х0 — внутренняя точка ко­нуса К- Построим одномерное подпространство L = {x; x = ix0, Зададим на L функционал / по формуле

< х, f) = {/xo, /> =/•

Докажем, что f линеен и неотрицателен. Если Xi = /iX0, X2 = t2Xo, то

(а, *, + а2х2, f) = < (cti^i + a2t2) xQ, f) = ci^ + a2t2 =

= ai (х\, f) + a2{xг, f).

Линейность / доказана. Для доказательства неотрицатель­ности f покажем, что если txa^K, то t^ 0. Допустим против­ное, что t < 0, но tx0^K. Тогда |/|х0еК и по определению конуса — Хо е К. Покажем, что это невозможно. Так как Хо — внутренняя точка К, то существует шар Sr0) с: К• Возьмем

произвольный элемент х е Е\ тогда х0 + 2 ц * ц е Sr (хо).

Поскольку мы видели, что —х0^К, то, согласно определе­нию 2 п.40.3 выпуклости конуса К, сумма элементов

- + ( + jjjTF) = TflJ е

Но тогда и х е/<. Так как х — произвольный элемент из Е, то отсюда следует, что К — Е, а по условию теоремы К не совпадает с Е. Значит, предположение о том, что txQ^K и t < 0, приводит к противоречию.

Таким образом, из txQ^K следует, что /^0. Но это озна­чает, что функционал f неотрицателен на L: если х = *х0^О, то(х, f)==(tx0, G. Итак, f линеен и неотрицателен на L,

причем L содержит внутреннюю точку К.. По теореме 2 функ­ционал f можно продолжить на все пространство Е, в резуль­тате чего мы получим функционал, о существовании которого говорилось в условии теоремы. На этом доказательство тео­ремы 3 заканчивается.

40.5. Теоремы отделимости. Пусть X — нормированное про­странство и в нем заданы множества М и N.

Определение. Будем говорить, что линейный ограни­ченный функционал х* (х* е X* — пространству, сопряженному к X) разделяет множества М н N, если для всех х е М и у е jV

< х, х*) < (у, х*). (1)

В этом пункте будет доказано несколько теорем отделимости о существовании функционала, разделяющего множества, в различных предположениях об этих множествах. Эти теоремы широко применяются в задачах оптимального управления (см. [11]).

Теорема 1 (об отделимости конусов). Пусть в нормиро­ванном пространстве X задано два выпуклых конуса Кi и /С2> причем конус К\ телесный, а конус К2 не пересекается с вну­тренностью К\. Тогда существует линейный функционал х*^Х*, разделяющий конусы К\ и К2 в следующем смысле:

< *, **> < 0 < < ».**> (2)

для любых у е= /С2.

Остановимся сначала на геометрическом смысле условия (2) разделения конусов К\ и К2- Множество точек iel, удовле­творяющих уравнению (х, х*) = 0, где х* ф 0 — фиксирован­ный элемент из X", образует плоскость в X. Эта плоскость делит X на два полупространства. Конус К\ лежит в полу­пространстве (х, д: *)^0, а конус К2 — в полупространстве {х, х)> 0.

Доказательство теоремы 1. Построим множество

K = Ki- = X: z = x-y, хе К„ у е= К2} (3)

и докажем, что К является телесным выпуклым конусом в X, не совпадающим с X. Для доказательства того, что К представ­ляет собой выпуклый конус, возьмем произвольные элементы Z\, Тогда, согласно (3), найдутся элементы Х\, х2^К\

и у и у22 такие, что

21=xt — Уи z2 = x2 — y2.

Для любых чисел а^О и а2^0 имеем о, 2, + а222 = а, (х, — у, ) 4- о22 у2) = (a, Xj -f «2X2) —

~ (aij/i 4- а2г/2) е К,

так как сг^ 4- & 2Х2 ^ Ki, а\уу 4- «2^/2 s ^2- Итак, доказано, что /С — выпуклый конус.

Далее, поскольку К\ с= К и iCi содержит внутренние точки, то и К обладает этим свойством, т. е. /( — телесный конус.

Докажем, наконец, что К ф X. Пусть хв — внутренняя точка конуса К\. Докажем методом от противного, что тогда —хаф ф. К. Допустим, что это не так. Тогда найдутся х е К\ и у е е Кг такие, что — х0 = х — у. Отсюда ха + х = у.

Докажем, что хо 4* х — внутренняя точка конуса К\- Так как ха — внутренняя точка Ki, то найдется шар Sr(*o) cz К\. Но тогда, согласно определению выпуклого конуса, шар

х 4- Sr (хо) = {2 е Х\ г = х 4- х0 4- и, " ^ X, и е X , || и || < г}

также лежит в Ki. Следовательно, х0 4~ х — внутренняя точка К1, но х0 4- х = у е Оказалось, что конус К2 пересекается с внутренностью К\, что исключалось условием теоремы. Полу­ченное противоречие доказывает, что— хо^К, т. е. КфХ. Таким образом, для К выполнены все условия теоремы 3 пре­дыдущего пункта и согласно этой теореме существует неотри­цательный (в смысле конуса К) линейный функционал 1*еГ, не равный нулю. Для всех г е К имеем (г, х*)^0, откуда (х — у, х*)^0 для любых хе/Сь у е К2 (см. (3)). Следова­тельно, для всех x^Ki, У К2 выполняется неравенство (1). Так как 0 е Ki и 0 е /С2, то этому неравенству можно придать вид (2). Теорема доказана.

Перейдем к теоремам отделимости для множеств, не явля­ющихся конусами. Для этого нам понадобится следующая конструкция. Поставим каждому множеству М cr X в соответ­ствие следующее множество:

K{M) = {ze=X : z = Хх, ieM).

Очевидно, К (М) всегда является конусом. Лемма 1. Если множество М выпукло, то множество К [М) есть выпуклый конус.

Доказательство. Пусть ги г2 е К (М)\ тогда z{ = A[Xb г2 = Я2х2, где Ai ^ О, Х2 ^ 0, хь х2 s М. Для любых а^О, а2 ^ О имеем

а^! 4- а2г2 = a^iXi -f 0.2X2X2 =

=(а, ^ 4- ^ [^хгйаг *« + ыгтаг х> ]'

если a, Ai 4- а2Х2 > 0 (в противном случае щгt 4~ «222 = 0 е К (М)). Поскольку М выпукло (см. п. 1.7), то выражение в квадратных

скобках принадлежит Af, а тогда, по определению К(М), а{2\ + ot222 е К (М). Лемма I доказана.

Лемма 2. Пусть М —выпуклое тело (см. п. 35.1) и ОфМ. Тогда К(М) не совпадает с X.

Доказательство. Пусть х0 — внутренняя точка М. Пока­жем, что — хофК(М). Если это не так и — Xq ^K(M), то най­дутся А.^0 и х^М такие, что — х0 = Ях, причем Я, ф0, иначе бы OeAf, Но тогда х = —Я~'л; 0е1

Поскольку и Хо е Af, то вследствие выпуклости М аЯ~1(— xQ) + (1 — а)х0 е М для всех а е [0, 1]. Возьмем Я

а = , , ■ ■ и получим

1 -j- Л

1 + А 1 1 + А

Но по условию 0 ф М. Полученное противоречие доказывает, что —х0ФК{М), и лемма 2, таким образом,.доказана.

Лемма 3. Пусть М — выпуклое тело и ОфМ. Тогда на X можно определить линейный функционал х* е X* такой, что х* ф 0, {х, х*) ^ 0 для любых х е М.

Доказательство. Построим выпуклое тело К(М)ФХ (см. леммы I и 2). По теореме 3 п. 40.4 существует линейный функционал х* ф 0 такой, что (х, х*) ^ 0 для всех х е К (М). Но MczJ\(M) и, значит, х* — искомый функционал. Лемма 3 доказана.

Теперь мы можем перейти к формулировке и доказательству теорем об отделимости множеств.

Теорема 2. Пусть в нормированном пространстве X задано два выпуклых непересекающихся множества М и N, причем мно­жество М имеет внутренние точки. Тогда существует линейный функционал х* ф 0, х* е X*, разделяющий множества М и N. Доказательство. Построим множество

L = M — N = {zs=X: z = х — у, ieM, y< =JV}.

Множество L выпукло (см. задачу 11 к § 1); далее, L имеет внутренние точки, так как М cz L. Кроме того, ОфМ. В про- тнвном случае 0 = х — у, где х^М, y^N, откуда х = у, но М и N не пересекаются. Значит, ОфМ. По лемме 3 сущест­вует х'фО, л'еГ, неотрицательный на М т.е. (г, х*)^0для всех z е М. Но это значит, что

< *, *•> > {у, х) (4)

для всех xeAf и y^N. Теорема 2 доказана.

Обсудим геометрический смысл этой теоремы. Фиксируя у ен N в (4), мы видим, что множество {{х, х*>, х^=М} огра­ничено снизу, а потому существует b — inf (х, х*). Аналогично,

существует а = sup (у, х*).

ye=N


Пусть с заключено между а и Ь. Тогда для всех jteM, хе А' справедливо неравенство

(у, /)< £ < < х, х*>.

Множество всех х е X, для которых (х, х*) = с, является гипер­плоскостью в X. Эта гиперплоскость делит пространство X на два полупространства, в одном из которых {х, х*) ^ с, а в другом (х, х*> > с. В первом из них лежит множество N, а во втором — множество М.

Теорема 3. Пусть М — замкнутое выпуклое множество в нормированном пространстве X и точка х0 ф. М. Тогда точку Хо можно строго отделить от М, т. е. существует х* е Е' такой, что

с = sup < х, х*) < 0, **> • (5)

цел

Доказательство. Заметим сначала, что неравенство (5) можно записать так: для всех х е М

(х, **> < с < (х0, х*). (6)

Заметим теперь, что множество Х\М — дополнение М — открыто и содержит точку х0. Поэтому найдется шар N ~Sr(x0), не пересекающийся с М. По теореме отделимости 2 множества М и N можно разделить ненулевым линейным функционалом х* е X*, т. е.

(х, х*)< с < (у, х*>

для любых х е М, г/е N.

Последнее неравенство запишем в виде

(х, х*> < с < (х0, х*) + (г, х*), где zeSr(0). Так как х* фО, то

inf (z, х*) < 0.

г е sr (0)

Значит, с < (х0, х*), и неравенство (6), а с ним и теорема 3, доказаны.

40.6. Принцип седловой точки и теорема Куна — Таккера.

Пусть Q — множество в нормированном пространстве X и на Q определены функционалы < р (х) и -ф (х) = (x)}f (п функци­оналов). Поставим задачу: найти minqp(x) при условиях xeQ, (|)(х)< 0 (т. е. все \|), (х)^0, 1 = 1, ..., п). Кратко задачу мож­но записать так:

min{ф(х); xe=Q, ф(х)< 0}. (1)

Таким образом, задача (1) есть задача об отыскании мини­мума функционала ф (х) на множестве Q при ограничениях типа неравенств. В случае, когда Q, ф(х), 'ф (х) выпуклы, задача (1) называется задачей выпуклого программирования.

Определение 1. Функционалом Лагранжа задачи (1) называется следующий функционал:

l(x, k) = < р(х) + (ф(х)Д), (2)

п

где k = е Еп, а (ф (х), к) = £ А£ фг (х) — скалярное произведе­ние в Еп. Числа Аь..., кп называются множителями Лагранжа.

Функционал Лагранжа зависит, таким образом, от двух переменных: ^eQcI и к

Определение 2. Точка (х°Д°), где А® е назы­

вается седловой точкой функции Лагранжа (2), если для всех xeQ и всех А^О выполняются неравенства

/(л: 0, А)< /(х°, A0)< /(x, А0) (3)

(или противоположные им неравенства).

Неравенства (3) имеют простой геометрический смысл: l(x°, k°) есть минимум l(x, k°) по переменной х и максимум l(x°, k) по переменной А. Подобным же образом устроена сед- ловая точка (0, 0) поверхности г = х2 у2 в Еъ.

Теорема 1 (принцип седловой точки). Пусть (х°, к°) — сед- ловая точка функционала Лагранжа (2); тогда х° является решением экстремальной задачи (1).

Доказательство. Запишем условие седловой точки (3) с учетом (2) подробнее. Для всех jeQ и i=l

имеем

Ф + i Агф, - (*°) < < ре) + Z А? фг (х°) < i=i «=1

< 4> (x)+tWt(x). (4) Левое неравенство дает для всех i= 1, п,

tW^Xtk^iix0). (5)

Отсюда следует, что все Если бы при некотором k

оказалось (х°) > 0, то, выбрав Аг = 0, i ф k, a kk > а£, мы нарушили бы это неравенство. Итак, т. е. ограниче-

л

ния типа неравенства выполнены. Далее, £ А^ф, (х°) = 0, так

как если это выражение отрицательно, то (5) при А = 0, а значит и (6), было бы невозможно. Заметим, что отсюда сле­дуют равенства

*М>, (лс°) = 0, /=1, (6)


С учетом (6) правую часть неравенства (4) можно записать в виде

п

Но тогда для всех xeQ таких, что гМл^^О, имеем г^фОс), т. е. решает задачу (1). Теорема доказана.

Приложение данной теоремы в теории регуляризации некор­ректных задач см. в [9], стр. 77 — 83.

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

Определение 3. Будем говорить, что для задачи (1) выполнено условие Слейтера, если существует элемент х е Q такой, что ф (х) < 0.

Теорема 2 (Кун — Таккер). Пусть множество Q и функ­ционалы ф и ij) выпуклые, и пусть для задачи (1) выполнено условие Слейтера. Элемент х° является решением задачи (1) тогда и только тогда, когда существует вектор К0 е Еп множи­телей Лагранжа такой, что

1(х°Л0)^1(хЛ% (7)

и выполнены условия (6).

Доказательство достаточности. Нетрудно заме­тить, что из (6) и (7) Еытекает условие седловой точки (3), и утверждение этой части теоремы следует из принципа седловой точки.

Доказательство необходимости. Пусть х° — реше­ние задачи (1). Рассмотрим в Ea+l множество М, состоящее из

векторов ц = (ц/)" =ь для каждого из которых существует век­тор х е Q такой, что

ф (х) — ф (х°) < Но, (х) < \it, i — 1, .. •, п.

Множество М содержит внутренние точки: если р.> 0, т. е.

> 0, k = 0, 1, ..,, п, то ц g М, а каждая точка — внутренняя.

Упражнение. Пользуясь выпуклостью функционалов Ф и •ф, докажите выпуклость М.

Наконец, точка 0 ф. М; иначе оказалось бы, что ф(х) < ф(х0), tp(x)< 0, х е Q, т. е. х° не является решением задачи (1).

Согласно теореме 2 п. 40.5 множество М можно отделить от точки 0 функционалом % е= (En+1)* = En+l, = ф 0. Это

означает, что существуют числа........................ Хп, не все равные

нулю одновременно и такие, что для всех р. е М (А,, р) ^ 0, т. е.

(В)

i =j

Из (8) следует, что все А, ^ 0, ибо М содержит все р > 0. Полагая в (8) = i= I, ..п, и устремляя затем р0

к < р (х) —■ ф (х°), получим

л

*оФ (х) + £ А^, (х) > Я0ф (х°) (9)

i=i

для всех ig Q.

Докажем теперь равенства (6). Очевидно, ifo (дс°) ^ 0, / = 1, ... ..., п. Допустим, что при г = & ^ (д: 0) = — а < 0. Рассмотрим точку neeQ, все координаты которой суть е > 0, кроме k-k, а = —а. Подставляя це в равенство (8), получим

п

[К, ре) = е Z х, — аХк > 0. 1=1 1 фк

При е-» + 0 имеем неравенство — аА^^О, откуда а это возможно лишь при Ай = 0. Значит, Xktyk (х°) = 0, и равен­ства (6) доказаны. Воспользуемся теперь условием Слейтера. Из него следует, что Х0 ф 0. Иначе, из (9) мы получили бы,

п

что Z ^i^M*)^ 0 Для всех x^Q, причем не все А/, i = «=1

= 1, ..., п, равны нулю. Положив в этом неравенстве х = Л,

п

получим 0 > Z (*) ^ 0» что невозможно. Итак, А0 > 0. «=1

Разделив неравенство (9) на А0, мы получим неравенство (с учетом (6))

< РМ+ Е(Л)гЫх)> ф(х°)+ t ЬТ%)ъ(х°),

/-I i=i

т. е, неравенство (7). Наконец, для всех xg Q таких, что имеем

Ф (*о) < Ф (х) + £ (Л) Ь (х) < Ф (х). Теорема доказана.


ЛИТЕРАТУРА


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-04-11; Просмотров: 758; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.092 с.)
Главная | Случайная страница | Обратная связь