We tackle the problem of efficiently approximating the volume of convex polytopes, when these are given in three different representations: H-polytopes, which have been studied extensively, V-polytopes, and zonotopes (Z-polytopes). We design a novel practical Multiphase Monte Carlo algorithm that leverages random walks based on billiard trajectories, as well as new empirical convergence tests and a simulated annealing schedule of adaptive convex bodies. We present a detailed experimental evaluation of our algorithm using a rich dataset containing Birkhoff polytopes and polytopes from structural biology. Our open-source implementation tackles problems that have been intractable so far, offering the first software to scale up in thousands of dimensions for H-polytopes and in the hundreds for V- and Z-polytopes on moderate hardware. Last, we illustrate our software in evaluating Z-polytope approximations.
翻译：我们解决了高效接近 convex 聚顶体体积的问题,这体现在三个不同的表述中: H-polytop, 已经广泛研究过, V-polytops 和 zonoopes (Z-polytops ) 。 我们设计了一个新型实用的多阶段蒙特卡洛 算法, 利用台球轨迹来利用随机行走, 以及新的实验性趋同测试和适应性 convex 体的模拟穿透时间表。 我们用包含 Birkhoff 多元形和结构生物学多面的丰富数据集对我们的算法进行了详细的实验性评估。 我们的开源执行解决了迄今为止一直难以解决的问题, 为H-polytops提供了以数千维为尺度的首个软件, 为中度硬件的 V- 和 Z- polytops 提供了数以百 个大小的软件。 最后, 我们用软件来评估 Z-polytope 近似值。
相关内容
微信扫码咨询专知VIP会员