凸集和凸函数

定义 集合$C$是$R^n$的一个子集，称$C$为凸集如果 $$\alpha x+(1-\alpha)y\in C,\quad \forall x,y\in C, \forall \alpha \in [0, 1]$$ 空集认为是凸集。 直观上来说，凸集就是“鼓鼓的”集合，因此任意两点的连线必需落在集合里面。同时也必需是连续的。如下图所示：

后文中如果不特别指明，则用$C$表示凸集。

命题1

• (a) 有限个凸集的交还是凸集。数学语言：任意集合$\{C_i|i\in I\}$的交$\cap_{i\in I}C_i$是凸集；
• (b) 两个凸集$C_1, C_2$的向量和(即集合$\{x_1+x_2|x_1\in C_1, x_2 \in C_2 \}$)$C_1+C_2$是凸集；
• (c) 对于任意的凸集$C$和标量$\lambda$，集合$\lambda C$(即集合$\{\lambda x|x\in C\}$)是凸的。进一步地，如果集合$C$是凸的且$\lambda_1,\lambda_2$是正的标量，则 $$(\lambda_1+\lambda_2)C=\lambda_1 C+\lambda_2 C$$
• (d) 凸集的闭包和内部点也是凸的，即$cl(C)$和$int(C)$也是凸的；
• (e) 通过一个仿射函数的凸集的映射和逆映射也是凸集。

这些命题的证明思路比较清晰，均是从定义出发。但是以后会经常使用这些思路，因此要多多体会。

证明：

(a)从集合$\cap_{i\in I}C_i$中取两点$x,y$，由于集合$C_i$是凸集，因此$x,y$的连线上的所有点均属于$C_i$，因此也均属于它们的交集，由此，$\cap_{i\in I}C_i$是凸的。

(b)同理可证(b)，取集合$C_1+C_2$里的两个点，表示为$x_1+x_2,y_1+y_2$，其中$x1,y1\in C_1$且$x_2,y_2\in C_2$，则对于任意的$\alpha\in[0,1]$，有 $$\alpha(x_1+x_2)+(1-\alpha)(y_1+y_2) = (\alpha x_1+(1-\alpha)y_1)+(\alpha x_2+(1-\alpha)y_2)$$

由于$C_1,C_2$是凸集，所以$(\alpha x_1+(1-\alpha)y_1)\in C_1,(\alpha x_2+(1-\alpha)y_2)\in C_2$，所以$\alpha(x_1+x_2)+(1-\alpha)(y_1+y_2) \in C_1+C_2$，由此，$C_1+C_2$是凸集。

(c) 任选两点$x,y\in\lambda C$，则$\frac{x}{\lambda},\frac{y}{\lambda}\in C$，则由于$C$是凸的，所以有： $$\alpha \frac{x}{\lambda} + (1-\alpha)\frac{y}{\lambda} \in C, \quad \forall \alpha\in[0,1]$$ 即 $$\frac{1}{\lambda}(\alpha x + (1-\alpha) y) \in C$$ 即 $$\alpha x + (1-\alpha) y \in \lambda C$$ 所以$\lambda C$是凸集。

(d)