Teorema de separação de hiperplanos - Hyperplane separation theorem

Ilustração do teorema da separação de hiperplanos.

Em geometria , o teorema da separação de hiperplanos é um teorema sobre conjuntos convexos disjuntos no espaço euclidiano n- dimensional . Existem várias versões bastante semelhantes. Em uma versão do teorema, se ambos os conjuntos são fechados e pelo menos um deles é compacto , então há um hiperplano entre eles e até mesmo dois hiperplanos paralelos entre eles separados por uma lacuna. Em outra versão, se ambos os conjuntos convexos disjuntos estiverem abertos, haverá um hiperplano entre eles, mas não necessariamente uma lacuna. Um eixo ortogonal a um hiperplano de separação é um eixo de separação , porque as projeções ortogonais dos corpos convexos sobre o eixo são disjuntas.

O teorema da separação de hiperplanos é devido a Hermann Minkowski . O teorema de separação de Hahn-Banach generaliza o resultado para espaços vetoriais topológicos .

Um resultado relacionado é o teorema do hiperplano de suporte .

No contexto de máquinas de vetores de suporte , o hiperplano de separação ideal ou hiperplano de margem máxima é um hiperplano que separa dois cascos convexos de pontos e é equidistante dos dois.

Declarações e provas

Hiperplano separação teorema  -  Let A e B ser dois disjuntos não vazio convexa subconjuntos de R n . Então, existe um vetor diferente de zero v e um número real c tal que

para todo x em A e y em B ; ou seja, o hiperplana , v o vector normal, separa A e B .

A prova é baseada no seguinte lema:

Lema  -  Seja um subconjunto convexo fechado não vazio de R n . Então existe um único vetor em de norma mínima (comprimento).

Prova de lema : Let Let ser uma sequência em tal que . Observe que está dentro, pois é convexo e assim . Desde a

as , é uma sequência de Cauchy e, portanto, tem limite x in . Ele é único uma vez que, se Y é em e tem norma δ, em seguida, e x = y .

Prova do teorema : dados conjuntos convexos não vazios disjuntos A , B , deixe

Como é convexo e a soma dos conjuntos convexos é convexo, é convexo. Pelo lema, o fechamento de , que é convexo, contém um vetor de norma mínima. Uma vez que é convexo, para qualquer polegada , o segmento de linha

encontra-se em e então

.

Pois , portanto, temos:

e deixar dá: . Assim, para qualquer x em A e y em B , temos: . Assim, se v for diferente de zero, a prova está completa, pois

De maneira mais geral (cobrindo o caso v = 0), consideremos primeiro o caso em que o interior de não está vazio. O interior pode ser exaurido por uma sequência aninhada de subconjuntos convexos compactos não vazios (a saber, put ). Como 0 não está dentro , cada um contém um vetor diferente de zero de comprimento mínimo e, pelo argumento da parte inicial, temos: para qualquer . Podemos normalizar o 's para ter o comprimento um. Então a sequência contém uma subsequência convergente (porque a n-esfera é compacta) com limite v , que é diferente de zero. Temos para qualquer x no interior de e por continuidade o mesmo vale para todo x em . Agora terminamos a prova como antes. Por fim, se possui interior vazio, o conjunto afim que abrange tem dimensão menor que a de todo o espaço. Conseqüentemente, está contido em algum hiperplano ; assim, para todo x em e terminamos a prova como antes.

O número de dimensões deve ser finito. Em espaços de dimensão infinita, há exemplos de dois conjuntos fechados, convexos e disjuntos que não podem ser separados por um hiperplano fechado (um hiperplano onde um funcional linear contínuo é igual a alguma constante), mesmo no sentido fraco, onde as desigualdades não são estritas.

A prova acima também prova a primeira versão do teorema mencionado no lede (para vê-lo, observe que a prova é encerrada sob a hipótese do teorema abaixo).

