本节主要讲凸集的概念以及保凸运算,这对于判断优化问题是否是凸的非常有帮助。这一节有一部分概念比较抽象,需要仔细研读。

凸集(Convex Set)

凸集

通过集合的任意两个点的线段还在集合中,即



仿射集(Affine Set)

通过集合的任意两个点的直线还在集合中



线性方程组的解集是一个仿射集。

凸组合(Convex Combination)



凸包(Convex Hull)

S的凸包是指S中所有点的凸组合组成的集合,凸包是包含S的最小的凸集。

锥(Cones)

锥组合Conic combination



是非负线性组合。

凸锥Convex Conic

任意两个点的锥组合还在集合中。

锥包Conic Hull

集合C的锥包是指C中所有元素的锥组合的集合

保凸运算

通过保凸运算,可以从凸集构造出其他凸集。

如何证明集合C的凸性?

有两种方法:

1.通过定义证明;

2.说明集合C可以通过一些简单的凸集(超平面,半空间,球,椭球,范数球,范数锥,多面体,半正定锥)通过保凸运算导出。

保凸运算包括:

* 取交集
* 仿射函数
* 透视函数
* 线性分式函数
取交集(Intersection)

任意凸集的交集都是凸集



上图的集合是凸集,因为p(t)关于x是线性函数,线性不等式的解集是凸集,要求对不同的t值成立,相当于取交集。所以S是凸集。

仿射函数(Affine Function)

设f是仿射函数,则凸集在f下的像以及原像都是凸的。

仿射函数具有形式:f(x)=Ax+bf(x)=Ax+b

仿射函数包括:缩放、平移、投影

透视和线性分式函数(Perspective and Linear-fractional Function)

透视函数把向量的最后一维归一化为1,然后丢掉它。形式化地表达如下:



凸集的像和原像在透视变换下都是凸的。

仿射函数和透视函数都属于线性分式函数。线性分式函数可以看成是仿射函数和投射函数的合成。



投射解释 线性分式函数可以看成一个矩阵

Q=[ACTbd]Q=[AbCTd]
作用于点(x,1),得到(Ax+b,cTx+d)(Ax+b,cTx+d),再作归一化使得最后一个分量是1,得到(f(x),1)(f(x),1)


条件概率

条件概率可以看成是通过线性分式映射得到

广义不等式(Generalized Inequalities)

称锥K⊆RnK⊆Rn为正常锥(Proper Cones),如果满足:

* K是凸的
* K是闭的
* K是实的,即有非空内部
* K是尖的,即不包含直线
正常锥K可用来定义广义不等式



当K=R+K=R+时,偏序关系⪯K⪯K即为通常意义上的序≤≤。

非负象限及分量不等式

非负象限是一个正常锥,相应的广义不等式⪯K⪯K对应于向量不等式。



半正定锥和矩阵不等式

半正定锥SnSn是正常锥,相应的广义不等式就是通常的矩阵不等式。即X⪯KYX⪯KY等价于Y−XY−X是半正定矩阵。对Sn+S+n有相似结论。

[0,1]上的非负的多项式锥



广义不等式的性质

传递性、自反、反对称等,类似于我们常见的不等式。

最小与极小元

广义不等式的一些性质与普通不等式有明显的区别,即对于R上的线性序,任意两点都是可比的
,而这个性质对其他广义不等式并不成立。这导致了最大最小的概念在广义不等式下有一些不同。

最小元

可以直观理解成比集合中的每个元素都小(⪯K⪯K)。形式化定义是


S⊆x+KS⊆x+K


极小元

可以直观理解成集合中没有比它更小的元素。形式化定义是


(x−K)∩S=x(x−K)∩S=x




极小元有多个。

分离与支撑超平面

超平面分离定理

两个不想交的凸集C和D,存在一个超平面aTx≤baTx≤b,把他们分离开。即对于集合D中所有元素非负,对于集合C中所有元素非正。



严格分离

不相交的凸集并不一定能被超平面严格分离,即使集合是闭集。

点和凸集的严格分离 如果C是闭凸集,而x0∉Cx0∉C,那么存在将x0x0和CC严格分离的超平面。

超平面分离定理的逆定理

任何两个凸集,至少一个是开集,当且仅当存在分离超平面时,它们不相交。

支撑超平面定理

若x0x0是集合C⊆RnC⊆Rn的边界bd Cbd C的一点,即


x0∈bd C=cl C/ int Cx0∈bd C=cl C/ int C


如果 aTx≤aTx0aTx≤aTx0对集合中的任何一点xx且a≠0a≠0,则{x|aTx=aTx0}{x|aTx=aTx0}是集合C在点x0x0
处的支撑超平面。



支撑超平面定理:对任意的非空凸集,在边界处存在支撑超平面。

逆定理:集合是闭的,并且有非空的内部,并且其边界上的每个点都存在支撑超平面,那么它是凸的。

对偶锥和广义不等式(Dual Cones and Generalized Inequalities)

对偶锥

令KK是一个锥,集合K∗={y|xTy≥0,∀x∈K}K∗={y|xTy≥0,∀x∈K}称为KK的对偶锥。K∗K∗是一个锥,并且总是凸的,即使KK不是凸锥。



从几何上看,当且仅当y∈K∗y∈K∗是KK在原点的一个支撑超平面的法线的反向。

仔细分析,对偶锥是这样的一个区域。区域中的每个点与KK中的每个点的夹角小于等于90°。K∗K∗的边界分别与KK的边界垂直。



常见对偶锥的例子:

* 非负象限。锥Rn+R+n的对偶锥是它本身。称为自对偶。
* 半正定锥。Sn+S+n也是自对偶的
* 范数锥的对偶:
对偶锥满足的性质:

如果KK是一个正常锥,那么它的对偶也是正常锥。K∗∗=KK∗∗=K。

K∗K∗是指KK的凸包和闭包,如果KK是凸和闭的,那么K∗∗=KK∗∗=K。

广义不等式的对偶(Dual Generalized Inequalities)

因为正常锥的对偶也是正常锥,所以可以从正常锥的对偶导出一个广义不等式。称⪯K∗⪯K∗为广义不等式⪯K⪯K的对偶。

关于广义不等式及其对偶的一些重要性质:



因为K∗∗=KK∗∗=K。

对偶广义不等式的最小元与极小元

待续

参考文献

[1] http://blog.csdn.net/xingce_cs/article/details/73748679
<http://blog.csdn.net/xingce_cs/article/details/73748679>
[2]《凸优化》

友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信