unexpected behaivour with polytope package, ( probably a bug , but not sure )

[mvnayagam]

Dear Developers and users,

recently I have been facing an issue with using the polytope package. I have A and b matrixes,

import polytope as PC
import numpy as np
a=np.array([ [-1.0 , -0.  ,-0. , -0.],
                     [ 0. ,  1.  , 0. ,  0. ],
                     [ 0.5, -0.5 , 0.5, -0.5],
                     [ 0.5, -0.5 ,-0.5,  0.5],
                     [ 0.5,  0.5 , 0.5, -0.5],
                    [-0. , -0.  ,-1. , -0. ] ])

b=np.array([-0.33333, 0.3125 , 0.05724, -0.01478, 0.3566 , -0.16667]) 

and create a polytope 'p' as

p=pc.Polytope(a, b)

For this polytope, I get some unwanted numbers when I calculate extreme points as

print(f'pc.extreme(p): \n{pc.extreme(p)}')

This gives

pc.extreme(p): 
[[3.34187e-01 3.00251e-01 3.31721e+13 3.31721e+13]
 [3.33330e-01 2.90870e-01 1.66670e-01 9.46500e-02]
 [3.41820e-01 2.99360e-01 1.66670e-01 9.46500e-02]
 [3.33330e-01 2.99360e-01 1.66670e-01 8.61600e-02]
 [3.33201e-01 3.12896e-01 4.97582e+13 4.97582e+13]
 [3.33330e-01 3.12500e-01 1.66670e-01 1.16280e-01]
 [3.41820e-01 3.12500e-01 1.66670e-01 1.07790e-01]
 [3.33330e-01 3.12500e-01 1.66670e-01 9.93000e-02]]

The polytope seems to be exploding along some directions ( so the values along the 3rd and 4th columns of pc.extreme(p) are 3.31721e+13 ). If I redo the calculation, sometimes the pc.extreme returns

pc.extreme(p): 
[[ 3.33330e-01  3.12500e-01  1.66670e-01  9.93000e-02]
 [ 3.33330e-01  2.99360e-01  1.66670e-01  8.61600e-02]
 [        -inf         -inf          inf          inf]
 [ 3.41820e-01  3.12500e-01  1.66670e-01  1.07790e-01]
 [ 3.41820e-01  2.99360e-01  1.66670e-01  9.46500e-02]
 [ 3.37299e-01  2.97482e-01 -9.95164e+13 -9.95164e+13]
 [ 3.33330e-01  3.12500e-01  1.66670e-01  1.16280e-01]
 [ 3.33330e-01  2.90870e-01  1.66670e-01  9.46500e-02]
 [         inf         -inf          inf          inf]]

In my view pc.extreme(p) contains unwanted or unexpected numbers.

1. Has anyone faced such an issue with the polytope package?
2. How to be sure that the polytope is correct or valid?

because doing

print(f'pc.is_convex(p) :  {pc.is_convex(p)}')
print(f'pc.is_fulldim(p): {pc.is_fulldim(p)}\n')

returns

pc.is_convex(p) :  True
pc.is_fulldim(p): True

But the

print(f'p.bounding_box: \n  {np.array(p.bounding_box)}')

returns

p.bounding_box:
 [[[0.33333]
  [0.29087]
  [0.16667]
  [0.08616]]

 [[0.34182]
  [0.3125 ]
  [    inf]
  [    inf]]]

some weird things are happening with this polytope p or polytope package. Any leads or suggestions are highly appreciated

Thank you for your time on this question

---

Best regards
Muthu Vallinayagam
Research, Institute of Experimental Physics
TU Freiberg
Germany

[slivingston]

You wrote "unexpected numbers". Do you know what the return value of extreme() should be? In particular, do you know whether there is a finite bounding box?

[mvnayagam]

thank you Herr @slivingston for your comment. yes, I know what it should be. The dimension is 4. The aexs range from 0 to 0.5. the bounding box should range up to only 0.18 and 0.12 at maximum., along the 3rd and 4th directions. But I see this is inf.

I am happy to share more info if you need it in any case

thank you

---

Best regards
Muthu Vallinayagam
Research, Institute of Experimental Physics
TU Freiberg
Germany

[necozay]

The polytope given above is unbounded. For unbounded polyhedra, a vertex representation does not exist, hence extreme would not give a reasonable result since we only compute extreme points (but not extreme rays).

If you expect it to have a bounding box with dimensions at most 0.18, 0.12 along the 3rd and 4th direction, you might want to double check how you specify your polytopic constraints.

As a simple counterexample, you can consider the following point:
x = [0.3343 0.3115 20.0000 19.9476]' is inside the polytope (satisfies Ax<=b for the given A and b) but is not within the bounding box you are expecting.

[mvnayagam]

That is the problem I am facing in my program. I try to solve polytope for different orders, let us say order l = 1, 2, 3, 4 ....
for each l there are 2*l**m polytope are generated, where m is the dimension of space. In the present case, it is 4.

The polytope

a=np.array([ [-1.0 , -0.  ,-0. , -0.], [ 0. ,  1.  , 0. ,  0. ], [ 0.5, -0.5 , 0.5, -0.5], [ 0.5, -0.5 ,-0.5,  0.5],
                     [ 0.5,  0.5, 0.5, -0.5], [-0. , -0.  ,-1. , -0. ] ])
b=np.array([-0.33333, 0.3125 , 0.05724, -0.01478, 0.3566 , -0.16667]) 

is the solution space after taking orders l = 1, 2, 3 into the calculation. The intersection operation is used to find the solution space. I opened another discussion #94 , regarding the intersection operation. The above polytope is made using &. still, I have to debug where the problem arises from

finally, I can use pc.bounding_box to get the bound box and say polytope is bounded or open. does polytope provide any other option to cross-check whether a given polytope is bounded or not? like polytope.is_valid?

Thank you

Best regards
Muthu Vallinayagam
Research, Institute of Experimental Physics
TU Freiberg
Germany