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 dual (minimization) problem is always greater than or equal to the solution to an associated primal problem. This is opposed to strong duality which only holds in certain cases.^[1]

Uses[]

Many primal-dual approximation algorithms are based on the principle of weak duality.^[2]

Weak duality theorem[]

The primal problem:

Maximize c^Tx subject to A x ≤ b, x ≥ 0;

The dual problem,

Minimize b^Ty subject to A^Ty ≥ c, y ≥ 0.

The weak duality theorem states c^Tx ≤ b^Ty.

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

Proof: c^Tx = x^Tc ≤ x^TA^Ty ≤ b^Ty

Generalizations[]

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

See also[]

• Convex optimization
• Max–min inequality

References[]