判断两个凸集有没有交集算法

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的最小的凸集