Use the Farkas Lemma to show the face correspondence of an unbounded pointed polyhedron P

Question

Use the Farkas Lemma to show that for every unbounded pointed polyhedron P there is an inequality $a^Tx \leq 1$ such that: $$P' = \{x \in P: a^Tx \leq 1 \}$$ is a polytope with a facet $F′ = {x ∈ P : a^Tx = 1}$, such that k-dimensional faces of F′ correspond to k + 1-dimensional faces of P and k-dimensional faces of P′ that are not faces of F′ are in bijection with the k-dimensional faces of P.

Answer 1

Consider the simplest non-trivial case of $P$: an angle in the plane.

The polytope $P$ has

• $2$-face the interior of the angle $\angle QSR$,
• $1$-faces $\vec{SQ}$ and $\vec{SR}$, and
• $0$-face the point $S$.

Choose $a^Tx = 1$ to be the red line, with $a$ chosen so $a^Tx < 1$ is the left half-plane. Then $P'$ has

• $2$-face the interior of the triangle $\triangle QSR$,
• $1$-faces $\overline{SQ}, \overline{SR}, \overline{QR}$
• $0$-faces the points $S, Q, R$.

$F'$ consists of

• $1$-face $\overline{QR}$ and
• $0$-faces the points $Q, R$.

So the two $0$-faces $Q, R$ correspond to the two $1$-faces $\overline{SQ}, \overline{SR}$ of $P'$, respectively, being the intersection of those two faces with $a^Tx = 1$. Note that $Q$ are $R$ are also $0$-faces of $P'$.

Meanwhile, the other $0$-face of $P'$ is the point $S$, which is also the sole $0$-face of the polytope $P$, which is the bijection they are referring to.

If you still don't see how to proceed, it may help to consider the case of $P$ being a $3$-dimensional polytope, with $a^Tx = 1$ being a plane instead of a line.