0
$\begingroup$

Every feasible solution of P puts an upper(or lower, depending on whether it is a maximization or minimization problem) bound on the optimal solution of D(assuming of course that D has a feasible region to begin with). Does this mean that existence of a feasible solution of P implies the existence of an optimal solution of D? I know that the inverse is true due to Strong Duality theorem.

(P is short for the Primal problem and D for the Dual)

$\endgroup$
3
$\begingroup$

If the Primal problem is feasible, but unbounded in the direction of optimisation, then the dual has no feasible solution. Otherwise, if the Primal problem has an optimal solution, then the dual has also an optimal solution.

So the answer for your question is that feasibility of the Primal problem does not imply optimality for the Dual problem. It just excludes the possibility that the Dual will be unbounded in the direction of optimisation.

$\endgroup$
  • $\begingroup$ What if the Dual does have a feasible solution (Primal problem is bounded in the direction of optimization). Does it ensure the optimality of the Dual in this case? $\endgroup$ – Ojas Feb 25 '15 at 12:55
  • $\begingroup$ Yes, it does. If both have feasible solutions, then both have optimal solutions. $\endgroup$ – Stefan Gyürki Feb 25 '15 at 12:58
  • $\begingroup$ Oh. Yeah, my bad. There were some confusing ideas in my head. Thanks. $\endgroup$ – Ojas Feb 25 '15 at 13:03

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.