基本分離定理

設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$。