Verifying Optimality via Complementary Slackness

Use complementary slackness as a practical optimality test. Given a candidate primal solution (and optionally a candidate dual), check primal feasibility, construct or check the matching dual via CS, and conclude whether the candidate is optimal or not.

Step 1 of 157%

Tutorial

Optimality as a Checklist

The complementary slackness theorem turns optimality into a checklist. Given a candidate primal solution $x^*$ and a candidate dual solution $y^*$ , we can certify both are optimal without ever solving either LP.

For the primal--dual pair

\text{(P)}\quad \max\, c^T x \quad \text{s.t.} \quad Ax \le b,\; x \ge 0,

\text{(D)}\quad \min\, b^T y \quad \text{s.t.} \quad A^T y \ge c,\; y \ge 0,

the pair $(x^*, y^*)$ is simultaneously optimal if and only if all three of the following hold:

Primal feasibility: $Ax^* \le b$ and $x^* \ge 0$ .
Dual feasibility: $A^T y^* \ge c$ and $y^* \ge 0$ .
Complementary slackness:

For each primal constraint $i$ : $y_i^*\bigl(b_i - (Ax^*)_i\bigr) = 0$ .
For each primal variable $j$ : $x_j^*\bigl((A^T y^*)_j - c_j\bigr) = 0$ .

In words: whenever a primal constraint is slack, the matching dual variable must be $0$ ; whenever a dual constraint is slack, the matching primal variable must be $0$ .

To verify a candidate pair, we just run the checklist.