Unbounded polyhedral Sethas at least one extreme direction

Question

I am asked to prove that an unbounded polyhedral set of the form $\{x : Ax = b, x \geq 0\}$ has at least one extreme direction. and I have a conceptual question of why not $\{x : Ax \geq b, x \geq 0\}$ or $\{x : Ax \leq b, x \geq 0\}$ has at least one extreme direction. I can't figure that out.

Answer 1

Let $X=\{\,x:Ax=b,x\ge 0\,\}$ be unbounded. We only need that $X$ is a non-empty, closed, convex, and unbounded subset of a finite-dimensional real vector space.

Pick $x_0\in X$ and a sequence $\{x_n\}_n$ with $x_n\in X$ and $\|x_n\|\to \infty$ and all $x_n\ne x_0$. The sequence $\{v_n:=\frac{x_n-x_0}{\|x_n-x_0\|}\}_n$ is in the compact unit sphere $S^{n-1}$, hence has a limit point $v\in S^{n-1}$.

I claim that for all $t\ge 0$, the point $x_0+tv$ is $\in X$. Indeed, assume $y:=x_0+t_1v\notin X$. As $X$ is closed, there exists $r>0$ such that $B_r(y)$ is disjoint from $X$. But then for any $n$ with $\|v_n-v\|<\frac r{t_1}$ and $\|x_n-x_0\|>\|y-x_0\|$, we arrive at a contradiction with the convexity of $X$. We conclude that indeed $x_0+tv$ is $\in X$ for all $t\ge 0$, as desired.