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

Иллюстрация теоремы об отделении гиперплоскостей.

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

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

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

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

Заявления и доказательства [ править ]

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

Доказательство леммы : Пусть Пусть последовательность в такой , что . Обратите внимание, что это в, поскольку выпукло и так . С${\ displaystyle \ delta = \ inf \ {| x |: x \ in K \}.}$${\ displaystyle x_ {j}}$${\ displaystyle K}$${\ displaystyle | x_ {j} | \ to \ delta}$${\ displaystyle (x_ {i} + x_ {j}) / 2}$${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle | x_ {i} + x_ {j} | ^ {2} \ geq 4 \ delta ^ {2}}$

${\displaystyle |x_{i}-x_{j}|^{2}=2|x_{i}|^{2}+2|x_{j}|^{2}-|x_{i}+x_{j}|^{2}\leq 2|x_{i}|^{2}+2|x_{j}|^{2}-4\delta ^{2}\to 0}$

as , является последовательностью Коши и поэтому имеет предел x в . Он уникален, так как если y находится внутри и имеет норму δ, то и x = y .${\displaystyle i,j\to \infty }$${\displaystyle x_{i}}$${\displaystyle K}$${\displaystyle K}$${\displaystyle |x-y|^{2}\leq 2|x|^{2}+2|y|^{2}-4\delta ^{2}=0}$${\displaystyle \square }$

Доказательство теоремы . Для непересекающихся непустых выпуклых множеств A , B пусть

${\displaystyle K=A+(-B)=\{x-y\mid x\in A,y\in B\}.}$

Так как выпукло и сумма выпуклых множеств выпукла, то выпукло. В силу леммы, замыкание в , которая является выпуклой, содержит вектор минимальной нормы. Поскольку является выпуклым, для любого in отрезок прямой${\displaystyle -B}$${\displaystyle K}$${\displaystyle {\overline {K}}}$${\displaystyle K}$${\displaystyle v}$${\displaystyle {\overline {K}}}$${\displaystyle n}$${\displaystyle K}$

${\displaystyle v+t(n-v),\,0\leq t\leq 1}$

лежит и так${\displaystyle {\overline {K}}}$

${\displaystyle |v|^{2}\leq |v+t(n-v)|^{2}=|v|^{2}+2t\langle v,n-v\rangle +t^{2}|n-v|^{2}}$.

Таким образом , мы имеем:${\displaystyle 0<t\leq 1}$

${\displaystyle 0\leq 2\langle v,n\rangle -2|v|^{2}+t|n-v|^{2}}$

и сдачи в аренду дает: . Следовательно, для любого х в А и у в В , имеем: . Таким образом, если v не равно нулю, доказательство завершено, так как${\displaystyle t\to 0}$${\displaystyle \langle n,v\rangle \geq |v|^{2}}$${\displaystyle \langle x-y,v\rangle \geq |v|^{2}}$

${\displaystyle \inf _{x\in A}\langle x,v\rangle \geq |v|^{2}+\sup _{y\in B}\langle y,v\rangle .}$

В более общем плане (охватывая случай v = 0) давайте сначала рассмотрим случай, когда внутренность не пуста. Внутренность может быть исчерпана вложенной последовательностью непустых компактных выпуклых подмножеств . ^{[ требуется пояснение ]} Поскольку 0 не входит , каждый содержит ненулевой вектор минимальной длины и, согласно аргументу в ранней части, мы имеем: для любого . Мы можем нормализовать 's, чтобы иметь длину один. Тогда последовательность содержит сходящуюся подпоследовательность (поскольку n-сфера компактна) с пределом v , который не равен нулю. У нас есть для любого x в интерьере${\displaystyle K}$${\displaystyle K_{1}\subset K_{2}\subset K_{3}\subset \cdots }$${\displaystyle K}$${\displaystyle K_{n}}$${\displaystyle v_{n}}$${\displaystyle \langle x,v_{n}\rangle \geq 0}$${\displaystyle x\in K_{n}}$${\displaystyle v_{n}}$${\displaystyle v_{n}}$${\displaystyle \langle x,v\rangle \geq 0}$${\displaystyle K}$и по непрерывности то же самое верно для всех x в . Завершим доказательство, как и раньше. Наконец, если внутреннее пространство пусто, то аффинное множество, которое оно охватывает, имеет размерность меньше, чем все пространство. Следовательно , содержится в некоторой гиперплоскости ; таким образом, для всех x in и завершаем доказательство, как и раньше.${\displaystyle K}$${\displaystyle K}$${\displaystyle K}$${\displaystyle \langle \cdot ,v\rangle =c}$${\displaystyle \langle x,v\rangle \geq c}$${\displaystyle K}$${\displaystyle \square }$

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

Вышеприведенное доказательство также доказывает первую версию теоремы, упомянутой в lede (чтобы увидеть ее, заметьте, что в доказательстве закрыто при условии следующей теоремы).${\displaystyle K}$

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

У нас также есть:

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

Обращение к теореме [ править ]

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

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

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

Если один из 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 .

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

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

Теорема о разделяющей оси (SAT) гласит, что:

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

SAT предлагает алгоритм проверки того, пересекаются ли два выпуклых тела или нет.

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

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

Если бы перекрестные произведения не использовались, определенные случаи без столкновения «ребро-кромка» рассматривались бы как конфликтующие. Для повышения эффективности параллельные оси могут быть рассчитаны как единственная ось.

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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