Теорема о фундаментальном разделении

Пусть S — непустое замкнутое выпуклое множество в  mathbbRn$\ mathbb {R} ^ n$ и y notinS$y \ notin S$. Тогда существует ненулевой вектор p$p$ и скалярный  beta$\ beta$ такой, что pTy> beta$p ^ T y&amp;gt; \ beta$ и pTx< beta$p ^ T x &amp;lt;\ beta$ для каждого x inS$x \ in S$

доказательство

Поскольку S — непустое замкнутое выпуклое множество и y notinS$y \ notin S$, то по теореме о ближайшей точке существует единственная минимизирующая точка  hatx inS$\ hat {x} \ in S$, такая что

 left(x− hatx right)T left(y− hatx right) leq0 forallx inS$\ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0 \ forall x \ in S$

Пусть p= left(y− hatx right) neq0$p = \ left (y- \ hat {x} \ right) \ neq 0$ и  beta= hatxT left(y− hatx right)=pT шляпах$\ beta = \ hat {x} ^ T \ left (y- \ hat {x} \ right) = p ^ T \ шляпа {х}$.

Тогда  left(x− hatx right)T left(y− hatx right) leq0$\ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0$

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

 Rightarrow left(y− hatx right)Tx leq left(y− hatx right)T hatx= hatxT left(y− hatx right)$\ 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, т.е. pTx leq beta$p ^ Tx \ leq \ beta$

Кроме того, pTy− beta= left(y− hatx right)Ty− hatxT left(y− hatx right)$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 $

 RightarrowpTy> beta$\ Rightarrow p ^ Ty&amp;gt; \ beta$

Эта теорема приводит к разделению гиперплоскостей. Гиперплоскости, основанные на приведенной выше теореме, могут быть определены следующим образом:

Пусть S1$S_1$ и S2$S_2$ — непустые подмножества в  mathbbR$\ mathbb {R}$, а H = \ left \ {X: A ^ TX = b \ right \}$H = \ left \ {X: A ^ TX = b \ right \}$ — гиперплоскость.

Говорят, что гиперплоскость H разделяет S1$S_1$ и S2$S_2$, если ATX leqb forallX inS1$A ^ TX \ leq b \ forall X \ in S_1$ и ATX geqb forallX inS2$A_TX \ geq b \ forall X \ in S_2$

Говорят, что гиперплоскость H строго разделяет S1$S_1$ и S2$S_2$, если ATX<b forallX inS1$A ^ TX &amp;lt;b \ forall X \ in S_1$ и ATX>b forallX inS2$A_TX&amp;gt; b \ forall X \ in S_2$

Говорят, что гиперплоскость H сильно разделяет S1$S_1$ и S2$S_2$, если ATX leqb forallX inS1$A ^ TX \ leq b \ forall X \ in S_1$ и ATX geqb+ varepsilon forallX inS2$A_TX \ geq b + \ varepsilon \ forall X \ in S_2$, где  varepsilon$\ varepsilon$ — это положительный скаляр.