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

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

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

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