Complementary Slackness
Table of Contents
The theorem
Consider the usual primal-dual pair of problems where \(A\) is an \(m \times n\) matrix:
| Primal LP | Dual LP |
|---|---|
| max \(\mathbf{c} \cdot \mathbf{x}\) | min \(\mathbf{b} \cdot \mathbf{y}\) |
| subject to | subject to |
| \( A \mathbf{x} \le \mathbf{b} \) | \( A^\top \mathbf{y} \ge \mathbf{c} \) |
| \( \mathbf{x} \ge 0\) | \( \mathbf{y} \ge 0\) |
Let \(\mathbf{x}\) be feasible for the primal LP and \(\mathbf{y}\) be feasible for the dual. Then we have that \(\mathbf{x}\) and \(\mathbf{y}\) are optimal solution of their respective LPs if and only if complementary slackness holds:
For \(1 \le i \le m\), either \(y_i=0\) or \(b_i - \sum_{j=1}^n a_{ij} x_j = 0 \) (or both).
Notice that \(b_i - \sum_{j=1}^n a_{ij} x_j\) is the slack in the \(i\)-th constraint in the primal.
For \(1 \le j \le n\), either \(x_j=0\) or \(\sum_{i=1}^m a_{ij} y_i - c_j = 0 \) (or both).
Notice that \(\sum_{i=1}^m a_{ij} y_i - c_j\) is the slack in the \(j\)-th constraint in the dual.
Each statement in this list is equivalent to the next:
- \(\mathbf{x}\) and \(\mathbf{y}\) are optimal for their respective LPs
\(\iff\)1 (by weak duality)
- \(\mathbf{c}^\top \mathbf{x} = \mathbf{y}^\top \mathbf{b}\)
\(\iff\) (recall the proof of Weak Duality: \(\mathbf{c}^\top \mathbf{x} \le \mathbf{y}^\top A \mathbf{x} \le \mathbf{y}^\top \mathbf{b}\) )
- \(\mathbf{c}^\top \mathbf{x} = \mathbf{y}^\top A \mathbf{x}\) and \(\mathbf{y}^\top A \mathbf{x} = \mathbf{y}^\top \mathbf{b}\).
\(\iff\) (algebra)
- \(\left(A^\top \mathbf{y} - \mathbf{c}\right)^\top \mathbf{x} = 0\) and \(\mathbf{y}^\top \left(\mathbf{b} - A \mathbf{x}\right) = 0\).
\(\iff\) (see below)
- The complementary slackness conditions hold.
The last equivalence is for the following reason: all of \(A^\top \mathbf{y} - \mathbf{c}\), \(\mathbf{x}\), \(\mathbf{y}\) and \(\mathbf{b} - A \mathbf{x}\) are vectors with non-negative entries, so their dot product is zero if and only if for each \(j\) one of the two vectors has a zero in the \(j\)-th entry.
Examples
One thing we can use complementary slackness for is to verify claims about optimal solutions.
Example 1. Say someone tells us that \(x_1^* = \frac{9}{7}, x_2^* = 0, x_3^* = \frac{1}{7}\) is an optimal solution for the following LP:
Maximize \(x_1-2x_2+3x_3\)
subject to \[\begin{aligned} x_1+x_2-2x_3 & \le 1 \\ 2x_1-x_2-3x_3 & \le 4\\ x_1+x_2+5x_3 & \le 2 \\ x_1, x_2, x_3 & \ge 0 \end{aligned}\]
Let’s try to verify that claim.
At least those values satisfy the constraints! Now let’s see what complementary slackness would tells us about an optimal solution \(y_1^*, y_2^*, y_3^*\) of the dual.
Because \(x_1^*\) and \(x_3^*\) are non-zero, the first and third constraints of the dual have no slack:
\[\begin{aligned} y_1^* + 2y_2^* + y_3^* & = 1 \\ -2y_1^* - 3y_2^* + 5 y_3^* & = 3\\ \end{aligned}\]
That’s only two equations for three unknowns! But checking the primal, we see that the alleged optimal solution shows some slack in the second constraint (that is \(2x_1^* -x_2^* -3x_3^* = \frac{15}{7} < 4\)), and thus, by complementary slackness again, \(y_2^*=0\). Plugging that in we get the following system:
\[\begin{aligned} y_1^* + y_3^* & = 1 \\ -2y_1^* + 5 y_3^* & = 3\\ \end{aligned}\]
The only solution is \(y_1^* = \frac{2}{7}, y_3^* = \frac{5}{7}\). So the dual should have optimal solution \(y_1^* = \frac{2}{7}, y_2^*=0, y_3^* = \frac{5}{7}\). Does it really? We can use complementary slackness again to check! We need to check it is feasible for the dual and that complementary slackness holds, and most of that has already been done in the process of coming up with these values of the \(y_i^*\).
We still need to check one inequality for feasibility: \(y_1^* -y_2^* + y_3^* \ge -2\), which clearly holds.
And we still need to check, since \(y_1^*, y_3^* >0\), that in the primal the first and third constraints have no slack. Plugging in we see that indeed they don’t, and so we conclude that the \(x_i^*\) and \(y_i^*\) are indeed optimal for the primal and dual respectively.
Example 2. Now imagine someone told us instead that \(x_1^* = \frac{9}{7}, x_2^* = 0, x_3^* = \frac{1}{7}\) was an optimal solution for the following different LP:
Maximize \(x_1+2x_2+3x_3\)
subject to \[\begin{aligned} x_1+x_2-2x_3 & \le 1 \\ 2x_1-x_2-3x_3 & \le 4\\ x_1+x_2+5x_3 & \le 2 \\ x_1, x_2, x_3 & \ge 0 \end{aligned}\]
(The only difference is the sign of the coefficient of \(x_2\) in the objective function!)
We can argue similarly to the first example and conclude that \(y_1^* = \frac{2}{7}, y_2^*=0, y_3^* = \frac{5}{7}\) is the only possibility for an optimal solution of the dual. But now this dual solution is not feasible! This shows that the proposed optimal solution of the primal is not actually optimal.
Read this as “if and only if”.