基本分离定理

设S是$\mathbb{R}^n$中的一个非空闭凸集，且$y \notin S$。则存在一个非零向量p和标量β，使得$p^T y>\beta$，并且对于每个$x \in S$，都有$p^T x < \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 ( y-x \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 \}$是一个超平面。

• 如果对于所有$X \in S_1$，$A^TX \leq b$，并且对于所有$X \in S_2$，$A_TX \geq b$，则称超平面H分离$S_1$和$S_2$。

• 如果对于所有$X \in S_1$，$A^TX < b$，并且对于所有$X \in S_2$，$A_TX > b$，则称超平面H严格分离$S_1$和$S_2$。

• 如果对于所有$X \in S_1$，$A^TX \leq b$，并且对于所有$X \in S_2$，$A_TX \geq b+ \varepsilon$，其中$\varepsilon$是一个正标量，则称超平面H强分离$S_1$和$S_2$。