Отделимость множеств: различия между версиями
Oleg23 (обсуждение | вклад) |
Oleg23 (обсуждение | вклад) |
||
Строка 7: | Строка 7: | ||
== Определения == | == Определения == | ||
− | '''Определение 1.''' ''Аффинной комбинацией | + | '''Определение 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.''' ''Аффинной оболочкой | + | '''Определение 2.''' ''Аффинной оболочкой множества $$A$$'' назовём множество всевозможных аффинных комбинаций точек множества $$A: \, aff A := |
− | \{\sum_{i = 1} ^ n \alpha_i x_i \, | \, n \in \mathbb N | + | \{\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.''' ''Относительной внутренностью | + | '''Определение 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$$ | + | '''Определение 4.''' Будем говорить, что ''множества $$A$$ и $$B$$ отделимы'', если найдётся такой действующий на $$X$$ линейный непрерывный функционал $$l \not= 0$$, что |
\begin{gather*} | \begin{gather*} | ||
\sup\limits_{x \in A}\left<l, x\right>\leq\inf\limits_{x \in A}\left<l, y\right>. | \sup\limits_{x \in A}\left<l, x\right>\leq\inf\limits_{x \in A}\left<l, y\right>. | ||
\end{gather*} | \end{gather*} | ||
− | Также говорят, что функционал $$l$$ | + | Также говорят, что ''функционал $$l$$ разделяет'' множества $$A$$ и $$B$$. |
− | '''Определение 5.''' Будем говорить, что множества $$A$$ и $$B$$ ''строго отделимы'', если найдётся такой действующий на $$X$$ линейный непрерывный функционал $$l\not=0$$, что | + | '''Определение 5.''' Будем говорить, что множества $$A$$ и $$B$$ ''строго отделимы'', если найдётся такой действующий на $$X$$ линейный непрерывный функционал $$l \not= 0$$, что |
\begin{gather*} | \begin{gather*} | ||
\sup\limits_{x \in A}\left<l, x\right><\inf\limits_{x \in A}\left<l, y\right>. | \sup\limits_{x \in A}\left<l, x\right><\inf\limits_{x \in A}\left<l, y\right>. | ||
\end{gather*} | \end{gather*} | ||
− | Также говорят, что функционал $$l$$ | + | Также говорят, что ''функционал $$l$$ строго разделяет'' множества $$A$$ и $$B$$. |
− | '''Предложение 1.''' Множества $$A, \, B$$ можно отделить тогда и только тогда, когда множество $$A − B$$ (имеется в виду сумма по Минковскому множеств $$A$$ и $$-B$$, то есть множество $$\{a - b \, | a \in A, \, b \in B \}$$) можно отделить от $$\{0\}$$ (множества, состоящего из одного нуля). Этим фактом мы воспользуемся при доказательстве следующей теоремы. | + | ==Теоремы отделимости== |
+ | |||
+ | '''Предложение 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_{x \in A}\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_{x \in A}\left<l, y\right>. | ||
+ | \end{gather*} | ||
+ | Последнее неравенство эквивалентно отделимости множеств $$A$$ и $$B$$. $$~~\blacksquare$$ | ||
+ | |||
+ | Этим фактом мы воспользуемся при доказательстве следующей теоремы. | ||
− | |||
'''Теорема 1.''' (О конечномерной отделимости). | '''Теорема 1.''' (О конечномерной отделимости). | ||
− | Пусть $$A, B$$ — непустые выпуклые подмножества $$R^n$$ и их относительные внутренности $$ri A$$ и $$ri B$$ не пересекаются. Тогда множества $$A$$ и $$B$$ можно отделить. | + | Пусть $$A, B$$ — непустые выпуклые подмножества $$\mathbb R^n$$ и их относительные внутренности $$ri A$$ и $$ri B$$ не пересекаются. Тогда множества $$A$$ и $$B$$ можно отделить. |
'''Доказательство.''' | '''Доказательство.''' | ||
− | Заметим, что так как $$ri A$$ и $$ri B$$ не пересекаются, то $$0\not\in (ri A-ri B)$$. Множество $$(ri A-ri B)$$ выпукло $$\Longrightarrow$$ (указать ссылку на лемму 1.4.2) $$\Longrightarrow$$ $$(ri A-ri B)$$ отделимо от нуля, а значит $$ri A$$ и $$ri B$$ отделимы, т.е. $$\exists l\not=0$$ и $$\gamma\in\mathbb{R}:$$$$\forall x\in{ri A},y\in{ri B} \Longrightarrow\left<l, x\right>\leq\gamma\leq\left<l, y\right>$$. | + | Заметим, что так как $$ri A$$ и $$ri B$$ не пересекаются, то $$0\not\in (ri A - ri B)$$. Множество $$(ri A - ri B)$$ выпукло $$\Longrightarrow$$ (указать ссылку на лемму 1.4.2) $$\Longrightarrow$$ $$(ri A-ri B)$$ отделимо от нуля, а значит $$ri A$$ и $$ri B$$ отделимы, т.е. $$\exists l\not=0$$ и $$\gamma\in\mathbb{R}:$$$$\forall x\in{ri A},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 \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$$ |
Версия 15:12, 27 октября 2023
Для получения многих результатов в выпуклом анализе ключевую роль занимают теоремы об отделимости выпуклых множеств. Дадим необходимые определения.
Далее будем считать, что $$X = (X, \, ||\cdot||)$$ - нормированное пространство, а $$A$$ и $$B$$ - его непустые подмножества. Дадим необходимые определения.
Определения
Определение 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_{x \in A}\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_{x \in A}\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_{x \in A}\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_{x \in A}\left<l, y\right>. \end{gather*} Последнее неравенство эквивалентно отделимости множеств $$A$$ и $$B$$. $$~~\blacksquare$$
Этим фактом мы воспользуемся при доказательстве следующей теоремы.
Теорема 1. (О конечномерной отделимости). Пусть $$A, B$$ — непустые выпуклые подмножества $$\mathbb R^n$$ и их относительные внутренности $$ri A$$ и $$ri B$$ не пересекаются. Тогда множества $$A$$ и $$B$$ можно отделить.
Доказательство. Заметим, что так как $$ri A$$ и $$ri B$$ не пересекаются, то $$0\not\in (ri A - ri B)$$. Множество $$(ri A - ri B)$$ выпукло $$\Longrightarrow$$ (указать ссылку на лемму 1.4.2) $$\Longrightarrow$$ $$(ri A-ri B)$$ отделимо от нуля, а значит $$ri A$$ и $$ri B$$ отделимы, т.е. $$\exists l\not=0$$ и $$\gamma\in\mathbb{R}:$$$$\forall x\in{ri A},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$$