Teorema del hiperplano de separación

En geometría, el teorema del hiperplano de separación es un enunciado sobre formas convexas disjuntas en el espacio euclídeo de n dimensiones. Hay varias versiones bastante similares. En una versión del teorema, si ambos conjuntos son disjuntos, cerrados y al menos uno de ellos es compacto, entonces existe un hiperplano entre ellos e incluso dos hiperplanos paralelos entre ellos separados por un espacio. En otra versión, si ambos conjuntos convexos disjuntos están abiertos, entonces existe un hiperplano entre ellos, pero no necesariamente un espacio. Un eje que es ortogonal a un hiperplano de separación es un eje de separación, porque las proyecciones ortogonales de los cuerpos convexos sobre el eje son disjuntos.

El teorema de separación de hiperplanos se debe a Hermann Minkowski. Por otro lado, el teorema de Hahn–Banach generaliza el resultado a espacios vectoriales topológicos.

Un resultado relacionado es el del teorema del hiperplano de soporte.

En el contexto de máquinas de vectores de soporte, el hiperplano de separación óptima o el hiperplano de margen máximo es aquel hiperplano que separa las envolventes convexas de dos conjuntos de puntos, y es equidistante de ambas.

Declaraciones y demostraciones

En todos los casos, se supone que $A,B$ son subconjuntos disjuntos, no vacíos y convexos de ${ℝ}^n$. El resumen de los resultados es el siguiente:

Tabla resumen

$A$	$B$	$⟨x,v⟩$	$⟨y,v⟩$
		$\ge c$	$\le c$
Compacto cerrado	Cerrado	$>c_1$	$<c_2$ con $c_2<c_1$
Cerrado	Compacto cerrado	$>c_1$	$<c_2$ con $c_2<c_1$
Abierto		$>c$	$\le c$
Abierto	Abierto	$>c$	$<c$

El número de dimensiones debe ser finito. En espacios de dimensión infinita hay ejemplos de dos conjuntos cerrados, convexos y disjuntos que no pueden separarse por un hiperplano cerrado (un hiperplano donde un funcional lineal continuo es igual a alguna constante), incluso en el sentido débil donde las desigualdades no son estrictas.

Aquí no se puede relajar la hipótesis de compacidad; véase un ejemplo en la sección contraejemplos y unicidad. Esta versión del teorema de separación se generaliza a dimensiones infinitas; la generalización se conoce más comúnmente como teorema de separación de Hahn-Banach.

La demostración se basa en el siguiente lema:

Imagen de la demostración

Dado que un hiperplano de separación no puede intersecar los interiores de conjuntos convexos abiertos, se deduce el corolario siguiente:

Caso con posibles intersecciones

Si los conjuntos $A,B$ tienen posibles intersecciones, pero sus interiores relativos son disjuntos, entonces la prueba del primer caso aún se aplica sin cambios, lo que produce: Plantilla:Teorema en particular, se tiene el hiperplano de soporte. Plantilla:Teorema Plantilla:Demostración

Teorema recíproco

Téngase en cuenta que la existencia de un hiperplano que solo separa dos conjuntos convexos en el sentido débil de que ambas desigualdades no son estrictas, obviamente no implica que los dos conjuntos sean disjuntos. Ambos conjuntos podrían tener puntos ubicados en el hiperplano.

Contraejemplos y singularidad

El teorema no se aplica si uno de los cuerpos no es convexo

Si uno de los conjuntos A o B no es convexo, entonces hay muchos contraejemplos posibles. Por ejemplo, A y B podrían ser círculos concéntricos. Un contraejemplo más sutil es aquel en el que A y B son cerrados pero ninguno es compacto. Por ejemplo, si A es un semiplano cerrado y B está delimitado por un brazo de una hipérbola, entonces no existe un hiperplano de separación estricta:

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

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

(aunque, por un ejemplo del segundo teorema, existe un hiperplano que separa sus interiores). En otro tipo de contraejemplo se tiene que A es compacto y B es abierto. Por ejemplo, A puede ser un cuadrado cerrado y B puede ser un cuadrado abierto que toca a A.

En la primera versión del teorema, evidentemente el hiperplano de separación nunca es único. En la segunda versión, puede ser único o no. Técnicamente, un eje de separación nunca es único porque se le puede aplicar una traslación; en la segunda versión del teorema, un eje de separación puede ser único sin necesidad de obviar traslaciones.

El ángulo abocinado proporciona un buen contraejemplo para muchas separaciones de hiperplanos. Por ejemplo, en ${ℝ}^2$, el disco unitario está separado del intervalo abierto $((1,0),(1,1))$, pero la única recta que los separa contiene la totalidad de $((1,0),(1,1))$. Esto muestra que si $A$ está cerrado y $B$ está relativamente abierto, entonces no existe necesariamente una separación estricta para $B$. Sin embargo, si $A$ está cerrado como politopo, entonces existe dicha separación.

Más variantes

El lema de Farkas y los resultados relacionados pueden entenderse como teoremas de separación de hiperplanos cuando los cuerpos convexos están definidos por un número finito de desigualdades lineales.

Se pueden encontrar más resultados sobre conjuntos convexos disjuntos.

Uso en la detección de colisiones

En la detección de colisiones, el teorema de separación de hiperplanos se suele utilizar de la siguiente forma:

Independientemente de la dimensión considerada, el eje de separación es siempre una línea recta. Por ejemplo, en 3D, el espacio está separado por planos, pero el eje de separación es perpendicular al plano de separación.

El teorema del eje de separación se puede aplicar para la detección de colisiones rápida entre mallas poligonales. Las normales de cada cara o cualquier otra dirección de un elemento se utiliza como eje de separación. Téngase en cuenta que esto produce posibles ejes de separación, no líneas/planos de separación.

En 3D, el uso exclusivo de normales a las caras no logrará separar algunos casos de borde a borde que no colisionan. Se requieren ejes adicionales, que consisten en los productos cruzados de pares de aristas, una tomada de cada objeto.

Para aumentar la eficiencia, los ejes paralelos se pueden calcular como un solo eje.

Véase también

• Cono dual
• Lema de Farkas
• Teorema de Kirchberger
• Control óptimo

Bibliografía

• Plantilla:Cite book
• Plantilla:Cite book
• Plantilla:Cite book

• Plantilla:Cite book

Enlaces externos

• Detección y respuesta de colisiones