Теорема о разделении гиперплоскостей

О существовании гиперплоскостей, разделяющих непересекающиеся выпуклые множества

В геометрии теорема о разделении гиперплоскостей — это теорема о непересекающихся выпуклых множествах в n- мерном евклидовом пространстве . Существует несколько довольно похожих версий. В одной версии теоремы, если оба эти множества замкнуты и хотя бы одно из них компактно , то между ними есть гиперплоскость и даже две параллельные гиперплоскости между ними, разделенные зазором. В другой версии, если оба непересекающихся выпуклых множества открыты, то между ними есть гиперплоскость, но не обязательно какой-либо зазор. Ось, ортогональная разделяющей гиперплоскости, является разделяющей осью , потому что ортогональные проекции выпуклых тел на ось не пересекаются.

Теорема об отделении гиперплоскостей принадлежит Герману Минковскому . Теорема об отделении Хана–Банаха обобщает результат на топологические векторные пространства .

Связанным результатом является теорема о поддерживающей гиперплоскости .

В контексте опорных векторных машин оптимально разделяющая гиперплоскость или гиперплоскость с максимальным запасом — это гиперплоскость , которая разделяет две выпуклые оболочки точек и находится на одинаковом расстоянии от них. ^{[1] [2] [3]}

Заявления и доказательства

Теорема о разделении гиперплоскостей ^[4]  —  Пусть и — два непересекающихся непустых выпуклых подмножества . Тогда существуют ненулевой вектор и действительное число такие, что ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle v}$ ${\displaystyle c}$

${\displaystyle \langle x,v\rangle \geq c\,{\text{ and }}\langle y,v\rangle \leq c}$

для всех в и в ; т.е. гиперплоскость , нормальный вектор, разделяет и . ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle y}$ ${\displaystyle B}$ ${\displaystyle \langle \cdot ,v\rangle =c}$ ${\displaystyle v}$ ${\displaystyle A}$ ${\displaystyle B}$

Если оба множества замкнуты и хотя бы одно из них компактно, то разделение может быть строгим, то есть для некоторого ${\displaystyle \langle x,v\rangle >c_{1}\,{\text{ and }}\langle y,v\rangle <c_{2}}$ ${\displaystyle c_{1}>c_{2}}$

Во всех случаях предположим, что являются непересекающимися, непустыми и выпуклыми подмножествами . Краткое изложение результатов следующее: ${\displaystyle A,B}$ ${\displaystyle \mathbb {R} ^{n}}$

Число измерений должно быть конечным. В бесконечномерных пространствах существуют примеры двух замкнутых, выпуклых, непересекающихся множеств, которые не могут быть разделены замкнутой гиперплоскостью (гиперплоскостью, где непрерывный линейный функционал равен некоторой константе) даже в слабом смысле, где неравенства не являются строгими. ^[5]

Здесь компактность в гипотезе не может быть ослаблена; см. пример в разделе Контрпримеры и уникальность. Эта версия теоремы о разделении обобщается на бесконечномерную размерность; обобщение более известно как теорема о разделении Хана–Банаха .

Доказательство основано на следующей лемме:

Лемма  —  Пусть и — два непересекающихся замкнутых подмножества , и предположим, что — компактно. Тогда существуют точки и , минимизирующие расстояние над и . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle A}$ ${\displaystyle a_{0}\in A}$ ${\displaystyle b_{0}\in B}$ ${\displaystyle \|a-b\|}$ ${\displaystyle a\in A}$ ${\displaystyle b\in B}$

Доказательство леммы

