Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 46
Текст из файла (страница 46)
Однако симметрию здесь нетрудно восстановптгс нужно лишь взять вектор — с вместо с, постоянную — "( вместо ( и записать уравнение отделяющей гиперплосгюстя в виде < — с, и> = — "(. Очевидно, если гиперплоскость <с, и> = ( отделяет множества А и В, то гиперплоскость <дс, и> = р"< прп )г ть 0 также отделяет эти множества. Поэтому при необходимости можно считать, что )с( = 1. На рис. 4.10 — 4А4 изображены случаи, когда два множества собственно отделимы, на рис.
4.13 — сильно отделимы, на рис. 4.14 — строго отделимы. Однако ясно, что не всякие дза множества можно отделить гиперплоскостью (рис. 4.15). Ниже приводятся теоремы об отделимости выпуклых мнонгеств. Теорема 1. Пусть Х вЂ” непустое выпуклое множество иг Е". Тогда для любой точки уФГ1Х существует гиперплоскость <с, и> = (, собственно отделяющая множество Х и точку у, или, точнее, (с, х) ) 7 Чх ~ Х, 7) (с, у), (с,х)~у Ух~ иХ. Если точка у не принадлежит Х вЂ” замыканию Х, то лигожество Х (а также и Х) сильно отделимо от р.
Доказательство. Сначала рассмотрим случай УФХ. Напомним, что если Х вЂ” выпуклое множество, то Х также выпукло (см. теорему 1.2). Согласно теореме 4.1 ~огда существует проекция г=дг (у) точки у на множество Х, причем <з — у, х — г> ) 0 для всех хжХ. Положим с =в — у. С учетом влкмвнты ВыпуклОГО АнАлизА предыдущего неравенства будем иметь <с, х — у> = <г — у, х — г> + + <г — у, г — у> > !с!»>О или (с, х» <с, у>+ !с!'> <с, у> (хю »иХ). Это значит, что гиперплоскость (с, и) = (с, у) =Т сильно отделяет точку у от множества Х и, тем более, множества Х. Нетрудно видеть, что такая гиперплоскость не единственна.
Например, гиперплоскость (с, и> = (с, г) = ( также сильно отделяет Х и у, так как <с, х — г» 0 при всех х»иХ, <с, у — з> = <г— — у, у — г> — !с!' ( О. Теперь пусть У~Х, УФп'Х. Согласно теореме 1.11 тогда существует последовательность (у,)- у: У,ФХ, у»»иаНХ (й=1, 2, ...). По доказанному гиперплоскость <с„, и> = <с„у,>, где с»=(㻠— У»)/!з» вЂ” У»! з» = а»-(У»)» сильно отделяет Х и ун л так что <с„х» <с„, у,> при всех х»иХ.
По теореме Больцано— Вейерштрасса из последовательности (с„) (!с,! =1) можно выбрать подпоследовательность, сходящуюся к некоторому вектору с (!с! = 1). Без умаления общности можем считать, что вся последовательность (с„)- с. Переходя к пределу при й- ч в неравенстве (с„, х» (с„, у„) (х~Х), получаем <с, х) > (с, у) = = "( для всех х»иХ. Отсюда следует первое из неравенств (2).
Далее, возьмем любую точку х»ип'Х. Согласно определению 1АО существует такое е >О, что 0(х, 2з) П аНХ»н Х. Тогда и, = =х — ес»»вО(х, 2е)П аНХ (й= 1, 2, ...). Ясно, что (и,) - и= =.т — ес. Покажем, что и = х — ес»ни'Х. Поскольку г» = = уз (у»)ен Хс аНХ =аНХ, у»яаНХ, то г„— у»~(,(ЛХ— х надпространство, параллельное аН Х Тогда с» (г, — у,) /! г,— — у,!»и11ЛХ. Поскольку ? 1ЛХ замкнуто в Е", (с»1- с, то с»и е» 1ЛХ. Отсюда следует, что и=х — зсы аНХ. Кроме того, так как !и„— х! = е (й = 1, 2, ...), то при й - в имеем !и — х! = е, так что и =х — ее »и О(х, 2е).
Следовательно, и=х — ес~г(Хс ~ХсХ. Тогда (= <с, у> < (с, и> = <с, х — ес> = <с, х> — е( ( <с, х>, или Т ( <с, х> для каждой точки х~ г1 Х, т. е. и'Х и у строго отделимы. Теорема 2. Пусть А и  — непустые выпуклые множества из Е", НА 0 НВ=И (например, А ПВ=И). Тогда существует гиперплоскость (с, и) ="(, строго отделяющая множества г(А и г1В, собственно отделяющая множества А и В, а также их замыкания Л, В, причем если А и В имеют общую граничную точку у, то (= <с, у>. Верно и обратное: если два выпуклых множества А и В собственно отделимы, то г1А П г(В = О.
Доказательство. Введем множество Х=п'А — г(В= (х»и жР: х= а — Ь, ая и'А, Ь я и'В). По теоремам 1А, 1.10 множество Х выпукло. Поскольку и'А П г(В= О, то ОФХ. Возможно два случая: ОФХ или 0»нХ. Если ОФХ, то согласно теореме 1 точка 0 и множество Х сильно отделимы, т.е. существуют такие счьО, е>0, что <с, х» <с, 0>+ в = е при всех х»иХ.
Если 0»иХ, ОФХ, то по той же теореме 1 найдется такой вектор сФО, что ОтделимОсть Выпуклых множестВ $ ь) 197 <с, х» 0 для всех хы Х, причем <с, х» 0 при хып'Х. Таким образом, в обоих случаях существует такой вектор счьО, что (с,х) )0 Чхен Х, (с,х) )0 Ухе= в(Х. (3) Из первого неравенства (3) с учетом определения множества Х имеем (с,а)~)(с,Ь) чаек и'А, Ьяи'В. (4) Далее, по теореме 1.10 г(Хезби. Это значит что существуют а, ыг1А, Ь, ыи'В такие, что х, =а,— Ь, ыг1'Х.
Из второго неравенства (3) тогда имеем <с, х,> = <с, а, — Ь,» О, или <с, а,» <с, Ь,>, а,~аг1А, Ь,~нг1'В. (5) Неравенство (4) остается справедливым для всех предельных точек множеств г1А, г1В, т. е. для всех аыг1А, Ь|нг1В. Но по теореме 1.12 и'.4 =А, г<В=В, так что <с, а» <с, Ь> при любых аыА, ЬыВ. Отсюда 1В1(с,а)Ъзпр(с,Ь). Возьмем гипер- аИА ь— и в плоскость <с, и> =7, где 7 — произвольное число, удовлетворяющее неравенству 1п1 (с, а) ) )у~ )зпр(с, Ь). Тогда а=А ь=в (с,а))у)(с,Ь) 1заенА, ЬенВ. (6) Из (5), (6) следует собственно отделимость множеств А и В и, тем более, множеств А и В.
Если у ы А П В, то 7 = <с, у>. Покая'ем, что построенная гиперплоскость <с, и> =7 строго отделяет множества г1'А и и'В. Из (5), (6) следует, что либо <с, а,» 7, либо <с, Ь,> ( 7. Пусть <с, а,» 7 (случай <с, Ь,> ( (7 рассматривается аналогично). Возьмем произвольную точку а ~и г1 А. Тогда а — а, ы 1 1п А, а+ е (а — а,) ы аН А при всех е ы К и по определению относительно внутренней точки найдется такое е > О, что Ь =а+ е(а — аа)яг1А.
Отсюда а =аа,+(1 — а)Ь (се= =е/(1+е)ы(0, 1)). Умножим неравенство <с, а,»7 на а, <с, Ь> > 7 на 1 — а и сложим. Получим и<с, а,>+(1 — и) <с, Ь> = = <с, а» 7. Таким образом, <с, а» 7 при всех аыг1А. Отсюда и из (6) следует, что множества г1А и г1В строго отделимы. Докажем вторую часть теоремы. Пусть множества А и В собственно отделимы, но пусть тем не менее г( А П г1'В чь И. Возьмем какую-либо точку и ы г1 А П г1 В. Тогда при достаточно малом е> О имеем а, =и — з(а, — и)ыг1А, Ь, =и — е(Ь,— и)~г! В, где а„Ь, взяты из (5).
В силу (4) <с, а,> = <с, и>(1+ е) — е<с, а,> > > <с, Ъ,> = <с, и>(1+ е) — е<с, Ьа>. Отсюда получаем <с, а,> --= ( <с, Ь,>, что противоречит (5). Следовательно, г1А ПпВ= 8. Приведем одну теорему о сильной отделимости двух выпуклых множеств. Теорема 3.
Лусть А и  — два выпуклых замкнутых множества, не имеющие общих точек, причем хотя бы одно из этих множеств ограничено. Тогда множества А и В сильно отделимы, ргл. а ЭЛЕМЕНТЫ ВЬГПУКЛОГО АНАЛИЗА Доказательство. Введем множество Х=А — В. Покажем, что оно замкнуто. Пусть х — некоторая предельная точка множества Х, пусть последовательность 1х„) щХ сходится к х.
Поскольку х,щХ, то найдутся а„знА, ЬпщВ такие, что х„=и,— в Ьв <В=1, 2, ...). По условию одно из множеств А или В ограничено. Пусть для определенности ограничено множество А. Тогда последовательность <а„) тнА ограничена. По теореме Больцапо — Вейерштрасса найдется подпоследовательность )аап), сходящаяся к некоторой точке а. В силу замкнутости А точка а принадлежит А. Тогда Ьп„= аз„— ха„-пЬ = а — х при й„- оа, причем Ь щВ в силу замкнутости В. Таким образом, для точки х получили представление х= а — Ь, где ащА, Ь зиВ. Это значит, что хил Х. Замкнутость Х доказана. Далее, по условию множества А и В не имеют общих точек. Поэтому ОФХ=Х. По теореме 1 тогда существует гиперплоскость <с, и> = О такая, что <с, х) > ~с!'>О для всех хаХ.
Отсюда имеем (с, а — Ь) > ~с!в, или (с, а) > (с, Ь>+ ~с!в для всех п~нА, ЬшВ. Следовательно, 1п1 (с,а)~)зпр(с, Ь) + )с!з. Любая а-А ЬЫВ гиперплоскость <с, и> =т, где зпр(с, Ь)(Т~1п1 (с,а), будет амв сильно отделять множества А и В, что и требовалось. Заметим, что требование ограниченности хотя бы одного из множеств в теореме 3 не может быть ослаблено <см. рис.
4.14). 2. Теоремы отделимости являются одним из важных интрументов ио. следованяя свойств выпуклых функций и множеств, экстремальных задач. Ряд приложений этих теорем будут даны в последующих параграфах. Здесь же мы воспользуемся ими для получения представления любого выпуклого заминутого множества из йа в виде пересечения некоторого семейства полупространств. Определение 2. Гиперплоскость Г =1измйа: (с, и) = т) называют опорной к множеству Х, если (с, х) ) т при всех х щ Х и (с, у) = т для некоторой точки у щ Х. Опорную к Х гиперплоскость Г называют собственно оиорной к Х, если Х не содержится в Г, т. е.
(с, хе) ) ) т при некотором хв щ Х, Вектор с, являющийсн нормальным вектором опорной <соб. К огненно опорной) к Х гиперплоскости, праха. У дящей через точку уев Х, называют опорным 1собстввнно оперным) вектором множества Х в точке у <рис. 4дб). Отметим, что через лгобую граничную точку у выпуклого множества Х из Еа может быть проведена хотя бы одна опорная к Х гяперплоскость. В самом деле, если шс Х Ф Я, то граничными для Х будут только точки у ш Х, у <6 ~ ш<Х, и согласно теореме 1 через каждую такую точку у можно провести собственно опорную к Х гиперплоскость.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
