Complementary Slackness

y^_i (b_i - a_i^ x^) = 0 — slack constraints have zero dual price; active variables force tight dual constraints.

The idea

Complementary slackness is the test that certifies a pair of solutions — one primal, one dual — as jointly optimal. For the primal $\max c^{\top} x$ subject to $Ax \le b$, $x \ge 0$, the dual is $\min b^{\top} y$ subject to $A^{\top} y \ge c$, $y \ge 0$: one dual variable $y_i$ per primal constraint, one dual constraint per primal variable. Write $a_i^{\top}$ for row $i$ of $A$ and $a^{(j)}$ for its $j$-th column.

Complementary slackness. A primal-feasible $x^{}$ and a dual-feasible $y^{}$ are both optimal if and only if

$y^{}_{i}\,\bigl(b_i - a_i^{\top} x^{}\bigr) = 0 \quad \text{for every constraint } i, \qquad x^{}_{j}\,\bigl(a^{(j)\top} y^{} - c_j\bigr) = 0 \quad \text{for every variable } j.$

Each product has two nonnegative factors: feasibility keeps the slacks $b_i - a_i^{\top} x^{}$ and $a^{(j)\top} y^{} - c_j$ nonnegative, and $x^{}$ and $y^{}$ are nonnegative themselves. A product of nonnegative numbers vanishes only when a factor does, so the conditions say: a constraint with slack forces its dual variable to zero, and a positive variable forces its dual constraint to hold with equality. Geometrically, the optimum $x^{}$ sits at a vertex of the feasible region where the objective's level line leaves it: the walls meeting at $x^{}$ are the tight constraints, and every other wall has slack.

The conditions come from strong duality. At optimality the primal and dual objectives are equal, and their difference is exactly the sum of these products, so equality forces every product to zero.

Ways to work on it

• Walkthrough. State the complementary-slackness conditions and use them to relate slack constraints to zero dual prices.
• Practice. Given which constraints are tight vs slack at the optimum, identify the dual variables forced to zero.
• Hardest. Recover the full dual optimum from a 2-variable primal optimum using complementary slackness.

Not sure where to start? Take the ten-question placement test.