Отделимость множеств

Для получения многих результатов в выпуклом анализе ключевую роль занимают теоремы об отделимости выпуклых множеств. Дадим необходимые определения.

Пример выпуклого множества.

Пример невыпуклого множества.

Дадим сперва необходимые определения.

Определения

Определение 1. Аффинной комбинацией точек $$x_1, x_2, \ldots, x_n \in X$$ назовём выражение $$\sum_{i = 1} ^ n \alpha_i x_i$$, где числа $$\alpha_1, \alpha_2, \ldots, \alpha_n$$ удовлетворяют условию $$\sum_{i = 1} ^ n \alpha_i = 1$$.

Определение 2. Аффинной оболочкой множества $$A$$ назовём множество всевозможных аффинных комбинаций точек множества $$A: \, aff A := \{\sum_{i = 1} ^ n \alpha_i x_i \, | \, n \in \mathbb N, \, x_1, \, x_2, \ldots, x_n \in X, \, \sum_{i = 1} ^ n \alpha_i = 1\}$$.

Определение 3. Относительной внутренностью множества $$A$$ назовём его «внутренность относительно аффинной оболочки $$A$$», то есть множество точек $$ri \, A := \{x \in X \, | \, \exists \varepsilon > 0: O(x, \, \varepsilon) \cap aff A \subset A\}$$. Здесь $$ O(x, \, \varepsilon) = \{y \in X \, | \, ||y - x|| < \varepsilon \}$$ - открытый шар в нормированном пространстве $$X$$.

Определение 4. Будем говорить, что множества $$A$$ и $$B$$ отделимы, если найдётся такой действующий на $$X$$ линейный непрерывный функционал $$l \not= 0$$, что \begin{gather*} \sup\limits_{x \in A}\left<l, x\right>\leq\inf\limits_{y \in B}\left<l, y\right>. \end{gather*}

Также говорят, что функционал $$l$$ разделяет множества $$A$$ и $$B$$.

Определение 5. Будем говорить, что множества $$A$$ и $$B$$ строго отделимы, если найдётся такой действующий на $$X$$ линейный непрерывный функционал $$l \not= 0$$, что \begin{gather*} \sup\limits_{x \in A}\left<l, x\right><\inf\limits_{y \in B}\left<l, y\right>. \end{gather*}

Также говорят, что функционал $$l$$ строго разделяет множества $$A$$ и $$B$$.

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

Предложение 1. Множества $$A, \, B$$ можно отделить тогда и только тогда, когда множество $$A − B$$ (имеется в виду сумма по Минковскому множеств $$A$$ и $$-B$$, то есть множество $$\{a - b \, | \, a \in A, \, b \in B \}$$) можно отделить от $$\{0\}$$ (множества, состоящего из одного нуля).

Доказательство.

1. Необходимость. Пусть множества $$A, \, B$$ отделимы. Это означает, что $$\exists l \not= 0$$ - линейный непрерывный функционал на $$X$$ такой, что \begin{gather*} \sup\limits_{x \in A}\left<l, x\right>\leq\inf\limits_{y \in B}\left<l, y\right>. \end{gather*} То есть \begin{gather*} \forall x \in X \; \forall y \in Y \left<l, x\right> \leq \left<l, y\right>, \end{gather*} что означает: \begin{gather*} \forall x \in X \; \forall y \in Y \left<l, x - y\right> \leq 0 = \left<l, 0\right>, \end{gather*} или \begin{gather*} \sup_{z \in A - B} \left<l, z\right> \leq 0 = \inf_{z \in \{0\}} \left<l, z\right>. \end{gather*} Последнее неравенство эквивалентно отделимости множества $$A - B$$ от множества $$\{0\}$$.