Пусть и — произвольные пары точек, и пусть . Так как компактно, то оно содержится в некотором шаре с центром в ; пусть радиус этого шара равен . Пусть — пересечение с замкнутым шаром радиуса вокруг . Тогда компактно и непусто, так как содержит . Так как функция расстояния непрерывна, существуют точки и , расстояние которых является минимальным по всем парам точек в . Осталось показать, что и на самом деле имеют минимальное расстояние по всем парам точек в . Предположим от противного, что существуют точки и такие, что . Тогда, в частности, , и по неравенству треугольника . Следовательно, содержится в , что противоречит тому факту, что и имели минимальное расстояние по . ${\displaystyle a\in A}$ ${\displaystyle b\in B}$ ${\displaystyle r_{1}=\|b-a\|}$ ${\displaystyle A}$ ${\displaystyle a}$ ${\displaystyle r_{2}}$ ${\displaystyle S=B\cap {\overline {B_{r_{1}+r_{2}}(a)}}}$ ${\displaystyle B}$ ${\displaystyle r_{1}+r_{2}}$ ${\displaystyle a}$ ${\displaystyle S}$ ${\displaystyle b}$ ${\displaystyle a_{0}}$ ${\displaystyle b_{0}}$ ${\displaystyle \|a_{0}-b_{0}\|}$ ${\displaystyle A\times S}$ ${\displaystyle a_{0}}$ ${\displaystyle b_{0}}$ ${\displaystyle A\times B}$ ${\displaystyle a'}$ ${\displaystyle b'}$ ${\displaystyle \|a'-b'\|<\|a_{0}-b_{0}\|}$ ${\displaystyle \|a'-b'\|<r_{1}}$ ${\displaystyle \|a-b'\|\leq \|a'-b'\|+\|a-a'\|<r_{1}+r_{2}}$ ${\displaystyle b'}$ ${\displaystyle S}$ ${\displaystyle a_{0}}$ ${\displaystyle b_{0}}$ ${\displaystyle A\times S}$ ${\displaystyle \square }$

Доказательство иллюстрации.

Доказательство теоремы

Сначала докажем второй случай. (См. схему.)

WLOG, компактен. По лемме существуют точки и на минимальном расстоянии друг от друга. Так как и не пересекаются, то имеем . Теперь построим две гиперплоскости, перпендикулярные отрезку прямой , с перекрёстком и перекрёстком . Мы утверждаем, что ни одна из них не входит в пространство между , и, таким образом, перпендикулярные гиперплоскости удовлетворяют требованию теоремы. ${\displaystyle A}$ ${\displaystyle a_{0}\in A}$ ${\displaystyle b_{0}\in B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle a_{0}\neq b_{0}}$ ${\displaystyle L_{A},L_{B}}$ ${\displaystyle [a_{0},b_{0}]}$ ${\displaystyle L_{A}}$ ${\displaystyle a_{0}}$ ${\displaystyle L_{B}}$ ${\displaystyle b_{0}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle L_{A},L_{B}}$ ${\displaystyle (a_{0},b_{0})}$

Алгебраически гиперплоскости определяются вектором и двумя константами , такими что . Наше утверждение состоит в том, что и . ${\displaystyle L_{A},L_{B}}$ ${\displaystyle v:=b_{0}-a_{0}}$ ${\displaystyle c_{A}:=\langle v,a_{0}\rangle <c_{B}:=\langle v,b_{0}\rangle }$ ${\displaystyle L_{A}=\{x:\langle v,x\rangle =c_{A}\},L_{B}=\{x:\langle v,x\rangle =c_{B}\}}$ ${\displaystyle \forall a\in A,\langle v,a\rangle \leq c_{A}}$ ${\displaystyle \forall b\in B,\langle v,b\rangle \geq c_{B}}$

Предположим, что существует некоторая такая, что , тогда пусть будет основанием перпендикуляра из к отрезку прямой . Так как является выпуклой, находится внутри , и по плоской геометрии ближе к , противоречие. Аналогичное рассуждение применимо к . ${\displaystyle a\in A}$ ${\displaystyle \langle v,a\rangle >c_{A}}$ ${\displaystyle a'}$ ${\displaystyle b_{0}}$ ${\displaystyle [a_{0},a]}$ ${\displaystyle A}$ ${\displaystyle a'}$ ${\displaystyle A}$ ${\displaystyle a'}$ ${\displaystyle b_{0}}$ ${\displaystyle a_{0}}$ ${\displaystyle B}$

Теперь о первом случае.

Подойти к обоим изнутри с помощью и , так чтобы каждый был замкнутым и компактным, а объединения были относительными внутренностями . ( Подробности см. на странице относительной внутренней части .) ${\displaystyle A,B}$ ${\displaystyle A_{1}\subseteq A_{2}\subseteq \cdots \subseteq A}$ ${\displaystyle B_{1}\subseteq B_{2}\subseteq \cdots \subseteq B}$ ${\displaystyle A_{k},B_{k}}$ ${\displaystyle \mathrm {relint} (A),\mathrm {relint} (B)}$

Теперь, согласно второму случаю, для каждой пары существует некоторый единичный вектор и действительное число , такие, что . ${\displaystyle A_{k},B_{k}}$ ${\displaystyle v_{k}}$ ${\displaystyle c_{k}}$ ${\displaystyle \langle v_{k},A_{k}\rangle <c_{k}<\langle v_{k},B_{k}\rangle }$

Поскольку единичная сфера компактна, мы можем взять сходящуюся подпоследовательность, так что . Пусть . Мы утверждаем, что , тем самым разделяя . ${\displaystyle v_{k}\to v}$ ${\displaystyle c_{A}:=\sup _{a\in A}\langle v,a\rangle ,c_{B}:=\inf _{b\in B}\langle v,b\rangle }$ ${\displaystyle c_{A}\leq c_{B}}$ ${\displaystyle A,B}$

Предположим, что нет, тогда существует такое , что , тогда, поскольку , для достаточно большого , имеем , противоречие. ${\displaystyle a\in A,b\in B}$ ${\displaystyle \langle v,a\rangle >\langle v,b\rangle }$ ${\displaystyle v_{k}\to v}$ ${\displaystyle k}$ ${\displaystyle \langle v_{k},a\rangle >\langle v_{k},b\rangle }$

Поскольку разделяющая гиперплоскость не может пересекать внутренности открытых выпуклых множеств, то имеем следствие:

Теорема разделения I  —  Пусть и — два непересекающихся непустых выпуклых множества. Если открыто, то существуют ненулевой вектор и действительное число, такие, что ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle v}$ ${\displaystyle c}$

${\displaystyle \langle x,v\rangle >c\,{\text{ and }}\langle y,v\rangle \leq c}$

для всех в и в . Если оба множества открыты, то существуют ненулевой вектор и действительное число такие, что ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle y}$ ${\displaystyle B}$ ${\displaystyle v}$ ${\displaystyle c}$

