基本分离定理

设 S 为 $\mathbb{R}^n$ 中的非空闭凸集，且 $y otin S$。然后，存在一个非零向量 $p$ 和标量 $\beta$，使得对于每个 $x \in S$，$p^T y>\beta$ 和 $p^T x < \beta$

证明

由于 S 是非空闭凸集，并且 $y otin S$，因此根据最近点定理，存在唯一的极小点 $\h​​at{x} \in S$，使得

$\left ( x-\hat{x} ight )^T\left ( y-\hat{x} ight )\leq 0 \forall x \in S$

设 $p=\left ( y-\hat{x} ight ) eq 0$ 和 $\beta=\hat{x}^T\left ( y-\hat{x} ight )=p^T\hat{x}$。

则 $\left ( x-\hat{x} ight )^T\left ( y-\hat{x} ight )\leq 0$

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

$\Rightarrow \left ( y-\hat{x} ight )^Tx\leq \left ( y-\hat{x} ight )^T \hat{x}=\hat{x}^T\left ( y-\hat{x} ight )$ 即 $p^Tx \leq \beta$

此外，$p^Ty-\beta=\left ( y-\hat{x} ight )^Ty-\hat{x}^T \left ( y-\hat{x} ight )$

$=\left ( y-\hat{x} ight )^T \left ( y-x ight )=\left \| y-\hat{x} ight \|^{2}>0$

$\Rightarrow p^Ty> \beta$

该定理导致分离超平面。基于上述定理的超平面可以定义如下 −

设 $S_1$ 和 $S_2$ 为 $\mathbb{R}$ 的非空子集，$H=\left \{ X:A^TX=b ight \}$ 为超平面。

• 如果 $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$

• 称超平面 H如果 $A^TX \leq b \forall X \in S_1$ 且 $A_TX \geq b+ \varepsilon \forall X \in S_2$，则强烈分离 $S_1$ 和 $S_2$，其中 $\varepsilon$ 为正标量。