【凸优化学习笔记3】几种重要的凸集

参考资料：
1.凌青老师的凸优化课（b站）
2.Stephen Boyd的《凸优化》中译本（清华大学出版社）
全部使用LaTex公式书写

仿射集、凸集、凸锥总结

上一篇文章讲到9个概念：
仿射集、凸集、凸锥(集)
仿射组合、凸组合、凸锥组合
仿射包、凸包、凸锥包

要从组合的概念切入去理解。
因为集是从组合定义的，包是从组合构造的。

设一个集合$C$中取任意$k$个点 $x_1,...,x_k$，且选取 ${\theta }_1,...,{\theta }_k\in \mathbf{R}$，
我们构造新点：${\theta }_1{x}_1+\cdots +{\theta }_k{x}_k$

对于这个新点，根据系数条件不同有：

新点的组合类型	条件
仿射组合	${\theta }_1+...+{\theta }_k=1$
凸组合	${\theta }_1+...+{\theta }_k=1$，${\theta }_1+...+{\theta }_k⩾0$
凸锥组合	${\theta }_1+...+{\theta }_k⩾0$

有了组合的概念，就能定义集。比如一个集合中任意点的仿射组合还在这个集合中，这个集合就是一个仿射集。

有了组合的概念，我们还能定义包。比如一个集合中任意点的凸组合，可构造出这个集合的凸包。

几种重要的凸集

空集、单点集、n维空间和子空间、直线和线段、射线

①空集
空集是仿射集、凸集、凸锥。

②单点集
一个点的集合（单点集）是仿射集、凸集，但不是凸锥。除非这个点是原点。

③${\mathbf{R}}^n$空间和子空间
一个${\mathbf{R}}^n$空间是仿射集、凸集、凸锥。
对于一个${\mathbf{R}}^n$空间的子空间，它满足加法和数乘封闭。也就是过原点。
所以一个${\mathbf{R}}^n$空间的子空间是仿射集、凸集、凸锥。

④直线和线段
直线是仿射集。
如果直线过原点，它才是凸集、凸锥。
（直线如果过原点，那么它是一个高维空间的低维子空间，它一定是个凸锥）

线段一定是凸集，但不是仿射集、凸锥。
只有当线段退化成一个点，才会变成一个仿射集；当这个点是原点，才会变成一个凸锥。

⑤射线
即 { x 0 + θ v ∣ θ ⩾ 0 } , v ≠ 0 \left\{x_{0}+\theta v \mid \theta \geqslant 0\right\}, v \neq 0 {x0​+θv∣θ⩾0},v=0
它是凸集，但不是仿射集。
且只有当$x_0$是原点才是凸锥。

超平面与半空间

超平面（hyperplane）
即与给定向量$a$内积为常数的点的集合：
$$\left\{x\mid a^{T}x=b\right\},a\in {\mathbf{R}}^n,a\ne 0且b\in \mathbf{R}$$
以二维空间为例：

图左有一个超平面$a^{T}x=b$，是一条直线。
这条直线(超平面)将这个二维空间分成了两部分：$\left\{x\mid a^{T}x⩾b\right\}$、$\left\{x\mid a^{T}x<b\right\}$
每个部分就是一个半空间（half space）。

---

一个超平面是一个仿射集、凸集，但不是一个凸锥。
如果这个超平面过原点，它才是一个凸锥（变成子空间了）。

半空间是一个凸集，但不是仿射集，也不是凸锥。

球和椭球

这里的球和椭球是定义在欧几里得空间中的。

球的定义：
B ( x c , r ) = { x ∣ ∥ x − x c ∥ 2 ⩽ r } = { x ∣ ( x − x c ) T ( x − x c ) ⩽ r 2 } B\left(x_{c}, r\right)=\left\{x \mid\left\|x-x_{c}\right\|_{2} \leqslant r\right\}=\left\{x \mid\left(x-x_{c}\right)^{T}\left(x-x_{c}\right) \leqslant r^{2}\right\} B(xc​,r)={x∣∥x−xc​∥2​⩽r}={x∣(x−xc​)T(x−xc​)⩽r2}
其中$x_c$是球心，$r$是半径。即到球心距离小于半径的所有点集，这个距离是用二范数定义的。

球是一个凸集。
可用凸集的定义来证明，证明集合中任意两点的凸组合在集合内。
证明（证明过程中使用了三角不等式的性质）：

---

