首页 » 学习 » 保留凸性质的集合运算

保留凸性质的集合运算

交集(intersection)

如果集合S_1S_2都是凸集,那么他们的交集S_1\cap S_2也是凸集。我们也可以拓展到任意数量的凸集的交集\cap_{\alpha \in A}S_{\alpha}也是凸集。

举个例子,多面体是半空间和超平面的交集。因为半空间和超平面都是凸集,那么多面体也是一个凸集。

仿射函数(affine function)

仿射函数是通过线性函数和常数的组合实现从R^nR^m的映射。
仿射函数不会打破凸性质,也就是通过通过仿射函数f(x)=Ax+b其中A\in R^{m \times n},b\in R^m,如果x属于凸集S,那么仿射函数
f(S)=\{f(x)\mid x\in S\} 也是凸的。
同样,反过来使用仿射函数也不会破坏凸性质,即f^{-1}(S)=\{x\mid f(x)\in S\}也是凸的。

通过仿射函数可以拓展很多已知是凸的函数到新的函数。例如缩放(A\ne 0,b=0)和平移(A=0,b\ne 0)都是特殊的仿射函数,所以他们都不会改变凸性质。

通过仿射函数f(x)=(P^{1/2}x,c^Tx)可以将双曲线锥(hyperbolic cone)\{x\mid x^TPx \leqslant (c^Tx)^2,c^Tx \geqslant 0\} 变成二阶锥(second-order cone)\{(z,t)\mid z^Tz \leqslant t^2,t \geqslant0\}

透视函数(perspective function)

透视函数是将R^{n+1}空间映射到R^n空间,定义域dom PR^n \times R_{++},例如P(z,t)=z/t。其中R_{++}为正数集\{x\in R \mid x>0\}\times为笛卡尔积(cartesian product)S_1\times S_2=\{(x_1,x_2)\mid x_1\in S_1,x_2\in S_2\}

透视函数通过将一维变量变成常数,降一维。类似于一个相机,通过二维图片记录某一位置的三维空间。

如果在透视函数P(z,t)=z/t的定义域内的C是凸的,那么透视结果P(C)=\{P(x)\mid x\in C\}也是凸的。类似的,C\subseteq R^n是凸的,那么P^{-1}(C)=\{(x,t)\in R^{n+1}\mid x/t \in C, t>0\}也是凸的。

线性分式函数(linear-fractional function)

g:R^n\rightarrow R^{m+1}是仿射的,也就是g(x)=\begin{bmatrix}A\\c^T\end{bmatrix}x+\begin{bmatrix}b\\d\end{bmatrix}其中A\in R^{m\times n},b\in R^m,c\in R^n,d\in R。那么称函数f=P\circ g,也就是形如f(x)=(Ax+b)/(c^Tx+d)\\dom f=\{x\mid c^Tx+d>0\}为线性分式函数。保留凸性质的运算

可以这样理解线性分式函数,首先通过仿射函数g将n维空间内的点仿射到n+1维空间内,再通过透视函数P降维到n维空间内。因为仿射函数和透视函数都不会改变凸性质,所以线性分式函数也不会改变凸性质。

可以将线性函数和仿射函数都是线性分式函数的特例。例如规定c=0,d>0那么线性分式函数则变成了仿射函数。

标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注