凸优化4——不改变凸集凸性质的变换

发布时间 2023-07-14 18:08:45作者: 孙bob

本节对应凌青老师7,8两课

1. 两凸集交集(并集不一定)

2. 仿射函数及其逆函数

 可以看到,仿射函数是将原n维向量线性映射到m维向量

而逆仿射依然不改变凸性质,逆仿射可以如下表示

3. 缩放、移位

4. 两凸集的和

两凸集的和可以表示为

在证明时,可以先构造一个辅助集合,如下:

 上面这个辅助集合易证是凸集,而将该辅助集合通过

 的仿射变换,即可得到两集合的和,故得证

5. 透视函数与反透视

透视比较有意思,实际上是一种降维的操作,首先对定义域有要求,如下:

 这表示P中的点是n+1维的向量,其中前n维取值是实数集,而最后一维是++大于0的(此处 'x' 意义等同上面辅助集合中的)

而透视函数则将该n+1维向量映射到n维

 这里证明也是通过凸集的定义来证,主要一点如下所示:

证明思路:原凸集中任意两点连接成的线段,在透射后的集合中仍对应一条线段,且该线段中的每一点与原线段的点可以一一映射 

在原凸集中任取两点,X,Y,这两端点经过透视降维后,对应于上式中X'/Xn+1  和 Y'/Yn+1

而这两点前的系数,由sita决定,且一一对应并属于[0,1],故透射后仍是一条线段

反透视可以表达如下:

7. 线性分数函数

先来看一下线性分数函数的样子

这个很常见对吧(dom表示f的定义域)

一个凸集经过这个非线性变换仍然是凸集,老师给出一个很有意思的角度理解,都是利用上述已知结论

即,线性分数函数=先仿射再透射

其中,仿射如下:

AX+b是一个m维向量,CX+d是一个标量,整体是m+1维的,该m+1维的集合,经过透射,不就是(AX+b)/(CX+d)嘛!! 

这个时候再看,仿射一次不改变凸,透射也是,因此线性分数函数不改变凸性质,豁然开朗