凸集的定义与常见凸集

通常认为，如果某个实际问题可以表述为凸优化问题，那么事实上已经解决了这个问题，然而凸优化问题的识别还比较困难，本文将先介绍凸集的定义与常见凸集。

仿射集

如果集合 C⊆RnC\subseteq R^{n} 是仿射的，等价于：对于任意的 x1,x2∈Cx_{1},x_{2}\in C 及 θ∈R\theta \in R 有 θx1+(1−θ)x2∈C\theta x_{1}+(1-\theta)x_{2}\in C ，即 CC 包含了 CC 中任意两点的系数之和为1的线性组合。

将其扩展到多个点的情况：如果 θ1+θ2+...+θk=1\theta_{1}+\theta_{2}+...+\theta_{k}=1 ，我们则称具有 θ1x1+θ2x2+...+θkxk\theta_{1}x_{1}+\theta_{2}x_{2}+...+\theta_{k}x_{k} 形式的点为 x1,x2,...,xkx_{1},x_{2},...,x_{k} 的仿射组合。例如线性方程组的解集 C={x∣Ax=b}C=\{x|Ax=b\}是一个仿射集。

称由集合 C⊆RnC\subseteq R^{n} 中点的所有仿射组合所组成的集合为 CC 的仿射包：

aff C={θ1x1+...+θkxk∣x1,...,xk∈C,θ1+θ2+...+θk=1}\mathrm{aff}\ C=\{\theta_{1}x_{1}+...+\theta_{k}x_{k}|x_{1},...,x_{k}\in C,\theta_{1}+\theta_{2}+...+\theta_{k}=1\}

仿射包是包含 CC 的最小的仿射集合，即如果集合 SS 满足 C⊆SC\subseteq S，则 aff C⊆S\mathrm{aff}\ C\subseteq S ，同时将集合 CC 的仿射维数定义为其仿射包的维数。例如 R2R^{2} 上的单位圆环的维数为1，但其仿射维数为2，因为其仿射包为全空间 R2R^{2}

凸集

如果集合 CC 为凸集，那么对于任意的 x1,x2∈Cx_{1},x_{2}\in C 与0≤θ≤10\le \theta\le 1都有 θx1+(1−θ)x2∈C\theta x_{1}+(1-\theta)x_{2}\in C，与仿射集的区别在于仿射集并没有 θ≥0\theta\ge0 的要求，例如一条线段是凸集，而一条直线是仿射集。

扩展到多维的情况，如果有 θ1+θ2+...+θk=1,θi≥0\theta_{1}+\theta_{2}+...+\theta_{k}=1,\theta_{i}\ge0 ，则称具有 θ1x1+θ2x2+...+θkxk\theta_{1}x_{1}+\theta_{2}x_{2}+...+\theta_{k}x_{k} 形式的点为 x1,x2,...,xkx_{1},x_{2},...,x_{k} 的凸组合。

称由集合 C⊆RnC\subseteq R^{n} 中点的所有凸组合所组成的集合为 CC 的凸包：

conv C={θ1x1+...+θkxk∣x1,...,xk∈C,θ1+...+θk=1,θi≥0}\mathrm{conv}\ C=\{\theta_{1}x_{1}+...+\theta_{k}x_{k}|x_{1},...,x_{k}\in C,\theta_{1}+...+\theta_{k}=1,\theta_{i}\ge0\}

与仿射包同样，凸包也是包含 CC 的最小的凸集，在一般情况下，设 C∈RnC\in R^{n} 是凸集，xx 是随机变量，并且 x∈Cx\in C 的概率为1，那么 E x∈CE\ x\in C

一些重要的凸集

识别出凸集对于识别凸优化问题较为重要，这里将介绍一些比较重要的凸集。

任意的仿射集和子空间都是凸集，一些比较简单的例如空集 ∅\emptyset ，单点集{x0}\{x_{0}\}，全空间 RnR^{n} ，直线/射线/线段都是凸的。

还有一些比较重要的凸集如下：

  1. 超平面 {x∣aTx=b}\{x|a^{T}x=b \}和半空间 {x∣aTx≤b}\{x|a^{T}x\le b\}
  2. Euclid球 B(xc,r)={x∣ ∣∣x−xc∣∣2≤r}B(x_{c},r)=\{x|\ ||x-x_{c}||_{2}\le r\}
  3. 椭球 ξ={x∣(x−xc)TP−1(x−xc)≤1}\xi=\{x|(x-x_{c})^{T}P^{-1}(x-x_{c})\le1\}
  4. 范数球 {x∣ ∣∣x−xc∣∣≤r}\{x|\ ||x-x_{c}||\le r\}，其中 ∣∣⋅∣∣||\cdot|| 是 RnR^{n} 中的范数
  5. 范数锥 C={(x,t)∣ ∣∣x∣∣≤t}⊆Rn+1C=\{(x,t)|\ ||x||\le t\}\subseteq R^{n+1}
  6. 多面体 P={x∣ajT≤bj,j=1,...,m,cjTx=dj,j=1,...,p}P=\{x|a_{j}^{T}\le b_{j},j=1,...,m,c_{j}^{T}x=d_{j},j=1,...,p\}，即为有限个半空间和超平面的交集，单纯形也为凸集，是一种特殊的多面体
  7. 半正定锥 S+n={X∈Rn∗n∣X=XT,X⪰0}S_{+}^{n}=\{X\in R^{n*n}|X=X^{T},X\succeq0\}，即为半正定对称矩阵的集合
  • 技术