Teorema Pemisahan Fundamental

Misalkan S adalah cembung tertutup yang tidak kosong yang ditetapkan di $ \ mathbb {R} ^ n $ dan $ y \ notin S $. Kemudian, ada vektor bukan nol $ p $ dan skalar $ \ beta $ sehingga $ p ^ T y> \ beta $ dan $ p ^ T x <\ beta $ untuk setiap $ x \ dalam S $

Bukti

Karena S adalah himpunan konveks tertutup yang tidak kosong dan $ y \ notin S $ maka dengan teorema titik terdekat, terdapat titik minimalisasi yang unik $ \ hat {x} \ dalam S $ sehingga

$ \ kiri (x- \ topi {x} \ kanan) ^ T \ kiri (y- \ topi {x} \ kanan) \ leq 0 \ depan x \ dalam S $

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

Lalu $ \ kiri (x- \ topi {x} \ kanan) ^ T \ kiri (y- \ topi {x} \ kanan) \ leq 0 $

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

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ Tx \ leq \ left (y- \ hat {x} \ kanan) ^ T \ hat {x} = \ hat {x} ^ T \ kiri (y- \ hat {x} \ kanan) $ i, e., $ p ^ Tx \ leq \ beta $

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

$ = \ kiri (y- \ topi {x} \ kanan) ^ T \ kiri (yx \ kanan) = \ kiri \ | y- \ topi {x} \ kanan \ | ^ {2}> 0 $

$ \ Rightarrow p ^ Ty> \ beta $

Teorema ini menghasilkan pemisahan hyperplanes. Hyperplanes berdasarkan teorema di atas dapat didefinisikan sebagai berikut -

Misalkan $ S_1 $ dan $ S_2 $ adalah subset yang tidak kosong dari $ \ mathbb {R} $ dan $ H = \ left \ {X: A ^ TX = b \ right \} $ menjadi hyperplane.

• Hyperplane H dikatakan memisahkan $ S_1 $ dan $ S_2 $ jika $ A ^ TX \ leq b \ untuk semua X \ di S_1 $ dan $ A_TX \ geq b \ untuk semua X \ di S_2 $

• Hyperplane H dikatakan memisahkan $ S_1 $ dan $ S_2 $ jika $ A ^ TX <b \ forall X \ in S_1 $ and $ A_TX> b \ forall X \ in S_2 $

• Hyperplane H dikatakan memisahkan $ S_1 $ dan $ S_2 $ jika $ A ^ TX \ leq b \ forall X \ in S_1 $ dan $ A_TX \ geq b + \ varepsilon \ forall X \ in S_2 $, di mana $ \ varepsilon $ adalah skalar positif.