凸集、凸函数、凸优化关系示意图

凸集

若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是凸函数，则称为凸规划。

例如：无约束优化，线性规划等

凸规划性质优秀，求解简单稳定，是非常理想的模型。