凸集

作者: 微斯人_吾谁与归 | 来源:发表于2019-05-15 16:58 被阅读15次

凸集

一.仿射集合与凸集

1.仿射集合（affine set）

过两个点的直线方程： $y=\theta x_{1}+(1-\theta) x_{2}, \theta \in \mathbf{R}$ ， $x_{1} \neq x_{2}$ 且为n维空间的两个点。可以更改写为 $y=x_{2}+\theta\left(x_{1}-x_{2}\right)$

快照45.png

仿射集：一个集合C是仿射集，若对任意的 $x_{1}, x_{2} \in C 且 \theta \in \mathbf{R}$ ，则连接 $x_1,x_2$ 的直线也在这个集合内。如直线是一个仿射集，线段不是仿射集，二维空间是一个仿射集，二维空间中一个正方形不是仿射集。
仿射组合：如果 $\theta_{1}+\cdots+\theta_{k}=1$ ，我们称 $\theta_{1} x_{1}+...+\theta_{k} x_{k}$ 为 $x_{1}, \cdots, x_{k}$ 的仿射组合
仿射组合与仿射集合的关系：一个仿射集合中包含其中任意多个点的仿射组合。即C是一个仿射集合，那么对 $x_{1}, \cdots, x_{k} \in C$ ，且 $\theta_{1}+\cdots+\theta_{k}=1$ ，那么 $\theta_{1} x_{1}+...+\theta_{k} x_{k}$ 任然在C中。
- 证明：不妨设C是一个仿射集， $x_1,x_2,x_3$ 是集合C中任意三点， $，，\theta_{1}，\theta_{2}，\theta_{3} \in R$ ,且 $\theta_{1} +\theta_{2} +\theta_{3}=1$ ，
  
  下证 $\theta_{1} x_{1}+\theta_{2} x_{2}+\theta_{3} x_{3} \in C$
  
  由仿射集的定义可知 $\frac{\theta_{1}}{\theta_{1}+\theta_{2}}x_1+\frac{\theta_{2}}{\theta_{1}+\theta_{2}}x_2 \in C$
  
  所以 $(\theta_{1}+\theta_{12})( \frac{\theta_{1}}{\theta_{1}+\theta_{2}}x_1+\frac{\theta_{2}}{\theta_{1}+\theta_{2}}x_2 )+(1-\theta_{1}-\theta_{2})x_3 \in C$
  
  所以 $\theta_{1} x_{1}+\theta_{2} x_{2}+\theta_{3} x_{3} \in C$
  
  得证
仿射集的子空间：
- 定义：如果C是一个仿射集， $x_{0} \in C$ ，则集合 $V=C-x_{0}=\left\{x-x_{0} | x \in C\right\}$ 称为仿射集C的子空间
- 与C相关的子空间的性质：关于加法与数乘封闭， $v_{1}, v_{2} \in V, \alpha, \beta \in \mathbf{R}$ ， $v_{1}+ v_{2} \in V$ ， $\alpha v_{1}+\beta v_{2} \in V$
  - 证明：因为 $v_{1}, v_{2} \in V$
    
    所以 $v_{1}+x_{0} \in C, v_{2}+x_{0} \in C$
    
    因为C是仿射的，由仿射集合与仿射组合的关系可知 $\alpha v_{1}+\beta v_{2}+x_{0}=\alpha\left(v_{1}+x_{0}\right)+\beta\left(v_{2}+x_{0}\right)+(1-\alpha-\beta) x_{0} \in C$ ，
    
    所以 $\alpha v_{1}+\beta v_{2}+x_{0} \in C$
    
    所以 $\alpha v_{1}+\beta v_{2} \in V$
- 仿射集合可以表示为 $C=V+x_{0}=\left\{v+x_{0} | v \in V\right\}$ ，即子空间加上一个偏移。仿射空间的子空间与偏移向量 $x_0$ 的选择无关，所以 $x_0$ 可以是C中任意一点。仿射空间C的维数为子空间V的维数。
- 例题：快照46.png

