Weak duality

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

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

• Convex optimization
• Max–min inequality