跳转至

超平面、半空间与多面体

在本节中,我们介绍超平面、半空间与多面体。

超平面#

超平面

如果一个集合满足

\{x \mid a^Tx = b\} \ s.t. \ a \in \mathbb{R}^n, a \neq 0, b \in \mathbb{R}

那么我们将其称为一个超平面。

从解析来看,超平面是x分量中线性不定方程的解集;从几何来说,超平面也可以被解释为与给定向量a的内积为一特定值的点集;由于内积可以被看作是一个向量在另一个向量的投影,我们也可以将a理解为一个有超平面的 法向向量,那么常数b就是确定超平面距离原点的偏移量。将上式做一个简单的形变,我们可以得到\{x \mid a^T (x - x_0) = 0\} = a^\perp + x_0

超平面是凸还是仿射

仿射

分割超平面#

分割超平面

对于不相交的非空凸集C, D,存在a \neq 0, b使得:

a^Tx \leq b \text{for} x \in C, \ a^Tx \geq b \text{for} x \in D

那么我们称超平面\{x \mid a^Tx = b\}CD的分割超平面。

严格分割超平面需要更多假设(比如C闭合,D是单元素集(singleton set))

支持超平面#

支持超平面

集合C在边界点x_0的支持超平面是

\{x \mid a^tx = a^tx_0\}

其中a \neq 0, \ \forall x \in C, a^T \leq a^Tx_0

支持超平面定理

支持超平面只在凸的边界点存在

半空间#

空间S \subseteq \mathbb{R}^n中的超平面将该空间划分成两个半空间。

半空间

如果一个集合满足

\{x \mid a^Tx \leq b\} \ s.t. \ a \neq 0

那么我们将其称为一个半空间。

半空间是凸还是仿射

多面体#

一个 多面体(polyhedra) 指的是一个有限数目的线性等式与不等式的解集:

多面体

P = \{x \mid a^T_jx \leq b_j,\ j = 1, 2, ..., m,\ c^T_jx = d_j,\ j = 1, 2, ..., p\}

我们可以发现,一个多面体实际上是一个有限数量的超平面与半空间的交集。仿射集(比如子空间、超平面、线)、射线、线段、半空间等都是多面体。

上式常被化简为P = \{x \mid Ax \preceq b, Cx = d\}

\preceq

符号\preceq表示\mathbb{R}^n中的 向量不等(vector inequality) 或者 分量不等(componentwise inequality)u \preceq v表示u_i \leq v_i \ s.t. \ i = 1, 2, ..., m

多面体凸吗

一个有边界的多面体有时被称为 多胞形(polytope)^\star

^\star:有些人倾向于将多胞形与多面体反过来叫。


最后更新: 2021-05-06 19:36:11

评论