Teorema del hiperplano de separación

Teorema del hiperplano de separación
Ilustración del teorema del hiperplano de separación
Tipo	Teorema
Campo	Geometría convexa Espacio vectorial topológico Detección de colisiones
Conjeturado por	Hermann Minkowski
Problema abierto	No
Generalizaciones	Teorema de separación de Hahn-Banach

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

Sean $A$ y $B$ dos subconjuntos convexos no vacíos disjuntos de $\mathbb {R} ^{n}$. Entonces, existe un vector distinto de cero $v$ y un número real $c$ tales que: $\langle x,v\rangle \geq c\,{\text{; y además }}\langle y,v\rangle \leq c$ para todos los $x$ en $A$ e $y$ en $B$; siendo $\langle \cdot ,v\rangle =c$ el mencionado hiperplano y $v$ su vector normal, que separa $A$ y $B$. Si ambos conjuntos son cerrados y al menos uno de ellos es compacto, entonces la separación puede ser estricta, es decir, $\langle x,v\rangle >c_{1}\,{\text{y }}\langle y,v\rangle <c_{2}$ para algún $c_{1}>c_{2}$.

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

Tabla resumen

$A$	$B$	$\langle x,v\rangle$	$\langle y,v\rangle$
		$\geq c$	$\leq 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$	$\leq 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:

Sean $A$ y $B$ dos subconjuntos cerrados disjuntos de $\mathbb {R} ^{n}$ y supóngase que $A$ es compacto. Entonces existen los puntos $a_{0}\in A$ y $b_{0}\in B$ que minimizan la distancia $\|a-b\|$ sobre $a\in A$ y $b\in B$.

Demostración

Sean $a\in A$ y $b\in B$ un par de puntos cualquiera y sea $r_{1}=\|b-a\|$. Dado que $A$ es compacto, está contenido en alguna bola centrada en $a$. Sea el radio de esta bola $r_{2}$, y sea $S=B\cap {\overline {B_{r_{1}+r_{2}}(a)}}$ la intersección de $B$ con una bola cerrada de radio $r_{1}+r_{2}$ alrededor de $a$. Entonces $S$ es compacto y no está vacío porque contiene a $b$. Dado que la función de distancia es continua, existen puntos $a_{0}$ y $b_{0}$ cuya distancia $\|a_{0}-b_{0}\|$ es la mínima entre todos los pares de puntos en $A\times S$. Queda por demostrar que $a_{0}$ y $b_{0}$ de hecho tienen la distancia mínima sobre todos los pares de puntos en $A\times B$. Supóngase por contradicción que existen dos puntos $a'$ y $b'$ tales que $\|a'-b'\|<\|a_{0}-b_{0}\|$. Entonces en particular, $\|a'-b'\|<r_{1}$, y por la desigualdad del triángulo, $\|a-b'\|\leq \|a'-b'\|+\|a-a'\|<r_{1}+r_{2}$. Por lo tanto, $b'$ está contenido en $S$, lo que contradice el hecho de que $a_{0}$ y $b_{0}$ tenían una distancia mínima sobre $A\times S$. $\square$

Imagen de la demostración

Demostración

