如何找到多面體的所有頂點


5

我有一個由一組線性不等式給出的凸多面體,例如:

$$x_1 \ geq 0,~~ x_2 \ geq 0,~~ x_3 \ geq 0\\x_1 + x_2 \ leq 1,~~ x_2 + x_3 \ leq 1,~~ x_3 + x_1 \ leq 1$$ 我想列出多面體的所有極端。在這種情況下,這些要點是: $$(0,0,0),~~(1,0,0),~~(0,1,0),~~(0,0,1),~~(1 / 2,1 / 2,1 / 2)$$

在python中,有幾個線性編程庫,例如scipy.linprog或cvxpy,可以使用Simplex方法返回一個這樣的極值點。但我想列出所有這些。我該怎麼辦?

6

The problem of enumerating all vertices of a polytope has been studied, see for example Generating All Vertices of a Polyhedron Is Hard by Khachiyan, Boros, Borys, Elbassioni & Gurvich (available free online at Springer's website) and A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets by T. H. Matheiss and D. S. Rubin. That's a pretty old survey though (1980), so newer methods may be available.

A naive brute force approach can be deduced from the definition of vertex/extreme point. Let's call the polytope $P$. Pseudocode can be as follows:

  1. Select a subset of $n$ inequalities (in you example $n = 3$), getting a smaller linear system of inequalities with submatrix $A'$ and vector $b'$.

  2. Solve the linear system $A'x = b'$. There are three cases here:

    a. The system has no solution: Then, return to (1) and select another subset (not chosen before).

    b. The system has no unique solution: Then, $A'$ is linearly dependent. Return to (1) and select a new subset.

    c. The system has a unique solution: If that solution is feasible for $P$, then it's a vertex. Go back to (1).

The algorithm ends when no new subsets can be chosen. Note that different subsets of rows could yield the same vertex.

A second alternative can be treating the polyhedron's vertices and edges as a graph (might work faster than the brute force solution above):

  1. Start at any vertex $x$ of the polytope. For example, the one you found using the Simplex, Interior Point or Ellipsoid method with some cost function.
  2. Find all $P$'s edges incident to $x$. That is, all 1-dimensional faces of $P$. This can be done similar to pivoting on nonbasic variables (with respect to the current vertex). Note that vertices are 0-dimensional faces of $P$.
  3. Explore this graph (with the analogy of vertices and edges) using breadth-first search or depth-first search.

As @batwing mentioned, another alternative is using the Double Description Method by Motzkin et al. to generate all extreme points and extreme rays of a general convex polyhedron represented as a system of linear inequalities $Ax \leq b$. An implementation called cdd can be found at Komei Fukuda's website here, while this GitHub repo contains pycddlib, a Python wrapper to interact with that library. Finally, at this repo the package pypoman is developed to interact with the Python wrapper to get the extreme points for $Ax \leq b$ starting from $A$ and $b$.


2

It seems to me that cdd libraries can be useful to solve this problem. Description is available at cdd. There is an implementation of this function in R: rcdd. You can use the following instruction to solve this problem:

install.packages("rcdd")
require(rcdd)
scdd(makeH(rbind(-diag(3),c(1,1,0),c(0,1,1),c(1,0,1)),c(rep(0,3),rep(1,3))))