Weak duality

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

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

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