2

We know that every point in a feasible region $(X)$ of a Linear Program can be represented as a convex combination of the extreme points of $X$ plus a non-negative combination of the extreme directions of $X$. I solved a linear program in $R^{4}$ and got four extreme points and six extreme directions, and then I was asked to represent a point $x^{*}$ using these Extreme points and directions. This will leave me with $10$ unknowns ($4$ weights for each extreme point, along with $6$ scalar unknowns for each extreme direction), while having at most $5$ equations (including the convexity constraint of the summation of convex weights to $1$). Is there a generic way to do this, or just by trial and error?

For instance, I got the following four extreme points: $$x_{1} = (0,1,0,1)$$ $$x_{2} = (0,1,0,0)$$ $$x_{3} = (0,0,0,1)$$ $$x_{4} = (0,0,0,0)$$ and the following $6$ extreme directions: $$d_{1} = (0,4/7,2/7,1/7)$$ $$d_{2} = (1/3,1/3,0,1/3)$$ $$d_{3} = (0,0,2/3,1/3)$$ $$d_{4} = (1/2,0,0,1/2)$$ $$d_{5} = (0,0,1,0)$$ $$d_{6} = (1,0,0,0)$$ and I was asked to represent $x^{*} = (1,1,1,2)$.

M47145
  • 4,106
rodrigo
  • 171

1 Answers1

1

The problem can be formulated and solved as a linear program.

Enumeration of the extreme points $\mathbf{x}_1$, ..., $\mathbf{x}_n$ and rays $\mathbf{d}_1$, ..., $\mathbf{d}_m$ yields a $\mathcal{V}$-representation (vertex-representation) of the polyhedron (feasible region) $X$. Just write down two matrices $V$ and $R$, where the rows of $V$ are the vertices $\mathbf{x}_1$, ..., $\mathbf{x}_n$ and the rows of $R$ are the rays $\mathbf{d}_1$, ..., $\mathbf{d}_m$. That is $X=\{\mathbf{x}\mid V\mathbf{u} + R\mathbf{v} = \mathbf{x}, \mathbf{u} \geq \mathbf{0}, \mathbf{1}^T\mathbf{u} = 1, \mathbf{v} \geq \mathbf{0}\}$.

Now, you ask whether some given $\mathbf{x}^*$ is contained in $X$, i.e, find a feasible solution $(\mathbf{u}_0, \mathbf{v}_0)$ of

$\quad$ $V\mathbf{u} + R\mathbf{v} = \mathbf{x}^*, \mathbf{u} \geq \mathbf{0}, \mathbf{1}^T\mathbf{u} = 1, \mathbf{v} \geq \mathbf{0}$.

This can easily be done by linear programming.

Note that the vector $\mathbf{u}_0$ encodes the coefficients of the convex combination of the vertices and the vector $\mathbf{v}_0$ encodes the coefficients of the conical combination of the rays.

Willem Hagemann
  • 618