凸优化6：多面体

多面体(Polyhedra)

多面体定义为有限个线性等式和不等式的解集。

.

因此，多面体时有限个半空间和超平面的交集。仿射集合（例如子空间、超平面、直线）、射线、线段、半空间都是多面体。

多面体是凸集。有界的多面体有时也称为多胞形。下图为五个半空间的交集定义的多面体

image-20231211225718138

image-20231211225718138

可以使用紧凑表达式

.

其中

,

此处的代表上的向量不等式（分量不等式）：表示.

例如，非负象限是具有非负分量的点的集合，即

非负象限既是多面体也是锥，因此被称为多面体锥

单纯形(Simplexes)

单纯形是一类重要的多面体。设个点仿射独立，即线性独立，那么这些点就决定了一个单纯形，如下

,

这个单纯形的仿射维数为，因此也称为空间的维单纯形

一些常见的单纯形

1维单纯形是一条线段；2维单纯形是一个三角形；3维单纯形是一个四面体

单位单纯形是由零向量和单位向量决定的维单纯形，可以表示为满足下列条件的向量的集合：

概率单纯形是由单位向量决定的维单纯形，可以表示为满足下列条件的向量的集合。概率单纯形中的向量对应于含有个元素的集合的概率分布，可理解为第个元素的概率

使用多面体描述单纯形

为了用多面体来描述单纯形，采用以下步骤将单纯形的定义式变形：

由单纯形的定义式可知，的充要条件是，对于某些，有，与之等价地，若定义和,

可以知道的充要条件是.

对于成立。可以注意到仿射独立意味着矩阵的秩维。因此，存在非奇异矩阵使得

对式子左乘，得到

从上面两个式子中可以看出当且仅当并且向量满足和，换言之，我们得到了的充要条件为：

这些是的线性等式和不等式，可以描述一个多面体。

多面体的凸包描述

有限集合的凸包是.

这个凸包是一个有界的多面体，但是无法简单地用多面体地定义式来描述（即难以用线性等式和不等式地集合将其表示出来）

凸包的一个扩展表示是。其中。此处考虑的非负线性组合，但是仅仅要求前个系数之和为1。此外，还可以将上式解释为点的凸包加上的锥包。上面这个凸包的表示定义了一个多面体。反之也成立，任意多面体可以表示为这样的形式

“如何表示多面体”这一问题有一些非常实用的结果，一个简单的例子是定义在范数空间的上的单位球

可以由个线性不等式(其中表示第维的单位向量)表示为多面体的形式。