基本的な分離定理

Sを$ \ mathbb {R} ^ n $と$ y \ notin S $の空でない閉じた凸集合とします。次に、各$ x \ in S $に対して$ p ^ T y> \ beta $および$ p ^ T x <\ beta $となるような非ゼロベクトル$ p $およびスカラー$ \ beta $が存在します。

証明

Sは空ではない閉じた凸集合であり、$ y \ notin S $であるため、最も近い点定理により、次のような一意の最小化点$ \ hat {x} \ in S $が存在します。

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

$ p = \ left（y- \ hat {x} \ right）\ neq 0 $および$ \ beta = \ hat {x} ^ T \ left（y- \ hat {x} \ right）= p ^ Tとします。 \ hat {x} $。

次に、$ \ 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）$つまり、$ p ^ Tx \ leq \ beta $

また、$ 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 $

この定理により、超平面が分離されます。上記の定理に基づく超平面は、次のように定義できます。

$ S_1 $と$ S_2 $を$ \ mathbb {R} $の空でないサブセットとし、$ H = \ left \ {X：A ^ TX = b \ right \} $を超平面とします。

• $ A ^ TX \ leq b \ forall X \ in S_1 $と$ A_TX \ geq b \ forall X \ in S_2 $の場合、超平面Hは$ S_1 $と$ S_2 $を分離すると言われます。

• $ A ^ TX <b \ forall X \ in S_1 $と$ A_TX> b \ forall X \ in S_2 $の場合、超平面Hは$ S_1 $と$ S_2 $を厳密に分離すると言われています

• $ A ^ TX \ leq b \ forall X \ in S_1 $と$ A_TX \ geq b + \ varepsilon \ forall X \ in S_2 $の場合、超平面Hは$ S_1 $と$ S_2 $を強く分離すると言われます。ここで、$ \ varepsilon $は正のスカラーです。