4.3. Complementary Slackness: Another Optimality Condition

Strong duality (Theorem 4.3) provides a necessary and sufficient condition for a solution of an LP to be optimal. In this section, we provide another optimality condition, again based on duality. This condition follows from strong duality and is central to a number of algorithmic techniques, most prominently the primal-dual schema.

Again, we consider a primal LP

\[\begin{gathered} \text{Maximize } cx\\ \begin{aligned} \text{s.t. }Ax &\le b\\ x &\ge 0 \end{aligned} \end{gathered}\tag{4.12}\]

and its dual

\[\begin{gathered} \text{Minimize } b^Ty\\ \begin{aligned} \text{s.t. }A^Ty &\ge c^T\\ y &\ge 0. \end{aligned} \end{gathered}\tag{4.13}\]

Let \(\hat x\) be a feasible solution of the primal LP (4.12) and let \(\hat y\) be a feasible solution of the dual LP (4.13). These two solutions are said to satisfy complementary slackness if

Primal complementary slackness: For all \(1 \le j \le n\),

\[\hat x_j = 0 \text{ or } \sum_{i=1}^m a_{ij}\hat y_i = c_j \text{ and}\]

Dual complementary slackness: For all \(1 \le i \le m\),

\[\hat y_i = 0 \text{ or } \sum_{j=1}^n a_{ij}\hat x_j = b_i.\]

We call an inequality constraint

\[\sum_{j=1}^n a_{ij} x_j \le b_i\]

tight for a given feasible solution \(\hat x\) of (4.12) if

\[\sum_{j=1}^n a_{ij} \hat x_j = b_i.\]

In other words, there is no slack: We cannot increase \(\sum_{j=1}^n a_{ij}\hat x_j\) without violating this constraint.

With this terminology, primal complementary slackness states that every primal variable \(x_j\) is \(0\) or its corresponding constraint in the dual is tight. Dual complementary slackness states that every dual variable \(y_i\) is \(0\) or its corresponding constraint in the primal is tight.

Said even differently, primaly complementary slackness states that only the non-negativity constraint of the primal variable \(x_j\) or its corresponding dual constraint has some slack; they can't both have slack. Dual complementary slackness states that only the non-negativity constraint of the dual variable \(y_i\) or its corresponding primal constraint has some slack; they can' both have slack. In this sense, the "slackness" of these pairs of constraints is complementary.

Theorem 4.5: Let \(\hat x\) be a feasible solution of the primal LP (4.12) and let \(\hat y\) be a feasible solution of its dual LP (4.13). \(\hat x\) is an optimal solution of (4.12) and \(\hat y\) is an optimal solution of (4.13) if and only if \(\hat x\) and \(\hat y\) satisfy complementary slackness.

Proof: Since \(\hat x\) is a feasible primal solution, we have

\[A\hat x \le b.\]

Since \(\hat y\) is a feasible dual solution, we have

\[A^T\hat y \ge c^T,\]

that is,

\[\hat y^TA \ge c.\]

Therefore,

\[c \hat x \le \hat y^T A \hat x \le \hat y^T b = b^T \hat y.\]

By strong duality Theorem 4.3, \(\hat x\) and \(\hat y\) are optimal solutions of (4.12) and (4.13) if and only if

\[c \hat x = b^T \hat y.\]

Thus, \(\hat x\) and \(\hat y\) are optimal solutions if and only if

\[c \hat x = \hat y^T A \hat x \quad \text{and} \quad \hat y^T A \hat x = \hat y^T b,\]

which is equivalent to

\[\left(\hat y^T A - c\right) \hat x = 0 \quad \text{and} \quad \hat y^T \left(b - A \hat x\right) = 0.\]

Next observe that every coordinate \(\hat x_j\) of \(\hat x\) is non-negative because \(\hat x\) is a feasible primal solution. Every coordinate of \(\hat y^T A - c\) is non-negative because \(\hat y^T A \ge c\) (\(\hat y\) is a feasible dual solution). Thus, \(\bigl(\hat y^T A - c^T\bigr) \hat x\) is the inner product of two vectors with non-negative coordinates and is zero if and only if

\[\left(\sum_{i=1}^m \hat y_ia_{ij} - c_j\right)\hat x_j = 0\]

for all \(1 \le j \le n\), that is, \(\hat x_j = 0\) or \(\sum_{i=1}^m \hat y_ia_{ij} = c_j\). In other words, \(\bigl(\hat y^TA - c\bigr)\hat x = 0\) if and only if primal complementary slackness holds for \(\hat x\) and \(\hat y\).

An analogous argument shows that \(\hat y^T\bigl(b - A\hat x\bigr) = 0\) if and only if \(\hat y_i = 0\) or \(b_i - \sum_{j=1}^n a_{ij} \hat x_j = 0\) for all \(1 \le i \le m\), that is, if and only if dual complementary slackness holds for \(\hat x\) and \(\hat y\).

Since \(\hat x\) and \(\hat y\) are optimal if and only if both \(\bigl(\hat y^TA - c\bigr)\hat x = 0\) and \(\hat y^T\bigl(b - A\hat x\bigr) = 0\), we have that \(\hat x\) and \(\hat y\) are optimal if and only if both primal and dual complementary slackness hold for \(\hat x\) and \(\hat y\). ▨