本文参考自清华大学研究生公共课教材——数学系列《最优化理论与算法》（第二版）

一：凸集

定义：设S为n维欧式空间中\mathbb{R}^{n}中的一个集合，若对S中任意两点，联结它们的线段仍属于S，称这样的集合S是一个凸集。

用代数的形式表达为：对S中任意两点x^{(1)}，x^{(2)}及每个实数\lambda \in [0,1]，都有

                                                                   \lambda x^{(1)}+(1-\lambda )x^{(2)}\in S

称S为凸集

                                                      \lambda x^{(1)}+(1-\lambda )x^{(2)}称为x^{(1)}，x^{(2)}的凸组合。

 

下面验证几个集合是否为凸集：

例一：验证集合H=\left \{ x|p^{T}x=a \right \}为凸集，其中，p为n维列向量，a为实数

对于任意两点x^{(1)}，x^{(2)}\in H，及每个实数\lambda \in [0,1]都有

                                                                             \lambda p^{T}x^{(1)}+(1-\lambda)x^{(2)}

                                                                            \because p^{T}x^{(1)}=p^{T}x^{(2)}=a

                                                                            \therefore \lambda p^{T}x^{(1)}+(1-\lambda)x^{(2)}=\lambda a+(1-\lambda)a=a

所以\lambda x^{(1)}+(1-\lambda )x^{(2)}\in H

H称为\mathbb{R}^{n}中的一个超平面，所以超平面为凸集。

 

例二：验证集合H^{-}=\left \{ x|p^{T}x\leqslant a \right \}为凸集

对于任意两点x^{(1)},x^{(2)}\in H^{-}，及每个实数\lambda \in [0,1]都有

                                                                          p^{T}\left [ \lambda x^{(1)}+(1-\lambda)x^{(2)} \right ]\leqslant a

上式左=\lambda p^{T}x^{(1)}+(1-\lambda)x^{(2)}

                                                                         \because p^{T}x^{(1)}\leqslant a     p^{T}x^{(2)}\leqslant a

                                                                         \lambda+(1-\lambda)=1

                                                                         \therefore \lambda p^{T}x^{(1)}+(1-\lambda)p^{T}x^{(2)}\leqslant a

所以\lambda x^{(1)}+(1-\lambda)x^{(2)}\in H^{-}

所以H^{-}为凸集，集合H^{-}=\left \{ x|p^{T}x\leqslant a \right \}称为半空间，所以半空间为凸集

 

例三：验证集合L=\left \{ x|x=x^{(0)}+\lambda d,\lambda\geqslant 0 \right \}为凸集，其中d是给定的非零向量，x^{(0)}是定点

对于任意两点x^{(1)},x^{(2)}\in L及每一个数\lambda \in [0,1]，必有x^{(1)}=x^{(0)}+\lambda_{1}d，x^{(2)}=x^{(0)}+\lambda_{2}d，\lambda_{1},\lambda_{2}是非负数

                                                   \lambda x^{(1)}+(1-\lambda)x^{(2)}=\lambda(x^{(0)}+\lambda_{1}d)+(1-\lambda)(x^{(0)}+\lambda_{2}d)

                                                                                     =x^{(0)}+\left [ \lambda \lambda_{1}+(1-\lambda)\lambda_{2} \right ]d

由于\lambda \lambda_{1}+(1-\lambda)\lambda_{2}\geqslant 0，所以\lambda x^{(1)}+(1-\lambda)x^{(2)}\in L，所以L为凸集

集合L=\left \{ x|x=x^{(0)}+\lambda d,\lambda\geqslant 0 \right \}成为射线，所以射线为凸集，x^{(0)}为射线的预点

 

二：极点

若假设S为非空凸集，x=\lambda x^{(1)}+(1-\lambda)x^{(2)}(\lambda \in (0,1)),x^{(1)},x^{(2)} \in S，必推得x=x^{(1)}=x^{(2)}，则称x为凸集S的极点

这个论断对于紧凸集是正确的，但是对于无界集并不成立，此时引入极方向的概念

 

三：极方向

设S为\mathbb{R}^{n}中的闭凸集，d为非零向量，如果对S中的每一个x，都有射线

                                                                                  \left \{ x+\lambda d|\lambda\geqslant 0 \right \}\subset S

则称向量d为S的方向。

设d^{(1)}和d^{(2)}是S的两个方向，若对任意正数\lambda，有d^{(1)}\neq \lambda d^{(2)}，则称d^{(1)}和d^{(2)}为两个不同的方向。

若S的方向d不能表示为该集合中两个不同方向的正的线性组合，则称d为S的极方向。

 

四：凸集分离定理

对于两个集合S1，S2，存在一个超平面H，使S1在H的一边，S2在H的另一边。

设超平面的方程为P^{T}x=a，那么对于H某一边的点x，有p^{T}x\geqslant a，而对另一边的点x，必有p^{T}x\leqslant a

称超平面分离集合S_{1}和S_{2}

Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