Relation of vertices of polytopes

46 Views Asked by At

Consider the convex polytope

$$P=\{x\in\mathbb R^n:Ax\leq b, x\geq 0\}$$

for a matrix $A\in\mathbb R^{m\times n}$ and $b\in\mathbb R^m$. Motivated by the usual procedure of transforming a polytope into augmented form, we consider the augmented form of $P$ with

$$Q=\{(x,s)\in\mathbb R^{n+m}:Ax+Is=b,x,s\geq 0\}$$

where $I$ is the $m\times m$ identity matrix.

Naturally, for every element $x\in P$, there is a unique $s$ with $(x,s)\in Q$ (say $s(x)$) and for every $(x,s)\in Q$, we have $x\in P$.

What I am wondering is the following: is $x$ a vertex of $P$ if and only if $(x,s(x))$ is a vertex of $Q$.


One direction is clear to me: let $x$ be a vertex of $P$, then there is an admissible half-plane $\alpha^Ty\leq \beta$ (i.e. $y\in P$ implies $\alpha^Ty\leq \beta$ for any $y$) such that $\{x\}$ is the face induced by the intersection, i.e.

$$y\in P\text{ and }\alpha^Ty\leq \beta\text{ implies }y=x.$$

Then consider the half-plane $\gamma^T(y,s)^T\leq\beta$ in the space $\mathbb R^{n+m}$ with $\gamma^T=(\alpha^T,0)$. The plane is admissible for $Q$ since

$$(y,s)\in Q\text{ implies }y\in P\text{ implies }\gamma^T(y,s)^T\leq\beta$$

using admissibility of $\alpha^Ty\leq \beta$ for $P$. Now, let $(y,s)\in Q$ and $\alpha^Ty=\gamma^T(y,s)^T=\beta$. The former implies $y\in P$ and the together with the latter, we obtain $y=x$ (and thus $s=s(x)$). Therefore, $\{(x,s(x))\}$ is the face induced by the intersection of $Q$ and the $\gamma$, $\beta$ half-plane, i.e. is a vertex.