基本分离定理

---

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

证明

由于 S 是非空闭凸集，并且 $y \notin S$ 因此根据最近点定理，存在唯一的最小化点 $\h​​at{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 \帽子{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$

$\右箭头 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 $ 是正标量。