假设我们知道多面体的顶点，并且想要得到它的半空间表示a*x<=b

Question

我想得到半空间表示A*x <= b，给定多面体的顶点（python或Matlab）

假设vertices = [2 -2; 2 2; -10 2; -10 -2];是顶点，我使用了两个不同的库并给出了两个不同的答案，不确定为什么它们给出了不同的答案

• 使用https://github.com/stephane-caron/pypoman

    from numpy import array
    from pypoman import compute_polytope_halfspaces
  
    vertices = map(array, [[2,-2],[2, 2], [-10, 2], [-10, -2]])
    A, b = compute_polytope_halfspaces(vertices)
    print(A)
    print(b)
  

  输出：

  A =      [[ -0.00000000e+00  -1.00000000e+00]
               [ -1.00000000e+00  -0.00000000e+00]
               [  4.93432455e-17   1.00000000e+00]
               [  1.00000000e+00  -0.00000000e+00]]
  b = [  2.  10.   2.   2.]
  

• 使用多参数工具箱3（http://people.ee.ethz.ch/~mpt/3/）（Matlab）

    vertices = [2 -2; 2 2; -10 2; -10 -2];
    Xc = Polyhedron(vertices);
  

  输出：

        >> Xc.A
  
        ans =
  
                0   -0.4472
            0.4472   -0.0000
                0    0.4472
        -0.0995   -0.0000
  
        >> Xc.b
  
        ans =
  
            0.8944
            0.8944
            0.8944
            0.9950
  

任何有助于理解为什么会发生这种情况的东西都会让你非常感激

Answer 1

使用Python包^{}，可以从凸多面体的顶点计算凸多面体的半空间表示，如下所示：

从顶点表示到半空间表示

"""How to compute the halfspace representation of a convex polytope.

The polytope is given in vertex representation,
and this script shows how to convert the vertex representation
to a halfspace representation.
"""
import numpy as np
import polytope

vertices = np.array([[2, -2], [2, 2], [-10, 2], [-10, -2]])
poly = polytope.qhull(vertices)  # convex hull
    # `poly` is an instance of the class `polytope.polytope.Polytope`,
    # which is for representing convex polytopes.
    # Nonconvex polytopes can be represented too,
    # using the class `polytope.polytope.Region`.
print('Halfspace representation of convex polytope:')
print('matrix `A`:')
print(poly.A)
print('vector `b`:')
print(poly.b)
# print(poly)  # another way of printing
    # a polytope's halfspace representation

问题中给出的半空间表示表示相同的多面体

这个问题使用了两个不同的软件包 每一个都提供了不同的半空间表示。 如下面代码所示，这两个半空间 表示表示相同的多面体。代码 还表明，它们与上面使用 Python包polytope

"""Showing that the question's halfspace representations are the same polytope.

Any polytope has infinitely many minimal halfspace representations.
The representations below happen to be minimal, and equal up to scaling and
permutation of rows of `A` and elements of `b`.
"""
import numpy as np
import polytope

# halfspace representation computed using `polytope`
# from the vertex representation given in the question
vertices = np.array([[2, -2], [2, 2], [-10, 2], [-10, -2]])
poly = polytope.qhull(vertices)
# first halfspace representation given in the question
A = np.array([
    [-0.00000000e+00, -1.00000000e+00],
    [-1.00000000e+00, -0.00000000e+00],
    [4.93432455e-17, 1.00000000e+00],
    [1.00000000e+00, -0.00000000e+00]])
b = np.array([2., 10., 2., 2.])
question_poly_1 = polytope.Polytope(A, b)
# second halfspace representation given in the question
A = np.array([
    [0.0, -0.4472],
    [0.4472, -0.0000],
    [0.0, 0.4472],
    [-0.0995, -0.0000]])
b = np.array([0.8944, 0.8944, 0.8944, 0.9950])
question_poly_2 = polytope.Polytope(A, b)
# check that all the above halfspace representations
# represent the same polytope
assert poly == question_poly_1, (poly, question_poly_1)
assert poly == question_poly_2, (poly, question_poly_2)

上面的Python代码与polytopeversion 0.2.3一起使用

包polytope可以使用包安装程序^{}从Python Package Index (PyPI)安装：

pip install polytope