Extreme points from constraint expression of convex space

Question

I'm looking for the extreme points of the convex set $S\subset [-1,1]^{n\times 3}$ with $r\in S$ such that \begin{equation} r_{i} \ge r_{k} \iff i\ge k, \end{equation} where the first inequality refers to lexicographical inequality in $\mathbb{R}^3$, and \begin{equation} \sum_i^n r_i = 0 \end{equation} It was easy to characterize the extreme points satisfying only the first set of constraints. The second set has proven to be more difficult and I don't want to waste my time when there's already a solution out there.

Are there any program packages or methods out there that would easily solve this problem? If so, what are they?

Answer 1

The most reputable-looking source I could find was

M. E. Dyer, L. G. Proll. An algorithm for determining all extreme points of a convex polytope, Mathematical Programming, Vol. 12, Issue 1, p. 81-96.

The problem is likely only solvable for the case of convex polyhedra; there is a theorem that states that convex polyhedra can be expressed in terms of a convex combination of a finite number of extreme points and a finite number of extreme rays. No such claim can be made about convex sets in general.

The algorithm runtime will be exponential in the dimensionality of the polyhedron. To enumerate all of the vertices of an $n$-cube, all $2^n$ vertices must be enumerated. The problem is probably NP-hard.