Định lý tách cơ bản

Cho S là một tập lồi, đóng, không rỗng trong $ \ mathbb {R} ^ n $ và $ y \ notin S $. Sau đó, tồn tại một vectơ khác 0 $ p $ và vô hướng $ \ beta $ sao cho $ p ^ T y> \ beta $ và $ p ^ T x <\ beta $ cho mỗi $ x \ trong S $

Bằng chứng

Vì S là tập lồi đóng không rỗng và $ y \ notin S $ do đó theo định lý điểm gần nhất, tồn tại một điểm cực tiểu duy nhất $ \ hat {x} \ trong S $ sao cho

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

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

Sau đó $ \ 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 $

Ngoài ra, $ 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 $

Định lý này dẫn đến việc phân tách các siêu mặt phẳng. Các siêu mặt phẳng dựa trên định lý trên có thể được định nghĩa như sau:

Gọi $ S_1 $ và $ S_2 $ là các tập con không rỗng của $ \ mathbb {R} $ và $ H = \ left \ {X: A ^ TX = b \ right \} $ là một siêu phẳng.

• Siêu phẳng H được cho là sẽ phân tách $ S_1 $ và $ S_2 $ nếu $ A ^ TX \ leq b \ forall X \ in S_1 $ và $ A_TX \ geq b \ forall X \ trong S_2 $

• Siêu phẳng H được cho là phân tách chặt chẽ $ S_1 $ và $ S_2 $ nếu $ A ^ TX <b \ forall X \ in S_1 $ và $ A_TX> b \ forall X \ trong S_2 $

• Siêu phẳng H được cho là phân tách rõ ràng $ S_1 $ và $ S_2 $ nếu $ A ^ TX \ leq b \ forall X \ in S_1 $ và $ A_TX \ geq b + \ varepsilon \ forall X \ in S_2 $, trong đó $ \ varepsilon $ là một đại lượng vô hướng dương.