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

Consider a linear programming problem,

$${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{maximize}}}\quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b,\\&x\geq 0,\end{aligned}}}$$

(1)

where ${\displaystyle A}$  is ${\displaystyle m\times n}$  and ${\displaystyle b}$  is ${\displaystyle m\times 1}$ . The dual problem of (1) is

$${\displaystyle {\begin{aligned}{\underset {y\in \mathbb {R} ^{m}}{\text{minimize}}}\quad &b^{\top }y\\{\text{subject to}}\quad &A^{\top }y\geq c,\\&y\geq 0.\end{aligned}}}$$

(2)

The weak duality theorem states that ${\displaystyle c^{\top }x^{*}\leq b^{\top }y^{*}}$  for every solution ${\displaystyle x^{*}}$  to the primal problem (1) and every solution ${\displaystyle y^{*}}$  to the dual problem (2).

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 edit

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.

• Convex optimization
• Max–min inequality