Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 47
Текст из файла (страница 47)
Если шт Х = 8, то аПХ те Еа, ГРХ = Х, и через каждую *очку у ш Х можно провести гиперплоскость Г: (с, х — у) = Ю, где с — лтобой ненулевой вектор из ортогонального дополнения к ййпХ. Тогда Х ~ а11Хс Г, так что à — опорная $51 ОТДЕЛИМОСТЬ ВЫПУКЛЫХ МНОЖЕСТВ 199 к Х гиперплоскость, пе являющаяся собственно опорной. Теорема 1 уточняет, что если у гн Х, у ~ г( Х, то среди опорных к Х гиперплоскостей, проходящих через точку у, можно найти собственно опорную. Заметим, что выпуклое множество с непустой внутренностью не может иметь опорных гиперплоскостей, не являющихся собствеипо опорными.
Это вытекает иа следующего несколько более общего утверждения. Теор е м а 4. Пусть Х вЂ” выпуклое множество из Е", ш1 Х Ф И, Пусть гектор с Ф О и число ч таковы, что (с, х) > ч при всех х г= Х. Тогда (с, х) >Т гугш(п(Х. Д о к а з а т о л ь с т в о. Допустим поотивное; пусть существует такая точка хз ш гп1 Х, что (с, хз> = Т. По определению внутренней точки найдется такое е, > О, что г = х, — есД с) ш Х при всех е (О < е < е,).
Тогда Т < (с, г) = (с, хс) — е(с) = т — е(с( < Т. Получилось противоречивое неравенство, из которого и следует утвержденна теоремы. С л е д с т в п е 1. Пусть Х вЂ” выкуклое лтожестео из Е", 1п( Х Ф ю1. Тогда любая гиперплоскость (с, х — у) = О, опорная к множеству Х в какой-либо точке у ш Гр Х, яв.гяется собственно о ~орной к Х, или, точнее, (с, х — у) > О гух гн(п(Х.
Доказательство. Ич определеяня опорной гнперплоскости к Х в точке у следует, что (с, х) > (с, у) = 1п((с, х) = 1п1 (с, х) = Т при всех хыХ х==Х х гн Х. В силу теоремы 4 тогда <с, х) > т = <с, у) для любой точки х ш (п(Х. В следующей теореме показывается, что выпуклое замкнутое множест- во полностью характериауется своими опорными гиперплоскостями. Т о о р е м а 5.
Всякое неп устое выпуклое замкнутое множество Х из Е" (Х Ф Е") является пересечением замкнутых полупространств, образо- ванных всевозможными опорными гиперп.госкостями к множеству Х, со- держагуими Х. Доказательство. Поскольку Х~ Е". то ГРХ~ 8. Возьмем лго- бую точку у ш Гр Х. Множество всех опорных векторов множества Х в точ- ке у обозначим через Сг. Выше было замечено, что С, Ф Ег при всех у ш ж ГРХ. Обозначим А= () () (хг <с, х — у>~ )0). Пам надо покау=грх снс, зать, что Л = Х, Если х ш Х, то для всех у ш Гр Х и всех с ш С, имеем (с, х — у» О, т.
е. х ш А. Следовательно. Х с Л. Докажем обратное включопио А с Х Допустим противное: пусть су- ществует точка а ш Л, а зы Х. Поскольку Х вЂ” замкнутое множество, то по теореме 1 множество Х и точка а сильно отделимы. Точнее, при доказа- тельстве теоремы 1 было показано, что гнперплоскость <с„и — г> = О, где г = Ух(а), с. = г — а, такова, что (с„х — г) > О при всех х ш Х = Х, а (с„а — г) < О. Это значит, что с. ш С, (г ш Гр Х), и поэтому для точки а ш А должно бы быть (с„а — г) > О в силу опредоления А.
Полученное противоречие показывает, что А с Х. Трсбусгюе равенство Л = Х до- казано. Согласно теореме 5 выпуклое замкнутое множество характеризуется си- стемой неравенств (с, х) > (с, у) (х гн Х), котоРые могкпо записать в ви- де 1п1(с, х> =- <с, у), с ш Сг, у гм Гр Х. Если заменить с на — е, то эти усх ловия приводят к равенствам зпр<е,х>=(в,у>, егп — С„, угнГРХ. Тах ним образом, всякое выпуклое замкнутое множество Х хараитериауется зна- чениями функции 6 (е, Х ) = з«Р (е, х), называегюй опорной ~~ ункцией мяох игества Х (здесь возмогкны аначения 6(е, Х) = оо для некоторых е гн Е"), Это обстоятельство отражено также и в следующей теореме.
ВЛУЭИННТЫ ВЬШУИЛОГО АНАЛИЗА [РЛ. о Теорема 6. Пусть дла двух множеств А, В ив К" иевеетно, что вир(е,а)~эир(е,Ь) е'е»пйв», [в[=1. оЫА ЬЫВ Тогда со А с со В; в частности, если А, В выпуклы и еамкнуты, то А»= В. Кали вир (е, а) = еир (е, Ь) >»»е аи Е", [ в [ = 1, оЫА ЬЫВ то со А = со В; в частности, если А, В выпуклы и еамкнуты, то А = В. Докаэательство. Допустим, что соА»лсоВ. Тогда существует точка а,»н соА, но а,ф со В.
По теореме 5.1 множество юВ и точка ао сильно отделимы, т, е, существуют такое ваш Ее ([еа! = 1), ео) О, что <еа, Ь) «ео, ао) — ео при всех Ь ш соВ. Отсюда, пользуясь теоремой 19, имеем (е,Ь)4 еир (е,а) — е = эир (е,а) — е при всех ЬаисоВ, ВЫСО А так что эиэ (е, Ь) = эир (е, Ь) ~ эир(е, а) — е < еир (е, а). При о' — о' а-,> а' ЬмсоВ о аЯА о >плп к противоречию с условием теоремы.
Следовательно, со А с со В. Если А, В выпуклы и еамкнуты, то в силу теорем 1.5, 1.6 А = со А = А = со А, со В = В, и поэтомуА сВ. Справедливость последнего утвер>кде- ния теоремы следует иэ того, что равенство б(е, А) = б(е, В) эквивалент- но двум неравенствам б(е, А) <6(е, В), б(е, В) <б(е, А) (е»иЕ"). 3. Теорему 2 можно истолковать как необходимое условие пустоты пе- ресечения двух выпуклых множеств А и В; если А [) В = >2[, А и В выну>ь лы (тогда г[А ПгйВ = »о), то необходимо существуют вектор е»ВЕе (е Ф 0) и число 7 такие, что (е, а) > 7 при всех а ш А и (с, Ь) < 7 при всех Ь ш В.
Положим ໠— — е, сг = — с, 7» = 7, 7, = — 7. Тогда приведенное необходимое условие пустоты пересечения двух выпуклых множеств А и В может быть ваписано в следующей симметричной форме: (е, и) >у >»»и»н А, (е, и) ~ 7 'а»и»и В, с» + ег —— О, "[» + "[г = О, где хотя бы один иэ векторов с, или аг не равен нулю.
Следующая теорема обобщает это утверждение и дает необходимое условие пустоты пересечения любого конечного числа выпуклых множеств [52). Теорема 7. Пусть некуатые множества Аа, А», ..., Ан ив Ее выпуклы и А, [[ А» ()...[[ А = И. Тогда необходимо существуют векторы еа, е»,..., а, »и К", не еае равные нулю, и числа 7а, 7», ..., 7„, такие, что (аыи))7» 'а»иаэА», [=0,1, ...,ы. (7) со+ а»+...+ е„= О, (6) 7а+ 7» + " ° + 7 = О. (9) Для докаэательства атой теоремы нам понадобится прямое (декартово) проиэведение конечного числа множеств, а также прямое проивведение евклидовых пространств. Напомним соответствующие определения.
Определение 3. Пусть Ан ..., А — какие-либо множества. Множество А, состоящее иэ всевоэможных упорядоченных наборов (точек) а = = (а„..., а ), где а» = А» (» 1, ..., >и), наэывается прямым проиеведением множеств А», ..., Ан и обоаначается черве А» Х .. Х А =А. ОТДЕЛИМОСТЬ ВЫНУИЛЫХ МНОЖЕСТВ 201 Пусть Х 1, ..., ы~™ — вещественные линейные пространства. Положим п1 »»те Ь=Ь 1Х ...ХВ ы. для элементов (точек) а = (а», ..., а ), Ь = = (Ь», ..., Ь„)»н В определим сумму а+ Ь = (а»+ Ь», ..., а + Ь„) и про наведение на вещественное число па = (паь ..., аа,„), где под а»+ Ь» и ыа» понимаются соответствующие операции в Еп» (» = 1, ..., тл). В результате получим вещественное линейное пространство Ь, называемое прямым п1 п»п и» и» произведением линейных пространств В 1, ..., В ~.
Если В =Š— евклидовы пространства раэмерности и» (» = 1,..., тл), то в прямом пронэвеп» пе» денни Е=Е Х...ХЕ также можно ввести скалярное проиэведение (а, Ь) = (аь Ь») +... + (а, Ь ) и норму )а! = (а, а)ы» = ((а»(1+... ...+ )а )в)пе, где (а», Ь») и )а») — соответственно скалярное произведение и норма в Е '. Полученное евклидова пространство Е нааывают прап» пе». мым проиеведением евклидовых пространств Е „..., Е;раэмерностьпро странства Е равна п»+... + и,„. Например, само евклидова пространство Е" является прямым произведением п одномерных евклидовых пространств: Е" = Е' Х...
ХЕ'. Параллелепипед (и = (и', ..., и"): а» ~ и' ( й», = 1, ..., и) представляет собой прямое проиэведение отреэков (»»», 0») (» = 1, ..., и). Прямое проиэведение выпуклых множеств, очевидно, само выпукло. Докаэательство теоремы 7. Пусть Е=Е")(...)(Е» — прямое проиэведение тл и-мерных евклидовых пространств. Тогда А = А» Х... ...)(А»мЕ. Введем в Е едиагональноев множество В = (Ь = (Ьь ..., Ь ): Ь, = ... = Ь = ае, ао»иА»). Нетрудно видеть, что пересечение () А» пу»-о сто тогда и только тогда, когда А () В пусто.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
