Teorema de Separação Fundamental

Seja S um conjunto convexo fechado não vazio em $ \ mathbb {R} ^ n $ e $ y \ notin S $. Então, existe um vetor diferente de zero $ p $ e escalar $ \ beta $ tal que $ p ^ T y> \ beta $ e $ p ^ T x <\ beta $ para cada $ x \ em S $

Prova

Uma vez que S é um conjunto convexo fechado não vazio e $ y \ notin S $, portanto, pelo teorema do ponto mais próximo, existe um único ponto de minimização $ \ hat {x} \ em S $ tal que

$ \ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0 \ forall x \ in S $

Seja $ p = \ left (y- \ hat {x} \ right) \ neq 0 $ e $ \ beta = \ hat {x} ^ T \ left (y- \ hat {x} \ right) = p ^ T \ hat {x} $.

Então $ \ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ T \ left (x- \ hat {x} \ right) \ leq 0 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ Tx \ leq \ left (y- \ hat {x} \ right) ^ T \ hat {x} = \ hat {x} ^ T \ left (y- \ hat {x} \ right) $ i, e., $ p ^ Tx \ leq \ beta $

Além disso, $ p ^ Ty- \ beta = \ left (y- \ hat {x} \ right) ^ Ty- \ hat {x} ^ T \ left (y- \ hat {x} \ right) $

$ = \ left (y- \ hat {x} \ right) ^ T \ left (yx \ right) = \ left \ | y- \ hat {x} \ right \ | ^ {2}> 0 $

$ \ Rightarrow p ^ Ty> \ beta $

Este teorema resulta na separação de hiperplanos. Os hiperplanos baseados no teorema acima podem ser definidos da seguinte forma -

Sejam $ S_1 $ e $ S_2 $ subconjuntos não vazios de $ \ mathbb {R} $ e $ H = \ left \ {X: A ^ TX = b \ right \} $ um hiperplano.

• Diz-se que o hiperplano H separa $ S_1 $ e $ S_2 $ se $ A ^ TX \ leq b \ forall X \ in S_1 $ e $ A_TX \ geq b \ forall X \ in S_2 $

• Diz-se que o hiperplano H separa estritamente $ S_1 $ e $ S_2 $ se $ A ^ TX <b \ forall X \ in S_1 $ e $ A_TX> b \ forall X \ in S_2 $

• Diz-se que o hiperplano H separa fortemente $ S_1 $ e $ S_2 $ se $ A ^ TX \ leq b \ forall X \ in S_1 $ e $ A_TX \ geq b + \ varejpsilon \ forall X \ in S_2 $, onde $ \ varejpsilon $ é um escalar positivo.