对于任意集合C(可能是仿射集可能不是)构造尽可能小的仿射集：
- 仿射包：我们记集合C中的点的所有仿射组合组成的集合C为仿射包。仿射包是包含C最小的仿射集合。
  $\ \operatorname{aff} C=\left\{\theta_{1} x_{1}+\cdots+\theta_{k} x_{k} | x_{1}, \cdots, x_{k} \in C, \theta_{1}+\cdots+\theta_{k}=1\right\} \$
  例如：快照47.png

当C集合只有X1,X2两点时，C的仿射包是过X1,X2的直线，当C有 X1,X2,X3三个点时，C的仿射包是整个平面。

仿射维数与相对内部：
- 集合C的维数：我们定义集合C的仿射维数为其仿射包的维数。
- 相对内部：如果集合 $C \subseteq \mathbf{R}^{n}$ ,它的仿射维数小于n,那么这个集合在仿射集合aff $C \neq \mathbf{R}^{n}$ ，我们定义集合C的相对内部为 $\operatorname{aff} C$ 的内部，记为 $relintC$ ,即relint $C=\{x \in C | B(x, r) \cap$ aff $对某些C \subseteq C对某些r>0$
  
  其中 $B(x, r)=\{y |\|y-x\| \leqslant r\}$ ，||.||可以是任范数。

2.凸集

定义:一个集合C是凸集，当任意两点之间的线段上的点任然在C内，
- 等价于：对于集合内任意两点 $x_{1}, x_{2} \in C$ ，和满足0 $\leqslant \theta \leqslant 1$ ，都有 $\theta x_{1}+(1-\theta) x_{2} \in C$ 。所以仿射集都是凸集。
- 等价于：C内任意元素的凸组合都在C内
凸组合： $x_{1}, \cdots, x_{k}$ 的凸组合为 $\theta_{1} x_{1}+\cdots+\theta_{k} x_{k}$ ，其中 $\theta_{1}+\cdots+\theta_{k}=1$ ， $\theta_{i} \geqslant 0, i=1, \cdots, k$ ，。
凸集与凸组合的关系：一个集合是一个凸集等价于集合包含其中所有点的凸组合。
下面是一些简单的凸集与非凸集的例子：快照48.png
凸包：我们称集合C中包含所有点的凸组合的集合称为其凸包。即为convC:

$\operatorname{conv} C=\left\{\theta_{1} x_{1}+\cdots+\theta_{k} x_{k} | x_{i} \in C, \theta_{i} \geqslant 0, i=1, \cdots, k, \theta_{1}+\cdots+\theta_{k}=1\right\}$ .凸包总是凸的，它是包含C的最小凸集。

快照49.png

凸组合的概念可以扩展到无穷级数、积分以及大多数形式的概论分布。假设 $\theta_{1}, \theta_{2}, \cdots$ 满足， $\theta_{i} \geqslant 0, \quad i=1,2, \cdots, \quad \sum_{i=1}^{\infty} \theta_{i}=1$ ，并且 $x_{1}, x_{2}, \cdots \in C$ ，其中 $C \subseteq \mathbf{R}^{n}$ 为凸集，那么如果下列级数收敛，我们有 $\sum_{i=1}^{\infty} \theta_{i} x_{i} \in C$ 。
更一般的， $p : \mathbf{R}^{n} \rightarrow \mathbf{R}$ ，对所有 $x \in C$ 满足 $p(x) \geqslant 0$ 且 $\int_{C} p(x) d x=1$ ，其中C是凸集，那么如果下列积分存在，我们有 $\int_{C} p(x) x d x \in C$ 。
最一般的是， $C \subseteq \mathbf{R}^{n}$ 是凸集，x是随机变量。并且 $x \in C$ 的概率是1，那么E(x) $\in C$ .

3.锥（cone）

锥（非负齐次）：如果对于任意的 $x \in C$ 和 $\theta \geqslant 0$ 都有 $\theta x \in C$ ，我们称集合C是锥或者非负齐次。
凸锥(Convex Cone)：如果集合C是锥，并且是凸的，称C为凸锥。等价于，对任意的 $x_{1}, x_{2} \in C$ 和 $\theta_{1}, \theta_{2} \geqslant 0$ 都有 $\theta_{1} x_{1}+\theta_{2} x_{2} \in C$ 。（可以理解为 $\theta_{1} x_{1}+\theta_{2} x_{2}$ 为以 $\theta_1x_1$ 和 $\theta_2x_2$ 为边长组成的平行四边形的对角线，所以一定在直线0- $x_1$ 和 $0-x_2$ 中间）

快照50.png
锥组合（非负线性组合）：具有 $\theta_{1} x_{1}+\cdots+\theta_{k} x_{k}, \theta_{1}, \cdots, \theta_{k} \geqslant 0$ 形式的点称为点 $x_{1}, \cdots, x_{k}$ 的锥组合（或非负线性组合）
锥包：集合C的锥包是C中元素的所有锥组合的集合，即 $\left\{\theta_{1} x_{1}+\cdots+\theta_{k} x_{k} | x_{i} \in C, \theta_{i} \geqslant 0, i=1, \cdots, k\right\}$ 。
- 它是包含C的最小凸锥。
  
  快照51.png

4.仿射集合、凸集、凸锥的类比

仿射组合： $\theta_{1}+\cdots+\theta_{k}=1$
凸组合： $\theta_{1}+\cdots+\theta_{k}=1$ ， $\theta_{i} \geqslant 0, i=1, \cdots, k$ ，。
锥组合： $\theta_{1}, \cdots, \theta_{k} \geqslant 0$
- 当只有一个集合C只有一个元素时{x},那么这个集合是一个仿射集，也是一个凸组合，如果x为原点则是一个锥组合，否则不是锥组合。
- 当C是空集时，它既是仿射集，又是凸集，又是凸锥。
- $\mathbf{R}^{n}$ 空间既是仿射集又是凸集又是凸锥。
- 任意直线 一定是一个仿射集，也是凸集，不一定是凸锥，只有经过原点时才是凸锥。
- 任意线段不是仿射集，除非这个线段只有一个点。是一个凸集。不是凸锥（除非只有一个点且这个点是原点）
- 射线 $x_0+\theta V|\theta>=0,x_0 \in R^n,\theta \in R,v \in R^n$ ,不是一个仿射集，是一个凸集，当 $x_0=0$ 时是凸锥。

二.重要的例子

1.超平面与半空间

超平面：，其中
- a是超平面的法向量，取 $x_0$ 为超平面任意一点，那么超平面可以表示为 $\left\{x | a^{T}\left(x-x_{0}\right)=0\right\}$
半空间：一个超平面将划分为两个半空间。。
- 办空间是凸的，但是不是仿射的，当 $a^{T} x \leqslant 0$ 时半空间是凸锥。
  快照25.png

2.Euclid球和椭球

球:在 $R^n$ 的空间中Euclid球（或简称为球）具有下面的形式， $B\left(x_{c}, r\right)=\left\{x |\left\|x-x_{c}\right\|_{2} \leqslant r\right\}=\left\{x |\left(x-x_{c}\right)^{T}\left(x-x_{c}\right) \leqslant r^{2}\right\}$
- 球是不是仿射集，是凸集。
  - 证明：球是一个凸集
    
    如果球是一个凸集， $\left\|x_{1}-x_{c}\right\|_{2} \leqslant r,\left\|x_{2}-x_{c}\right\|_{2} \leqslant r$ ，并且0 $\leqslant \theta \leqslant 1$ ，那么
    
    $\left\|\theta x_{1}+(1-\theta) x_{2}-x_{c}\right\|_{2}=\left\|\theta\left(x_{1}-x_{c}\right)+(1-\theta)\left(x_{2}-x_{c}\right)\right\|_{2}$
    
    $\leqslant \theta\left\|x_{1}-x_{c}\right\|_{2}+(1-\theta)\left\|x_{2}-x_{c}\right\|_{2}$ （二范数的三角不等式）
    
    $\leqslant r$
    
    得证
- 球的另一个表示法： $B\left(x_{c}, r\right)=\left\{x_{c}+r u |\|u\|_{2} \leqslant 1\right\}$
椭球：椭球是一个凸集，它具有如下的形式 $\mathcal{E}=\left\{x |\left(x-x_{c}\right)^{T} P^{-1}\left(x-x_{c}\right) \leqslant 1\right\}$ 。
- $P=P^T$ ,且P的特征值大于零，即P是对称正定矩阵
- $x_c$ 决定了椭球的球心，矩阵P决定了椭球从 $x^c$ 的方向的扩展幅度。 $\mathcal{E}$ 的半长轴是由 $\sqrt{\lambda_{i}}$ 给出，这里 $\lambda_{i}$ 为P的特征值。
- 椭球的另一个表示形式 $\mathcal{E}=\left\{x_{c}+A u |\|u\|_{2} \leqslant 1\right\}$ ，A是非奇异方正，A= $p^{1/2}$ ,当A是对称半正定矩阵但是奇异时，称为退化的椭球，其仿射维数等于A的秩。
- 球是一个特殊的椭圆，P= $r^2I$ ,r是奇异值，I是单位矩阵
- 例如： $\varepsilon=\left\{x | x^{T} \left( \begin{array}{ll}{4} & {0} \\ {0} & {1}\end{array}\right)^{-1} x \leq 1\right\}$ 即 $\varepsilon=\left\{\left(x, x_{0}\right) | \frac{1}{4} x_{1}^{2}+x_{2}^{2}=1\right\}$ 。可以看出矩阵P决定扩展幅度。

3.范数球和范数锥

4.多面体

多面体：多面体被定义为有限个数等式和不等式的解集，。多面体是有限个半空间和超平面的交集。
- 一些仿射集合（如子空间、超平面、直线）、射线、线段、都是多面体
- 多面体是凸集，多面体可以无界。

5.单纯形

单纯型：设k+1个点仿射独立，即线性独立，那么这些点决定了一个单纯形，称为空间的k维单纯形。
- 单纯形是凸包
- 常见的单纯形，1维单纯形是一条直线，2维单纯形是一个三角形，三维单纯型是一个四面体。n维空间至多有n维单纯形。
- 概率单纯形:- 由单位向量 $e_{1}, \cdots, e_{n} \in \mathbf{R}^{n}$ 决定的n-1维单纯型，它可以表示为如下形式的集合 $x \succeq 0, \quad \mathbf{1}^{T} x=1$
- 单位单纯形:- 由零向量和单位向量 $0,e_1,e_2,...e_n \in R^n$ 决定的n维单纯型，它可以表示如下形式的集合 $x \succeq 0, \quad \mathbf{1}^{T} x \leqslant 1$
- 单纯型是一个多面体
  - 快照52.png

6.半正定锥

对称矩阵集合： $\mathbf{S}^{n}=\left\{X \in \mathbf{R}^{n \times n} | X=X^{T}\right\}$ 。
半正定矩阵集合： $\mathbf{S}_{+}^{n}=\left\{X \in \mathbf{S}^{n} | X \succeq 0\right\}$ 。
正定矩阵集合： $\mathbf{S}_{++}^{n}=\left\{X \in \mathbf{S}^{n} | X>0\right\}$ 。

$S_n$ $S_{n+}$ $S_{n++}$

凸集是是是

凸锥是是否
例题： $S^2$ 上的半正定锥。我们有 $X=\left[ \begin{array}{ll}{x} & {y} \\ {y} & {z}\end{array}\right] \in \mathbf{S}_{+}^{2} \quad \Longleftrightarrow \quad x \geqslant 0, \quad z \geqslant 0, \quad x z \geqslant y^{2}$ ，可以将按照x,y,z表示在 $R^3$ 中。
快照54.png

	$S_n$	$S_{n+}$	$S_{n++}$
凸集	是	是	是
凸锥	是	是	否

三.保凸运算

保凸运算是指经过此类运算的得到的集合任然是凸集，因此我们可以用这些运算来确定或是构建集合的凸性。

1.交集

如果 $S_1$ 和 $S_2$ 是凸集，那么 $S_{1} \cap S_{2}$ 也是凸集。例如，多面体是半空间与超平面的交集，所以多面体是凸集。
可以扩展到无穷个集合的交，即如果对任意的 $\alpha \in \mathcal{A}$ ， $S_{\alpha}$ 都是凸的，那么 $\bigcap_{\alpha \in \mathcal{A}} S_{\alpha}$ 也是凸的。

2.仿射函数

函数 $f : \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$ 是仿射的，如果它是一个一个线性函数和一个常数的和，即具有 $f(x)=A x+b$ 的形式，其中 $A \in \mathbf{R}^{m \times n}, b \in \mathbf{R}^{m}$ 。
假设 $S \subseteq \mathbf{R}^{n}$ 是凸的，并且 $f : \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$ 是仿射函数，那么S在f下的象 $f(S)=\{f(x) | x \in S\}$ 也是凸的。

类似的， $f : \mathbf{R}^{k} \rightarrow \mathbf{R}^{n}$ 是仿射函数，那么S在f下的原象 $f^{-1}(S)=\{x | f(x) \in S\}$ 是凸的。
- 平移： $S+a=\{x+a | x \in S\}$
- 伸缩： $\alpha S=\{\alpha x | x \in S\}$

3.投影

$对于某些T=\left\{x_{1} \in \mathbf{R}^{m} |\left(x_{1}, x_{2}\right) \in S\right.对于某些x_2 \in R^n$ , $S \subseteq \mathbf{R}^{m} \times \mathbf{R}^{n}$ .若S是凸集，那么T也是凸集

4.两个集合的和

$S_{1}+S_{2}=\left\{x+y | x \in S_{1}, y \in S_{2}\right\}$ ，如果 $S_1,S_2$ 是凸集那么 $S_1+S_2$ 也是凸的。

5.两个集合的直积（Cartesian乘积）

$S_{1} \times S_{2}=\left\{\left(x_{1}, x_{2}\right) | x_{1} \in S_{1}, x_{2} \in S_{2}\right\}$

6.部分和

$S=\left\{\left(x, y_{1}+y_{2}\right) |\left(x, y_{1}\right) \in S_{1},\left(x, y_{2}\right) \in S_{2}\right\}$
多面体
线性矩阵不等式的解
双曲锥
椭球
快照55.png

7.线性分式及透视函数

透视函数
- 定义：P: $P : \mathbf{R}^{n+1} \rightarrow \mathbf{R}^{n}, P(z, t)=z / t$ 为透视函数，其定义域为 $\operatorname{dom} P=\mathbf{R}^{n} \times \mathbf{R}_{++}$ ，（ $R_{++}$ 表示正实数集合）。透视函数对向量进行伸缩，或者进行规范化，使最后一维分量为1并舍弃之。
- 快照56.png

如果 $C \subseteq \operatorname{dom} P$ ，如果C是凸集，那么C的象P(C)也是凸集。例如线段经过小孔成象后还是线段。
- 证明：假设 $x=\left(\tilde{x}, x_{n+1}\right), y=\left(\tilde{y}, y_{n+1}\right) \in \mathbf{R}^{n+1}$ 并且 $x_{n+1}>0, y_{n+1}>0$ 。
  
  那么对于0 $\leqslant \theta \leqslant 1$
  
  $P(\theta x+(1-\theta) y)=\frac{\theta \tilde{x}+(1-\theta) \tilde{y}}{\theta x_{n+1}+(1-\theta) y_{n+1}}$
  
  $=\frac{\theta \tilde{x}}{\theta x_{n+1}+(1-\theta) y_{n+1}}+\frac{(1-\theta )\tilde{y}}{\theta x_{n+1}+(1-\theta) y_{n+1}}$
  
  $=\frac{\theta x_{n+1}}{\theta x_{n+1}+(1-\theta) y_{n+1}}P(x)+\frac{(1-\theta )y_{n+1}}{\theta x_{n+1}+(1-\theta) y_{n+1}}P(y)$
  
  $=\mu P(x)+(1-\mu) P(y)$
  
  其中 $\mu=\frac{\theta x_{n+1}}{\theta x_{n+1}+(1-\theta) y_{n+1}} \in[0,1]$
  
  因为 $与\mu与\theta$ 之间是单调的，当 $\theta$ 在[0,1]之间变化时， $\mu$ 也在[0,1]之间变化，所以线段形成线段 $P([x, y])=[P(x), P(y)]$ 。
透视函数的反函数
- 定义：一个凸集在透视函数下的原象也是凸集。如果 $C \subseteq \mathbf{R}^{n}$ 是凸集，那么 $P^{-1}(C)=\left\{(x, t) \in \mathbf{R}^{n+1} | x / t \in C, t>0\right\}$ 也是凸集。
- 证明：为证明上述，假设 $(x, t) \in P^{-1}(C),(y, s) \in P^{-1}(C), 0 \leqslant \theta \leqslant 1$
  
  证明一个凸集在透视函数下的原象也是凸集即证明 $\theta(x, t)+(1-\theta)(y, s) \in P^{-1}(C)$
  
  即证明 $\frac{\theta x+(1-\theta) y}{\theta t+(1-\theta) s} \in C$
  
  （显然， $\theta t+(1-\theta) s>0$ ）。这可从下式看出 $\frac{\theta x+(1-\theta) y}{\theta t+(1-\theta) s}=\mu(x / t)+(1-\mu)(y / s)$
  
  其中 $\mu=\frac{\theta t}{\theta t+(1-\theta) s} \in[0,1]$ 。
  
  得证。
线性分式函数
- 定义：线性分式函数是由透视函数和仿射函数复合而成的。设 $g : \mathbf{R}^{n} \rightarrow \mathbf{R}^{m+1}$ 是仿射的，即 $g(x)=\left[ \begin{array}{c}{A} \\ {c^{T}}\end{array}\right] x+\left[ \begin{array}{l}{b} \\ {d}\end{array}\right]$ 其中 $A \in \mathbf{R}^{m \times n}, b \in \mathbf{R}^{m}, c \in \mathbf{R}^{n}$ 并且 $d \in \mathbf{R}$ 。则由 $f=P \circ g$ 给出的仿射函数 $f : \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$ ， $f(x)=(A x+b) /\left(c^{T} x+d\right), \quad \operatorname{dom} f=\left\{x | c^{T} x+d>0\right\}$ 。称为线性分式（或投射）函数。仿射函数与线性线性函数都是特殊的线性分式函数。
- 投射解释：可以将线性分式函数方便的写成矩阵 $Q=\left[ \begin{array}{cc}{A} & {b} \\ {c^{T}} & {d}\end{array}\right] \in \mathbf{R}^{(m+1) \times(n+1)}$
  
  左乘点（x,1）得到 $\left(A x+b, c^{T} x+d\right)$ ，然后将所得结果伸缩变换或归一化，使其最后一个分量为1，得到（f(x),1）。
- 集合解释：这个表达式将 $和R^n 和R^{n+1}$ 空间上的一组投射联系了起来。也就是说，对于空间 $R^n$ 空间上的一个点 $z$ ，我们可以构造一个 $R^{n+1}$ 空间的（开）射线 $\mathcal{P}(z)=\{t(z, 1) | t>0\}$ 。这条射线的每个点的最后一个分量均是正值。反之， $R^{n+1}$ 空间中每条以原点为顶点并且最后一个分量为正值的射线均可以由一些 $v \in \mathbf{R}^{n}$ 表示为 $\mathcal{P}(v)=\{t(v, 1) | t \geqslant 0\}$ 。P表示 $R^n$ 与最后一个分量为正的射线之间的投射干洗。这种关系是一一对应和满的
- 线性分式函数可以表示为 $f(x)=\mathcal{P}^{-1}(Q \mathcal{P}(x))$
- 线性分式函数也是保凸的