Constructing a direction of unboundedness of a linear program I think if a linear program is unbounded, there is a direction of unboundedness.
Consider a linear program,
$$\min \{ cx \mid Ax = d, x \geq 0\}$$
Given that the linear program is feasible and unbounded, I want to explicitly construct a direction of unboundedness $y$ such that

*

*$cy < 0$

*$Ay = 0, y \geq 0$.

I have tried to use the difference of two feasible solutions $x' - x$ such that $x' \geq x$ as a direction. However, this is implicitly using a direction of unboundedness. What are other ways to construct a direction of unboundedness?
 A: I claim that if $\{cx \mid Ax = d, x \geq 0\}$ is non-empty and without lower bound, then $\{cx \mid Ax = 0, x \geq 0\}$ (which is necessarily non-empty) must be without lower bound.
In particular, because $\{cx \mid Ax = d, x \geq 0\}$ has no lower bound, weak duality implies that the dual optimization problem
$$
\max\{d^Tz \mid A^Tz \leq c^T\}
$$
must be completely infeasible. That is, $A^Tz \geq c^T$ has no solutions. But this implies that the optimization problem
$$
\max\{0^Tz \mid A^Tz \leq c^T \}
$$
is also infeasible. Strong duality implies that this could only occur if the corresponding primal problem, $\min\{cx \mid Ax = 0, x \geq 0\}$, is feasible without lower bound.
It immediately follows that there exists a $x' \in\{x \mid Ax = 0, x \geq 0\}$ with $cx' < 0$. Taking $y = \frac{x'}{\|x'\|_1} = \frac{x'}{1^Tx'}$ gives us the desired "direction of unboundedness".

An alternative proof for the existence of such a $y$:
We note that $\{cx \mid Ax = d, x \geq 0\}$ is unbounded below, and the the feasible set $F = \{x \mid Ax = d, x \geq 0\}$ is convex. Let $x_0 \in F$.
For any $k < cx_0$, there exists an $x$ with $cx \le k$. By convexity and linearity, we see that $x_0 + t\frac{x - x_0}{\|x - x_0\|_1} \in F$ for $0 \le t \le \|x - x_0\|_1$. Moreover, since $cx < k$, we have
$$
cx_0 - k = c(x_0 - x) \le \|c\|_\infty \|x_0 - x\|_1 \implies \|x - x_0\|_1 \ge \frac{cx_0 - k}{\|c\|_\infty}.
$$
Now, for any $n \in \Bbb N$, define
$$
C_n = \left\{\frac{x - x_0}{\|x - x_0\|_1} \mid cx \le -n\right\}.
$$
The sets $C_1,C_2,\dots$ form a nested sequence of compact subsets of $\{x:Ax = 0\}$. It follows that their intersection $C = \bigcap_{n \in \Bbb N}C_n$ is non-empty.
Thus, there exists a $y$ for which $\|y\|_1 = 1$, $x_0 + ty \in F$ for all $t \geq 0$, and $c(x_0 + ty)$ is decreasing over $t$.
To argue that $y \geq 0$, it suffices to note that if this were not the case, then it would be impossible to have $x_0 + ty \in F \subset \{x:x \geq 0\}$ for all $t \geq 0$.
