Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In weak duality theorem, we assume $x_i$ and $y_i$ are feasible. But how could we show a primal program is unbounded by this theorem?

Suppose we have a primal program: $\max \mathbf c^\top \mathbf x, \mathbf A\mathbf x \leq \mathbf b, \mathbf x \geq 0$ such that: $\mathbf A$ has no rows which are all zero, $\mathbf c$ is not the zero vector, $c_j \geq 0$ for $j=1,\dots,n$ and $a_{ij} \leq 0$ for $i=1,\dots,m$ and $j=1,\dots,n$.

It seems obvious that this LP is always unbounded, but how to apply weak duality here?

share|improve this question

1 Answer 1

Weak duality for maximization problems asserts that the if $\mathbf{p}$ is a feasible solution to the dual problem, and $\mathbf{x}$ is a feasible solution to the primal problem, then

$$\mathbf{p}^{T}\mathbf{b} \geq \mathbf{c}^{T}\mathbf{x}.$$

Unfortunately, the classic corollary in this case states that:

  • If the optimal cost of the primal problem is unbounded, then the dual is infeasible.
  • If the optimal cost of the dual problem is unbounded, then the primal is infeasible.

You want something like the converse of the first statement in the corollary. If you show that the dual is infeasible, then the primal must be unbounded or infeasible by weak duality, and then you just have to show that the primal is feasible.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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