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.
Best Answer
We note that by weak duality, the optimal value of the dual is an upper bound on the value of the primal (in this case, because the primal is a maximization problem). Now the result is immediate: suppose there is a feasible (dual) point. Then the optimal value of the dual is bounded, and hence the primal cannot be unbounded.