Complementary Slackness Conditions

Consider the standard primal–dual LP pair.

Primal: $\max\; c^T x$ subject to $A x \le b,\ x \ge 0.$

Dual: $\min\; b^T y$ subject to $A^T y \ge c,\ y \ge 0.$

By the strong duality theorem, any optimal pair $(x^*, y^*)$ satisfies $c^T x^* = b^T y^*.$ Combined with primal–dual feasibility, this identity forces a precise pairing between constraint slacks and variable values — the complementary slackness (CS) conditions.

For each primal constraint $i = 1, \ldots, m{:}$

$$y_i^* \cdot (b_i - a_i^T x^*) = 0.$$

For each primal variable $j = 1, \ldots, n{:}$

$$x_j^* \cdot (a_j^T y^* - c_j) = 0.$$

Equivalently:

• $y_i^* > 0 \;\Longrightarrow\; a_i^T x^* = b_i$ (positive dual variable ⇒ primal constraint is tight).
• $a_i^T x^* < b_i \;\Longrightarrow\; y_i^* = 0$ (slack primal constraint ⇒ zero shadow price).
• $x_j^* > 0 \;\Longrightarrow\; a_j^T y^* = c_j$ (positive primal variable ⇒ corresponding dual constraint is tight).
• $a_j^T y^* > c_j \;\Longrightarrow\; x_j^* = 0$ (slack dual constraint ⇒ corresponding primal variable is zero).

These conditions are both necessary and sufficient for a primal–dual feasible pair to be optimal.