${\displaystyle \langle x,v\rangle >c\,{\text{ and }}\langle y,v\rangle <c}$

для всех в и в . ${\displaystyle x}$ ${\displaystyle A}$ ${\displaystyle y}$ ${\displaystyle B}$

Случай с возможными пересечениями

Если множества имеют возможные пересечения, но их относительные внутренности не пересекаются, то доказательство первого случая по-прежнему применимо без изменений, что дает: ${\displaystyle A,B}$

Теорема разделения II  —  Пусть и — два непустых выпуклых подмножества с непересекающимися относительными внутренностями. Тогда существуют ненулевой вектор и действительное число, такие, что ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle v}$ ${\displaystyle c}$

${\displaystyle \langle x,v\rangle \geq c\,{\text{ and }}\langle y,v\rangle \leq c}$

в частности, у нас есть теорема о поддерживающей гиперплоскости .

Теорема об опорной гиперплоскости  —  если — выпуклое множество в и — точка на границе , то существует опорная гиперплоскость , содержащая . ${\displaystyle A}$ ${\displaystyle \mathbb {R} ^{n},}$ ${\displaystyle a_{0}}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle a_{0}}$

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

Если аффинная оболочка не является всем , то расширяем аффинную оболочку до опорной гиперплоскости. В противном случае не пересекается с , поэтому применяем приведенную выше теорему. ${\displaystyle A}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \mathrm {relint} (A)=\mathrm {int} (A)}$ ${\displaystyle \mathrm {relint} (\{a_{0}\})=\{a_{0}\}}$

Обратная теорема

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

Контрпримеры и уникальность

Теорема неприменима, если одно из тел невыпуклое.

Если один из A или B не является выпуклым, то существует множество возможных контрпримеров. Например, A и B могут быть концентрическими окружностями. Более тонкий контрпример — это тот, в котором A и B оба замкнуты, но ни один из них не компактен. Например, если A — замкнутая полуплоскость, а B ограничен одним плечом гиперболы, то строго разделяющей гиперплоскости не существует:

${\displaystyle A=\{(x,y):x\leq 0\}}$

${\displaystyle B=\{(x,y):x>0,y\geq 1/x\}.\ }$

