📂Optimization

Proof of Strong 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*} $$

Given the primal and dual problems of the linear programming problem as shown above, if $\mathbf{x}^{\ast} = \left( x_{1}^{\ast} , \cdots , x_{n}^{\ast} \right)$ is the optimal solution for the primal problem, and $\mathbf{y}^{\ast} =\left( y_{1}^{\ast} , \cdots , y_{m}^{\ast} \right)$ is the optimal solution for the dual problem, then the following inequality holds. $$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$

Explanation

The strong duality theorem simply guarantees that the optimal values of the primal and dual problems actually coincide, as illustrated above.

Proof ¹

It suffices to show that the dual feasible solution $\mathbf{y}^{\ast}$ satisfies $\sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast}$. Let’s assume that the simplex method was used to solve the optimization problem. We know that the simplex method produces a solution whether or not an optimal solution exists. Assuming that an optimal solution does exist, the final dictionary obtained through the simplex method can be written as $$ \zeta = \overline{\zeta} + \sum_{j \in \mathcal{N}} \overline{c_{j}} x_{j} $$ This is because we assume it to be the optimal dictionary, so we will use an asterisk $\cdot^{\ast}$ instead of bar $\overline{\cdot}$ for notation. If we write this for the base variables $\left\{ x_{j} \right\}_{j=1}^{n}$, non-base variables $\left\{ w_{i} \right\}_{i=1}^{m}$, and their coefficients $d_{i}^{\ast}$, then $$ \zeta = \zeta^{\ast} + \sum_{j=1}^{n} c_{j}^{\ast} x_{j} + \sum_{i=1}^{m} d_{i}^{\ast} w_{i} $$ Meanwhile, since $\zeta^{\ast}$ is the optimal solution for the primal problem, $$ \zeta^{\ast} = \sum_{j=1}^{n} c_{j} x_{j}^{\ast} $$ Thus, setting for $i = 1 , \cdots, m$, $$ y_{i}^{\ast} := - d_{i}^{\ast} $$ we have $$ \begin{align*} \sum_{j=1}^{n} c_{j} x_{j} =& \zeta^{\ast} + \sum_{j=1}^{n} c_{j}^{\ast} x_{j} + \sum_{i=1}^{m} d_{i}^{\ast} w_{i} \\ =& \zeta^{\ast} + \sum_{j=1}^{n} c_{j}^{\ast} x_{j} + \sum_{i=1}^{m} \left( - y_{i}^{\ast} \right) \left( b_{i} - \sum_{j=1}^{n} a_{ij} x_{j} \right) \\ =& \zeta^{\ast} - \sum_{i=1}^{m} b_{i} y_{i}^{\ast} + \sum_{j=1}^{m} \left( c_{j}^{\ast} + \sum_{i=1}^{m} y_{i}^{\ast} a_{ij} \right) x_{j} \end{align*} $$ Looking at the above equation as a linear equation for $x_{j}$ and matching the coefficients gives us $$ \begin{align*} \zeta^{\ast} =& \sum_{i=1}^{m} b_{i} y_{i}^{\ast} \\ c_{j} =& c_{j}^{\ast} + \sum_{i=1}^{m} y_{i}^{\ast} a_{ij} \qquad j = 1, \cdots , n \end{align*} $$ Since we have already stated that $\zeta^{\ast} = \sum_{j=1}^{n} c_{j} x_{j}^{\ast}$, we thus initially obtain the equation that we wanted in the theorem, $$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \zeta^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$ Given that $c_{j}^{\ast}$ is the optimal coefficient for the primal problem, and for the same reason $c_{j}^{\ast} \le$, and therefore $d_{i}^{\ast} \le 0$, $$ \begin{align*} \sum_{i=1}^{m} y_{i}^{\ast} a_{ij} \ge c_{j} & \qquad j = 1 , \cdots , n \\ y_{i}^{\ast} \ge 0 & \qquad i = 1 , \cdots , m \end{align*} $$ i.e., we can guarantee that $\mathbf{y} = \left( y_{1}^{\ast}, \cdots , y_{m}^{\ast} \right)$ is a feasible solution for the dual problem.

■

See Also

Duality in Linear Programming

If you’re not majoring in optimization but just covering it as a course, linear programming can be fully learned with just two topics: the simplex method and duality. Of course, that doesn’t mean the process is easy just because there are only those two.

While the simplex method discusses the specific method, duality is a largely 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} $$