Teorema da separação I  -  Sejam A e B dois conjuntos convexos fechados não vazios disjuntos, um dos quais é compacto. Então, existe um vetor diferente de zero v e números reais tais que

para todos os x em A e Y em B .

Aqui, a compactação da hipótese não pode ser relaxada; veja um exemplo na próxima seção. Esta versão do teorema da separação generaliza para dimensão infinita; a generalização é mais comumente conhecida como teorema da separação de Hahn-Banach .

Nos tambem temos:

Teorema da separação II  -  Sejam A e B dois conjuntos convexos não vazios disjuntos. Se A está aberto, então existe um vetor diferente de zero v e um número real tal que

para todos os x em A e Y em B . Se ambos os conjuntos estiverem abertos, então existe um vetor diferente de zero v e um número real tal que

para todos os x em A e Y em B .

Isso segue da versão padrão, uma vez que o hiperplano de separação não pode interceptar os interiores dos conjuntos convexos.

Converso do teorema

Observe que a existência de um hiperplano que apenas "separa" dois conjuntos convexos no sentido fraco de ambas as desigualdades serem não estritas obviamente não implica que os dois conjuntos sejam disjuntos. Ambos os conjuntos podem ter pontos localizados no hiperplano.

Contra-exemplos e singularidade

O teorema não se aplica se um dos corpos não for convexo.

Se um de A ou B não for convexo, existem muitos contra-exemplos possíveis. Por exemplo, A e B podem ser círculos concêntricos. Um contra-exemplo mais sutil é aquele em que A e B são ambos fechados, mas nenhum é compacto. Por exemplo, se A é um meio plano fechado e B é limitado por um braço de uma hipérbole, então não há um hiperplano de separação estrita:

(Embora, por uma instância do segundo teorema, haja um hiperplano que separa seus interiores.) Outro tipo de contra-exemplo tem A compacto e B aberto. Por exemplo, A pode ser um quadrado fechado e B pode ser um quadrado aberto que toca Uma .

Na primeira versão do teorema, evidentemente o hiperplano de separação nunca é único. Na segunda versão, pode ou não ser único. Tecnicamente, um eixo de separação nunca é único porque pode ser transladado; na segunda versão do teorema, um eixo de separação pode ser único até a translação.

Use na detecção de colisão

O teorema do eixo de separação (SAT) diz que:

Dois objetos convexos não se sobrepõem se existe uma linha (chamada eixo) na qual as projeções dos dois objetos não se sobrepõem.

SAT sugere um algoritmo para testar se dois sólidos convexos se cruzam ou não.

Independentemente da dimensionalidade, o eixo de separação é sempre uma linha. Por exemplo, em 3D, o espaço é separado por planos, mas o eixo de separação é perpendicular ao plano de separação.

O teorema do eixo de separação pode ser aplicado para detecção rápida de colisão entre malhas poligonais. Cada cara é normal de direcção ou outra funcionalidade é utilizada como um eixo de separação. Observe que isso produz possíveis eixos de separação, não separando linhas / planos.

Em 3D, o uso de normais de face por si só não conseguirá separar alguns casos de não colisão borda a borda. Eixos adicionais, consistindo de produtos cruzados de pares de arestas, um tirado de cada objeto, são necessários.

Para aumentar a eficiência, os eixos paralelos podem ser calculados como um único eixo.

Veja também

Notas

Referências

  • Boyd, Stephen P .; Vandenberghe, Lieven (2004). Otimização convexa (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3.
  • Golshtein, EG; Tretyakov, NV (1996). Lagrangianas modificadas e mapas monótonos na otimização . Nova York: Wiley. p. 6. ISBN 0-471-54821-9.
  • Shimizu, Kiyotaka; Ishizuka, Yo; Bard, Jonathan F. (1997). Programação matemática indiferenciável e de dois níveis . Boston: Kluwer Academic Publishers. p. 19. ISBN 0-7923-9821-1.

links externos