首页 » 学习 » 典型凸集

典型凸集

  1. 超平面(hyperplane)和半空间(halfspace)
  2. 欧几里得球(euclidean ball)和椭球体(ellipsoid)
  3. 多面体(polyhedra)和单纯形(simplex)
  4. 参考

本文是我在学习Convex Optimization这本书第2章Convex sets过程的读书笔记,翻译了凸优化基本概念的定义和相关性质。一些名词的翻译参考了其他博客的翻译,没有经过仔细查阅文献,所以专业名词都保存了英文原文。

1 超平面(hyperplane)和半空间(halfspace)

超平面是形如
\{x \mid a^Tx=b\}
的集合,其中a \in R^n,a\ne 0,b\in R。虽然名为平面,但不一定为平面。二维空间中,超平面为一条线;三维空间中,超平面为一个平面。可以将移动b
\{x\mid a^T(x-(a^T)^{-1}b)=0\}
的形式,就可以很明显得看出超平面的方向为a的垂直方向,
(a^T)^{-1}b为平面中的一个点。

一个超平面把整个空间划分为两部分。超平面定义中的等号变为大于或小于号\{x \mid a^T x \leqslant b\}即可得到一个半空间

2 欧几里得球(euclidean ball)和椭球体(ellipsoid)

欧几里得球,也就是我们常说的球体,在R^n空间中表示为
\begin{aligned}B(x_c,r)&=\{x\mid \parallel x-x_c\parallel _2 \leqslant r \}\\&=\{x \mid (x-x_c)^T(x-x_c)\leqslant r^2\}\end{aligned}
其中r>0B(x_c,r)为距离球心x_c小于球半径r内所有的点。也可以表示为
B(x_c,r)=\{x_c+ru\mid \parallel u \parallel _2 \leqslant 1 \}

与球体相似的椭球体可以表示为
\varepsilon =\{x \mid (x-x_c)^TP^{-1}(x-x_c)\leqslant 1\}
其中P=P^T\succ 0 ,即对称且正定。很明显,如果将P^{-1}变为一个常数乘单位阵,则可以将椭球体变为球体。
同样可以想球体一样表示为
\varepsilon =\{x_c +Au\mid \parallel u \parallel _2 \leqslant 1 \}
其中A为满秩方阵。

3 多面体(polyhedra)和单纯形(simplex)

多面体是有限数量的线性等式和不等式的解,可以表示为
P=\{x\mid a_i^Tx \leqslant b_i,i=1 , \ldots,m, c_j^Tx=d_j,j=1,\ldots p\}
因此,多面体是有限数量的超平面和半空间的交集

单纯体是多面体的一个特例,由k+1个仿射独立(affinely independext)的点v_0,\ldots,v_k构成的凸包(convex hull),即
\begin{aligned}C&=conv\{v_0,\ldots,v_k\}\\&=\{\theta_0v_0+\cdots+\theta_kv_k\mid \theta \succeq 0,\mathbf{1}^T\theta=1\}\end{aligned}
其中\mathbf{1}为所有元素均为1的矩阵。
v_0,\ldots,v_k仿射独立意为v_1-v_0,\ldots,v_k-v_0线性独立。

当不再规定单纯体所有点都仿射独立,而仅仅m个点仿射独立,单纯体就拓展成了一般的多面体。
conv\{v_1,\ldots,v_k\}=\{\theta_1 v_1+\cdots+\theta_kv_k\mid \succeq0,\mathbf{1}^T\theta=1\}
其中仿射独立的部分对应前面定义中的的半平面部分,不仿射独立的部分对应超平面部分。

4 参考

标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注