凸集分离定理
理学领域术语
凸集分离定理是凸集理论的最基本的定理,它是指在很弱的条件下,两个不相交的凸集总可用超平面分离。
定义
凸集分离定理(超平面分离定理)是应用凸集到最优化理论中的重要结果,这个结果在最优化理论中有重要的位置。所谓两个凸集分离,直观地看是指两个凸集合没有交叉和重合的部分,因此可以用一张超平面将两者隔在两边。
设为两个非空集合,如果存在非零向量及使得
则称超平面分离了集合与。
证明
为了证明凸集分离定理,先给出凸集的一个性质,我们不妨把一个闭凸集想象成为一个三维的充满了气体的气球(因为必须是凸的),那么,在气球外一点,到气球内个点(包括内部)的距离是不一样的,但肯定在气球上有一点,它到的距离是所有距离中最小的,这是凸集特有的性质。下面是这个性质的定义及证明:
引理
设为非空闭凸集,,则存在唯一的,使得该点与的距离最小,即有:
根据范数的等价性,这里的范数可以是任何一种范数。
引理证明
先证明其存在性,考虑单位超球
取足够大的正数,使。
因为为闭集,而是一个有界闭集,所以是一个非空有界闭集,于是可以在上的某一点取得它的最大值,在另一点上取得其最小值。
设这个最小值在处达到,即是到的最小距离点,记此距离值为。
再证唯一性。
假设还存在另一点,使
记。
因为,两边取范数,则有
但是由于是凸集,是与的凸组合,所以。
而由于是到的最小距离,故
根据平行四边形定律(两对角线的平方和等于一组临边平方和的两倍),有:
把(1)和(2)代入,有
故有,唯一性得证。在此基础上,可以给出凸集分离定理的证明。
定理证明
因为为非空集合,是外的一点,故由引理知,存在一点,使得
设,那么因为凸集,故有,使
因此,
上式两边的可消去,得
在上式中,令,得
记,有
若记,则有
另一方面,由于
所以
定理得证。
应用
凸集分离定理的一个应用例子是Farkas引理,这个定理是最优性条件中最重要的基础。
利用Farkas引理,还可以证明有价值的Gordan定理和择一性定理。Gorden定理在证明最优性条件中著名的Kuhn-Tucker条件,是极为关键的基础。
参考资料
最新修订时间:2022-08-25 17:42
目录
概述
定义
证明
参考资料