Grundlegender Trennungssatz

Sei S eine nicht leere geschlossene, konvexe Menge in $ \ mathbb {R} ^ n $ und $ y \ notin S $. Dann existiert ein Nicht-Null-Vektor $ p $ und ein Skalar $ \ beta $, so dass $ p ^ T y> \ beta $ und $ p ^ T x <\ beta $ für jedes $ x \ in S $

Beweis

Da S nicht leer ist, geschlossene konvexe Menge und $ y \ notin S $, so existiert nach dem nächsten Punktsatz ein eindeutiger Minimierungspunkt $ \ hat {x} \ in S $, so dass

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

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

Dann $ \ 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, d. h. $ p ^ Tx \ leq \ beta $

Außerdem ist $ 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 $

Dieser Satz führt zur Trennung von Hyperebenen. Die auf dem obigen Satz basierenden Hyperebenen können wie folgt definiert werden:

Sei $ S_1 $ und $ S_2 $ nicht leere Teilmengen von $ \ mathbb {R} $ und $ H = \ left \ {X: A ^ TX = b \ right \} $ eine Hyperebene.

Die Hyperebene H soll $ S_1 $ und $ S_2 $ trennen, wenn $ A ^ TX \ leq b \ für alle X \ in S_1 $ und $ A_TX \ geq b \ für alle X \ in S_2 $
Die Hyperebene H soll $ S_1 $ und $ S_2 $ streng trennen, wenn $ A ^ TX <b \ für alle X \ in S_1 $ und $ A_TX> b \ für alle X \ in S_2 $
Die Hyperebene H soll $ S_1 $ und $ S_2 $ stark trennen, wenn $ A ^ TX \ leq b \ für alle X \ in S_1 $ und $ A_TX \ geq b + \ varepsilon \ für alle X \ in S_2 $, wobei $ \ varepsilon $ ist ein positiver Skalar.