[科普中国]-凸集分离定理

凸集分离定理是凸集理论的最基本的定理，它是指在很弱的条件下，两个不相交的凸集总可用超平面分离。1

定义凸集分离定理（超平面分离定理）是应用凸集到最优化理论中的重要结果，这个结果在最优化理论中有重要的位置。所谓两个凸集分离，直观地看是指两个凸集合没有交叉和重合的部分，因此可以用一张超平面将两者隔在两边。

设为两个非空集合，如果存在非零向量及使得

则称超平面分离了集合与。

证明为了证明凸集分离定理2，先给出凸集的一个性质，我们不妨把一个闭凸集想象成为一个三维的充满了气体的气球（因为必须是凸的），那么，在气球外一点，到气球内个点（包括内部）的距离是不一样的，但肯定在气球上有一点，它到的距离是所有距离中最小的，这是凸集特有的性质。下面是这个性质的定义及证明：

引理设为非空闭凸集，，则存在唯一的，使得该点与的距离最小，即有：

根据范数的等价性，这里的范数可以是任何一种范数。

引理证明先证明其存在性，考虑单位超球

取足够大的正数，使。

因为为闭集，而是一个有界闭集，所以是一个非空有界闭集，于是可以在上的某一点取得它的最大值，在另一点上取得其最小值。

设这个最小值在处达到，即是到的最小距离点，记此距离值为。

再证唯一性。

假设还存在另一点，使

记。

因为，两边取范数，则有

但是由于是凸集，是与的凸组合，所以。

而由于是到的最小距离，故

根据平行四边形定律（两对角线的平方和等于一组临边平方和的两倍），有：

把（1）和（2）代入，有

故有，唯一性得证。在此基础上，可以给出凸集分离定理的证明。

定理证明因为为非空集合，是外的一点，故由引理知，存在一点，使得

设，那么因为凸集，故有，使

因此，

上式两边的可消去，得

在上式中，令，得

记，有

若记，则有

另一方面，由于

所以

定理得证。

应用凸集分离定理的一个应用例子是Farkas引理，这个定理是最优性条件中最重要的基础。

利用Farkas引理，还可以证明有价值的Gordan定理和择一性定理。Gorden定理在证明最优性条件中著名的Kuhn-Tucker条件，是极为关键的基础。

本词条内容贡献者为:

杜强 - 高级工程师 - 中国科学院工程热物理研究所