29-2 Complementary slackness

Complementary slackness describes a relationship between the values of primal variables and dual constraints and between the values of dual variables and primal constraints. Let $\bar x$ be a feasible solution to the primal linear program given in $\text{(29.16)–(29.18)}$, and let $\bar y$ be a feasible solution to the dual linear program given in $\text{(29.83)–(29.85)}$. Complementary slackness states that the following conditions are necessary and sufficient for $\bar x$ and $\bar y$ to be optimal:

$$\sum_{i = 1}^m a_{ij}\bar y_i = c_j \text{ or } \bar x_j = 0 \text{ for } j = 1, 2, \dots, n$$

and

$$\sum_{j = 1}^m a_{ij}\bar x_j = b_i \text{ or } \bar y_i = 0 \text{ for } j = 1, 2, \dots, m.$$

a. Verify that complementary slackness holds for the linear program in lines $\text{(29.53)–(29.57)}$.

b. Prove that complementary slackness holds for any primal linear program and its corresponding dual.

c. Prove that a feasible solution $\bar x$ to a primal linear program given in lines $\text{(29.16)–(29.18)}$ is optimal if and only if there exist values $\bar y = (\bar y_1, \bar y_2, \dots, \bar y_m)$ such that

1. $\bar y$ is a feasible solution to the dual linear program given in $\text{(29.83)–(29.85)}$,
2. $\sum_{i = 1}^m a_{ij}\bar y_i = c_j$ for all $j$ such that $\bar x_j > 0$, and
3. $\bar y_i = 0$ for all $i$ such that $\sum_{j = 1}^n a_{ij}\bar x_j < b_i$.

a. An optimal solution to the LP program given in $\text{(29.53)}$-$\text{(29.57)}$ is $(x_1, x_2, x_3) = (8, 4, 0)$. An optimal solution to the dual is $(y_1, y_2, y_3) = (0, 1 / 6, 2 / 3)$. It is then straightforward to verify that the equations hold.

b. First suppose that complementary slackness holds. Then the optimal objective value of the primal problem is, if it exists,

$$\begin{aligned} \sum_{k = 1} c_kx_k & = \sum_{k = 1}^n \sum_{i = 1}^m a_{ik}y_ix_k \\ & = \sum_{i = 1}^m \sum_{k = 1}^n a_{ik}x_ky_i \\ & = \sum_{i = 1}^m b_iy_i, \end{aligned}$$

which is precisely the optimal objective value of the dual problem. If any $x_j$ is $0$, then those terms drop out of them sum, so we can safely replace $c_k$ by whatever we like in those terms. Since the objective values are equal, they must be optimal. An identical argument shows that if an optimal solution exists for the dual problem then any feasible solution for the primal problem which satisfies the second equality of complementary slackness must also be optimal.

Now suppose that $x$ and $y$ are optimal solutions, but that complementary slackness fails. In other words, there exists some $j$ such that $x_j \ne 0$ but $\sum_{i = 1}^m a_{ij}y_i > c_j$, or there exists some $i$ such that $y_i \ne 0$ but $\sum_{j = 1}^n a_{ij}x_j < b_i$. In the first case we have

$$\begin{aligned} \sum_{k = 1} c_kx_k & < \sum_{k = 1}^n \sum_{i = 1}^m a_{ik}y_ix_k \\ & = \sum_{i = 1}^m \sum_{k = 1}^n a_{ik}x_ky_i \\ & = \sum_{i = 1}^m b_iy_i. \end{aligned}$$

This implies that the optimal objective value of the primal solution is strictly less than the optimal value of the dual solution, a contradiction. The argument for the second case is identical. Thus, $x$ and $y$ are optimal solutions if and only if complementary slackness holds.

c. This follows immediately from part (b). If $x$ is feasible and $y$ satisfies conditions 1, 2, and 3, then complementary slackness holds, so $x$ and $y$ are optimal. On the other hand, if $x$ is optimal, then the dual linear program must have an optimal solution $y$ as well, according to Theorem 29.10. Optimal solutions are feasible, and by part (b), $x$ and $y$ satisfy complementary slackness. Thus, conditions 1, 2, and 3 hold.