Sum of two polyhedra is a polyhedron I'm reviewing for a midterm next week in an optimization course. Currently, I'm having a great deal of trouble with a review problem. The problem is as follows:
Let P and Q be polyhedra in R^n. Let P+Q = {x + y | x in P and y in Q}.
(a) Show that P+Q is a polyhedron
(b) Show that every extreme point of P+Q is the sum of an extreme point of P and an extreme point of Q.
First, I know this question has been asked on here before, but, due to the OP's lack of info, it went pretty much unanswered.
My attempt has been as follows:
My professor says P is a polyhedron if P can be written in the form P = { x in Rn | ai'x >= bi, for i = 1,...,m} equivalently, if A is the matrix with row vectors ai, we have P = {x in Rn | Ax >= b}.  So a polyhedron is the intersection of a finite number of half spaces. However, after this, I'm entirely lost.
I have that z = x+y, but cannot begin to show how or why the sum of any arbitrary x from P and y from Q must lie in a polyhedron. I tried to show that z satisfied (ai+hi)*z >= bi + gi, ai and hi are the constraints that x and y satisfy respectively, but I don't think that is true. Any advice as to how I could approach this problem / what is wrong with my approach would be greatly appreciated.
 A: a) 
Let $P=\{x|Ax\ge a\}, Q=\{y|By\ge b\}$.
Now define $M=\{(x,y,z)|Ax\ge a, By \ge b, z=x+y\}$.
$P+Q$ is the projection of $M$ on the $z$ coordinates, therefore a polyhedron.
b)
We want to show that $x$ must be an extreme point in $P$, if $z=x+y$ is an extreme point in $P+Q$
First let's assume that $x$ is not an extreme point in $P$, i.e. there are $x_1,x_2\in P\backslash\{x\}$ and $0<\lambda<1$ s.t.
$$\lambda x_1 + (1-\lambda) x_2 = x$$
Since $x_1, x_2\in P$, also $z_1:=x_1+y, z_2:=x_2+y\in P+Q$ (this is how $P+Q$ is defined).
As you might have guessed, $\lambda z_1 + (1-\lambda) z_2 = z$ (it's easy to check this, just replace the $z_1, z_2$ with their definition, expand and simplify).
But wait, we depicted $z$ as a linear combination of elements of $P+Q$(to be formally correct: $0<\lambda<1,\;z_1,z_2\in (P+Q)\backslash\{z\},\;\lambda z_1+(1-\lambda)z_2 = z$)
Hence $z$ cannot be an extreme point in $P+Q$.
So we showed if $x$ is not an extreme point in $P$, then $z=x+y$ cannot be an extreme point in $P+Q$.
Apply the contraposition and you're done: If $z=x+y$ is an extreme point in $P+Q$ then $x$ is an extreme point in $P$.
Note that $x, P$ and $y, Q$ are mutually interchangable.
A: My answer for (a):
Let $C = \{(x, y) \mid x \in P, y \in Q\}$, clearly, $C$ is a polyhedron.
Define a linear transformation $T: R^n \times R^n \to R^n$ by $T(x, y) = x + y$. Then $P+Q$ is the image of $C$ under $T$.
By theorem 19.3 in convex analysis, R.T. Rockfeller, we conclude $P+Q$ is a polyhedron.