椭球的定义：
$$\mathcal{E}=\left\{x\mid {\left(x-x_c\right)}^T{P}^{-1}\left(x-x_c\right)⩽1\right\}$$
这是椭球的一个加权二范数形式的表达，中间有一个矩阵P。
$x_c$是椭球的中心。
P是一个对称正定矩阵，即$P=P^T\succ 0$。
（注：正定矩阵：奇异值都为正的矩阵。奇异值：$\sqrt{eig(A^{T}A)}$ ）
P决定了椭球从$x_c$向各个方向扩展的幅度。
假设二维空间的情况下，P的两个奇异值即为椭球的半轴长。

举个简单的例子，P为对角二阶方阵（可直接得出奇异值）：

此外，如果设 $P=r^2{I}_n$（$I_n$为n阶单位矩阵），椭球就退化成一个球。

椭球也是一个凸集。

多面体（polyhedron）

多面体常用于线性规划。

多面体被定义为有限个线性等式和不等式的解集。
$$\mathcal{P}=\left\{x\mid a_j^{T}x⩽b_j,j=1,\cdots ,m,c_j^{T}x=d_j,j=1,\cdots ,p\right\}$$
看上面的式子，可理解为多个半空间和超平面的交集。

比如下图是由5个半空间的交集构成的多面体：

多面体是凸集。

单纯形（Simplex）

在${\mathbf{R}}^n$空间中选择 $v_0,...,v_k$ 共 $k+1$ 个点，
若$v_1-v_0,...,v_k-v_0$ 线性无关，
则与上述点相关的单纯形为：
C = conv ⁡ { v 0 , ⋯   , v k } = { θ 0 v 0 + ⋯ + θ k v k ∣ θ ⪰ 0 , 1 T θ = 1 } C=\operatorname{conv}\left\{v_{0}, \cdots, v_{k}\right\}=\left\{\theta_{0} v_{0}+\cdots+\theta_{k} v_{k} \mid \theta \succeq 0, \mathbf{1}^{T} \theta=1\right\} C=conv{v0​,⋯,vk​}={θ0​v0​+⋯+θk​vk​∣θ⪰0,1Tθ=1}
（式中 $\theta$ 代表了所有$\theta$组成的向量，用于表示都是非负的；$1$代表了k个1组成的向量，用于表示加和为1）
可见单纯形是一个基于空间中选取点集构造的凸包。

可以推出，k一般≤n维数。单纯型也称为${\mathbf{R}}^n$空间的k维单纯形。
1维单纯形是一条线段；2维单纯型是一个三角形（包含内部）；3维单纯形是一个四面体。

举个2维空间中的2维单纯形例子：
（右图，k不能取到3，因为2维空间中三个向量必定线性相关）

---

重要结论：
单纯形是多面体的一种。即单纯形可用多面体的形式表达。

这个结论在直观上比较容易想象，比如2维空间的三角形，3维空间的四面体。
下面证明一下。

证明：Simplex是Polyhedron的一种。即Simplex可以用Polyhedron的形式表达出来。

