如何将构成凸包的半空间转换为一组极值点？

Question

我在欧几里德空间中有一个凸集(3D,但想要nD的答案),其特征是有限的半空间集(法向量+点).

有没有更好的算法来找到凸集的极值点而不是计算暴力所有点是3(或,n)半空间的交点并消除那些非极值点？

Answer 1

关键术语是多面体 P 的顶点枚举。下面描述的算法的思想是考虑对偶多面体 P*。然后 P 的顶点对应于 P* 的面。使用Qhull有效地计算 P* 的面，然后通过求解线性方程的相应子系统来找到顶点。

该算法是在 BSD 许可的工具集“根据顶点或（In）Equalities for Matlab分析 N 维多面体”中实现的，由Matt J编写，特别是其组件lcon2vert。然而，为了阅读算法并用另一种语言重新实现它，使用Michael Kleder的较旧且更简单的con2vert文件更容易，Matt J 的项目建立在它的基础上。

我将逐步解释它的作用。MathWorks 站点上记录了各个 Matlab 命令（例如convhulln），其中包含对底层算法的引用。

输入由一组形式为 的线性不等式组成Ax<=b，其中 A 是矩阵，b 是列向量。

步骤 1. 尝试定位多胞体的内点

首先尝试的是c = A\b，这是超定线性系统 的最小二乘解Ax=b。如果按A*c<b分量成立，则这是一个内点。否则，尝试多变量最小化，目标函数为 0 和所有数字的最大值A*c-b。如果这未能找到成立的点A*c-b<0，则程序以“无法找到内部点”退出。

步骤 2. 平移多面体，使原点为其内点

这是b = b - A*c在 Matlab 中完成的。因为 0 现在是一个内点，所以 b 的所有条目都是正的。

步骤 3. 标准化，使右侧为 1

这只是 A 的第 i 行除以 b(i)，由D = A ./ repmat(b,[1 size(A,2)]);在 Matlab 中完成。从现在开始，只使用矩阵 D。注意D的行是开头提到的双多面体P*的顶点。

步骤 4. 检查多面体 P 是否有界

如果多面体 P 的对偶 P* 的顶点位于通过原点的某个超平面的同一侧，则多面体 P 是无界的。这是通过使用convhulln计算给定点的凸包体积的内置函数来检测的。作者检查在矩阵 D 上附加零行是否增加了凸包的体积；如果是，则程序退出并显示“检测到非边界约束”。

步骤 5. 计算顶点

这是循环

for ix = 1:size(k,1)
    F = D(k(ix,:),:);
    G(ix,:)=F\ones(size(F,1),1);
end

这里，矩阵 k 对双多胞体 P* 的面进行编码，每一行都列出了面的顶点。矩阵 F 是 D 的子矩阵，由 P* 的一个面的顶点组成。反斜杠调用线性求解器，并找到 P 的顶点。

第 6 步：清理

由于多胞体是在第 2 步翻译的，所以这个翻译用 撤消V = G + repmat(c',[size(G,1),1]);。剩下的两行试图消除重复的顶点（并不总是成功）。