(Хотя, согласно второй теореме, существует гиперплоскость, разделяющая их внутренности.) Другой тип контрпримера имеет компактный A и открытый B. Например, A может быть замкнутым квадратом, а B может быть открытым квадратом, который касается A.

В первой версии теоремы, очевидно, разделяющая гиперплоскость никогда не является единственной. Во второй версии она может быть единственной, а может и не быть. Технически разделяющая ось никогда не является единственной, поскольку ее можно перенести; во второй версии теоремы разделяющая ось может быть единственной с точностью до переноса.

Угол рога дает хороший контрпример для многих разделений гиперплоскости. Например, в единичный круг не пересекается с открытым интервалом , но единственная линия, разделяющая их, содержит всю . Это показывает, что если замкнуто и относительно открыто , то не обязательно существует разделение, которое является строгим для . Однако, если замкнуто, то такое разделение существует. ^[6] ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle ((1,0),(1,1))}$ ${\displaystyle ((1,0),(1,1))}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$

Больше вариантов

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

Можно найти больше результатов. ^[6]

Использование при обнаружении столкновений

При обнаружении столкновений теорема о разделении гиперплоскостей обычно используется в следующей форме:

Теорема о разделяющей оси  —  Два замкнутых выпуклых объекта не пересекаются, если существует линия («разделяющая ось»), на которую проекции двух объектов не пересекаются.

Независимо от размерности, разделяющая ось всегда является линией. Например, в 3D пространство разделено плоскостями, но разделяющая ось перпендикулярна разделяющей плоскости.

Теорема о разделяющей оси может быть применена для быстрого обнаружения столкновений между полигональными сетками. Нормаль каждой грани или другое направление элемента используется как разделяющая ось. Обратите внимание, что это дает возможные разделяющие оси, а не разделяющие линии/плоскости.

В 3D использование только нормалей граней не позволит разделить некоторые случаи не сталкивающихся ребер. Требуются дополнительные оси, состоящие из перекрестных произведений пар ребер, по одному от каждого объекта. ^[7]

Для повышения эффективности параллельные оси можно рассчитывать как одну ось.

Смотрите также

• Двойной конус
• Лемма Фаркаса
• Теорема Кирхбергера
• Оптимальное управление

Примечания

1. Хасти, Тревор ; Тибширани, Роберт ; Фридман, Джером (2008). Элементы статистического обучения: добыча данных, вывод и прогнозирование (PDF) (Второе изд.). Нью-Йорк: Springer. С. 129–135.
2. Witten, Ian H.; Frank, Eibe; Hall, Mark A.; Pal, Christopher J. (2016). Data Mining: Practical Machine Learning Tools and Techniques (Четвертое изд.). Morgan Kaufmann. С. 253–254. ISBN 9780128043578.
3. Дейзенрот, Марк Питер; Фейсал, А. Альдо; Онг, Ченг Сун (2020). Математика для машинного обучения . Cambridge University Press. стр. 337–338. ISBN 978-1-108-45514-5.
4. Бойд и Ванденбергхе, 2004, Упражнение 2.22.
5. Хаим Брезис , Анализ функций: теория и приложения , 1983, примечание 4, стр. 7.
6. Stoer, Josef; Witzgall, Christoph (1970). Выпуклость и оптимизация в конечных измерениях I. Springer Berlin, Heidelberg. (2.12.9). doi :10.1007/978-3-642-46216-0. ISBN 978-3-642-46216-0.
7. «Расширенная векторная математика».

Ссылки

• Бойд, Стивен П.; Ванденберг, Ливен (2004). Выпуклая оптимизация (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3.
• Гольштейн, Э.Г.; Третьяков, Н.В. (1996). Модифицированные лагранжианы и монотонные отображения в оптимизации . Нью-Йорк: Wiley. С. 6. ISBN 0-471-54821-9.
• Симидзу, Киётака; Ишизука, Йо; Бард, Джонатан Ф. (1997). Недифференцируемое и двухуровневое математическое программирование . Бостон: Kluwer Academic Publishers. стр. 19. ISBN 0-7923-9821-1.

• Солтан, В. (2021). Свойства поддержки и разделения выпуклых множеств в конечной размерности . Extracta Math. Т. 36, № 2, 241-278.

Внешние ссылки

• Обнаружение столкновений и реагирование