1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.