If $P$ is an unbounded polyhedron, there exists a point $c \in P$ and a vector $d \neq 0 $ such that $ \forall \lambda \geq 0$, $c+ \lambda d \in P$

Question

If $P$ is an unbounded polyhedron, there exists a point $c \in P$ and a vector $d \neq 0 $ such that $ \forall \lambda \geq 0$, $c+ \lambda d \in P$.

Hi so I dont know if this is true or not, intuitively it made sense to me because in an unbounded polyhedron there is somewhere where we can go to "infinity".

Im asking if my formulation is correct, or if there is a way to make my formulation correct.

I tried proving this statement the following way:

Assuming the second part is false, then there exists a maximal $\lambda$ for which the statements holds, lets call it $k$.

Define $Z:= \max \{c+ \lambda d \mid c \in P ,\; 0 \leq \lambda \leq k,\; c+ \lambda d \in P \} +1$.

Now i want to show that the distance of two arbitrary points in $P$ is smaller than $Z$.

Let $a ,b \in P$. Look at $a+(b-a)$ this is clearly in the Set we described so $|a-b| <Z$ and we are done.

Is this proof correct ?

Answer 1

Take $z$ in the polyhedron $\cal P$. Since $\cal P$ is unbounded there exists a sequence $(v_i)_i$ of vectors such that $z + v_i\in\cal P$ and $\Vert v_i\Vert\to\infty$. We can assume $\Vert v_i\Vert > 0$ for all $i$. Then $u_i = v_i/\Vert v_i\Vert\in B[0,1]$, the closed ball of radius $1$. Since this ball is compact, there exists a convergent subsequence $u_{i_k}\to u\in B[0,1]$.

Say $\cal P$ is defined by the matrix inequality $Ax\preceq b$. We have \begin{align*} Au & = \lim_k Au_{i_k}\\ & = \lim_k \frac{1}{\Vert v_{i_k}\Vert} Av_{i_k}\\ & = \lim_k \frac{1}{\Vert v_{i_k}\Vert} (A(z+v_{i_k}) - Az)\\ & \preceq \lim_k \frac{1}{\Vert v_{i_k}\Vert}(b - Az) &&; z+v_{i_k}\in\cal P\\ & = 0. \end{align*} Thus, $u\ne0$, $Au\preceq0$ and $$ A(z+\lambda u) = Az + \lambda Au\preceq b + 0 = b. $$ So $z+\lambda u\in\cal P$ for all $\lambda >0$. In other words,

If $\cal P$ is an unbounded polyhedron, for every $z\in\cal P$ there exists a ray with origin in $z$ included in $\cal P$.

Answer 2

A possible proof sketch, by contradiction.

Suppose there is no such line. Pick some point $c$ in $P$. Then every line through $P$ meets $P$ in a segment. The length of that segment varies continuously with the direction of the line so can be thought of as a function on the $n-1$ sphere centered at $c$. Since it's a continuous function on a compact set, it is bounded, so $P$ is bounded.

This argument shows that all you need to know about $P$ is that it's convex (it need not be a polytope). Then you can start at any $c$ and find an umbounded ray in $P$/