Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 57
Текст из файла (страница 57)
Это значит, что х ~ Х. Замкнутость Х доказана. Далее, по условию множества А и В не имеют общих точек. Поэтому 0 ф Х = Х. По теореме 1 тогда существует гиперплоскость (с, х) =0 такая, что (с, х) > !с$р > О для всех х Е Х. Отсюда имеем (с, а — Ь) > !с|с, или (с, а) ) $5.
ОТДЕЛИМОСТЬ ВЫПУКЛЫХ МНОЖЕСТВ 193 192 Гл. 4. ЭЛЕМЕНТЫ ВЪ|ПУКЛОГО АНАЛИЗА д' (с>,и)~)т! ЧиеА, (,,и)> Г, СЪЕВ, с>+сз — — О, г>+ гз — — О, (7) (8) (2) ) ) (с, Ь)+[с[э для всех аЕ А, Ь е В. Следовательно, |п[(с, а) > знр(с, Ь)+[с[э. ел ьвп Любая гиперплоскость (с, х) = у, где зпр(с, Ь) < у < !п[(с, а) будет сильно ген вел отделять множества А и В, что и требовалось. П Заметим, что требование ограниченности хотя бы одного из множеств в теореме 3 не может быть ослаблено (см. рис. 4.14).
2. Теоремы отделимости являются одним нв важных инструментов исследования свойств выпуклых функции и множеств, экстремальных задач, Ряд приложений этих теорем будут даны в последующих параграфах. Здесь же мы воспользуемся ими для получения представления любого выпуклого замкнутого множества из Е" в виде пересечения некоторого семейства полупространств. Определение 2. Гиперплоскость Г=(нее": (с, и) =т) называют опорной к мно>кеству Х, если (с, х) ) т при всех х е Х и (с, у) = т для некоторой точни у е Х. Опорную к Х гиперплоскость Г называют собственно опорной к Х, если Х не содержится в Г, т. е.
(с, хо) > г при некотором хо е Х. Вектор с, являющийся нормальным вектором опорной [собст. венно опорной! к Х гиперплоскости, проходящей через точку ус Х, называют опорным [собственно опорнь>м] вектором множества Х в точке у (рис. 4.16). Отметим, что через любую граничную точку у выпуклого множества Х из Е~ может быть проведена хотя бы одна опорная к Х гиперплоскость. В самом деле, если !и! Х ф >З, то граничными для Х будут только точки у е Х, у б!п1 Х, и согласно теореме 1 через нажду>о такую точку у можно прове. (с,х-у) = 0 сти собственно опорную к Х гиперплоскость. Если |и! Х =>и, то ан Х ~ Е, Гр Х = Х, и через кажду>о точку у е Х можно Рис, 4.16 провести гиперплоскость Г: (с, х — у) =О, где с — любой нену- левой вектор из ортогонального дополнения н Пв Х, Тогда Х с аЕХ с Г, так что à — опорная к Х гиперплоскость, не являющаяся собственно опорной. Теорема 1 уточняет, что если у е Х, у б г! Х, то среди опорных к Х гиперплоскостей, проходящих через точку у, можно найти собственно опорную.
Заметим, что выпуклое множество с непустой внутренностью ие может иметь опорных гиперплоскостей, не являющихся собственно опорными. Зто вытекает из следующего несколько более общего утверждения. Теорема 4. Пусть Х вЂ” выпуклое множество из Е", !и! ХТ'|2>. Пусть вектор сфО и число т таковы, что (с, х) > т дри всех х Е Х.
Тогда (с,х)) у Чхя!и! Х. Доказательство. Допустим противное, 'пусть существует такая точка х> е |п1 Х, что (с, хо) = т. По определению внутренней точки найдется такое го > О, что г = хо — гс/[с[ е Х при всех г, О< е < го. Тогда т < (с г) = (с хо)-а[с[= у — а[с[< т. Получилось противоречивое неравенство, из которого и следует утверждение теоремы, П Сл едет в не 1. Пусть Х вЂ” зьтуклог множество иг Е", |и! Х тй>. Тогда любая гилгрллоскость (с, х-у) = О, опорная к множгству Х в какой либо точке у Е Гр Х, являгтел собственно опорной к Х, или, точнег, (с, х — у) > 0 >>х е!и! Х.
Доказательство. Из определения опорной гиперплоскости к Х в точке у следует, что (с,х) >(с, у) = !и| (с,х) = !и (с, х) = г при всех хеХ. В силу теоремы 4 тогда (с, х) > геХ геХ > т = (с, у) для любой точки х Е !и! Х, П В следующей теореме показывается, что выпуклое замкнутое множество полностью характеризуется своими опорными гиперплоскостями, Теорема 5. Всякое неаустог выпуклоеэамннутогмножгствоХ из Е" (ХТЕ ) является пересечением замкнутых долупрогтранств, образованных всевозможными опорными гипгрплоскостями к множеству Х, содержащими Х. Доказательство.
Поскольку Х ~Е", то Гр Х фи>. Возьмем любую точку уеГр Х. Множество всех опорных векторов множества Х в точке у обозначим через С„. выше было замечено, что Сг ~ Я при всех у е Гр Х. Обозначим А = [] [] (х: (с, х-у) ) О). Нам г е грх г е с„ надо показать, что А = Х.
Если х е Х, то для всех у е Гр Х и всех с е С„имеем (ц х — у) > О, т. е. х е А. Следовательно, Х с А. Докажем обратное включение А с Х. Допустим противное: пусть существует точна а и А, а ф Х. Поскольку Х вЂ” замкнутое множество, то по теореме 1 множество Х и точка а сильно отделимы. Точнее, при доказательстве теоремы 1 было показано, что гиперплоскость (с„и— -л)=О, где х=Рх(а), с„=г-а, такова, что (с„, х-г) >О при всех хе Х=Х, а (с„а-г) <О. Это значит, что с, е С, г е Гр Х, и поэтому для точки а е А должно бы быть (с„, а — г) > 0 в силу определения А.
!г|олученное противоречие показывает, что А с Х. Требуемое равенство А = Х доказано. П Согласно теореме 5 выпуклое замкнутое множество характеризуется системой неравенств (с, х) ) (с, у), х Е Х, которые можно записать в виде !п1(с, х) = (с, у), се С, у 6Гр Х. Если заменить с на е = -с, то эти условия приводят к равенствам зцр(е,х) = (е, у), е е -С, х г' у Е Гр Х. Таким образом, вснкое выпуклое замкнутое множество Х характеризуется значениями функции б(е, Х) = знр(е, х), называемой опорной функцигй множества Х (здесь х возможны значения 6(е, Х) = со для некоторых е Е Е"). Это обстоятельство отражено таюне и в следующей теореме. Теорема 6.
Пусть для двух множгсл>вА, В из Е" известно, что зир(е,а) < зцр(е, Ь) ге еЕ~> [с[=1. ел ьав Тогда со А С со В; з частности, если А, В вьтуклы и замкнутьь то А С В. Если зир(е,а)= зпр(е,Ь) теЕЕч, [в[=1, аал ьел то со А =со В; в частности, голи А, В выпуклы и замкнуты, то А = В. Доказательство.
Допустим, чтосоА)бсоВ.Тогда существуетточка а есоА, но а б у со В. По теореме 1 множество со В и точка ао сильно отделимы, т. е. существуют такое ео е е Е", [го[=1, го >О, что (ео, Ь) < (ео, а>)-го при всех Ь есо В. Отсюда, пользуясь теоремой 1 9, имеем (ео, Ь) < еир (го,а) — го — — зир(ео,а) — го при всех Ь е соВ, твк что зир(ео, Ь) = гегьХ гел ьев эцр (го, Ь) < эвр(ео, а) — го < зир(ео, а). Пришли к противоречию с условием теоремы. ВесоВ аал Следовательно, со А С со В. Если А, В выпуклы и замкнуты, то в силу теорем 1,2, 1.6 А = =соА = А =соА, со В = В, и поэтому А С В. Справедливость последнего утверждения теоремы следует из того, что равенство 6(е, А) = 6(е,В) эквивалентно двум неравенствам б(е, А) < б(е, В), б(е, В) ч б(е, А), е е Е". П 3.
Теорему 2 можно истолковать как необходимое условие пустоты пересечения двух выпуклых множеств А и В: если А г> В = |2>, А и В выпуклы (тогда и' А п г! В = Е>), то необходимо существуют вектор с е е", с э!О, и число т такие, что (с, а) > т при всех ае А и (с, ь) < т при всех Ь Е В. Положим с! — — с, сг — — -с, Г> —— .Г, .Гз — — — т. Тогда приведенное необходимое условие пустоты пересечения двух выпуклых множеств А и В может быть записано в следующей симметричной форме: где хотя бы один из векторов с, или сз не равен нулю. Следующая теорема обобщает это утверждение и дает необходимое условие пустоты пере.
сечения любого конечного числа выпуклых множеств [83; 225; 276]. Она называется теоремой Дубовицкого А. Я., Милютина А. А., которые впервые ее доказали для конусов. Теорема 7 [465]. Пусть нглустыг множества Ао,А>,...,Ат из Е" гьтуклы и АоГ>А! Г>...Г>А =>З. Тогда необходимо сУЩествцют вгктоРы со, с>,..., с ЕЕ", нг гсг равные нулю, и числа Го, т>, ..
ч т такиг, что (с|,и)>т! >уиЕА>, >=О,...,т, ге+с!+...+с =О, то+ 7! +... + т,„= О. 7 Ф.П. Васильев 194 Гл, 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА $5. ОТДЕЛИМОСТЬ ВЫПУКЛЪ|Х МНОЖЕСТВ 195 ,>, » (10) (сь, и) ) 7ь — — 1п! (сз, а) > — со аз л Чи с Аь, й = 1,, тп., (12) со ю с! +... + с = О. (сс и) Э 7О Час АО. Для доказательства этой теоремы нам понадобится прямое (декартово) произведение ко- нечного числа множеств, а также прямое произведение евклидовых пространств. Напомним соответствующие определения. О яре деление 3.
Пусть Ат,, А какие-либо множества. Множество Л, состоящее из всевозможных упорядоченных йаборов ~точек) а= (а>,..., а ), где а! = А«, » = 1,..., тп, называется прямым произведением множеств А>,..., А н обозначается через А! х ... ...хА =А, Пусть 1 "',, 0" — вещественные линейные пространства. Положим Ь = Ь ~~ х... х Ь" .
Для элементов (точек) а=(а„..., а ), 6 = (ь! «..., ь ) с ь определим сумму а+ь =(а>-ьь>, ..., а +6 ) и произведение на вещественное число аа=(аа>, „аа ), где пода,.+Ь! и аат »« »т понимаются соответствующие операции в Е ', » = 1,..., т. В результате получим веществен- ное линеиное пространство Ь, называемое прямым произведением линейных пространств Ь "«,..., Ьч". Если б "« = Е" — евклидовы пространства размерности пг, « = 1,..., т, то в прямом произведении Е =Е « х ... х Е" также можно ввести скалярное произведение (а ь)=(а>, ь!) 1-,...! (а, ь ) и ноРмУ]а]=(а а)~т~=(]а>]~+...ч]а ]~)~т~, где (ат, 6 ) и]а ]— соответственно скалярное произведение и норма в Ет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
