Let $ P = \{x \in \mathbb{R}^d:Ax \leq b\}$ be a polyhedron, where $A = \begin{bmatrix} a_1^T\\a_2^T\\...\end{bmatrix}$, then the cone hull of $(a_1,a_2,\cdots)$ is $\mathbb{R}^d$. How to prove this statement?
I think the intuition is pretty clear, but I don't know how to express them in math notations and give a strict proof.
My idea:
- if the polyhedron is not bounded, then it has at least one recession directions
$$ \text{rec} P = \{Ax\leq 0\} \neq \varnothing$$
- For nonzero $y \in \text{rec}P$, there should be $-y\notin \text{cone} (a_1,a_2,\cdots)$
Could someone help me?
Let $C= \{ \sum_k \lambda_k A^T e_k \}_{\lambda \ge 0}$. Note that $C$ is a closed, convex cone.
Suppose $C$ is strictly contained in $\mathbb{R}^d$. In particular, there is some point $y \notin C$.
Hahn Banach shows that there some $h \neq 0$ such that $h^Ty > 0$ and $h^ T (A^T \sum_k \lambda_k e_k) \le 0$ for all $\lambda_k \ge 0$ ($y$ plays no role other than to establish $h \neq 0$). Equivalently, $\lambda^T Ah \le 0$ for all $\lambda \ge 0$, or $Ah \le 0$.
Now note that if $y \in P$, then $x+t h \in P$ for all $t \ge 0$, and so $P$ is unbounded.