Théorème de séparation fondamental
Soit S un ensemble convexe fermé non vide dans $ \ mathbb {R} ^ n $ et $ y \ notin S $. Alors, il existe un vecteur non nul $ p $ et scalaire $ \ beta $ tel que $ p ^ T y> \ beta $ et $ p ^ T x <\ beta $ pour chaque $ x \ dans S $
Preuve
Puisque S est un ensemble convexe fermé non vide et $ y \ notin S $ donc par le théorème du point le plus proche, il existe un point de minimisation unique $ \ hat {x} \ dans S $ tel que
$ \ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0 \ forall x \ in S $
Soit $ p = \ left (y- \ hat {x} \ right) \ neq 0 $ et $ \ beta = \ hat {x} ^ T \ left (y- \ hat {x} \ right) = p ^ T \ chapeau {x} $.
Puis $ \ 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 $
De plus, $ 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 $
Ce théorème conduit à séparer les hyperplans. Les hyperplans basés sur le théorème ci-dessus peuvent être définis comme suit -
Soit $ S_1 $ et $ S_2 $ des sous-ensembles non vides de $ \ mathbb {R} $ et $ H = \ left \ {X: A ^ TX = b \ right \} $ être un hyperplan.
On dit que l'hyperplan H sépare $ S_1 $ et $ S_2 $ si $ A ^ TX \ leq b \ forall X \ in S_1 $ et $ A_TX \ geq b \ forall X \ in S_2 $
On dit que l'hyperplan H sépare strictement $ S_1 $ et $ S_2 $ si $ A ^ TX <b \ forall X \ in S_1 $ et $ A_TX> b \ forall X \ in S_2 $
On dit que l'hyperplan H sépare fortement $ S_1 $ et $ S_2 $ if $ A ^ TX \ leq b \ forall X \ in S_1 $ et $ A_TX \ geq b + \ varepsilon \ forall X \ in S_2 $, où $ \ varepsilon $ est un scalaire positif.