Compute H-representation of a polytope after projection onto lower-dimensional space

370 Views Asked by At

For a convex polytope described by many equalities and inequalities: $P = \{(x,y): Ax + By \leq c, Dx+Ey = f\}$, can we get H-representation of the polytope $Q$ after projecting $P$ to x-space. In other words: $Q = \{x: \exists~y:Ax + By \leq c, Dx+Ey = f \}$. I vaguely recall that I learnt some theorems claiming there exists a finitely many half spaces describing $Q$.

Consider a more general setting that matrix $E$ is not square and not full column/row rank.

Is this a well-studied problem (what is its name?) If we cannot get H-representation of $Q$ by simple linear algebra, I'm pretty sure we can do this numerically, any famous algorithms?

1

There are 1 best solutions below

2
On BEST ANSWER

You can use Fourier-Motzkin elimination (see e.g. https://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination) for this task. The method is simple but slightly above linear algebra since it respect linear inequalities.

The method is exact and effective but not efficient as it may produces several redundant inequalities. Finding more efficient methods is still a topic of current research.