4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ let's say $c=0$, does it allow us to make this approach any faster? $\endgroup$ May 9 at 5:12
  • $\begingroup$ I don't see how. $\endgroup$
    – prubin
    May 9 at 22:24
  • $\begingroup$ 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. $\endgroup$ May 10 at 6:35
  • 1
    $\begingroup$ On the bright side, it parallelizes nicely. $\endgroup$
    – prubin
    May 10 at 15:29

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.