Extreme points of a simple polyhedron

Question

Consider the polyhedron given by the set of inequalities \begin{align} \mathbf{b}^T\mathbf{x} ~&\leq~ c \\ \mathbf{e}^T\mathbf{x} - 1 ~&\leq~0 \\ \mathbf{x}~&\geq~0 \end{align} where $\mathbf{x}\in\mathbb{R}^d$, $\mathbf{b}$ is a given element-wise positive vector, $c$ is a given positive constant and $\mathbf{e}$ is the $d-$dimensional all-ones vector.

I am interested in the extreme points of this polyhedron. If the constraint $\mathbf{b}^T\mathbf{x} \leq c$ was not there, it is easy to see that the polyhedron is simply the probability simplex or the standard simplex (basically the convex hull of columns of a $d\times d$ identity matrix $I_d$ and the origin). In that case, the extreme points would indeed be the columns of $I_d$ and the origin, thus $d+1$ extreme points.

When this constraint $\mathbf{b}^T\mathbf{x} \leq c$ is added, I am curious to know whether it is easy to calculate the new set of extreme points. For instance, some of the extreme points will get retained. It is easy to find these by identifying the columns of $I_d$ that satisfy $\mathbf{b}^T\mathbf{x} \leq c$ and those that don't. Is there a simple algorithm to find the newly added extreme points using the ones that were retained and the ones that were removed?

score 4 · Accepted Answer · answered May 08 '21 at 14:56

4

Let's assume that (a) the full polyhedron is not empty (a solution to the inequalities exists) and (b) you have identified the extreme points of the unit simplex that remain extreme points after the new constraint has been added. Any other extreme points will necessarily satisfy the new constraint as an equality ($\mathbf{b}^T\mathbf{x}=c$). Since they are extreme points, at least $d-1$ of the original constraints must also be binding there. So you can look for all feasible solutions of $$\mathbf{b}^T\mathbf{x}=c$$ where all but one component of $\mathbf{x}$ is zero (by enumeration), and then take the system \begin{align*} \mathbf{b}^{T}\mathbf{x} & =c\\ \mathbf{e}^{T}\mathbf{x} & =1 \end{align*} and look for all solutions where $d-2$ components of $\mathbf{x}$ are zero (again, by enumerating the $d \choose 2$ combinations of components that might not be zero).

answered May 08 '21 at 14:56

prubin

39,078
3
37
104

let's say $c=0$, does it allow us to make this approach any faster? – dineshdileep May 09 '21 at 05:12
I don't see how. – prubin May 09 '21 at 22:24
will see if there are some more approaches. Evaluating all those combinations (crudely, $d^2$ complexity) I guess is a bit problematic. Thanks for the answer. Will see if this scales in practice in my problem. – dineshdileep May 10 '21 at 06:35
1

On the bright side, it parallelizes nicely. – prubin May 10 '21 at 15:29

Extreme points of a simple polyhedron

1 Answers1