仿射集合和凸集

直线与线段

x1x2Rn 空间中的两个点,那么

y=θx1+(1θ)x2,θR

组成一条穿越 x1x2直线

y=θx1+(1θ)x2,θ[0,1]

构成了 x1x2 之间的(闭)线段

还有如下一种表示形式,它类似于直线的参数方程:

y=x2+θ(x1x2)

仿射集合

如果通过集合 CRn 中任意两个不同点的直线仍然在集合 C 中,那么称集合 C仿射的,即

x1,x2C,θx1+(1θ)x2C(θR)

这个概念可以推广至多个点的情况:如果 θ1++θk=1,那么称 θ1x1++θkxkx1,,xk仿射组合。如果一个集合中的任意两点的仿射组合仍在该集合中,那么称该集合为仿射集合

V 是一个子空间(即关于加法和数乘运算是封闭的),则仿射集合 C 可以表示为

C=V+x0={v+x0vV}

与仿射集合 C 相关联的子空间 Vx0 的选取无关,所以 x0 可以是 C 中的任意一点。

我们称由集合 CRn 中的点的所有仿射组合组成的集合为 C仿射包,即

affC={θ1x1++θ1x1x1,,xkC,θ1++θk=1}

仿射包是包含 C 的最小的仿射集合。

仿射维数与相对内部

集合 C仿射维数 为其仿射包的维数。例如,R2 上的单位圆环 xR2x12+x22=1 的仿射包是全空间 R2,故其仿射维数为 2

考虑 R3 中处于 (x1,x2) 平面的一个正方形,定义

C={xR31x11,1x21,x3=0}

其仿射包为 x1,x2 平面,即 affC=xR3x3=0C 的仿射维数小于 3,其相对内部为

relintC={xR31<x1<1,1<x2<1,x3=0}

CR3 中的边界是其自身,而相对边界是其边框,即

clCrelintC={xR3max{|x1|,|x2|},x3=0}

凸集

若对 x1,x2C 和对 θ[0,1],都有

θx1+(1θ)x2C

则称集合 C凸集

仿射集合是凸集

由于仿射集包含穿过集合中任意不同两点的整条直线,任意不同两点间的线段自然也在集合中,因而仿射集是凸集。

凸集和非凸集
凸集和非凸集

如图所示,左边的正六边形是凸集;中间的图形不是凸集,因为任意两点之间的连线不一定都被集合包含;右边的正方形也不是凸集,因为它仅包含部分边界。

我们称 θ1x1++θ1x1 为点 x1,,xk 的一个凸组合,其中 θ1++θk=1 并且 θi0,i=1,,k。可以将点的图组合理解为他们的混合或加权平均,θi 代表混合时 xi 所占的份数。

我们称集合 C 中所有点的凸组合的集合为其凸包,即

convC={θ1x1++θkxkxiC,θi0,i=1,,k,θ1++θk=1}
凸包
凸包

如图所示,左边的一系列散点的闭包是外层散点连线所构成的多边形;右边的图形的闭包是用与图形相切的部分代替凹陷的部分重新构成的封闭图形。

凸组合的概念可以扩展到无穷级数、积分以及大多数形式的概率分布。例如:

i=1θi=1i=1θixiCCp(x)dx=1Cp(x)xdxC

如果对 xCθ0 都有 θxC,那么我们称集合 C或者非负齐次。若集合 C 是锥并且是凸的,则称 C凸锥,即对 x1,x2Cθ1,θ20,都有

θ1x1+θ2x2C

半径为 的扇形和母线长为 的圆锥面是典型的凸锥,如图所示:

锥

和凸组合和凸包类似,可以定义锥组合和锥包。集合 C 的锥包是 C 中元素的所有锥组合的集合,如图所示:

锥包
锥包

小结

仿射集 凸集 凸锥
θx1+(1θ)x2C θx1+(1θ)x2C θxC θ1x1+θ2x2C
θR θ[0,1] θ0 θ1,θ20
仿射组合 凸组合 锥组合
θ1x1++θkxk θ1x1++θkxk θ1x1++θkxk
θ1++θk=1 θ1++θk=1
θi0,i=1,,k θi0,i=1,,k
仿射包 凸包 锥包
θ1++θk=1 θ1++θk=1
θi0,i=1,,k θi0,i=1,,k
Next