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