凸集分離定理

在此基礎上，可以給出凸集分離定理的證明。 凸集分離定理證明因為為非空集合，是外的一點，故由引理知，存在一點，使得設，那么因為凸集，故有，使因此， 套用凸集分離定理的一個套用例子是Farkas引理，這個定理是最優性條件中最重要的基礎，見

定義

設S_1,S_2\subseteq R^n為兩個非空集合，如果存在非零向量p\in R^n及\alpha\in R使得
S_1\subseteq H^-=\left \{ {x\in R^n |p^Tx\leq \alpha} \right \}
S_2\subseteq H^+=\left \{ {x\in R^n |p^Tx\geq \alpha} \right \}
則稱超平面H=\left\{ {x\in R^n|p^Tx=\alpha} \right\}分離了集合S_1與S_2。

證明

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

引理

設S\subseteq R^n為非空閉凸集，y\in R^n \setminus S，則存在唯一的\overline{x}\in S，使得該點與y的距離最小，即有：
\|x-y\|=inf\left\{{\|x-y\||x\in S}\right\}>0
根據範數的等價性，這裡的範數可以是任何一種範數。

引理證明

先證明其存在性，考慮單位超球
B=\left\{ {z\in R^n| \|z\|\leq1} \right\}
取足夠大的正數\beta，使D=S\cap (\left\{ y\right\}+\beta B)\neq \emptyset。
因為S為閉集，而\left\{ y\right\}+\beta B是一個有界閉集，所以D是一個非空有界閉集，於是S可以在D上的某一點取得它的最大值，在另一點上取得其最小值。
設這個最小值在x\in D處達到，即x是y到S的最小距離點，記此距離值為r。
再證唯一性。
假設還存在另一點x'\in S，使\|x'-y\|=\|x-y\|=r~~~~~~~~~~~(1)
記x''=\frac{1}{2}(x+x')。
因為x''-y=\frac{1}{2}x-\frac{1}{2}y+\frac{1}{2}x'-\frac{1}{2}y，兩邊取範數，則有
\|x''-y\|\leq\frac{1}{2}\|x-y\|+\frac{1}{2}\|x'-y\|=r
但是由於S是凸集，x''是x\in S與x'\in S的凸組合，所以x''\in S。
而由於r是y到S的最小距離，故\|x''-y\|=r~~~~~~~~~(2)
根據平行四邊形定律（兩對角線的平方和等於一組臨邊平方和的兩倍），有：
\|x-x'\|^2+4\|x''-y\|^2=2\|x-y\|^2+2\|x'-y\|^2
把（1）和（2）代入，有
\|x-x'\|^2=2r^2+2r^2-4r^2=0
故有x=x'，唯一性得證。在此基礎上，可以給出凸集分離定理的證明。

凸集分離定理證明

因為S為非空集合，y是S外的一點，故由引理知，存在一點x'\in S，使得
\|x'-y\|=inf\left\{ {\|x-y\||x\in S} \right\}>0
設x\in S，那么因S為凸集，故有\lambda\in(0,1)，使
z=\lambda x+(1-\lambda)x'\in S
因此，\|x-y\|^2\leq \|z-y\|^2=\|\lambda x+(1+\lambda)x'-y\|=\|(x-y)+\lambda(x-x')\|^2=\|x-y\|^2+\lambda^2\|x-x'\|^2+2\lambda(x-y)^T(x-x')
上式兩邊的\|x-y\|^2可消去，得
\lambda\|x-x'\|^2+2(x'-y)^T(x-x')\geq0,\forall\lambda\in(0,1),\forall x\in S
在上式中，令\lambda \to 0^，得
(x-y)^T(x-x')\geq0,\forall x\in S
記p=y-x'\neq0，有
p^T(x-x')\leq0,\forall x\in S
若記\alpha=p^Tx，則有
p^Tx\leq p^Tx'\leq 0,\forall x\in S
另一方面，由於
p^Ty-\alpha=p^T(y-x')=(y-x')^T(y-x')=\|y-x'\|^2>0
所以p^Tx\leq\alpha<p^Ty,\forall x\in S
定理得證。

套用

凸集分離定理的一個套用例子是Farkas引理，這個定理是最優性條件中最重要的基礎，見 Farkas引理 詞條。
利用Farkas引理，我們還可以證明有價值的Gordan定理和擇一性定理。Gorden定理在證明最優性條件中著名的Kuhn-Tucker條件，是極為關鍵的基礎。

相關詞條

熱門詞條

聯絡我們