Teorema fondamentale di separazione

Sia S un insieme convesso chiuso non vuoto in $ \ mathbb {R} ^ n $ e $ y \ notin S $. Quindi, esiste un vettore diverso da zero $ p $ e $ \ beta $ scalare tali che $ p ^ T y> \ beta $ e $ p ^ T x <\ beta $ per ogni $ x \ in S $

Prova

Poiché S è un insieme convesso chiuso non vuoto e $ y \ notin S $ quindi per il teorema del punto più vicino, esiste un unico punto di minimizzazione $ \ hat {x} \ in S $ tale che

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

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

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

$ \ Freccia destra \ sinistra (y- \ hat {x} \ destra) ^ T \ sinistra (x- \ hat {x} \ destra) \ 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 $

Inoltre, $ p ^ Ty- \ beta = \ left (y- \ hat {x} \ right) ^ Ty- \ hat {x} ^ T \ left (y- \ hat {x} \ right) $

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

$ \ Freccia destra p ^ Ty> \ beta $

Questo teorema si traduce nella separazione degli iperpiani. Gli iperpiani basati sul teorema di cui sopra possono essere definiti come segue:

Siano $ S_1 $ e $ S_2 $ sottoinsiemi non vuoti di $ \ mathbb {R} $ e $ H = \ left \ {X: A ^ TX = b \ right \} $ un iperpiano.

  • Si dice che l'iperpiano 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 $

  • Si dice che l'iperpiano H separa rigorosamente $ S_1 $ e $ S_2 $ se $ A ^ TX <b \ forall X \ in S_1 $ e $ A_TX> b \ forall X \ in S_2 $

  • Si dice che l'iperpiano H separa fortemente $ S_1 $ e $ S_2 $ se $ A ^ TX \ leq b \ forall X \ in S_1 $ e $ A_TX \ geq b + \ varepsilon \ forall X \ in S_2 $, dove $ \ varepsilon $ è uno scalare positivo.