一、超平面分离定理

一个重要的想法：用超平面或者仿射函数将两个不相交的凸集分离开来。

超平面分离定理

假设$C$和$D$是两个不相交的凸集，即$C \cap D = \varnothing$，

那么存在$a \neq 0$和$b$使得对于所有$x \in C$ 有$a^Tx \leq b$，对于所有$x \in D$有$a^Tx \geq b$。

即超平面$\{x|a^Tx = b\}$称为集合$C$和$D$的分离超平面，或称超平面分离了集合$C$和$D$.

证明：我们假设$C$和$D$的距离为正，这里定义(欧几里得)距离为

$$\textbf{dist}(C, D) = \text{inf}\{\|u-v\|_2 |u \in C, v \in D\}$$

并且假设存在$c \in C, d \in D$达到这个最小距离，即

$$\textbf{dist}(C, d) = \|c - d\|_2$$

定义$a = d - c, b = \frac{\|d\|^2_2 - \|c\|^2_2}{2}$.我们希望证明$f(x) = a^Tx-b=(d-c)^Tx-\frac{\|d\|^2_2 - \|c\|^2_2}{2}=(d-c)^T(x-\frac{1}{2}(d+c))$在$C$中非正且在$D$中非负。

反证：假设存在点$u \in D$，并且$f(u)<0$，那么

$$\begin{aligned} f(u) &= (d-c)^T(u-\frac{1}{2}(d+c))\\ &= (d-c)^T(u-d+\frac{1}{2}(d-c))\\ &= (d-c)^T(u-d)+\frac{1}{2}\|d -c\|^2_2 \end{aligned}$$

因为$f(u) < 0$，故$(d-c)^T(u-d) < 0$.

观察到：

$$\begin{aligned} \left.\frac{d}{dt}\|d + t(u -d) - c\|_2^2\right|_{t=0} &= \left.\frac{d}{dt}[t^2\|u-d\|^2_2 + 2t(u-d)^T(d-c) + \|d-c\|^2_2]\right|_{t=0}\\ &= 2(u-d)^T(d-c) < 0 \end{aligned}$$

由于$f(u)$在$t=0$时导数小于0，因为对于足够小的$0 < t \leq 1$，我们有：

$$\|d+t(u-d)-c\|_2^2 \leq \|d-c\|$$

即点$d+t(u-d)$比$d$更靠近$c$，又因为$u, d \in D$，故$(1-t)d + tu = d + t(u-d) \in D$。

这与$d$是$D$中离$C$的最近点不符，故$\forall u \in D, f(u) \geq 0$.

同理可证，$f(x)$在$C$中非正。

严格分离

即对于任意$x \in C$有$a^Tx <b$并且对于任意$x \in D$有$a^Tx >b$，则称其为集合$C$和$D$的严格分离。

超平面分离定理的逆定理

是不成立的。

即$C = D = \{0\} \in \mathbb{R}$，超平面$x = 0$可以分离$C$和$D$，但是$C$和$D$是相交的。

需要给$C$和$D$增加一些条件：

任意两个凸集$C$和$D$，如果其中至少一个是开集，那么当且仅当存在分离超平面时，它们不相交。

二、支撑超平面

定义

设$C \subseteq \mathbb{R}^n$而$x_0$是其边界$\textbf{bd}C$上的一个点，即

如果$a \neq 0$，并且任意$x \in C$满足$a^Tx \leq a^Tx_0$ ，那么称超平面$\{x | a^T x = a^T x_0\}$为集合$C$在点$x_0$处的支撑超平面。

几何解释为超平面$\{x|a^Tx = a^Tx_0\}$与$C$相切于点$x_0$，并且半空间$\{x|a^Tx \leq a^T x_0\}$包含$C$。

支撑超平面定理

对于任意非空凸集$C$和任意$x_0 \in \textbf{bd}C$，在$x_0$处存在$C$的支撑超平面。

支撑超平面的逆定理

如果一个集合是闭的，具有非空内部，并且其边界上每个点均存在支撑超平面，那么它是凸的。