分离平面定理是凸分析和凸优化中一个重要的基础定理
定义1(分离平面):
假设\(S_1,S_2 \subset E^n\),假设存在一个超平面\(H=\{x:p^Tx=\alpha\}\),且使得：
则称\(H\)为\(S_1\)与\(S_2\)的分离平面(严格分离平面)。
引理1:
设\(R\)为\(E^n\)上一个不包含原点的非空闭凸集，则存在一个超平面严格分离\(R\)与原点。
证明：任取\(x_1\in R\),令\(\delta=\Vert x_1 \Vert >0\)，则\(R \cap U_\delta(0)\)为非空有界闭集(紧集)，于是连续函数\(\Vert x_1 \Vert\)在其上面有最小值点，设为\(x_0\),显然\(x_0\)也是\(\Vert x_1 \Vert\)在整个\(R\)上的最小值点。现取超平面\(H=\{x:x_0^Tx=\frac{1}{2}x_0^Tx_0\}\)。
则对\(\forall x \in R\)，根据凸性有\(\lambda x +(1-\lambda)x_0 \in R,\forall \lambda \in (0,1)\)，于是\(\Vert \lambda x +(1-\lambda)x_0 \Vert \geq \Vert x_0 \Vert\)，进一步得到\(\Vert x-x_0 \Vert ^2 \lambda +2x_0^T(x-x_0)\geq 0\)
由此可以得到：\(x_0^T(x-x_0)\geq 0\)，否则只要取\(\lambda < -2\frac{x_0^T(x-x_0)}{\Vert x-x_0 \Vert ^2}\)就可以得到与上面的不等式矛盾。
于是\(x_0^Tx\geq x_0^Tx_0 >\frac{1}{2}x_0^Tx_0,\forall x \in R\)，而\(x_0^T0=0 <\frac{1}{2}x_0^Tx_0\),所以\(H\)为原点与\(R\)的严格分离平面。
引理2:
设\(R_1\)与\(R_2\)为不相交的非空闭凸集合，其中\(R_2\)为紧集，则存在超平面\(H\)严格分离\(R_1\)与\(R_2\).
证明：令\(R=R_1-R_2\)。根据\(R_1\)与\(R_2\)为凸集合，可以得到\(R\)为凸集；根据\(R_1\)与\(R_2\)为闭集合且\(R_2\)紧集，可以得到\(R\)为闭集\(^*\)；根据\(R_1\)与\(R_2\)不相交，得到\(0 \notin R\).
则由引理1，有超平面\(H_R=\{x:x_0^Tx=\frac{1}{2}x_0^Tx_0=\alpha\}\)，其中\(x_0\)为\(R\)中距离原点最近的点。
则\(\forall x \in R\)，设
则有\((x_{01}-x_{02})^T(x_1-x_2) > \alpha >0\)，所以\((x_{01}-x_{02})^Tx_1 \geq (x_{01}-x_{02})^Tx_2+\alpha\)，于是\(\mathop{inf}\limits_{x_1 \in R_1}(x_{01}-x_{02})^Tx_1\geq\mathop{sup}\limits_{x_2 \in R_2}(x_{01}-x_{02})^Tx_2+\alpha >\mathop{sup}\limits_{x_2 \in R_2}(x_{01}-x_{02})^Tx_2\)
取\(\beta:\mathop{inf}\limits_{x_1 \in R_1}(x_{01}-x_{02})^Tx_1<\beta<\mathop{sup}\limits_{x_2 \in R_2}(x_{01}-x_{02})^Tx_2\)<并定义超平面\(H=\{x:x_0^Tx=\beta\}\)
再根据\(\beta\)的取法，可以任意得到\(H\)为\(R_1\)与\(R_2\)的严格分离平面。
引理3:
设\(R\)为不包含原点的非空凸集合，存在超平面\(H\)分离原点与集合\(R\)。
证明：记\(P(x)=\{y:y^Ty=1,y^Tx \geq 0\}\)(即与\(x\)夹角小于\(\frac{\pi}{2}\)的单位向量集合)，\(P(x)\)为非空闭集合。
对\(\forall k \in \mathbf{N}^+\)及\(x_i\in R(i=1,2,\dots,k)\)，记\(Q=\{x:x=\sum\limits_{i=1}^{k}\alpha_ix_i,\sum\limits_{i=1}^{k}\alpha_i=1,x_i \in R,\alpha_i \geq 0,i=1,2,\dots,k\}\)，则\(Q\)为紧集，且\(0 \notin R\)。
于是由引理1，存在\(y_0 \in E^n\)使得\(y_0^Tx_i >0 ,i=1,2,\dots,k\)。不失一般性，我们假设\(y_0^Ty_0=1\)，于是\(\cap_{i=1}^{k}P(x_i)\neq \emptyset\)。
而由于\(p(x)\)是紧集\(p=\{y:y^Ty=1\}\)的闭子集，于是\(\cap_{x\in R}p(x)\neq \emptyset\)(可能需要反证法证明？)。
取\(z\in\cap_{x\in R}p(x)\)，则\(\forall x\in R,z^Tx\geq 0\)
记超平面\(H=\{x:z^Tx=0\}\)，则\(H\)分离原点和\(R\)。
定理(分离平面定理):
设\(R_1、R_2\)为不相交的非空凸集，则存在超平面\(H\)分离\(R_1、R_2\).
证明:令\(R=R_1-R_2\)为凸集且\(0\notin R\)(因为\(R_1、R_2\)不相交)
由于引理3，存在\(z\)，使得\(z^Tx\geq 0,\forall x\in R\)
于是，设\(x=x_1-x_2\in R(x_1\in R_1,x_2\in R_2)\)，则有\(z^T(x_1-x_2)\geq 0\)，所以\(z^Tx_1\geq z^Tx_2(\forall x_1\in R_1,\forall x_2\in R_2)\)
取\(\beta:\inf\limits_{x_1\in R_1}z^Tx_1 \geq \beta \geq \sup\limits_{x_2\in R_2}z^Tx_2\)
取超平面\(H=\{x:z^Tx=\beta\}\)，可以分离\(R_1,R_2\)