《凸优化》笔记（一）：凸集

本文转载自：https://blog.****.net/u010366427/article/details/51867027

笔记是根据《Convex Optimization》写的，对应第2章。

2 凸集

2.1 凸集(convex sets) 
　　如果在集合CC中的任意两点满足： 

θx1+(1−θ)x2∈Cθx1+(1−θ)x2∈C

其中0≤θ≤10≤θ≤1，则集合CC为凸集 
2.2 重要例子 
1) 超平面与半空间(hyperplanes and halfspaces) 
　　超平面定义为{x|aTx=b}{x|aTx=b}，半空间被定义为{x|aTx≤b}{x|aTx≤b}。从直观上看，超平面在空间中为一块板子，划分的两边则分别为半空间。 
 
2) 球和椭球 
　　球的形式为 

{x|||x−xc||2≤r}={x│(x−xc)T(x−xc)≤r2}{x|||x−xc||2≤r}={x│(x−xc)T(x−xc)≤r2}

椭球的形式为 

{x│(x−xc)TP−1(x−xc)≤1}{x│(x−xc)TP−1(x−xc)≤1}

其中PP是对称的正定矩阵。 
 
3) 范数球和范数锥 
　　范数球为： 

{x|||x−xc||≤r}{x|||x−xc||≤r}

范数锥为： 

{(x,t)|||x||≤t}{(x,t)|||x||≤t}

 
4) 多面体 

{x|aTjx≤bj,j=1,…,m,cTjx≤dj,j=1,…,p}{x|ajTx≤bj,j=1,…,m,cjTx≤dj,j=1,…,p}

 
5) 半正定锥 
　　满足如下条件的集合Sn+S+n是凸集：θ1、θ2≥0θ1、θ2≥0并且A,B∈Sn+A,B∈S+n，则θ1A+θ2B∈Sn+θ1A+θ2B∈S+n。其中Sn+S+n是半正定矩阵。 
 
2.3 保凸运算 
1) 交集 
　　如果AA与BB均为凸集，则A与B的交集也为凸集。 
2) 仿射函数 
　　仿射函数即线性函数加常数。如果xx为凸集，则f(x)=Ax+bf(x)=Ax+b为凸集。仿射函数的逆函数也保凸。 
3) 线性分式以及透视函数 
　　透视函数即P(z,t)=z/tP(z,t)=z/t，这里zz是n−1n−1维向量，tt是最后一维分量。例如P(x1,x2,x3)={x1/x3,x2/x3}P(x1,x2,x3)={x1/x3,x2/x3}，PP的定义域是正定对称矩阵。从几何上看，透视函数类似小孔成像，是从高维到低维的映射。 
 
　　线性分式即f(x)=(Ax+b)/(cTx+d)f(x)=(Ax+b)/(cTx+d)其定义域为{x|cTx+d>0}{x|cTx+d>0}。其逆函数也保凸。线性分式可看做在原集合内做拉伸，故而保凸。 
 
2.4 广义不等式 
　　广义不等式即定义了拥有多个分量的变量之间的比较： 

x≥ky⟺x−y∈kx≥ky⟺x−y∈k

 

x>ky⟺x−y∈int(k)x>ky⟺x−y∈int(k)

int(k)int(k)即kk的内部的点。注意kk必须为凸的、闭的、有非空内部且不包含直线。 
2.5 minimum and minimal 
　　Minimum即能和集合内所有点进行比较，且最小。Minimal即在集合内能比较的所有点中最小。 
 
左图为minimum，右图为minimal。 
2.6 分割面与支撑面 
　　分割面即能将两个集合分开的超平面，有严格不严格之分，严格即两个集合没有交点。两个凸集一定存在一个分割面。 
　　支撑面即集合边缘有个点使得aTx≤aTx0aTx≤aTx0成立。其中x是集合内的点，a≠0a≠0。