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?


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.

| cite | improve this answer | |
  • $\begingroup$ I was afraid of that. I had various versions; some more efficient than others. The big jump is going from three to four points. I don't have access to that article right now, but the abstract suggests it contains what I need (and that I may have had the right general idea). $\endgroup$ – Deathbreath Jan 4 '13 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.