基本概念

凸集 （通俗版本）集合中任意两点的连线仍在集合中。

（严格定义）设n维度欧式空间中点集\(\mathbb{K}\)，\(X_1,X_2\)为集合中任意两点，若对任意实数\(\alpha\in [0,1]\)，满足： \[ \alpha X_1+(1-\alpha)X_2\in\mathbb{K} \] 则称该集合\(\mathbb{K}\)为凸集。

凸组合 设n维度欧式空间中点集\(\mathbb{K}\)，\(X_1,\cdots,X_k\)为集合中任意\(k\)个点，若存在\(k\)个实数\(0\leq\alpha_i\leq 1,i=1,\cdots,k\)并且\(\sum_{i=1}^{k}\alpha_i =1\)，满足： \[ X=\sum_{i=1}^{k}\alpha_i X_i \] 则称\(X\)为\(X_1,\cdots,X_k\)的凸组合。\(0 <\alpha_i< 1,i=1\)，称为严格凸组合。

顶点 设\(\mathbb{K}\)凸集，\(X\in\mathbb{K}\),如果\(X\)不能用\(\mathbb{K}\)中不同两点的严格凸组合表示，则称\(X\)为\(\mathbb{K}\)的一个顶点。

也即，对\(0 <\alpha< 1\)有， \[ X\neq \alpha X_1+(1-\alpha)X_2,\forall X_1,X_2\in\mathbb{K},X_1\neq X_2 \] # 几个定理

定理1（线性规划问题的可行域为凸集） 若线性规划问题存在可行域， \[ D=\{\textbf{X}\vert \sum_{i=1}^{n}\textbf{P}_ix_i=\textbf{b},x_i\geq 0\} \] 是凸集。（小写的x代表\(X\)的分量）

proof 设\(X_1,X_2\)为\(D\)中任意两个相异的点，\(A\)是以\(P_i\)为行向量的矩阵。 则有， \[ AX_1=b,AX_2=b \] 于是，两点连线上任意一点\(X\)满足， \[ \begin{align*} AX=& A(\alpha X_1+(1-\alpha)X_2)\\ =&\alpha AX_1+AX_2-\alpha AX_2\in\mathbb{K}\\ =& \alpha b+b-\alpha b\\ =& b \end{align*} \] 故\(X\in D\)，\(D\)凸集。

定理2 若\(\mathbb{K}\)为有界凸集，则集合内任意一点可以表示为\(\mathbb{K}\)的顶点的凸组合。

proof 对于二维的情况比较形象。 已知三角形为有界凸集。任何有界凸集可以用凸多边形逼近，而任意凸多边形可以划分成可数个三角形。承认上诉逻辑，我们只需要证明：三角形的任意一点可以用顶点的凸组合表出。

设\(X_1,X_2,X_3\)为三角形的三个顶点。\(X\)为三角形内任意一点。若\(X\)在三条边上（即落在任意两个顶点的连线上），由凸集定义显然有顶点的凸组合表示。 若不在三条边上，做过\(X\)与\(X_1\)的射线交另外两点的连线于\(X'\)，于是有， \[ X'=\alpha X_2+(1-\alpha)X_3 \] \[ X=\lambda X'+(1-\lambda)X_1 \] \[ \lambda,\alpha\in(0,1) \] 代入即得， \[ X=(1-\lambda)X_1+\lambda\alpha X_2+\lambda(1-\alpha)X_3 \] 将三个系数相加不难发现和为\(1\)。 至此，我们得到了\(X\)用顶点的凸组合的表示。

但是对于二维以上的情形，就没有这么直观了，我们需要将三角形换成所谓的“单纯形”。

单纯形是二维的三角形，三维的四面体，在任意维度的推广。n-维单纯形是一个有 n+1 个顶点，n+1 个面 (facet) 的多面体。这个词译自英语 simplex，「单纯」其实意味着基本，因为他是组成更复杂结构（复形 complex）的基本构件。