How to compute the projection of a polyhedron?

Question

Suppose that we have a polyhedron in $(x,y)$:

$$P=\{ (x,y) \mid A_1 x + A_2 y \leq b \}$$

How can I find the polyhedron $P_x = \{ x \mid (x,y) \in P \}$? In other words, I would like to write $$P_x=\{x \mid A_x x \leq b_x\}$$ for some $A_x$ and $b_x$.

Answer 1

There are several software packages around which will do the job for you.

Theoretically, you can solve the problem by Fourier-Motzkin elimination. The idea is to eliminate the existential quantifiers in $\mathbf{P}_\mathbf{x} = \{\mathbf{x}\mid\exists \mathbf{y}: A_1\mathbf{x} + A_2\mathbf{y}\leq \mathbf{b}\}$, where bold letters indicate vectors. Application of Fourier-Motzkin elimination yields the matrix $A_x$ and the vector $\mathbf{b}_x$. Be aware that the matrix and the vector will contain redundant rows in general.

Answer 2

This can be done with the PolyhedralSets package of Maple 2015. Here is an example in two dimensions.

with(PolyhedralSets):
p := PolyhedralSet([3 <= x, 10 <= y+x, x <= 10, y <= x+1]):
Plot(p);

px := Project(p, [x]):
Plot(px);

Display(px);

$$\dots,[y=0,9/2\leq x,x\leq 10],\dots $$

Answer 3

If your projection is $\rho$, then at least one vertex of $P$ is in the preimage (under $\rho$) of any vertex of $P_x$.

As the image of a compact set, we know $P_x$ is simply some interval $[x_0, x_1]$, and by the remark above you can find $x_0$ and $x_1$ as the smallest and largest $x$-coordinates of any vertex of $P$.

Things aren't as simple projecting into higher than $1$ dimension, but it's nice here.