凸集

仿射集合和凸集

主要内容：

• 直线和线段
• 仿射集
• 凸集
• 凸锥

直线和线段

定义1（直线和线段）
对于$R^n$空间中不同的两点$\forall x_1\ne x_2$，令
$$y=\theta x_1+(1-\theta )x_2=x_2+\theta (x_1-x_2),$$
当$\theta \in R$时，具有上述形式的点，即构成了穿过$x_1,x_2$的直线。

当$\theta \in [0,1]$时，具有上述形式的点，即构成了以$x_1,x_2$为端点的线段。

从第二个等式来看，上述形式的点以$x_2$为起点，$x_1-x_2$为方向，$\theta$衡量了点在方向$x_1-x_2$上距离起点$x_2$的距离。

---

仿射集

定义2（仿射集）
通过集合$C\subseteq R^n$中任意两点的直线仍旧在集合$C$中，称集合$C$是仿射的。

等价于，$\forall x_1,x_2\in C$，$\theta x_1+(1-\theta )x_2\in C,\theta \in R$

注
仿射的拉丁语意为相关，即$\sum X_i\in C$

例1
一条直线也是仿射集，因此直线上任意两点构成的直线仍在原先的直线上。

---

定义3（仿射组合）
扩展至多点，当${\theta }_1+...+{\theta }_n=1$，称具有形式${\theta }_1{x}_1+...+{\theta }_n{x}_n$的点为$x_1,...,x_n$的仿射组合。

例2
一类特殊的仿射集：

对于线1，当$x_1,x_2\in C$时，由于仿射集要求组合点的系数之和为1，显然$x_1+x_2=x^{\ast }\notin C$，从图像上即组合后的点$x^{\ast }$不落在线1上；但对于线2，当$x_1,x_2\in C$时，$x_1+x_2=0\in C$，即此时C是仿射集，但此时$x_1$和$x_2$的系数之和并非1。

---

定义4（仿射包）
包含C的最小仿射集（集合C中的点的所有仿射组合构成的集合）：
affC={θ1x1+...+θnxn∣xi∈C,i=1,...,n,θ1+...+θn=1}\text{aff}C=\{\theta_1x_1+...+\theta_nx_n|x_i\in C,i=1,...,n,\theta_1+...+\theta_n=1\}affC={θ1​x1​+...+θn​xn​∣xi​∈C,i=1,...,n,θ1​+...+θn​=1}

例3
线性方程组的解集（超平面上的点）：

线性方程组的解集：C={x∣Ax=b}C=\{x|Ax=b\}C={x∣Ax=b}，$A\in R^{m\times n}$，$b\in R^m$，直接可从仿射集的定义可判断。

假设$x_1,x_2\in C$，$\forall \theta$，有：
$$A(\theta x_1+(1-\theta )x_2)=\theta b+(1-\theta )b=b$$
因此C中任意点的仿射组合仍在C中，C是仿射集。

换个角度，对比例1，一条线是仿射集，很容易得出超平面也是仿射集。

---

凸集

定义5（凸集）
通过集合$C\subseteq R^n$中任意两点的线段仍旧在集合$C$中，称集合$C$是凸集。

等价于，$\forall x_1,x_2\in C$，$\theta x_1+(1-\theta )x_2\in C,\theta \in [0,1]$

注
将仿射集合中的$\theta \in R$限制在$\theta \in [0,1]$即成了凸集。换个角度该定义意为，从点$x_2$看向点$x_1$，中间无任何阻碍，都能看见。

例4
一个集合$C$是仿射集，必然也是凸集。因为对仿射集$C$而言，任意两点连线的直线属于$C$，那么任意两点连线的线段必然属于$C$，满足凸集的定义。

例5
下图是$R^2$空间中一些常见的凸集和非凸集的例子：

左一内部点全能连通，因此是凸集；中间的图，两点间连线有一部分点不在集合内，不是凸集；右一，边界有一部分缺失，当连接缺失两边点，其构成的线段不在集合内，因此不是凸集。

---

定义6（凸组合）
当${\theta }_1+...+{\theta }_n=1,{\theta }_i\ge 0$，称具有形式${\theta }_1{x}_1+...+{\theta }_n{x}_n$的点为$x_1,...,x_n$的凸组合。

定义7（凸包）
包含C的最小凸集：
convC={θ1x1+...+θnxn∣xi∈C,θi≥0,i=1,...,n,θ1+...+θn=1}convC=\{\theta_1x_1+...+\theta_nx_n|x_i\in C,\theta_i\ge0,i=1,...,n,\theta_1+...+\theta_n=1\}convC={θ1​x1​+...+θn​xn​∣xi​∈C,θi​≥0,i=1,...,n,θ1​+...+θn​=1}

例6
按定义，很容易验证，空集$\varphi$，单点集{x}\{x\}{x}，空间$R^n$是仿射集，自然也都是凸集。

---

例7
半空间{x∣aTx≤b}\{x|a^Tx\le b\}{x∣aTx≤b}是凸集，但非仿射集，如下$R^2$上的半空间：

半空间（阴影区域）任意两点线段的连线仍在半空间内。

