📂Optimization

Proof of Weak Duality Theorem in Linear Programming

Theorem

$$ \begin{align*} \text{Maximize} & \sum_{j=1}^{n} c_{j} x_{j} & \text{(Primal)} \\ \text{subject to} & \sum_{j=1}^{n} a_{ij} x_{j} \le b_{i} & i = 1 ,\cdots , m \\ & x_{j} \ge 0 & j = 1, \cdots , n \end{align*} $$ $$ \begin{align*} \text{Minimize} & \sum_{i=1}^{m} b_{i} y_{i} & \text{(Dual)} \\ \text{subject to} & \sum_{i=1}^{m} y_{i} a_{ij} \ge c_{j} & j = 1 ,\cdots , n \\ & y_{i} \ge 0 & i = 1, \cdots , m \end{align*} $$

Let’s say the primal problem and dual problem of the given linear programming problem are expressed as above. If $\left( x_{1} , \cdots , x_{n} \right)$ is a feasible solution for the primal problem, and $\left( y_{1} , \cdots , y_{m} \right)$ is a feasible solution for the dual problem, then the following inequality holds. $$ \sum_{j=1}^{n} c_{j} x_{j} \le \sum_{i=1}^{m} b_{i} y_{i} $$

Explanation

The weak duality theorem, in simple terms, guarantees that the objective function values of the primal and dual problems do not reverse as depicted above.

Proof ¹

$$ \begin{align*} \sum_{j} c_{j} x_{j} \le& \sum_{j} \left( \sum_{i} y_{i} a_{ij} \right) x_{j} & \because \text{Dual Constraint} \\ =& \sum_{i,j} y_{i} a_{ij} x_{j} \\ =& \sum_{i,j} x_{j} a_{ij} y_{i} \\ =& \sum_{i} \left( \sum_{j} a_{ij} x_{j} \right) y_{i} \\ \le& \sum_{i} b_{i} y_{i} & \because \text{Primal Constraint} \end{align*} $$

■

See Also

Duality in Linear Programming

If you’re not specializing in optimization but taking it as a course, learning just the simplex method and duality would mean you’ve learned everything about linear programming. Of course, saying it’s just those two doesn’t mean the material is easy.

While the simplex method discusses the specific method, duality discusses the theoretical - purely mathematical discussion that a dual problem exists for the primal problem, and their optimal solutions are the same. This is guaranteed by the following duality theorems.

Weak Duality Theorem

$$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} \le \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$

Strong Duality Theorem

$$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$