3.1 Теоремы отделимости

В теории экстремальных задач фундаментальную роль игра­ют теоремы отделимости. Основное содержание этих теорем сво­дится к тому, что для двух выпуклых множеств X и У утвер­ждается существование гиперплоскости, такой, что множество X находится в одном из полупространств, определяемых этой гипер­плоскостью, а множество У — в другом. В этом случае говорят, что данная гиперплоскость отделяет эти множества друг от дру­га.

Теорема 3.1 Пусть X - выпуклое множество, х$ ^ X. Тогда существуют число е > 0 и ненулевой вектор а 6 Ка такие, что для всех х из X.

Доказательство. Возьмем произвольную точку ж' £ X и рас­смотрим множество

X' = X П {х £ В4 |  ||ж - х0\\ < \\х' - х0\\}.

Это множество непусто (так как оно содержит ж'), замкнуто и ограничено. Поэтому непрерывная функция /(ж) = ||ж — жо|| до­стигает на нем своего минимума. Другими словами, существует точка г 6 I' С I такая, что из условия ж £ X' следует

||ж — жо|| > \\г — жо||.

Понятно, что это неравенство справедливо и для точек ж из мно­жества X \ X', так как для них по построению множества X' имеем

||ж — жо|| > ||ж' — жо|| > \\г — жо||.

Пусть ж - некоторая точка из множества X. Тогда при любом А £ [0,1] точка у = Аж + (1 — Х)г принадлежит X и, как мы установили выше,

II 1|2 \ || ||2

\\у - ж0||   > \\г - х0\\ . Это неравенство можно переписать так:

\\2 ~ хо\\2 < ||^(ж — г) + г ~ жо||2 =

= А2||ж — г||2 + 2А(ж — г, г — жо) +    — жо||2. Тогда для любого А £ [0,1] справедливо соотношение

А2||ж — г\\2 + 2А(ж — г, г — жо) > 0.

Это возможно лишь, если (ж — г, 2 — жо) > 0. Положим а = жо — г (рис. 1) и е = ||а||2. По условию жо ^ X, поэтому а ф 0. Так как (а, ж — г) < 0, то (а, ж) + (а, жо — г) — (а, жо) < 0 и (а, ж) < (а, жо) — е. Теорема доказана.

Установленный факт называют сильной отделимостью выпук­лого множества X от не принадлежащей его замыканию точки жо- Термин отделимость отражает геометрическую суть неравен­ства (3.1), которое показывает, что можно так провести гипер­плоскость, что точка жо и множество X окажутся лежащими по разные стороны от нее. А сильная отделимость означает, что расстояние между точками множества X и точкой жо больше не­которого положительного числа.

Если точка жо находится на границе выпуклого множества X, то ее нельзя сильно отделить от X. В этом случае можно постро­ить гиперплоскость, проходящую через жо так, что все множество X окажется по одну сторону от указанной гиперплоскости. Это утверждение основывается на том, что для выпуклого множества X справедливо равенство гЫХ = гЫХ. В силу этого, если точка жо — граничная для множества X, то жо не может быть внутрен­ней точкой для множества X.

Теорема 3.2 Пусть X - выпуклое множество, жо $ X. Тогда существует ненулевой вектор а £ Кп такой, что (а, ж) < (а, жо) для всех х £ X.

Доказательство. Покажем сначала, что для любого выпукло­го множества X верно включение: гЫХ С X. Пусть г £ гпЬХ. Тогда существует симплекс, внутри которого находится точка г, а вершины симплекса а1,..., ап+1 принадлежат множеству гпЬХ. Ввиду непрерывности расстояний от точки г до граней симплек­са, как функций координат его вершин, найдется е > 0, такое, что изменение положения вершин в пределах окрестностей В{ак,е) не приводит к "выходу"точки г за пределы "смещенного"симплекса. В каждой из указанных окрестностей может быть выбрана точка Ьк, принадлежащая множеству X, поскольку о' £ I. В силу вы­пуклости, множество X содержит весь симплекс с вершинами в точках Ьк и, следовательно, точку г. Таким образом мы показали, что гЫХ С X.

По условию жо $ X. Следовательно, жо $ гЫХ и каждая окрестность точки жо содержит точки, не принадлежащие множе­ству X. Поэтому найдется последовательность точек {ж^} такая, что хк —т- жо и хк ^ X. Из теоремы 1 вытекает, что для каждого к найдется ненулевой вектор ак такой, что (ак,х) < (ак,хк) для любого ж £ X. Без ограничения общности можно считать, что для всех к справедливо \\ак\\ = 1. Из теоремы Вейерштрасса сле­дует, что существует подпоследовательность {ак'}1 сходящаяся к некоторому вектору а, ||а|| = 1. Так как (ак',х) < (ак',хк1) при всех ж £ X, то при / —т- со в пределе получим (а, ж) < (а, жо) для всех ж £ X. Теорема доказана.

Теорема 3.3 Пусть X и У - выпуклые множества, не имею­щие общих точек. Тогда существует ненулевой вектор а £ Ка такой, что (а, ж) < (а, у) для всех ж £ X и у £У.

Доказательство. Рассмотрим множество Е = X — У точек вида г = ж — у, где х £ X ж у £ У. Легко показать, что оно выпукло. По условию теоремы у множеств X ж У нет общих точек. Это значит, что множество Z не содержит точки 0. Поэтому в силу теоремы 3.2 точку 0 можно отделить от множества Z, то есть найдется ненулевой вектор а такой, что

(а, г) < (а, 0) = 0 для всех г £ Z.

Из определения множества Z получаем

(а, ж) < (а, у) для всех х £ У и у £ У. Теорема доказана.

Теорема 3.4 Пусть У, У выпуклые замкнутые множества, пересечение которых пусто,и множество X ограничено. Тогда существуют число е > 0 и ненулевой вектор а £ Ка такие, что (а, х) < (а, у) — е для всех х £ X и у £ У.

Доказательство. Как и в предыдущей теореме, рассмотрим выпуклое множество Z = X — У. Покажем, что оно замкнуто. Действительно, пусть гк = хк — ук —> 2о при к —т- со, где хк £ X, ук £ У. Убедимся, что 2о £ Z. Так как множество X - ком­пакт, то можно считать, что хк —> хо при к —> со, и, следователь­но, ук —т- уо = хо — го при к —> со. Отсюда, поскольку множества X и У замкнуты и точка жо принадлежит первому, а уо - второму из них, следует, что 2о принадлежит Z. Таким образом, множество Z содержит свои предельные точки, то есть является замкнутым. Поскольку множества У и У не имеют общих точек, то выпуклое замкнутое множество Z не содержит нуля. Тогда по теореме 3.1

 

Рис. 2. Множества У и У сильно отделены друг от друга

найдутся ненулевой вектор а и число е > 0 такие, что

(а, г) < (а, 0) — е = —е

для любого г Є 2 или (а, ж) < (а, у) — є для всех ж Є У и у Є У (рис. 2). Теорема доказана.

Следующий пример (рис. 3) показывает, что если множества X и У неограничены, то сильно отделяющей гиперплоскости мо­жет не существовать, а множество 2 = X — У может оказаться открытым. Пусть У = {ж Є і?2 | Ж2 > 1/жі,жі > 0}, У = {ж Є і?2 І Ж2 = 0}. В этом случае 2 = {ж Є і?2 | Ж2 > 0} и требуемая гиперплоскость отсутствует.