3
$\begingroup$

For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different:

Weak duality: If $\bar{x}$ is a feasible solution to $(P)$ and $\bar{y}$ is a feasible solution to $(D)$, then:

  1. $c^T \bar{x} \le b^T\bar{y}$
  2. if equality holds in the above inequality, then $\bar{x}$ is an optimal solution to $(P)$ and $\bar{y}$ is an optimal solution to $(D)$.

Strong duality: If there exists an optimal solution $x'$ for $(P)$, then there exists an optimal solution $y'$ for $(D)$ and the value of $x'$ in $(P)$ equals the value of $y'$ in $(D)$.

Are these two statements not saying the same thing? In other words, isn't the second statement (2.) in definition of Weak duality saying the same thing as strong duality?

Let's say we are given an LP $(P)$ and we find a dual $(D)$. Then can the same dual be used to deduce either strong duality or weak duality?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

Weak duality is a property stating that any feasible solution to the dual problem corresponds to an upper bound on any solution to the primal problem. In contrast, strong duality states that the values of the optimal solutions to the primal problem and dual problem are always equal. Was this helpful enough?

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Oh so its strong in the sense that it gives a stronger statement: one just gives an inequality while the other gives a equality? $\endgroup$
    – mmtauqir
    Nov 18, 2012 at 9:43
  • 3
    $\begingroup$ Yes, exactly. The names are good hints for that. $\endgroup$
    – Ilan Kom
    Nov 18, 2012 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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