Polytope, Python - 寻找极值点

Question

我需要找到由矩阵关系 Ax <= b 给出的多胞形的所有极值点的列表，其中 x 为非负数。我知道 100% 的时间，多胞体是非退化的。我使用的第一个解决方案是生成一个运行dom 非负向量和运行一个 LP，向量是 objective 函数（所以基本上；在运行dom 中优化方向）。这当然有很多问题：花了大量的时间，最后我不能确定解决方案是否正确。

然后我尝试使用polytope工具箱；使用 'extreme' 函数。我运行在一个我已经很熟悉的实例上：

import numpy as np
import polytope as pc
    
A = np.array([[0,1,0,1,0], [0,0,1,0,1], [1,0,0,0,1], [0,1,1,0,0], [1,0,0,0,0]])
K = A - A.transpose()
C = np.vstack( (K, -np.eye(5) , [1]*5)

p = pc.Polytope(C, [0]*10+[1])
print(pc.extreme(p))

我期望的输出是 (.5, .5, 0, 0, 0), (0, 1/3, 1/3, 1/3, 0) 和 (0, 0, 0, 0 , 0).但是，我只得到一个None。我看到存储库中有一个关于使用 extreme() 的 example，但我看不出我做错了什么。

附带说明一下，如果您有其他库可以解决这个问题（在多面体中找到极值点），我很乐意接受。

Answer 1

您的问题不清楚（请参阅我的评论），但您应该使用 pycddlib。我试过了，结果接近你的期望：

import numpy as np
import cdd as pcdd

A = np.array([[0,1,0,1,0], [0,0,1,0,1], [1,0,0,0,1], [0,1,1,0,0], [1,0,0,0,0]])
K = A - A.transpose()
C = np.vstack( (K, -np.eye(5), [1]*5) )
b = [[0]]*10 + [[1]]
M = np.hstack( (b, -C) )


mat = pcdd.Matrix(M, linear=False, number_type="fraction") 
mat.rep_type = pcdd.RepType.INEQUALITY

poly = pcdd.Polyhedron(mat)
ext = poly.get_generators()
print(ext)

给出：

 1 1/3 0 1/3 1/3 0
 1 0 0 0 1/2 1/2
 1 0 0 0 0 0

第一列中的“1”表示该行代表一个极值点。

Polytope, Python - 寻找极值点

Polytope, Python - find extreme points

python

geometry

mathematical-optimization