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$

1 Answer 1

Reset to default
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$
3
  • $\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, 2015 at 12:55
  • $\begingroup$ Yes, it does. If both have feasible solutions, then both have optimal solutions. $\endgroup$
    – Stefan Gyürki
    Feb 25, 2015 at 12:58
  • $\begingroup$ Oh. Yeah, my bad. There were some confusing ideas in my head. Thanks. $\endgroup$
    – Ojas
    Feb 25, 2015 at 13:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .