10

我在欧几里得空间（3D，但想要 nD 的答案）中有一个凸集，其特征是有限的半空间集（法线向量 + 点）。

是否有更好的算法来找到凸集的极值点，而不是计算蛮力所有是 3 个（或，n）半空间的交点并消除那些不是极值点的点？

4

2 回答 2

6

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

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

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

输入由一组形式为 的线性不等式组成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]);. 剩下的两行试图消除重复的顶点（并不总是成功）。

于 2016-01-06T00:59:43.027 回答
2

我是polco的作者，这是一个实现“双重描述方法”的工具。众所周知，双重描述方法适用于许多退化问题。它已被用于计算数以千万计的生成器，主要用于计算系统生物学问题。

该工具用 Java 编写，在多核 CPU 上并行运行，并支持各种输入和输出格式，包括文本和 Matlab 文件。您可以通过给定的苏黎世联邦理工学院大学系链接找到有关该软件和双重描述方法的更多信息和出版物。

于 2016-10-18T22:21:47.093 回答