# Prove a property of primal-dual problems

When I was studying the computation aspects of quantile regression, I consulted some linear programming book and found an interesting property as follows:

If the primal problem have unbounded solutions, then the dual problem doesn't have feasible solution.

Formally, if let (P) denote the following primal linear programming problem:

$$\max z = c^Tx$$ $$\text{subject to } Ax \leq b, x \geq 0$$ where $A \in \mathbb{R}^{m \times n}$, $c, x \in \mathbb{R}^n$, $b \in \mathbb{R}^m$, in addition, we can assume each component of $b$ is strictly positive, namely, $b > 0$.

Then its dual problem (D) has the form: $$\min w = b^Ty$$ $$\text{subject to } A^Ty \geq c, y \geq 0$$

The assertion is that if there are feasible solutions $x$ of (P) such that drive $c^Tx$ arbitrarily large (for which case the constraint set is unbounded), then there is no feasible solution for problem (D). The textbook provided some "proof" which can't quite satisfy myself.

My thought is going to prove by contradiction: given the existence of unbounded solution for (P), clearly, $y^Tb$ can be arbitrarily large, I want to combine this fact with the constraint $y \geq 0$ to derive some inconsistency of the system $A^Ty \geq c$. While this seems always possible under low dimension setting, how to prove this rigorously for the general setting? Thanks in advance.

• @Glen_b Thank you. I think I got this by myself. – Zhanxiong Feb 7 '15 at 16:10