Consider a bounded polyhedron $P$, and a dimension reducing projection $\Omega$ (ie a linear operator $\Omega$ such that $\Omega^2 = \Omega$), claim: if $u$ is an extreme point of $P$ then $\exists \Omega$ such that $\Omega u$ is an extreme point of $\Omega P$


Intuitively this feels obvious, I can take any polytope, consider any vertex, and there always seems to be a "right way" to look at the shape, so that if I were to squash the shape along an axis perpendicular to the axis-of-sight I end up with a lower dimensional shape that ALSO has an extreme point induced by original extreme point.

Perhaps some more formal intuition: we have that every vertex in the projection $\Omega P$ is the projection of a vertex in $P$, not immediately helpful but it gives us an idea to work with.

So my attempt at a proof:

Consider such a point $u$. There will be a collection of inequalities (at least $n$ if we are in $\mathbb{R}^n$ ) that are tight for this point. That is

$$ a_1^T u = b_1 \\ a_2^T u = b_2 \\ \vdots \\ a_n ^T u = b_n $$

Of course this can be rephrased as

$$ A^T u = B$$

Now Suppose the general polyhedron of which $u$ is an extreme point is:

$$ Cx \le d $$

Now what I want to do, but don't know how to express mathematically, is that I want to compute an abstract projection of this polyhedron $\Omega(Cx \le d)$ , then I want to compute the same abstract projection of $A^T$, reason that none of the inequalities of the $\Omega A^T$ subset of $\Omega C$ is redundant, and then show that $ \Omega u$ is tight for them, letting me conclude that that $\Omega u$ is an extreme point of projected polyhedra.

But formally, I don't know how to express that. And it may not even be the best way.

  • $\begingroup$ Is your polyhedron convex? $\endgroup$ – Hagen von Eitzen Aug 10 '16 at 5:57
  • $\begingroup$ Yes, it is convex $\endgroup$ – frogeyedpeas Aug 10 '16 at 6:11

Take a vector $n \in \mathbb{R}^n$ such that $$n^\top u > n^\top p \qquad\forall p \in P\setminus\{u\}.$$ Such an $n$ exists since every extreme point of a polytope is exposed.

Then, you use $$\Omega(x) := (n^\top x) \, n.$$


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.