Primero se demuestra el segundo caso (véase el diagrama). Sin pérdida de generalidad, $A$ es compacto. Según el lema, existen dos puntos $a_{0}\in A$ y $b_{0}\in B$, cuya distancia entre sí es mínima. Como $A$ y $B$ son disjuntos, se tiene que $a_{0}\neq b_{0}$. Ahora, se construyen dos hiperplanos $L_{A},L_{B}$ perpendiculares al segmento recto $[a_{0},b_{0}]$, con $L_{A}$ a través de $a_{0}$ y $L_{B}$ a través de $b_{0}$. Se afirma que ni $A$ ni $B$ entran en el espacio entre $L_{A},L_{B}$ y, por lo tanto, los hiperplanos perpendiculares a $(a_{0},b_{0})$ satisfacen el requisito del teorema. Algebraicamente, los hiperplanos $L_{A},L_{B}$ están definidos por el vector $v:=b_{0}-a_{0}$ y dos constantes $c_{A}:=\langle v,a_{0}\rangle <c_{B}:=\langle v,b_{0}\rangle$, tales que $L_{A}=\{x:\langle v,x\rangle =c_{A}\},L_{B}=\{x:\langle v,x\rangle =c_{B}\}$. Nuestra afirmación es que $\forall a\in A,\langle v,a\rangle \leq c_{A}$ y $\forall b\in B,\langle v,b\rangle \geq c_{B}$. Supongamos que hay algún $a\in A$ tal que $\langle v,a\rangle >c_{A}$, entonces sea $a'$ el pie de la perpendicular desde $b_{0}$ al segmento de línea $[a_{0},a]$. Dado que $A$ es convexo, $a'$ está dentro de $A$ y, por estar en el mismo plano, $a'$ está más cerca de $b_{0}$ que de $a_{0}$, lo que supone una contradicción. Un argumento similar se aplica a $B$. A continuación se demuestra el primer caso. Acérquese a ambos conjuntos $A,B$ desde el interior por $A_{1}\subseteq A_{2}\subseteq \cdots \subseteq A$ y $B_{1}\subseteq B_{2}\subseteq \cdots \subseteq B$, de modo que cada $A_{k},B_{k}$ sea cerrado y compacto, y las uniones sean los interiores relativos de $\mathrm {relint} (A),\mathrm {relint} (B)$ (consúltese la página interior relativo para obtener más detalles). Ahora, en el segundo caso, para cada par $A_{k},B_{k}$ existe algún vector unitario $v_{k}$ y número real $c_{k}$, tal que $\langle v_{k},A_{k}\rangle <c_{k}<\langle v_{k},B_{k}\rangle$. Como la esfera unitaria es compacta, se puede tomar una subsecuencia convergente, de modo que $v_{k}\to v$. Ahora, $c_{A}:=\sup _{a\in A}\langle v,a\rangle ,c_{B}:=\inf _{b\in B}\langle v,b\rangle$. Entonces, se puede afirmar que $c_{A}\leq c_{B}$, separando así $A,B$. Supóngase que esto no es así. Entonces, existe algún $a\in A,b\in B$ tal que $\langle v,a\rangle >\langle v,b\rangle$, luego desde $v_{k}\to v$, para $k$ lo suficientemente grande, se tiene que $\langle v_{k},a\rangle >\langle v_{k},b\rangle$, lo que es una contradicción.

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

Sean $A$ y $B$ dos conjuntos convexos no vacíos disjuntos. Si $A$ está abierto, entonces existe un vector $v$ distinto de cero y un número real $c$ tales que $\langle x,v\rangle >c\,{\text{y }}\langle y,v\rangle \leq c$ para todos los $x$ en $A$ y $y$ en $B$. Si ambos conjuntos son abiertos, entonces existe un vector $v$ distinto de cero y un número real $c$ tal que $\langle x,v\rangle >c\,{\text{e }}\langle y,v\rangle <c$ para todos los $x$ en $A$ y $y$ en $B$.

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:

Sean $A$ y $B$ dos subconjuntos convexos no vacíos de $\mathbb {R} ^{n}$ con interiores relativos disjuntos. Entonces, existe un vector distinto de cero $v$ y un número real $c$ tales que $\langle x,v\rangle \geq c\,{\text{y }}\langle y,v\rangle \leq c$

en particular, se tiene el hiperplano de soporte.

Si $A$ es un conjunto convexo en $\mathbb {R} ^{n},$ y $a_{0}$ es un punto en la frontera de $A$, entonces existe un hiperplano de soporte de $A$ que contiene a $a_{0}$.

Demostración

Si el intervalo afín de $A$ no es todo $\mathbb {R} ^{n}$, se extiende el intervalo afín a un hiperplano de soporte. De lo contrario, $\mathrm {relint} (A)=\mathrm {int} (A)$ es disjunto de $\mathrm {relint} (\{a_{0}\})=\{a_{0}\}$, y se puede aplicar el teorema anterior.

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\leq 0\}$

$B=\{(x,y):x>0,y\geq 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 $\mathbb {R} ^{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:

Dos objetos convexos cerrados son disjuntos si existe una línea recta (eje de separación) sobre la que las proyecciones de los dos objetos son disjuntas.

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

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3. 
• Golshtein, E. G.; Tretyakov, N.V. (1996). Modified Lagrangians and monotone maps in optimization. New York: Wiley. p. 6. ISBN 0-471-54821-9. 
• Shimizu, Kiyotaka; Ishizuka, Yo; Bard, Jonathan F. (1997). Nondifferentiable and two-level mathematical programming. Boston: Kluwer Academic Publishers. p. 19. ISBN 0-7923-9821-1. 

• Soltan, V. (2021). Support and separation properties of convex sets in finite dimension. Extracta Math. Vol. 36, no. 2, 241-278. 

Enlaces externos

• Detección y respuesta de colisiones

• Datos: Q6795830