2. Достаточность. Пусть множество $$A - B$$ отделимо от нуля. Тогда $$\exists l \not= 0$$ - линейный непрерывный функционал на $$X$$ такой, что \begin{gather*} \sup_{z \in A - B} \left<l, z\right> \leq 0 = \left<l, 0\right>, \end{gather*} то есть \begin{gather*} \sup_{z \in A - B} \left<l, z\right> \leq 0 = \left<l, 0\right>, \end{gather*} и поскольку $$\sup (A - B) = \sup A -\inf B$$, то заключаем \begin{gather*} \sup\limits_{x \in A}\left<l, x\right>\leq\inf\limits_{y \in B}\left<l, y\right>. \end{gather*} Последнее неравенство эквивалентно отделимости множеств $$A$$ и $$B$$. $$~~\blacksquare$$

Этим фактом мы воспользуемся при доказательстве следующей теоремы. Предпошлем доказательству одну лемму.

Лемма 1. Пусть непустое множество $$C \subset \mathbb R ^ n$$ выпукло, причём $$0 \not \in int \, C$$. Тогда $$C$$ отделимо от нуля.

Доказательство. Рассмотрим выпуклое замкнутое множество $$\overline C$$. Понятно, что нуль не принадлежит внутренности $$int \, \overline C$$, поскольку $$int \, C = int \, \overline C$$. Поэтому либо нуль не принадлежит множеству $$\overline C$$, либо принадлежит его границе $$\partial \overline C$$. Значит, в любом случае существует последовательность $$x_i \to 0, \, x_i \not \in \overline C \, \forall i$$. Рассмотрим множества $$C_i := \overline C - x_i$$. Имеем $$0 \not \in C_i \, \forall i$$. Каждое из этих непустых выпуклых замкнутых множеств $$C_i$$ можно отделить от нуля. Следовательно, для $$\forall i$$ существуют числа $$l_i \in \mathbb R$$ такие, что $$\left< l_i, \eta \right> \geqslant 0 \, \forall \eta \in C_i$$. Нормируем каждый вектор $$l_i$$. Тогда все эти векторы единичные. Перейдём (по теореме Больцано-Вейерштрасса) от ограниченной последовательности $$(l_i)$$ к сходящейся подпоследовательности $$(l_{i_k})$$, обозначим $$l = \lim_{k \to +\infty} l_{i_k}, \, l \not= 0$$. Из определения множеств $$C_i$$ и неравенства Коши-Буняковского: \begin{gather*} \left< l_i, x \right> + |l_i| |x_i| \geqslant 0 \, \forall x \in \overline C \; \forall i. \end{gather*} Зафиксируем $$x \in \overline C$$, и, переходя в полученных неравенствах к пределу при $$i \to +\infty$$, получим $$\left< l, x \right> \geqslant 0$$. В силу произвольности выбора $$x$$ мы получаем, что $$C$$ отделимо от нуля. $$~~\blacksquare$$

Теорема 1. (О конечномерной отделимости). Пусть $$A, B$$ — непустые выпуклые подмножества $$\mathbb R^n$$ и их относительные внутренности $$ri \, A$$ и $$ri \, B$$ не пересекаются. Тогда множества $$A$$ и $$B$$ можно отделить.

Доказательство. Заметим, что так как $$ri \, A \cap ri \, B = \emptyset$$, то $$0\not\in (ri \, A - ri \, B)$$. Множество $$(ri \, A - ri \, B)$$ выпукло $$\Longrightarrow$$ $$(ri \, A - ri \, B)$$ отделимо от нуля в силу Леммы 1, а значит, $$ri \, A$$ и $$ri \, B$$ отделимы, то есть на $$X$$ существует линейный непрерывный функционал $$l \not= 0$$ и число $$\gamma \in \mathbb R: \forall x \in {ri \, A} \; \forall y \in {ri \, B} \Longrightarrow\left<l, x\right>\leq\gamma\leq\left<l, y\right>$$.

