Constructing a direction of unboundedness of a linear program

Question

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

1. $cy < 0$
2. $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?

Answer 1

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