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 ?

  • $\begingroup$ The negation of the statement in the question is that there for all $c,d$ there exists a $\lambda \ge 0$ such that $c+\lambda d \notin P$. So $\lambda$ depends on $c$ and $d$, and there is not obviously a maximum such value. $\endgroup$ – preferred_anon Nov 6 '19 at 20:52
  • $\begingroup$ @preferred_anon Thank you, I guess im wrong, any idea how i should proceed ? $\endgroup$ – user389647 Nov 6 '19 at 20:54
  • $\begingroup$ What is your definition of "unbounded polyhedron"? $\endgroup$ – Math1000 Nov 7 '19 at 3:01
  • 1
    $\begingroup$ Your proof is not correct, but the result seems to be true. $\endgroup$ – Leandro Caniglia Nov 30 '19 at 17:56

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$.


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$/

  • $\begingroup$ You are right, the key is compactness and continuity. $\endgroup$ – Leandro Caniglia Dec 1 '19 at 14:08

Your Answer

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