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

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

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

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

^Jfe^± WV^⁵'^-

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

(^Xa±JJ7f'^f)^{> 0}-

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

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

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

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

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

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

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

у'< Хо< у".

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

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

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

< у", Г>.

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

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

и' «а Хо

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

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

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

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

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

(aiXi -f а₂х₂, /> = (a_xyi + а₂у₂, /} + с (а^ + a₂t₂) =

~ «1 (у и /) + «2 (у₂, f) + + ca₂t₂ =

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

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

y + txо> 0. •

Тогда

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

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

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

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

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

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

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

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

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

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

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

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

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

Докажем, что f линеен и неотрицателен. Если Xi = /iX₀, X₂ = t₂Xo, то

(а, *, + а₂х₂, f) = < (cti^i + a₂t₂) x_Q, f) = ci^ + a₂t₂ =

= ^ai (х\, f) + a₂{xг, f).

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

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

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

- + ( + jjjTF) = TflJ ^е

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и у и у₂^К₂ такие, что

2₁=x_t — Уи z₂ = x₂ — y₂.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 -j- Л

1 + А ¹ 1 + А

Но по условию 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 и точка х₀ ф. М. Тогда точку Хо можно строго отделить от М, т. е. существует х* е Е' такой, что

с = sup < х, х*) < (х₀, **> • (⁵)

цел

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

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

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

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

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

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

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

inf (z, х*) < 0.

г е s_r (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 и всех А^О выполняются неравенства

/(л: ⁰, А)< /(х°, A⁰)< /(x, А⁰) (3)

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

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

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

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

имеем

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

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

tW^Xtk^iix⁰). (5)

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

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

л

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

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

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

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

п

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(В)

i =j

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

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

л

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

i=i

для всех ig Q.

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

п

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

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

п

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

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

п

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

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

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

/-I i=i

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

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

ЛИТЕРАТУРА

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться:

Популярное:

1. V7: Система линейных одновременных уравнений
2. АВТОМАТИЧЕСКИЙ КОНТРОЛЬ ЛИНЕЙНЫХ РАЗМЕРОВ
3. Ведомость линейных и сосредоточенных земляных работ.
4. Зоны, выделяемые вдоль режимообразующих линейных и водных объектов.
5. Как производится графический метод расчета нелинейных цепей постоянного тока?
6. Качественные характеристики оценок параметров нелинейных эконометрических моделей
7. Лекция 2.4. Динамическая точность линейных стационарных следящих систем при неслучайных воздействиях
8. Линейных источников излучения.
9. Метод простой интерации и Зейделя для решения систем нелинейных уравнений
10. Методы исследования нелинейных САР.
11. Написание программы на Паскале для решения задач на ввод-вывод линейных и двумерных массивов
12. Особенности оценки параметров нелинейных моделей