多面体定义+多面体是凸集+多面体的重要性质

在数学中， 多面体（polyhedron）是指由有限个线性不等式和等式定义的一个凸集合。具体地说， 多面体是线性约束条件下的解空间，也可以看作是凸多面体的推广。在优化、线性规划和几何中，多面体的定义尤为重要。

多面体定义

在$n$-维空间${\mathbb{R}}^n$中，一个多面体可以定义为满足有限个线性不等式和等式的所有点的集合。

标准定义：
一个集合$P\subseteq {\mathbb{R}}^n$是多面体，当且仅当存在一个矩阵$A\in {\mathbb{R}}^{m\times n}$和一个向量$b\in {\mathbb{R}}^m$，使得$P$可以表示为

P = { x ∈ R n : A x ≤ b } 。 P = \{ x \in \mathbb{R}^n : A x \leq b \}。 P={x∈Rn:Ax≤b}。

这里：

• $Ax\le b$表示一组线性不等式。
• $x\in {\mathbb{R}}^n$表示我们考虑的点在$n$-维空间中。

更一般地，多面体还可以包括一些线性等式，即：

P = { x ∈ R n : A x ≤ b , C x = d } 。 P = \{ x \in \mathbb{R}^n : A x \leq b, \ C x = d \}。 P={x∈Rn:Ax≤b, Cx=d}。

其中：

• $C\in {\mathbb{R}}^{k\times n}$和$d\in {\mathbb{R}}^k$定义了线性等式的约束。

在这个定义中，多面体的边界由这些不等式和等式所定义的半空间的交集来确定。

所以多面体的定义为：
一个集合$P\subseteq {\mathbb{R}}^n$是多面体，当且仅当存在一个矩阵$A\in {\mathbb{R}}^{m\times n}$和一个向量$b\in {\mathbb{R}}^m$， $C\in {\mathbb{R}}^{k\times n}$和$d\in {\mathbb{R}}^k$，使得：

P = { x ∈ R n : A x ≤ b , C x = d } ， P = \{ x \in \mathbb{R}^n : A x \leq b, \ C x = d \}， P={x∈Rn:Ax≤b, Cx=d}，

其中：

• $Ax\le b$是一组定义边界的线性不等式【半空间】。
• $Cx=d$是一组定义面的线性等式（可选）【超平面】。

多面体是凸集

从几何上看，多面体可以被认为是一个凸的几何对象。其几何结构可以分解为顶点、边、面等，取决于空间的维数。例如：

• 在三维空间中，一个多面体可能是立方体、四面体等，由平面限定的几何体。
• 在二维空间中，满足线性不等式的集合即为多边形。

多面体之所以凸，是因为线性不等式和等式的交集形成了一个凸集。这意味着，对于任何位于多面体内的两点$x,y\in P$，连接这两点的线段也完全位于$P$内，即

$$\forall \lambda \in [0,1],\lambda x+(1-\lambda )y\in P。$$

多面体重要性质

• 有界多面体：当多面体的定义约束使得$P$的边界是有限的时，我们称其为有界多面体，通常也叫做凸多面体（convex polytope）。

• 无界多面体：当多面体的定义约束不完全封闭$P$时，该多面体可能是无界的。

• 极点表示（顶点形式）：多面体也可以通过顶点的凸组合来表示。这是极点-极射线表示定理的内容。

1. 有界多面体（Convex Polytope）

一个有界多面体，或称为凸多面体，是一个由有限个线性不等式所定义的有限闭凸集合，即它的边界是有限的。这类多面体的几何形状是封闭的，并且在有限的空间中存在。

数学定义：

在 ${\mathbb{R}}^n$ 中，一个集合 $P$ 称为有界多面体或凸多面体，当且仅当存在有限个向量 $v_1,v_2,\dots ,v_k\in {\mathbb{R}}^n$ 和权重 ${\lambda }_i\ge 0$，满足：

$$P=\left\{x\in {\mathbb{R}}^n:x=\sum _{i=1}^k{\lambda }_i{v}_i,\sum _{i=1}^k{\lambda }_i=1\right\}。$$

也就是说，$P$ 是由其顶点的凸组合（convex combination）所生成的集合。

• 凸组合：凸组合表示权重的非负性和总和为1，从而保证了组合后的点仍然在多面体内部。

• 这种定义也表明，有界多面体是凸的，即如果 $x,y\in P$，那么对任意 $\lambda \in [0,1]$，$\lambda x+(1-\lambda )y\in P$。

• 有限个向量的非负线性组合（系数非负且求和为1）+有界多面体必定是凸的+ 有界多面体是顶点的凸组合构成的

2. 无界多面体（Unbounded Polyhedron）

一个无界多面体是由线性不等式或等式约束定义的集合，但这些约束并不完全限制集合在空间中的边界，使得多面体在某些方向上可以延伸到无限远。

数学定义：

在 ${\mathbb{R}}^n$ 中，一个集合 $P$ 称为无界多面体，当且仅当它可以表示为：

P = { x ∈ R n : A x ≤ b } ， P = \left\{ x \in \mathbb{R}^n : A x \leq b \right\}， P={x∈Rn:Ax≤b}，

其中 $A\in {\mathbb{R}}^{m\times n}$ 是一个矩阵，$b\in {\mathbb{R}}^m$ 是向量，且存在非零向量 $d\in {\mathbb{R}}^n$，使得

$$x+\lambda d\in P,\forall \lambda \ge 0。$$

这表明，可以沿着某个方向 $d$ 无限地延伸 $x$，而仍然保持在 $P$ 内，因此 $P$ 是无界的。

• 无界性：多面体的无界性来自于满足约束 $Ax\le b$ 的同时，存在一条无限延伸的方向。
• 满足线性不等式的时候，存在一条无限延伸的方向可以延伸到无限远

3. 极点表示（顶点形式）与极点-极射线表示定理

极点表示定理（或称顶点形式）指出，每个多面体都可以表示为其极点（顶点）的凸组合，且对于无界多面体，还需要包含其极射线的正组合。

• 极点：极点是多面体的顶点，表示那些不能通过其他点的凸组合来表示的点。
• 极射线：对于无界多面体，极射线（或称为方向向量）是那些可以沿其方向无限延伸的方向。

数学定义：

设 $P\subseteq {\mathbb{R}}^n$ 是一个多面体。根据极点-极射线表示定理，$P$ 可以表示为其极点和极射线的凸组合：

$$P=\left\{x\in {\mathbb{R}}^n:x=\sum _{i=1}^k{\lambda }_i{v}_i+\sum _{j=1}^l{\mu }_j{d}_j,{\lambda }_i\ge 0,\sum _{i=1}^k{\lambda }_i=1,{\mu }_j\ge 0\right\}。$$

其中：

• $v_1,v_2,\dots ,v_k$ 是 $P$ 的极点；
• $d_1,d_2,\dots ,d_l$ 是 $P$ 的极射线；
• ${\lambda }_i$ 和 ${\mu }_j$ 分别为非负权重，使得点 $x$ 是这些顶点和射线的线性组合。

解释：

• 有界多面体仅由其极点的凸组合生成，因此没有极射线项；
• 无界多面体需要极点和极射线的组合，才能表示出所有在多面体内部的点。
• 有界多面体=极点的凸组合（没有极线）；无界多面体==极点+极线（多面体内部）