第二章凸集

主要内容:

仿射集合和凸集
重要例子
保凸运算
广义不等式
分离和支撑超平面
对偶锥与广义不等式

2.1仿射集合和凸集

仿射集合

仿射集合：集合 $C\subseteq R^n$ 中任意两个不同点的直线仍然在集合 $C$ 中，那么称集合 $C$ 是仿射集合。

$\forall x_{1},x_{2}\in C,\forall\theta \in R,\theta x_{1}+(1-\theta)x_{2} \in C$

如上图，对于 $x_{1}\, x_{2}$ ，取不同的 $\theta$ 可以得到不同的点，这些点构成了经过 $x_{1}\, x_{2}$ 的直线。

如果将两个点扩展到多个点，引出仿射组合的概念，首先 $\theta_{1}+\theta_{2}+\cdots +\theta_{k}=1$ ，则具有 $\theta_{1}*x_{1}+\theta_{2}*x_{2}+\cdots +\theta_{k}*x_{k}$ 的形式的点为 $x_{1},x_{2},\cdots x_{k}$ 的仿射组合。

仿射集合的例子： $C= \left \{ x| Ax=b\right \}$ 显然

$\forall x_{1},x_{2}\in C,\forall \theta \in R, x = \theta x_{1}+(1-\theta)x_{2} Ax= A(\theta x_{1}+(1-\theta) x_{2})=\theta Ax_{1}+(1-\theta) Ax_{2}=\theta b+ (1-\theta)b= b$

仿射包：集合C中的点的所有仿射组合组成的集合为C的仿射包。

凸集

凸集可以理解成一种特殊的仿射集合，凸集的数学定义:

$\forall x_{1},x_{2}\in C,\forall \theta \in \left [ 0,1 \right ],\theta x_{1}+(1-\theta)x_{2} \in C$

可以看出相比于仿射，凸集就是对 $\theta$ 有取值范围的约束。几何上来看，仿射是经过两个点的直线在集合C中，而凸集则是连接两个点的线段在集合C中。

如上图，a是凸集，b和c均不是凸集。

凸组合：首先 $\theta_{1}+\theta_{2}+\cdots +\theta_{k}=1$ ，且 $\theta _{i}\geq 0,i=1\cdots k$ ，则具有 $\theta_{1}*x_{1}+\theta_{2}*x_{2}+\cdots +\theta_{k}*x_{k}$ 的形式的点为 $x_{1},x_{2},\cdots x_{k}$ 的凸组合。

凸包：集合C中所有点的凸组合的集合G为集合C的凸包。如下图，阴影部分即为包含十五个点的集合C的凸包。

锥

锥： $\forall x\in C,\forall \theta\geq 0,\theta x\in C$ ，这样的集合是锥，或非负齐次。

凸的锥，则为凸锥，即满足 $\forall x_{1},x_{2} \in C, \forall \theta_{1},\theta_{2}\geqslant 0,\theta_{1}x_{1}+\theta_{2}x_{2}\in C$ ，如下图为一个凸锥。

锥组合： $\theta _{i}\geq 0, i=1\cdots k$ ，具有 $\theta_{1}*x_{1}+\theta_{2}*x_{2}+\cdots +\theta_{k}*x_{k}$ 的形式的点为 $x_{1},x_{2},\cdots x_{k}$ 的锥组合。

如果每个 $x_{i}$ 都属于集合C，那么 $x_{i}$ 的每一个锥组合也在C中。

C是凸锥的充分必要条件是它包含其元素的所有锥组合。

锥包：集合C中的元素的所有锥组合的集合是集合C的锥包。

更多精彩内容