例8
半空间的另一种表述形式：假设$R^n$空间中有两个不同的点$a,b$，则所有距离$a$比$b$近的点构成的集合（2范数）：
{x∣ ∣∣x−a∣∣2≤∣∣x−b∣∣2}={x∣xTx−2aTx+aTa≤xTx−2bTx+bTb}={x∣2(b−a)Tx≤bTb−aTa}\{x|\ ||x-a||_2\le ||x-b||_2\}=\{x|x^Tx-2a^Tx+a^Ta\le x^Tx-2b^Tx+b^Tb\}=\{x|2(b-a)^Tx\le b^Tb-a^Ta\}{x∣ ∣∣x−a∣∣2​≤∣∣x−b∣∣2​}={x∣xTx−2aTx+aTa≤xTx−2bTx+bTb}={x∣2(b−a)Tx≤bTb−aTa}

例9
多面体，有限个线性不等式和等式的解集：
C={x∣ajTx≤bj,j=1,...,m,cjTx=dj,j=1,...,p}C=\{x|a_j^Tx\le b_j,j=1,...,m,c_j^Tx= d_j,j=1,...,p\}C={x∣ajT​x≤bj​,j=1,...,m,cjT​x=dj​,j=1,...,p}
可见多面体是有限个半空间和超平面的交集，因此半空间也是多面体，自然多面体也是凸集。

例10
Euclid球和椭球，$R^n$空间中的Euclid球有如下形式：
B(x0,r)={x∣ ∣∣x−x0∣∣2≤r}={x0+ru∣ ∣∣u∣∣2≤1}B(x_0,r)=\{x|\ ||x-x_0||_2\le r\}=\{x_0+ru|\ ||u||_2\le1\}B(x0​,r)={x∣ ∣∣x−x0​∣∣2​≤r}={x0​+ru∣ ∣∣u∣∣2​≤1}
即以$x_0$为圆心，$r$为半径的球。根据定义，假设$||x_1-x_0|{|}_2\le r,||x_2-x_0|{|}_2\le r$。

$$||\theta x_1+(1-\theta )x_2-x_0|{|}_2=||\theta (x_1-x_0)-(1-\theta )(x_2-x_0)|{|}_2\le ||\theta (x_1-x_0)|{|}_2+||\theta (x_2-x_0)|{|}_2\le r$$
凸组合的点仍旧在$B(x_0,r)$内，因此为凸集。（$R^2$中为圆，$R^3$中为球，其内点的连线仍在其中，自然满足凸集的要求。）

椭球也是凸集，ε={x∣(x−x0)TP−1(x−x0)≤1}={x0+Au∣ ∣∣u∣∣2≤1}\varepsilon=\{x|(x-x_0)^TP^{-1}(x-x_0)\le 1\}=\{x_0+Au|\ ||u||_2\le1\}ε={x∣(x−x0​)TP−1(x−x0​)≤1}={x0​+Au∣ ∣∣u∣∣2​≤1}，其中$P$是对称正定矩阵。

---

锥

定义8（凸锥）
$\forall x_1,x_2\in C$，${\theta }_1{x}_1+{\theta }_2{x}_2\in C,{\theta }_1,{\theta }_2\ge 0$

注
既然${\theta }_1,{\theta }_2$都可取到0，那么0点必然属于集合$C$

下图即是凸锥，根据向量加法的平行四边形法则，${\theta }_1{x}_1+{\theta }_2{x}_2$即红箭头交点处，改变${\theta }_1,{\theta }_2$的取值，红箭头交点可取遍锥内所有的点。

---

定义9（锥组合）
当${\theta }_i\ge 0,i=1,...,n$，称具有形式${\theta }_1{x}_1+...+{\theta }_n{x}_n$的点为$x_1,...,x_n$的锥组合。

定义10（锥包）
包含C的最小凸锥：
{θ1x1+...+θnxn∣xi∈C,θi≥0,i=1,...,n}\{\theta_1x_1+...+\theta_nx_n|x_i\in C,\theta_i\ge0,i=1,...,n\}{θ1​x1​+...+θn​xn​∣xi​∈C,θi​≥0,i=1,...,n}

例11
过原点的直线是凸锥。

例12
任意子空间是仿射的、凸锥。

例13
半正定锥，

用$S^n$表示n维对称矩阵，Sn={X∈Rn×n∣X=XT}S^n=\{X\in R^{n\times n}|X=X^T\}Sn={X∈Rn×n∣X=XT}，

用$S_{+}^n$表示n维半正定对称矩阵，S+n={X∈Sn∣X⪰0}S^n_+=\{X\in S^n|X\succeq0\}S+n​={X∈Sn∣X⪰0}，其是凸锥，首先过原点，再者，若${\theta }_1,{\theta }_2\ge 0$，$A,B$是半正定对称矩阵，
$$x^T({\theta }_{1}A+{\theta }_{2}B)x={\theta }_1{x}^{T}Ax+{\theta }_2{x}^{T}Bx\ge 0$$
满足凸锥的定义。

用$S_{++}^n$表示n维正定对称矩阵，S++n={X∈Sn∣X≻0}S^n_{++}=\{X\in S^n|X\succ0\}S++n​={X∈Sn∣X≻0}，当n=1，$S_{++}^n=R_{++}$，此时点集不过原点，不是凸锥，但其是实数轴上的半空间，因此是凸集。