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?

$\endgroup$
7
$\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?

$\endgroup$
  • 1
    $\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$ – mtahmed Nov 18 '12 at 9:43
  • 2
    $\begingroup$ Yes, exactly. The names are good hints for that. $\endgroup$ – Ilan Kom Nov 18 '12 at 10:00

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.