Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 3 down vote favorite

Assume the optimal value of a primal problem is bounded. Is the following statement true?

  • If the primal problem is bounded, then its dual problem is bounded as well.
share|improve this question
Why the anonymous downvote??? It is a valid question and I have upvoted it. – Ali Jul 16 '12 at 10:15
You are asking whether it is true that the duality gap of a linear optimization problem is always finite. I don't recall the answer but you should be able to find it in books on linear optimization in generality (where you will first find under which condition the duality gap is zero, and you can generalize from the case where the duality gap is nonzero to ask whether there are cases where the duality gap is infinite). – Wolfgang Bangerth Jul 16 '12 at 17:10

1 Answer

up vote 4 down vote

No. The primal LP min $x+y$ subject to $x-y\ge 0$ has no bounded objective.

Instead, one must assume boundedness of the primal and dual problem as a hypothesis, and then gets the result that both problems are solvable and their values agree.

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.