分離超平面定理

取 $C$ 中一點 $c^\star$、$D$ 中一點 $d^\star$，使得兩點間距離 $\|c^\star - d^\star\|$ 在 $C \times D$ 上取到最小值（因為其中一個集合緊緻、另一個非空凸，這個最小值存在）。

令 $a = d^\star - c^\star \ne 0$（因為 $C \cap D = \emptyset$，故 $c^\star \ne d^\star$），並取

也就是通過 $c^\star, d^\star$ 中點、且垂直於 $a$ 的超平面。

關鍵引理：對任意 $x \in C$，都有 $a^\top x \le a^\top c^\star$。

用反證法：若存在 $x \in C$ 使 $a^\top x > a^\top c^\star$，考慮線段 $c^\star + t(x - c^\star)$（$t \in [0,1]$，因 $C$ 凸，此線段完全落在 $C$ 內）。可以證明沿著這條線段前進一小步，到 $d^\star$ 的距離會比 $\|c^\star - d^\star\|$ 更小——與 $c^\star$ 是最近點矛盾。

同理可證對任意 $x \in D$，都有 $a^\top x \ge a^\top d^\star$。

把兩個不等式與 $b$ 的定義接起來，並利用 $a^\top c^\star \le b \le a^\top d^\star$（因為 $b$ 恰好是兩者的中點值），就得到對所有 $x \in C$ 有 $a^\top x \le b$、對所有 $x \in D$ 有 $a^\top x \ge b$。

∎