(最优化理论与方法)第二章最优化所需基础知识-第三节:重要凸集举例

(1)超平面

超平面:任取非零向量 a ∈ R n a\in \R^{n} aRn,形如

{ x ∣ a T x = b } , a ≠ 0 , b ∈ R \{x|a^{T} x=b\},a\not=0,b\in R {xaTx=b},a=0,bR

的集合称之为超平面

上述定义还可以表示为:

{ x ∣ a T ( x − x 0 ) = 0 } \{x|a^{T} (x-x_{0})=0\} {xaT(xx0)=0}

  • x 0 x_{0} x0为超平面上任意一点

下图:是由 R 2 R^{2} R2中由法向量 a a a和超平面上一点 x 0 x_{0} x0确定的超平面,对于超平面上任意一点 x x x x − x 0 x-x_{0} xx0都垂直于 a a a
在这里插入图片描述

(2)半空间

超平面:任取非零向量 a ∈ R n a\in \R^{n} aRn,形如

{ x ∣ a T x ≤ b } \{x|a^{T}x \leq b\} {xaTxb}

的集合称为半空间

一个超平面会将 R n R^{n} Rn划分为两个半空间,对于下图中的 R 2 R^{2} R2来说

  • a T x ≥ b a^{T}x \geq b aTxb决定的半空间(白色部分) :是向 a a a扩展的部分
  • a T x ≤ b a^{T}x \leq b aTxb决定的半空间(阴影部分) :是向 − a -a a扩展的部分,向量 a a a是这个半空间向外的法向量

在这里插入图片描述

(3)超平面和半空间与凸集和仿射集的关系

A:关系

关系:超平面和半空间与凸集和仿射集的关系总结如下

  • 超平面是仿射集
  • 超平面是凸集
  • 半空间不是仿射集
  • 半空间是凸集

B:证明(部分)

证明:超平面为凸集

证明:半空间为凸集

(4)(范数)球和椭球

(范数)球:设空间中到某一定点 x c x_{c} xc(称为球心)的距离小于等于定值 r r r(称为半径)的点的集合为(范数)球,即

B ( x c , r ) = { x ∣ ∣ ∣ x − x c ∣ ∣ ≤ r } = { x c + r u ∣ ∣ ∣ u ∣ ∣ ≤ 1 } B(x_{c}, r)=\{x|\quad ||x-x_{c}||\leq r\}=\{x_{c}+ru|\quad ||u||\leq1\} B(xc,r)={x∣∣xxc∣∣r}={xc+ru∣∣u∣∣1}

  • 一般来说,我们使用二范数度量距离,即使用2-范数球,即 { x ∣ ∣ ∣ x − x c ∣ ∣ ≤ r } \{x|\quad ||x-x_{c}||\leq r\} {x∣∣xxc∣∣r}

椭球:设形如

{ x ∣ ( x − x c ) T P − 1 ( x − x c ) ≤ 1 } = { x c + A u ∣ ∣ ∣ u ∣ ∣ 2 ≤ 1 } \{x| (x-x_{c})^{T}P^{-1}(x-x_{c})\leq1\}=\{x_{c}+Au|\quad ||u||_{2}\leq 1\} {x(xxc)TP1(xxc)1}={xc+Au∣∣u21}

的集合为椭球,其中 x c x_{c} xc称为椭球中心 P P P对称正定且 A A A可逆

(5)范数锥

范数锥:球和椭球的范围完全取决于 x x x的范围,而锥的范围则同时受 x x x t t t的控制。将形如

{ ( x , t ) ∣ ∣ ∣ x ∣ ∣ ≤ t } \{(x, t)|\quad ||x||\leq t\} {(x,t)∣∣x∣∣t}

的集合为范数锥

  • 使用二范数度量距离的锥称为二次锥,也称为冰淇淋锥

(6)多面体

多面体:我们把满足线性等式和不等式组的点的集合称为多面体,即

{ x ∣ A x ≤ b , C x = d } \{x|Ax\leq b,Cx=d\} {xAxb,Cx=d}

其中 A ∈ R m × n A\in \R^{m×n} ARm×n C ∈ R p × n C\in \R^{p×n} CRp×n x ≤ y x\leq y xy表示向量 x x x的每个分量都 ≤ y \leq y y的对应分量。多面体是有限个半空间和超平面的交

(7)单纯形

单纯形:单纯性是一类特殊的多面体。在 R n \R^{n} Rn空间中选择 { v 0 , v 1 , . . . , v k } \{v_{0}, v_{1}, ... ,v_{k}\} {v0,v1,...,vk}共计 k + 1 k+1 k+1个点,并要求向量线段 v 1 − v 0 , v 2 − v 1 , . . . , v k − v k − 1 , v 0 − v k v_{1}-v_{0},v_{2}-v_{1},...,v_{k}-v_{k-1},v_{0}-v_{k} v1v0,v2v1,...,vkvk1,v0vk构成线性无关组,则 { v 0 , v 1 , . . . , v k } \{v_{0}, v_{1}, ... ,v_{k}\} {v0,v1,...,vk}凸包构成 k k k-单纯形

  • 由于 R n \R^{n} Rn内最多可以有 n n n个向量组成线性无关组,因此上述定义满足 0 ≤ k ≤ n 0\leq k \leq n 0kn。这表明:在有限维向量空间内,单纯形不能无限扩张, R n R^{n} Rn空间中最多存在 n n n-单纯形

以下是一些常见的单纯形

  • 0-单纯形就是点
  • 1-单纯形就是线段
  • 2-单纯形就是三角形面
  • 3-单纯形就是四面体(包括内部)
  • 4-单纯形就是一个五胞体(包括内部)

(8)特殊矩阵集合和半正定锥

以下是三类特殊的矩阵集合

数学符号 S n S^{n} Sn S + n S^{n}_{+} S+n S + + n S^{n}_{++} S++n
中文名称对称矩阵对称半正定矩阵对称正定矩阵
数学表达式 { X ∈ R n × n ∣ X T = X } \{ X\in R^{n×n}|X^{T}=X\} {XRn×nXT=X} { X ∈ S n ∣ X ⪰ 0 } \{ X\in S^{n}|X⪰0\} {XSnX0} { X ∈ S n ∣ X ≻ 0 } \{ X\in S^{n}|X≻0\} {XSnX0}
是否为凸集
是否为凸锥

半正定锥:一般称 S + n S^{n}_{+} S+n为半正定锥,下图为二维半正定锥集合形状,其范围为 { ( x , y , z ) ∣ x ≥ 0 , z ≥ 0 , x z ≥ y 2 } \{(x,y,z)|x\geq0, z\geq0, xz\geq y^{2}\} {(x,y,z)x0,z0,xzy2}

在这里插入图片描述