凸优化|凸集

1. 直线和线段

假设 $x_1\ne x_2$ 是 $\mathbf{R}^n$ 空间（n维欧氏空间）中的两个点，直线

$$y=\theta x_1 + (1-\theta)x_2$$

是穿过 $x_1$ 和 $x_2$ 的直线，$\theta\in \mathbf{R}$ 。若满足 $\theta\in(0,1)$ ，则 $y$ 为连接 $x_1,x_2$ 的线段上的一点。

2. 仿射集(affine sets)

若集合 $C$ 包含 $C$ 中任意两点的线性组合，并且其系数之和为 1，则集合 $C$ 称为仿射集（两点形成的线段上任意一点都属于集合 $C$）。即对任意 $x_1,x_2\in C$ 并且 $\theta\in\mathbf{R}$ ，有 $\theta x_1+(1-\theta)x_2\in C$ 。

仿射集可以扩展至多个点。即任意 $x_1,x_2,\ldots,x_k\in C$ 并且 $\theta\in\mathbf{R}$ ，有 $\theta_1 x_1+\ldots+\theta_kx_k\in C$ ，其中 $\theta_1+\ldots+\theta_k=1$ ，则该集合为仿射集。

几何解释：

• 仿射变换前为直线，变换之后还是直线（直线上的点也仍然在变换后的直线上）
• 直线比例不变

维基百科上非常形象的一个gif图像：

仿射壳/包(affine full)。某个集合 $C\in\mathbf{R}$ 中的点的所有仿射组合组成的集合，称为仿射壳，表示为：

$$\mathbf{aff}\,C=\{\theta_1 x_1+\ldots+\theta_k x_k|x_1,\ldots,x_k\in C,\theta_1+\ldots+\theta_k=1\}$$

仿射壳是包含集合 $C$ 的最小仿射集。即集合 $S$ 是任意满足 $C\subseteq S$ 的仿射集，从而 $\mathbf{aff}\,C\subseteq S$ 。

仿射维数：仿射包的维数。

内点（interior）：$\text { int } C=\{x \mid B(x, r) \subseteq C, r>0\}$

相对内点（relative interior）：$\text { relint } C=\{x \mid B(x, r) \cap \operatorname{aff} C \subseteq C, r>0\}$

3. 凸集（convex sets）

如果 $C$ 中任意两点之间的线段位于 $C$ 中，则集合 $C$​ 是凸的。对于任意 $x_1,x_2\in C$ ，任意 $0\le\theta\le 1$ ，有

$$\theta x_1 + (1-\theta)x_2\in C$$

下图可直观地认识一些简单的凸集和非凸集。

从凸集的几何意义来看，凸集中的任意两点间一定是“无障碍可见”的，即任意一点能通过一条线段到达另外一点，且中间经过的所有点都属于该集合。这意味着凸集都是边界向外凸的，且不能含有未包含的边界点。

凸包。凸包是集合 $C$ 的最小凸集，包含集合 $C$ 中点的所有凸组合。

$$\mathbf{conv}\,C=\{\theta_1 x_1+\ldots+\theta_k x_k|x_i\in C,\theta_i\ge 0,i=1,\ldots,k,\theta_1+\ldots+\theta_k=1\}$$

下图是两个非凸集合的凸包。

凸组合的思想可以被推广至无穷和、积分以及最广泛的概率分布中（如数学期望）。

4. 凸锥（cones）

对于任意 $x_1,x_2,\in C$，以及任意 $\theta_1,\theta_2\ge 0$，凸锥满足

$$\theta_1x_1+\theta_2x_2\in C$$

凸锥：既是凸集又是锥。

其几何形状如下图。

锥包（conic hull）是包含集合 $C$ 的最小凸锥（集合 $C$ 内的点的所有锥的组合）。可表示为

$$\left\{\theta_{1} x_{1}+\cdots+\theta_{k} x_{k} \mid x_{i} \in C, \theta_{i} \geq 0, i=1, \ldots, k\right\}$$

锥包的几何意义可由下图解释。

5. 超平面和半空间

超平面。其中a为该平面的法向量（这里是用二维的线来表示超平面），表示超平面的方向。

半空间。被超平面分割为两个半空间。

6. 欧式球和椭球

欧式球（euclidean ball）：二维的圆，三维的球，……（以下为两种定义）

$$\begin{aligned} B\left(x_{c}, r\right) &=\left\{x \mid\left\|x-x_{c}\right\|_{2} \leq r\right\} \\ &=\left\{x \mid\left(x-x_{c}\right)^{T}\left(x-x_{c}\right) \leq r^{2}\right\} \\ B\left(x_{c}, r\right) &=\left\{x_{c}+r u \mid\|u\|_{2} \leq 1\right\} \end{aligned}$$

椭球（ellipsoid）：欧式球是椭球的特例，当且仅当 $P$ 为单位矩阵时椭球变为欧式球。（相当于欧式球做了旋转操作）

$$\begin{align} &E=\left\{x \mid\left(x-x_{c}\right)^{T} P^{-1}\left(x-x_{c}\right) \leq r^{2}\right\}, P 为对称正定矩阵 \\ &E=\left\{x_{c}+A u \mid\|u\|_{2} \leq 1\right\}, A=P^{1 / 2} \end{align}$$

7. 范数球和范数锥

范数（norm）：

$$\begin{aligned} &\|x\| \geq 0,\|x\|=0 \text { 当且仅当 } x=0 \\ &\|t x\|=|t|\|x\|, t \in \mathcal{R} ; \\ &\|x+y\| \leq\|x\|+\|y\| \end{aligned}$$

范数球（norm ball）：

$$B\left(x_{c}, r\right)=\left\{x \mid\left\|x-x_{c}\right\| \leq r\right\}$$

范数锥（norm cone）：

$$\{(x, t) \mid\|x\| \leq t\}$$

8. 多面体（Polyhedra）和单纯形（simplex）

由多个超平面围成的区域。

$$P=\left\{x \mid a_{j}^{T} x \leq b_{j}, c_{i}^{T} x=d_{i}\right\}$$

单纯形（simplex）：

$$\left\{\sum_{i=0}^{k} \theta_{i} v_{i} \mid \theta_{i} \geq 0, \sum_{i=0}^{k} \theta_{i}=1, v_{1}-v_{0}, \ldots, v_{k}-v_{0} \text { 线性无关 }\right\}$$

例如在二维平面有三个点（三点不在同一直线），任意其构成两个向量可以是线性无关的。

三维的单纯形其实就相当于去寻找包含三点的凸包。