凸集分離定理

凸集分離定理是凸集理論的最基本的定理，它是指在很弱的條件下，兩個不相交的凸集總可用超平面分離。

基本介紹

• 中文名：凸集分離定理
• 外文名：Separating Hyperplane Theorem
• 別稱：超平面分離定理
• 套用學科：物理
• 兩個凸集分離：兩個凸集合沒有交叉和重合的部分
• 範數的等價性：這裡的範數可以是任何一種範數

定義

凸集分離定理（超平面分離定理）是套用凸集到最最佳化理論中的重要結果，這個結果在最最佳化理論中有重要的位置。所謂兩個凸集分離，直觀地看是指兩個凸集合沒有交叉和重合的部分，因此可以用一張超平面將兩者隔在兩邊。

設為兩個非空集合，如果存在非零向量及使得

則稱超平面分離了集合與。

證明

為了證明凸集分離定理，先給出凸集的一個性質，我們不妨把一個閉凸集想像成為一個三維的充滿了氣體的氣球（因為必須是凸的），那么，在氣球外一點，到氣球內個點（包括內部）的距離是不一樣的，但肯定在氣球上有一點，它到的距離是所有距離中最小的，這是凸集特有的性質。下面是這個性質的定義及證明：

引理

設為非空閉凸集，，則存在唯一的，使得該點與的距離最小，即有：

根據範數的等價性，這裡的範數可以是任何一種範數。

引理證明

先證明其存在性，考慮單位超球

取足夠大的正數，使。

因為為閉集，而是一個有界閉集，所以是一個非空有界閉集，於是可以在上的某一點取得它的最大值，在另一點上取得其最小值。

設這個最小值在處達到，即是到的最小距離點，記此距離值為。

再證唯一性。

假設還存在另一點，使

記。

因為，兩邊取範數，則有

但是由於是凸集，是與的凸組合，所以。

而由於是到的最小距離，故

根據平行四邊形定律（兩對角線的平方和等於一組臨邊平方和的兩倍），有：

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

故有，唯一性得證。在此基礎上，可以給出凸集分離定理的證明。

定理證明

因為為非空集合，是外的一點，故由引理知，存在一點，使得

設，那么因為凸集，故有，使

因此，

上式兩邊的可消去，得

在上式中，令，得

記，有

若記，則有

另一方面，由於

所以

定理得證。

套用

凸集分離定理的一個套用例子是Farkas引理，這個定理是最優性條件中最重要的基礎。

利用Farkas引理，還可以證明有價值的Gordan定理和擇一性定理。Gorden定理在證明最優性條件中著名的Kuhn-Tucker條件，是極為關鍵的基礎。