Assume we know the vertices of a polytope, and want to get its halfspace representation A * x <= b

Question

I want to get halfspace representation A*x <= b, given the vertices of a polytope either python or Matlab.

Let's say vertices = [2 -2; 2 2; -10 2; -10 -2]; are the vertices, I used two different libraries and give two different answers, Not sure, why those give different answers.

• Using 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)
  

  Output :

  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.]
  

• Using Multi-Parametric Toolbox 3 (http://people.ee.ethz.ch/~mpt/3/) (Matlab)

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

  Output:

        >> 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
  

Anything helps to understand why this is happening really appreciate

Answer 1

Using the Python package polytope, a halfspace representation of a convex polytope can be computed from the polytope's vertices as follows:

From vertex representation to halfspace representation

"""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

The halfspace representations given in the question represent the same polytope

The question used two different software packages, and each of these gives a different halfspace representation. As checked with the code below, these two halfspace representations represent the same polytope. The code also shows that they equal the answer obtained above using the Python package 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)

The above Python code works with polytope version 0.2.3.

The package polytope can be installed from the Python Package Index (PyPI) using the package installer pip:

pip install polytope