1

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
    

任何有助于理解为什么会发生这种情况的事情真的很感激

4

1 回答 1

1

使用 Python 包polytope,可以从多面体的顶点计算凸多面体的半空间表示,如下所示:

从顶点表示到半空间表示

"""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 代码适用于polytope 0.2.3 版本

polytope可以使用包安装程序从Python包索引 (PyPI)安装包pip

pip install polytope
于 2021-06-06T01:45:41.597 回答