分离与支撑超平面

超平面分离定理

设两个凸集 $C\cap D=\mathrm{\varnothing }$，那么 $\mathrm{\exists }a\ne 0,b$ 使得对 $\mathrm{\forall }x\in C$ 有 $a^{\mathrm{\top }}x⩽b$，对 $\mathrm{\forall }x\in D$ 有 $a^{\mathrm{\top }}x⩾b$。称超平面 $\{x\mid a^{\mathrm{\top }}x=b\}$ 为凸集 $C$ 和 $D$ 的分离超平面，如图所示：

注：

• 严格分离：即超平面分离定理中的等号不成立。
• 超平面分离定理的逆命题：不成立。

支撑超平面

设 $C\subseteq {\mathbf{R}}^n$ 而 $x_0$ 是其边界 $\mathrm{bd}C$ 上的一点。如果 $a\ne 0$，并且对 $\mathrm{\forall }x\in C$ 有 $a^{\mathrm{\top }}x=a^{\mathrm{\top }}{x}_0$，那么称超平面 $\{x\mid a^{\mathrm{\top }}x=a^{\mathrm{\top }}{x}_0\}$ 为集合 $C$ 在点 $x_0$ 处的支撑超平面。从几何上看，超平面 $\{x\mid a^{\mathrm{\top }}x=a^{\mathrm{\top }}{x}_0\}$ 与 $C$ 相切于点 $x_0$，半空间 $\{x\mid a^{\mathrm{\top }}x⩽a^{\mathrm{\top }}{x}_0\}$ 包含 $C$，如图所示：