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