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.
$\begingroup$
$\endgroup$
-
$\begingroup$ Why the anonymous downvote??? It is a valid question and I have upvoted it. $\endgroup$ – Ali Jul 16 '12 at 10:15
-
$\begingroup$ 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). $\endgroup$ – Wolfgang Bangerth Jul 16 '12 at 17:10
$\begingroup$
$\endgroup$
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.
