Exercise 2.22 (Sum of polyhedra)

By definition, we can write $P=\{x\in {\Re }^n\mid Ax\ge b\}$ for some $m\times n$ matrix $A$ and $b\in {\Re }^m$; similarly, $Q=\{x\in {\Re }^n\mid Cx\ge d\}$ for some $m^{\prime }\times n$ matrix $C$ and $d\in {\Re }^{m^{\prime }}$.

(a)

Proof. We employ the following trick that will allow us to use the Fourier-Motzkin elimination algorithm. Notice that the Cartesian product of $P$ and $Q$ is a polyhedron in ${\Re }^{2n}$:

$$\begin{array}{llll}\hfill P\times Q& =\left\{\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \end{array}\right]\in {\Re }^{2n}|\begin{array}{c}x\in P\hfill \\ y\in Q\hfill \end{array}\right\}=\left\{\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \end{array}\right]\in {\Re }^{2n}|\begin{array}{c}Ax\ge b\hfill \\ Cx\ge d\hfill \end{array}\right\}& \hfill & \\ \hfill & =\left\{\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \end{array}\right]\in {\Re }^{2n}|\left[\begin{array}{cc}\hfill A\hfill & \hfill C\hfill \end{array}\right]\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \end{array}\right]\ge \left[\begin{array}{c}\hfill b\hfill \\ \hfill d\hfill \end{array}\right]\right\}& \hfill & \end{array}$$

Therefore, the following extension of $P\times Q$ to ${\Re }^{3n}$ must be a polyhedron as well:

$$Z:=\left\{\left[\begin{array}{c}\hfill x+y\hfill \\ \hfill x\hfill \\ \hfill y\hfill \end{array}\right]\in {\Re }^{3n}|\begin{array}{c}x\in P\hfill \\ y\in Q\hfill \end{array}\right\}=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill \end{array}\right]P\times Q.$$

Applying the Fourier-Motzkin elimination algorithm $2n$ times, we see that the resulting projection

$${\mathrm{\Pi }}_n(Z)=P+Q$$

is a polyhedron as well. □

(b)

Proof. Suppose for the sake of contradiction that we can find an extreme point of $P+Q$ which is the sum of two points $x+y$ at least one of which is not an extreme point. In case that $x$ is not an extreme point, we can find two vectors $p,p^{\prime }\in P$ (both different from $x$), and a scalar $\lambda \in [0,1]$, such that $x=\lambda p+(1-\lambda )p^{\prime }$. Using this, we can write

$$x+y=\lambda p+(1-\lambda )p^{\prime }+y=\lambda \left(p+y\right)+(1-\lambda )\left(p^{\prime }+y\right).$$

But that means that we have found two distinct vectors $p+y$ and $p^{\prime }+y$ in $P+Q$, both different from $x+y$, such that our extreme point is a convex combination of these two vectors. This is a contradiction to the assumption that $x+y$ is an extreme point.
The case when $y$ is not an extreme point of $Q$ follows similarly. □