判斷兩個凸集有沒有交集演算法

A. Hahn-Banach定理與凸集的分離性

Hahn-Banach定理，說的是， 賦范線性空間的某個子空間上的有界線性泛函可以被范數不減地延拓到全空間上 。這個定理是純代數的，但卻有著非常美妙的幾何形式，也因此被認為是最優化理論的基礎性定理。

首先，必須要弄清楚線性泛函這個對偶空間上的東西，是怎麼跟原空間聯系起來的。

我們把 記作是有界泛函 的零空間，容易知道它是原空間 的一個子空間。把這個空間做個平移， 表示的就是一個（閉）超平面。

在歐式空間裡面，我們要確定一個超平面，只需要知道平面上一點和這個平面的法向量方向。因此，在Hilbert空間中，我們會有用 的方式來表示一個超平面，這是因為Hilbert空間的對偶空間跟它本身是就是一樣（同構）的（Reize表示定理）。但是Banach空間不一樣，這就導致我們需要藉助它的對偶空間，上面的線性泛函 ，就起到向量 表示超平面法向的這一作用！

所以說，在Banach空間中討論幾何學，線性泛函就充當了超平面的作用，可以證明， 中的閉子空間與其有界線性泛函（關於其零空間構成的等價類）是一一對應的。

因此， Banach空間中集合的分離性就可以用線性泛函的語言來進行描述 ：
對於集合 ，如果存在常數 ，使得 就說線性泛函 分離 集合 和 。上面這個條件可以等價地表述為： 如果不等號嚴格成立，就說 是 嚴格分離 和 的。

那麼，泛函延拓是如何跟凸集分離聯系起來的呢？

Hahn-Banach定理有一個重要的推論，就是，對於單位球上的范數的 , 我們可以構造性的說明，存在一個有界線性泛函 ，使得 ，同時 ，這樣，根據線性運算元范數的定義： 。 這說明了，過單位球上的一點，可以做一個閉超平面，使得單位球全部位於超平面的一側！這本質就是支撐超平面定理！

進一步，很容易知道，如果一點位於單位球外，那麼必然存在一個超平面，把這點跟單位球給 嚴格分離 。

單位球是一個特殊的凸集，那對於一個任意的凸集怎麼辦？

首先我們假定這個凸集是有內點的（就算沒有內點，只要有相對內點就可以放在一個更小的子空間上討論），這時候不妨把這個內點平移到跟原點重合，我們的一個想法就是： 構造一個新的范數，讓這個凸集在新的范數下成為單位球。 設 是一個以原點為內點的均衡吸收的凸集，定義 為凸集 的Minkowski泛函。從而， 的內點集可以表示成 。

最終，我們可以得到泛函延拓定理的幾何形式：
設 是賦范線性空間 中的兩個凸集，同時 的內點集非空，且 不包含 的內點，則存在線性泛函 分離凸集 。

最後呢，我想把一個優化理論的基礎定理推廣到無窮維空間中去。

在歐式空間中，一個閉凸集，可以看作是所有包含這個凸集的半平面的交集。相對的，在Banach空間中，一個閉凸集，可以看作是所有包含這個凸集的半平面的交集，而這個半平面，是用線性泛函表示的。

這樣，我們成功地 用對偶空間中的元素去描述了原空間中的凸集 。這也是對偶性理論的基礎。

文章最後的最後，我想用簡單用凸集分離定理來證明 Mazur's Lemma.