Пусть $$x \in A$$. Тогда существует последовательность точек $$\{x_i\}$$, лежащая в $$ri A$$ и сходящаяся к $$x$$. Поэтому, $$\left<l, x_i\right>\leq\gamma,$$ $$\forall i$$. Переходя к пределу по $$i$$, получаем, что, $$\left<l, x\right>\leq\gamma$$. Поступив аналогично для точек $$y$$ множества $$B$$, получим, что полученный линейный непрерывный функционал $$l$$ также разделяет $$A$$ и $$B$$.$$~~\blacksquare$$

Теперь перейдём к бесконечномерному пространству $$X$$. Отделимость множеств в $$X$$ имеет существенные отличия от отделимости множеств в $$\mathbb R ^ n$$, что показывает следующий пример.

Пример 1. В бесконечномерном пространстве $$l_2$$ числовых последовательностей $$(x_1, \, x_2, \, \ldots, \, x_n, \, \ldots)$$, для которых ряд $$\sum_{i = 1} ^ {+\infty} x_i ^ 2 < \infty$$, рассмотрим множество П $$= \{x = (x_1, \, x_2, \, \ldots, \, x_n, \, \ldots) \, | \, |x_i| \leqslant 2 ^ {-i} \, \forall i \}$$ - гильбертов кирпич. Гильбертов кирпич содержит нуль (проверяется подстановкой последовательности $$(0, \, 0, \, \ldots, \, 0, \, \ldots)$$ в определение П), является выпуклым компактом, не лежит ни в каком конечномерном пространстве. Далее, $$int$$ П не содержит нуля. Действительно, предположим противное: пусть $$0 \in int$$ П. Тогда $$\exists \varepsilon > 0: B(0, \, \varepsilon) = \{x \in l_2 \, | \, ||x||_{l_2} \leqslant \varepsilon\} \subset$$ П. Выберем $$j = \Big \lfloor \log_2 \displaystyle \frac{1}{\varepsilon} \Big \rfloor + 1$$. Тогда $$2 ^ {-j} < 2 ^ {-\log_2 \frac{1}{\varepsilon}} = \varepsilon$$.

Докажем, что П нельзя отделить от нуля. (В конечномерном пространстве отделимость выпуклого множества с внутренностью, не содержащей нуля, была бы гарантирована Леммой 1).

Действительно, предположим противное: пусть множества П и $$\{0\}$$ отделимы. Тогда существует разделяющий их ненулевой линейный функционал $$l \in l_2 ^ {*} = l_2$$ (здесь $$l_2 ^ {*}$$ - пространство, сопряженное к $$l_2$$; из курса функционального анализа известно, что l_2 ^ {*} = l_2). Имеем \begin{equation} \label{eq1} \left< l, \, x \right> \geqslant 0 \; \forall x \in П. \end{equation} Рассмотрим две последовательности векторов $$e_i ^ {+} = (0, \, 0, \, \ldots, \, 0, \, 2 ^ {-i}, \, 0, \, \ldots)$$ и $$e_i ^ {-} = (0, \, 0, \, \ldots, \, 0, \, -2 ^ {-i}, \, 0, \, \ldots)$$, где $$i \in \mathbb N$$, а единственная ненулевая компонента векторов $$e_i ^ {+}, \, e_i ^ {-}$$ имеет номер $$i$$. Подставим векторы из этой последовательности в \eqref{eq1}. Получим, что если функционал $$l = (l_1, \, l_2, \, \ldots, \, l_n, \, \ldots)$$, то из $$\left< l, \, e_i ^ {+} \right> = l_i 2 ^ {-i} \geqslant 0, \, \left< l, \, e_i ^ {-} \right> = -l_i 2 ^ {-i} \geqslant 0$$ следует $$l_i = 0 \; \forall i$$, и значит, $$l = 0$$.

Сформулируем достаточные условия строгой отделимости множеств в этом пространстве в виде теоремы.

Теорема 2. (О строгой бесконечномерной отделимости). Пусть $$A, \, B$$ - непустые выпуклые подмножества $$X, \, A \cap B = \emptyset, \; A$$ компактно, а $$B$$ замкнуто. Тогда множества $$A$$ и $$B$$ можно строго отделить.

Доказательство.