Polyhedral cone is defined as $C= \{x \in \mathbb{R}^n \mid Ax \geq 0\}$. Let $C_1$ and $C_2$ be two polyhedral cones in $\mathbb{R}^n$. Show that $C_1+C_2$ is also a polyhedral cone.

My try: Let $x + y \in C_1 + C_2$ we need to show there is a matrix $D$ such that $D(x+y) \geq 0$. To show that we need to use the facts that $x \in C_1 \rightarrow Ax \geq 0$ and $y \in C_2 \rightarrow By \geq 0$ for some appropriate $A$ and $B$.

My question: How can we use $A$ and $B$ to connect them to $D$.


First, $z\in C_1+C_2$ if and only if there are $x,y$ such that $x+y=z$, $Ax\ge0$, $Bx\ge0$. That is, $z$ is the third component of vectors in the cone $$ \left\{ (x,y,z) \in (\mathbb R^n)^3: \pmatrix{I & I & -I \\ -I&-I&I \\ A & 0&0\\0&B&0} \pmatrix{x\\y\\z}\ge \pmatrix{ 0\\0\\0\\0} \right\}. $$ Now use Fourier-Motzkin elimination to compute the projection onto the $z$-component. It follows that $C_1+C_2$ is a polyhedral cone.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.