Fundamentalne twierdzenie o separacji

Niech S będzie niepustym, zamkniętym, wypukłym zbiorem w $ \ mathbb {R} ^ n $ i $ y \ notin S $. Wtedy istnieje niezerowy wektor $ p $ i skalarny $ \ beta $ taki, że $ p ^ T y> \ beta $ i $ p ^ T x <\ beta $ dla każdego $ x \ in S $

Dowód

Ponieważ S jest niepustym, zamkniętym zbiorem wypukłym i $ y \ notin S $, a zatem zgodnie z twierdzeniem o najbliższym punkcie, istnieje unikalny punkt minimalizacji $ \ hat {x} \ w S $ taki, że

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

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

Następnie $ \ 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 $

Ponadto $ 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 $

To twierdzenie prowadzi do oddzielenia hiperpłaszczyzn. Hiperpłaszczyzny oparte na powyższym twierdzeniu można zdefiniować następująco:

Niech $ S_1 $ i $ S_2 $ będą niepustymi podzbiorami $ \ mathbb {R} $ i $ H = \ left \ {X: A ^ TX = b \ right \} $ będzie hiperpłaszczyzną.

• Mówi się, że hiperpłaszczyzna H rozdziela $ S_1 $ i $ S_2 $, jeśli $ A ^ TX \ leq b \ forall X \ in S_1 $ i $ A_TX \ geq b \ forall X \ in S_2 $

• Mówi się, że hiperpłaszczyzna H ściśle oddziela $ S_1 $ i $ S_2 $, jeśli $ A ^ TX <b \ forall X \ in S_1 $ and $ A_TX> b \ forall X \ in S_2 $

• Mówi się, że hiperpłaszczyzna H silnie oddziela $ S_1 $ i $ S_2 $, jeśli $ A ^ TX \ leq b \ forall X \ in S_1 $ i $ A_TX \ geq b + \ varepsilon \ forall X \ in S_2 $, gdzie $ \ varepsilon $ jest dodatnim skalarem.