对于 C = conv ⁡ { v 0 , ⋯   , v k } = { θ 0 v 0 + ⋯ + θ k v k ∣ θ ⪰ 0 , 1 T θ = 1 } C=\operatorname{conv}\left\{v_{0}, \cdots, v_{k}\right\}=\left\{\theta_{0} v_{0}+\cdots+\theta_{k} v_{k} \mid \theta \succeq 0, \mathbf{1}^{T} \theta=1\right\} C=conv{v0​,⋯,vk​}={θ0​v0​+⋯+θk​vk​∣θ⪰0,1Tθ=1}，
我们知道$C$是${\mathbf{R}}^n$空间中的k维单纯形。
即证：对于任意$x\in C$，都可以用一组线性不等式和等式来表示。
↓
根据单纯形定义，$x\in C$可知：$x={\theta }_0{v}_0+{\theta }_1{v}_1+\cdots +{\theta }_k{v}_k$，$\theta ⪰0,1^T\theta =1$
∵ $1^T\theta =1$
∴ $x$右边构造成：
$x=(1-{\theta }_1-...-{\theta }_k)v_0+{\theta }_1{v}_1+\cdots +{\theta }_k{v}_k$
$=v_0+{\theta }_1(v_1-v_0)+...+{\theta }_k(v_k-v_0)$
我们定义 $y=\left({\theta }_1,\cdots ,{\theta }_k\right)$，$B=\left[\begin{array}{lll}{v}_1-v_0& \cdots & v_k-v_0\end{array}\right]\in {\mathbf{R}}^{n\times k}$
∴ 可得式子：$x=v_0+By$
∵ $v_1-v_0,...,v_k-v_0$ 线性无关
∴ $rank(B)=k$（即矩阵B的秩为k，为一个n行k列的列满秩矩阵）
对于一个列满秩矩阵，我们可以通过初等行变换，变换成这样一个矩阵：
$\left[\begin{array}{l}{I}^{k\times k}\\ 0^{(n-k)\times k}\end{array}\right]$
∴ 一定存在这样一个变换矩阵，我们设变换矩阵为$A^{n\times n}$（一个可逆的方阵），A可以分成上下两个分块$A_1,A_2$，即：
$AB=\left[\begin{array}{l}{A}_1^{k\times n}\\ A_2^{(n-k)\times n}\end{array}\right]B=\left[\begin{array}{l}I\\ 0\end{array}\right]$
那么我们把式子$x=v_0+By$左乘$A$：
$Ax=A{v}_0+ABy$
把$A$拆分为上下分块$A_1,A_2$后，分开来写，得到：
$A_{1}x=A_1{v}_0+y,A_{2}x=A_2{v}_0$ 这两个式子
∵ $y$是我们设的一个变量$\left({\theta }_1,\cdots ,{\theta }_k\right)$，由于里面没有${\theta }_0$
∴ 可得到 $y⪰0$，$1^{T}y⩽1$ 这两个不等式条件
因此，代入上面两个式子中第一个式子；再加上第二个式子，可得：
①$A_{1}x⪰A_1{v}_0$
②$1^T{A}_{1}x⩽1+1^T{A}_1{v}_0$
③$A_{2}x=A_2{v}_0$
这三个式子是$x$的线性等式和不等式，故其描述了一个多面体，得证。

对称矩阵集合

来看下面三个对称$n\times n$矩阵的集合：

对称矩阵集合：
${\mathbf{S}}^n=\left\{X\in {\mathbf{R}}^{n\times n}\mid X=X^T\right\}$

对称半正定矩阵的集合：
S + n = { X ∈ S n ∣ X ⪰ 0 } \mathbf{S}_{+}^{n}=\left\{X \in \mathbf{S}^{n} \mid X \succeq 0\right\} S+n​={X∈Sn∣X⪰0}
（符号 $⪰$ 的意思是矩阵所有特征值都大于等于0）

对称正定矩阵的集合：
S + + n = { X ∈ S n ∣ X ≻ 0 } \mathbf{S}_{++}^{n}=\left\{X \in \mathbf{S}^{n} \mid X \succ 0\right\} S++n​={X∈Sn∣X≻0}

这三个矩阵是否是凸集呢？矩阵是难以进行空间想象的。
我们先研究对称半正定矩阵集合 ${\mathbf{S}}_{+}^n$。

---

结论：对称半正定矩阵集合 ${\mathbf{S}}_{+}^n$是一个凸锥。
证明：

取任意系数${\theta }_1,{\theta }_2⩾0$，并取任意矩阵$A,B\in {\mathbf{S}}_{+}^n$，即证：
${\theta }_{1}A+{\theta }_{2}B\in {\mathbf{S}}_{+}^n$
根据半正定矩阵的定义，我们有：
$x^{T}Ax⩾0$，$x^{T}Bx⩾0$
那么$x^T\left({\theta }_{1}A+{\theta }_{2}B\right)x={\theta }_1{x}^{T}Ax+{\theta }_2{x}^{T}Bx⩾0$
证得 ${\theta }_{1}A+{\theta }_{2}B$ 是半正定矩阵。
又因为同形对称矩阵的数乘和加和不改变对称性，
所以矩阵 ${\theta }_{1}A+{\theta }_{2}B$ 是一个对称半正定矩阵，得证。

所以，
对称半正定矩阵集合 ${\mathbf{S}}_{+}^n$是一个凸锥。
对称矩阵集合 ${\mathbf{S}}^n$也是一个凸锥。（同形对称矩阵的数乘和加和不改变对称性）

然而，
对称正定矩阵集合${\mathbf{S}}_{++}^n$ 只是一个凸集，不是凸锥。
（可回到上面的证明，由于${\theta }_1,{\theta }_2$可取到0，因此根据正定矩阵定义，${\theta }_{1}A+{\theta }_{2}B$没办法证明大于0）

教材中举了2维空间中的半正定矩阵集合：