Intuitively, why is the complementary slackness condition true?

Question

What's an intuitive proof that shows that the conditions of complementary slackness are indeed true:

1. If $x^*_j > 0$ then the $j$-th constraint in the dual is binding.
2. If the $j$-th constraint in the dual is not binding, then $x^*_j = 0$

And similarly for the dual variables $y^*_i$ and constraints in the Primal. Where $x^*$ and $y^*$ are the optimal solutions to the Primal and Dual respectively.

What's an intuitive proof as to why this is the case? Staring at the equations makes sense algebraically, but I wish to understand it at a more visceral level.

Answer 1

As you have noted, complementary slackness follows immediately from strong duality, i.e., equality of the primal and dual objective functions at an optimum. Complementarity slackness can be thought of as a combinatorial optimality condition, where a zero duality gap (equality of the primal and dual objective functions) can be thought of as a numerical optimality condition.

In order to understand what complementary slackness means, the concept of dual variables as "shadow prices" is useful. The dual variable associated with a primal constraint is called the constraint's shadow price because it can be thought of as how much the objective function would increase if the constraint was relaxed (meaning e.g. the right hand side of a $\le$ constraint was increased).

Complementary slackness says that at an optimal solution, if a shadow price (dual variable) is positive, meaning that the objective function could be increased if the corresponding primal constraint was relaxed, then this primal constraint must be tight. If not, the primal objective function value could be improved (by changing the primal variables in order to make this non-binding primal constraint binding).

Answer 2

I find the geometric interpretation useful. Say we have the primal as $\max c x$ subject to $Ax \le b$ and $x \ge 0$. We know that optimum solutions are vertices of the polytope defined by the constraints. Each such vertex is defined by the intersection of $n$ linearly independent hyperplanes defined by the constraints. When is a vertex solution $x^*$ optimal for the direction $c$? It is optimal iff the vector $c$ is in the cone of the rows of $A$ defining the vertex $x^*$ (that is the vector $c$ can be written as a non-negative combination of the rows defining $x^*$). Otherwise we can improve the solution. The dual variables corresponding to the rows defining $x^*$ are strictly positive and the rest are $0$. This shows dual complementary slackness. Once we have strong duality we also get primal complementary slackness.