重要凸集

一些简单的凸集

• 空集 $\mathrm{\varnothing }$、任意一点（单点集）$\{x_0\}$、全空间 ${\mathbf{R}}^n$ 都是 ${\mathbf{R}}^n$ 的仿射（自然也是凸的）子集。
• 任意直线是仿射的。如果直线通过零点，则是子空间，因此，也是凸锥。
• 一条线段是凸的，但不是仿射的（除非退化为一个点）。
• 一条射线是凸的，但不是仿射的。如果射线的基点是零点，则它是凸锥。
• 任意子空间是仿射的、凸锥（自然是凸的）。

超平面与半空间

超平面是具有如下形式的集合

$$\begin{array}{r}\{x\mid a^{\mathrm{\top }}x=b\}\end{array}$$

其中 $a\in {\mathbf{R}}^n$，$a\ne 0$ 且 $b\in \mathbf{R}$。超平面是关于 $x$ 的非平凡线性方程的解空间（因此是一个仿射集合）。几何上，$\{x\mid a^{\mathrm{\top }}x=b\}$ 可以看作是法线方向为 $a$ 的超平面，而常数 $b$ 决定了这个平面从原点的偏移。下面给出的是超平面的点向式方程：

$$\begin{array}{r}\{x\mid a^{\mathrm{\top }}(x-x_0)=0\}\end{array}$$

一个超平面将全空间 ${\mathbf{R}}^n$ 划分为两个半空间。（闭的）半空间是具有如下形式的集合：

$$\begin{array}{r}\{x\mid a^{\mathrm{\top }}x⩽b\}\end{array}$$

半空间是凸的，但不是仿射的。

Euclid 球和椭球

${\mathbf{R}}^n$ 中的空间 Euclid 球（或简称为球）具有如下形式：

$$\begin{array}{r}B(x_c,r)=\{x\mid \parallel x-x_c{\parallel }_2⩽r\}\end{array}$$

其中向量 $x_c$ 是球心，标量 $r>0$ 是半径。Euclid 还有另一种常见的表达式为：

$$\begin{array}{r}B(x_c,r)=\{x_c+ru\mid \parallel u{\parallel }_2⩽1\}\end{array}$$

和 Euclid 球类似的还有椭球，它们具有如下形式：

$$\begin{array}{r}\mathcal{E}=\{x|(x-x_c{)}^{\mathrm{\top }}{P}^{-1}(x-x_c)⩽1\}\end{array}$$

其中 $P=P^{\mathrm{\top }}\succ 0$，即 $P$ 是对称正定矩阵。向量 $x_c$ 为椭球的中心，矩阵 $P$ 决定了椭球从 $x_c$ 向各个方向扩展的幅度。$\mathcal{E}$ 的半轴长度为 $\sqrt{{\lambda }_i}$，这里的 ${\lambda }_i$ 为 $P$ 的特征值。

椭球另一个常用的表示形式是

$$\begin{array}{r}\mathcal{E}=\{x_c+Au\mid \parallel u{\parallel }_2⩽1\}\end{array}$$

范数球和范数锥

范数锥是集合

$$\begin{array}{r}C=\{(x,t)\mid \parallel x\parallel ⩽t\}\in {\mathbf{R}}^{n+1}\end{array}$$

显然，它是一个凸锥。

多面体

多面体被定义为有限个线性等式和不等式的解集

$$\begin{array}{r}\mathcal{P}=\{x\mid a_i^{\mathrm{\top }}x⩽b_i,i=1,\cdots ,m,c_j^{\mathrm{\top }}x=d_j,j=1,\cdots ,p\}\end{array}$$

因此，多面体是有限个半空间和超平面的交集。仿射集合（例如子空间、超平面、直线）、射线、线段和半空间都是多面体。显而易见，多面体是凸集。

多面体可以使用紧凑表达式来表示

$$\begin{array}{r}\mathcal{P}=\{x\mid Ax⪯b,Cx=d\}\end{array}$$

单纯形

单纯形是一类重要的多面体。设 $k+1$ 个点 $v_0,\cdots ,v_k\in {\mathbf{R}}^n$ 仿射独立，即 $v_1-v_0,\cdots ,v_k-v_0$ 线性独立，那么这些点决定了一个单纯形状

$$\begin{array}{r}C=\mathrm{conv}\{v_0,\cdots ,v_k\}=\{{\theta }_0{v}_0+\cdots +{\theta }_k{v}_k\mid \theta ⪰0,{\mathbf{1}}^{\mathrm{\top }}\theta =1\}\end{array}$$

其中 $\mathbf{1}$ 表示所有分量均为 1 的向量。这个单纯形的仿射维数为 $k$，因而也称为 ${\mathbf{R}}^n$ 空间的 $k$ 维单纯形。

一维空间中的单纯形是一条线段，二维空间中的单纯形是一个三角形，三维空间中的单纯形是一个四面体

多面体的凸包描述

有限集合 $\{v_1,\cdots ,v_k\}$ 的凸包是

$$\begin{array}{r}\mathrm{conv}\{v_1,\cdots ,v_k\}=\{{\theta }_1{v}_1+\cdots +{\theta }_k{v}_k\mid \theta ⪰0,{\mathbf{1}}^{\mathrm{\top }}\theta =1\}\end{array}$$

它表示 $k-1$ 维空间中由 $k$ 个顶点组成的有界多面体。

半正定锥

设 ${\mathbf{S}}^n$ 表示 $n$ 阶对称矩阵的集合，即

$$\begin{array}{r}{\mathbf{S}}^n=\{X\in {\mathbf{R}}^{n\times n}\mid X=X^{\mathrm{\top }}\}\end{array}$$

这是一个维数为 $n(n+1)/2$ 的向量空间。我们用 ${\mathbf{S}}_{+}^n$ 表示对称半正定矩阵的集合

$$\begin{array}{r}{\mathbf{S}}_{+}^n=\{X\in {\mathbf{S}}^n\mid X⪰0\}\end{array}$$

用 ${\mathbf{S}}_{++}^n$ 表示对称正定矩阵的集合

$$\begin{array}{r}{\mathbf{S}}_{++}^n=\{X\in {\mathbf{S}}^n\mid X\succ 0\}\end{array}$$

集合 ${\mathbf{S}}_{+}^n$ 是一个凸锥，称为半正定锥。例如 ${\mathbf{S}}^2$ 上的半正定锥

$$\begin{array}{r}X=\left[\begin{array}{ll}x& y\\ y& z\end{array}\right]\in {\mathbf{S}}_{+}^2⟺\{\begin{array}{c}x⩾0\\ z⩾0\\ xz⩾y^2\end{array}\end{array}$$