(Mazur's Lemma)賦范線性空間中 弱收斂於 ，證明存在一個線性組合 強收斂於 。

首先我們證明 ，這里 表示凸組合， 表示閉包。
如若不然，即 ，根據凸集分離定理，存在線性泛函 將點 與閉集 嚴格分離，這與 弱收斂於 矛盾。

從而 Mazur's lemma 是顯然的。

B. 如何證明兩個凸集的向量和也是凸集

用定義。

設A,B是兩個凸集，和集是C。

令x,y是C中的兩點，x=a1+b1,y=a2+b2,其中a1,a2屬於A,b1,b2屬於B,只需證明ux+(1-u)y屬於C.而

ux+(1-u)y=u(a1+b1)+(1-u)(a2+b2)=(ua1+(1-u)a2)+(ub1+(1-u)b2)。

由A,B凸，後面的兩部分分別屬於A和B,所以ux+(1-u)y在A和B的和集C里。

介紹

凸集的邊界總是凸曲線。包含歐幾里得空間的給定子集A的所有凸集的交集稱為A的凸包。它是包含A的最小凸集。凸函數是在具有其epigraph（函數圖上或上方的點集合）為凸集的屬性的間隔上定義的實值函數。

凸最小化是一個優化的子領域，研究了凸函數在凸集上的最小化問題。用於凸集和凸函數屬性研究的數學分支稱為凸分析。

C. 海萊定理

我們只來證明當這組凸集的個數是有限多的時候的情況，當凸集的個數是無窮多的時候需要用到一些高等數學的知識。這個結論被稱之為Helly定理，它是歐式組合幾何中的最重要的結論之一。

為了證明這個結論，我們首先證明一個叫做Radon定理得結論：

如果平面上有n個點，其中n>3，那麼一定可以把他們分成兩組A，B並且A和B的凸包有交點。

這個結論的證明非常簡單。首先任取4個點，x, y, z, w。如果這4個點的凸包就是這4點組成的四邊形，那麼，A={x,y}, B為z,w以及其餘點的集合，顯然A的凸包和B的凸包有交點。如果x, y, z, w這4個點的凸包不是四邊形，而是三角形或者直線或者一個點，那麼一定有一點，比如x在y, z, w的凸包之中，取A={x}， B為其餘的點的集合，那麼顯然A的凸包和B的凸包也有交點。

現在我們可以證明Helly定理了。我們首先證明如果這些凸集的任何n-1個都有交點，那麼這些凸集的任何n個都有交點。如果這個結論正確，那麼歸納法可以證明整個結論。

令A1，A2，...， An為n個凸集。而 x1 為A2， A3， ...， An 的交點，但是可能不在A1中；同樣x2為A1， A3，...， An的交點，但可能不在A2中， 等等，

最後xn 為A1， A2， ...， An-1的交點。

現在考慮集合 {x1, x2, ..., xn}

根據Radon定理，我們可以把這個集合分成兩個子集，他們的凸包有交點，這樣，這個交點就在所有的凸集A1， A2， ...， An的交集中

D. 證明任意多個凸集的交仍然是凸集

在區域內任意兩點的連線【直線】上的點也都在該區域內，則該區域的稱為凸集。

設A、B兩點是凸集X和Y交集內的任意兩點。

因為A和B屬於凸集X，所以AB連線上所有點都在X內；

因為A和B屬於凸集Y，所以AB連線上所有點都在Y內；

即，A和B連線上所有的點同時在X內和Y內。

所以A和B連線上所有的點都在X和Y的交集內。

又由於A和B是任意的。

所以X和Y的交集是凸集。

(4)判斷兩個凸集有沒有交集演算法擴展閱讀：

令S是實數上的向量空間，或者更一般地，是在某個有序域上，這包括歐幾里德空間。如果對於C中的所有x和y，並且在區間（0,1）中的所有t。

也屬於C，則S中的集合C被稱為凸。換句話說，連接x和y的線段上的每個點都在C中。這意味著實際或復雜拓撲向量空間中的凸集是路徑連接的。此外，如果除了端點之外的連接x和y的線段上的每個點都在C的內部，則C是嚴格凸起的。

R的凸子集（實數集）僅僅是R的間隔。歐幾里得平面的凸子集的一些例子是實心的正多邊形，實心三角形和實心三角形的交集。歐幾里德三維空間的凸子集的一些例子是阿基米德固體和柏拉圖式固體。開普勒 - 波諾索多面體是非凸集的例子。

非凸集

不凸的集合稱為非凸集。 一個不是凸多邊形的多邊形有時被稱為凹多邊形，一些來源更普遍地使用術語凹集來表示非凸集，但大多數許可權禁止這種使用。

凸集的補集有時被稱為反凸集，特別是在數學優化的上下文中。

E. 凸集、凸函數、凸優化的簡介與聯系

若S為凸集，則S中任意兩點的連線也在S中。

簡單地說，沒有空洞和凹入部分的集合叫做凸集。

任意兩點的連線部分（包括這兩個點）叫做這兩個點的凸組合，不包括這兩個點叫做嚴格凸組合。

凸集的 性質 ：凸集的並集、加減法、數乘，仍是凸集。

凸集的 例子 ：歐式空間，超平面，半空間（被一個超平面分割的空間），多面集（凸多面體），多面錐，等。

引入概念： 極點 ，不能被表示為兩個不同點的凸組合的點，比如凸多邊形的角上的點。

極點可以表示有界閉凸集，或者說，有界閉凸集中任意一點可表示為極點的凸組合。

那無界呢？引入概念： 方向 ，一個方向的向量，使得S中任意一點x為端點，以此方向射出的射線仍在S內。引入概念： 極方向 ，不能被表示為S中兩個不同方向的 正 組合的方向。由於這個「正」字，類似極點的性質，極方向大概是所有方向中的極端位置，比如扇形的兩側邊界。

S的其他方向都能表示為極方向的正線性組合。

有了極點和極方向的概念，可引出 表示定理 ：若S為非空多面集，則存在有限個極點，有限個極方向（若S有界則為0個），點x屬於S等價於x可表示為極點和極方向的正組合。

凸集分離定理是凸集的一個重要性質。按如下思路由易到難證明：

1.（投影定理）若S為Rn中的閉凸集，y不屬於S，則存在唯一的一點x屬於S，x為點集S距離點y最近的點，稱為y在S上的投影。

2.（點與凸集分離定理）對任意S中的點z（除x以外），（x-z）與（x-y）夾角為鈍角，即內積小於0。由此，可用一個超平面將S與y隔開。

3.（凸集分離定理）S1和S2為Rn中兩個非空凸集，交集為空，則存在一個超平面將S1和S2分隔開。

應用：使用其推論Farkas定理、Gordan定理等都可把證明無解的問題轉化為證明有解的問題， 以「有解」證「無解」 。

Farkas定理 ：設A為m*n矩陣，c為n維向量，則Ax<=0，c'x>0有解的充要條件是A'y=c,y>=0無解。

Gordan定理 ：設A為m*n矩陣，則Ax<0，有解的充要條件是不存在非零向量y>=0，使A'y=0。

定義：任意兩個自變數x1x2，任意x在x1x2之間，則有f(x1)f(x2)連線在f(x)上方。

凸函數的加法、數乘仍是凸函數。

若S是非空凸集，f是定義在S上的凸函數，a是一個實數，則集合S2 = {x|x∈S，f(x)≤a}是凸集。

若S是非空凸集，f是定義在S上的凸函數，則f在S上的局部極小點（在其某鄰域內最小）是全局極小點，且極小點的集合是凸集。

雖然凸函數具有非常良好的性質，但相應的，凸函數的判別是非常困難的。據研究，多項式的凸函數判別是個NPhard問題。在此給出一階條件和二階條件：

一階條件：若S式Rn上非空凸集，f在S上可微，f是凸函數等價於任意點函數值大於等於函數在這一點的一階（切線）近似。

二階條件：若S式Rn上非空凸集，f在S上二次可微，f是凸函數等價於任意點處Hesse矩陣半正定。

一般來說，二階條件的使用更加簡單。

最優化模型中，若可行域S是凸集，目標函數f是凸函數，則稱為凸規劃。

例如：無約束優化，線性規劃等

凸規劃性質優秀，求解簡單穩定，是非常理想的模型。

F. 任何兩個凸集的交集是凸集嗎

是的。不妨設兩個凸集為P，Q，對於任意兩個點x，y∈P∩Q，由於P凸，故線段xy在P中，同理線段xy在Q中，故線段xy在P∩Q中。於是P∩Q凸

G. 任意多個凸集的交集還是凸集

凸集的定義: 實數 R （或復數 C 上）在向量空間中，集合 S 稱為凸集，如果 S 中任兩點的連線內的點都在集合 S 內。
設S1,S2為凸集. 任意A,B屬於S1∩S2. C是A,B兩點的連線內的任意1點
A,B屬於S1∩S2 =>A,B屬於S1=> A,B兩點的連線內的點都在S1=>C在S1 (1)
A,B屬於S1∩S2 =>A,B屬於S2=> A,B兩點的連線內的點都在S2=>C在S2 (2)
(1)(2)=>C在S1∩S2
因為C任意=>A,B兩點的連線內的點都在S1∩S2
因為A,B任意=>S1∩S2任兩點的連線內的點都在S1∩S2內=>S1∩S2為凸集

任意n, 設S1,S2...Sn為凸集,
由前可見, S=S1∩S2為凸集.
S'=S∩S3為凸集 (S=S1∩S2∩S3)
S''=S'∩S4為凸集...
=>S1∩S2∩S3...∩Sn為凸集

H. 關於凸包的問題

其實,(1)(2)兩個問題應該同時證明:

＞表示"包含"

設對於任意的凸集Ai,
滿足 Ai＞S ,

則 ∩Ai > ∩S (這里∩是對i=1到無窮)

即 ∩Ai > S

又因為Ai >∩Ai (這是由交集的定義決定了∩Ai 是最小)

所以對於任意的凸集Ai ,有
Ai >∩Ai > S

由上式中, 凸集Ai 的任意性,知
∩Ai 是包含S的最小的凸集