Weak duality

In applied mathematics, weak duality is a concept in optimization which states that the duality gap is always greater than or equal to 0. That means the solution to the primal (minimization) problem is always greater than or equal to the solution to an associated dual problem. This is opposed to strong duality which only holds in certain cases.^[1] Many primal-dual approximation algorithms are based on the principle of weak duality.^[2]

If $(x_{1},x_{2},....,x_{n})$ is a feasible solution for the primal minimization linear program and $(y_{1},y_{2},....,y_{m})$ is a feasible solution for the dual maximization linear program, then the weak duality theorem can be stated as $\sum _{i=1}^{m}b_{i}y_{i}\leq \sum _{j=1}^{n}c_{j}x_{j}$ , where $c_{j}$ and $b_{i}$ are the coefficients of the respective objective functions.

More generally, if $x$ is a feasible solution for the primal minimization problem and $y$ is a feasible solution for the dual maximization problem, then weak duality implies $g(y)\leq f(x)$ where $f$ and $g$ are the objective functions for the primal and dual problems respectively.

References

^ Boţ, Radu Ioan; Grad, Sorin-Mihai; Wanka, Gert (2009), Duality in Vector Optimization, Berlin: Springer-Verlag, p. 1, doi:10.1007/978-3-642-02886-1, ISBN 978-3-642-02885-4, MR 2542013.
^ Gonzalez, Teofilo F. (2007), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, p. 2-12, ISBN 9781420010749.

This applied mathematics–related article is a stub. You can help Wikipedia by expanding it.

[1] Boţ, Radu Ioan; Grad, Sorin-Mihai; Wanka, Gert (2009), Duality in Vector Optimization, Berlin: Springer-Verlag, p. 1, doi:10.1007/978-3-642-02886-1, ISBN 978-3-642-02885-4, MR 2542013.

[2] Gonzalez, Teofilo F. (2007), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, p. 2-12, ISBN 9781420010749.

[1]

[2]