<p><em>Weak duality</em> 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, <em>strong duality</em> states that the values of the optimal solutions to the primal problem and dual problem are always equal.
Was this helpful enough? </p>

CC BY-SA 3.0
2012-11-18T09:43:27.213Z
Oh so its strong in the sense that it gives a stronger statement: one just gives an inequality while the other gives a equality?
mmtauqir
CC BY-SA 3.0
2012-11-18T10:00:43.730Z
Yes, exactly. The names are good hints for that.
Ilan Kom
CC BY-SA 3.0
2012-11-18T08:40:50.193Z
2012-11-18T08:40:50.193Z
Ilan Kom
<p>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:</p>

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

<ol>
<li>$c^T \bar{x} \le b^T\bar{y}$</li>
<li>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)$.</li>
</ol>

<p><strong>Strong duality:</strong>
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)$.</p>

<p>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?</p>

<p>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?</p>

<ds.algorithms><optimization><linear-programming><primal-dual>
Difference between weak duality and strong duality?
mmtauqir
# Difference between weak duality and strong duality?

(Asked by: username_0 on 2012-11-18)

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?

**Tags:** ds.algorithms, optimization, linear-programming, primal-dual


---

## 1 answers

### Answer by username_1 on 2012-11-18. Score: 9 | Accepted answer

*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?

> **Comments:**
> **username_0**: Oh so its strong in the sense that it gives a stronger statement: one just gives an inequality while the other gives a equality?  
> **username_1**: Yes, exactly. The names are good hints for that.  

---

