分离平面定理是凸分析和凸优化中一个重要的基础定理
定义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\)