Linear Encodings for Polytope Containment Problems
Linear Encodings for Polytope Containment Problems
复制标题
多面体包含问题的线性编码
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Russ Tedrake
中科院分区：
文献类型：
--
作者：
Sadra Sadraddini;Russ Tedrake
多层控制问题是确定多层室是否包含在另一个多型中。复杂性在很大程度上取决于如何表示多面体。虽然当可用的平面有效地遏制多层膜（H-Polytopes）时，存在有效的必要条件（H-Polytopes），但当多型由H-聚植物的仿射转化表示时，我们将其称为AH-Polytopes，已知是CO的。 -NP完整。在本文中，我们为Ahpolytope问题中的AH-Polytope提供了足够的条件，可以将其作为一组线性约束，其尺寸与每个多层人群的超平面数量线性增长。这些有效的编码使我们能够将多面体的某些组成部分指定为决策变量，并将其纳入凸优化问题。我们介绍了结果对应用程序遏制问题的应用的有用性，计算多型Hausdorff距离以及找到对多型正交投影的内部近似值。包括说明性的例子。
The polytope containment problem is deciding whether a polytope is a contained within another polytope. The complexity heavily depends on how the polytopes are represented. While there exists efficient necessary and sufficient conditions for polytope containment when their hyperplanes are available (H-polytopes), the case when polytopes are represented by affine transformations of H-polytopes, which we refer to as AH-polytopes, is known to be co-NP-complete. In this paper, we provide a sufficient condition for AH-polytope in AHpolytope problem that can be cast as a linear set of constraints with size that grows linearly with the number of hyperplanes of each polytope. These efficient encodings enable us to designate certain components of polytopes as decision variables, and incorporate them into a convex optimization problem. We present the usefulness of our results on applications to the zonotope containment problem, computing polytopic Hausdorff distances, and finding inner approximations to orthogonal projections of polytopes. Illustrative examples are included.