凸集

定义

• 凸集（Convex Set）定义：集合 $C\subseteq {\mathbb{R}}^n$ 称为凸集，当且仅当对任意 $x,y\in C$ 以及任意 $\theta \in [0,1]$，都有：
  $\theta x+(1-\theta )y\in C$
  即连接集合内任意两点的线段完全包含在集合内部。

• 定义：半空间（Half-space）：在 $n$ 维欧氏空间 ${\mathbb{R}}^n$ 中，由线性不等式决定的集合称为闭半空间：
  $H=\{x\in {\mathbb{R}}^n\mid a^{T}x\le b\}$
  其中 $a\in {\mathbb{R}}^n$ ($a\ne 0$) 为法向量，$b\in \mathbb{R}$ 为标量。（注：由 $a^{T}x\ge b$ 定义的半空间同理）

• 凸函数（Convex Function）：
  设 $X\subseteq {\mathbb{R}}^n$ 为凸集。函数 $f:X\to \mathbb{R}$ 称为凸函数，当且仅当对任意 $x,y\in X$ 及任意 $\theta \in [0,1]$，都有：
  $f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$
  即函数图像上任意两点连线的割线段，始终位于函数图像的上方。

性质

1. 半空间是凸集
2. 凸集的交集仍然是凸集
3. 任意一族凸函数的点对点上确界仍为凸函数

证明

---

证明：半空间是凸集

1. 取元：任意取 $x,y\in H$，根据半空间的定义：

$a^{T}x\le b\text{且}{a}^{T}y\le b$

2. 构造凸组合：设 $z=\theta x+(1-\theta )y$，其中 $\theta \in [0,1]$。
3. 展开计算：利用矩阵乘法的分配律：

$a^{T}z=a^T(\theta x+(1-\theta )y)=\theta a^{T}x+(1-\theta )a^{T}y$

4. 放缩估计：由于 $\theta \ge 0$ 且 $1-\theta \ge 0$，将 $a^{T}x\le b$ 与 $a^{T}y\le b$ 代入：

$a^{T}z\le \theta b+(1-\theta )b=(\theta +1-\theta )b=b$

5. 结论：得到 $a^{T}z\le b$，即 $z\in H$。因此半空间 $H$ 是凸集。 $■$

---

证明：凸集的交集是凸集：设 $\{C_i{\}}_{i\in I}$ 是一族凸集（其中 $I$ 为任意索引集，可以是有限或无限集）。则它们的交集 $S={\bigcap }_{i\in I}{C}_i$ 也是凸集。

1. 取元：任意取 $x,y\in S={\bigcap }_{i\in I}{C}_i$。
2. 交集的性质：根据交集定义，对所有的 $i\in I$，都有 $x\in C_i$ 且 $y\in C_i$。
3. 利用单集合凸性：因为对每一个 $i\in I$，$C_i$ 本身都是凸集，所以对于任意 $\theta \in [0,1]$，其凸组合：

$z=\theta x+(1-\theta )y\in C_i(\forall i\in I)$

4. 回代交集：由于 $z$ 属于族中的每一个集合 $C_i$，因此 $z$ 必定属于它们的交集：

$z\in {\bigcap }_{i\in I}{C}_i=S$

5. 结论：符合凸集定义，因此 $S$ 也是凸集。 $■$

---

证明：任意一族凸函数的点对点上确界仍为凸函数

设 $\{f_i{\}}_{i\in I}$ 是定义在凸集 $X\subseteq {\mathbb{R}}^n$ 上的一族凸函数（索引集 $I$ 可以是任意有限或无限集）。
定义其点对点上确界函数为：

$f(x)={\sup }_{i\in I}{f}_i(x)$

则 $f(x)$ 也是 $X$ 上的凸函数。

1. 取元与定义：任意取 $x,y\in X$ 及 $\theta \in [0,1]$。设 $z=\theta x+(1-\theta )y\in X$。
2. 利用单个函数的凸性：对于任意固定的 $i\in I$，由于 $f_i$ 是凸函数，满足：

$f_i(z)\le \theta f_i(x)+(1-\theta )f_i(y)$

3. 放大右端：根据上确界的定义，对所有 $i\in I$，都有 $f_i(x)\le f(x)$ 且 $f_i(y)\le f(y)$。由于 $\theta \ge 0$ 且 $1-\theta \ge 0$，因此：

$\theta f_i(x)+(1-\theta )f_i(y)\le \theta f(x)+(1-\theta )f(y)$

4. 组合不等式：结合上面两式，对任意 $i\in I$ 均成立：

$f_i(z)\le \theta f(x)+(1-\theta )f(y)$

5. 取上确界：上式右端与索引 $i$ 无关（是一个固定的上界）。因此对左端关于 $i\in I$ 取上确界，不等式依然成立：

${\sup }_{i\in I}{f}_i(z)\le \theta f(x)+(1-\theta )f(y)$

即：

$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$

6. 结论：符合凸函数定义，$f(x)$ 是凸函数。 $■$

---