Linear Programming Duality
Motivation
Every linear program has a partner LP — the dual — with intimately connected structure. The dual provides a certificate of optimality: any feasible solution to the dual is an upper (or lower) bound on the primal optimum, and at the optimum the two values coincide. This duality has a striking number of consequences: it explains why every feasible LP has a dual interpretation as shadow prices, it underpins the minimax theorem for zero-sum games, it powers primal-dual algorithms for both LP and combinatorial optimization, and it generalizes to convex optimization more broadly (Dantzig 1963; Boyd and Vandenberghe 2004; Kleinberg and Tardos 2005).
For a working data scientist, duality matters because: (1) the dual variables are shadow prices with concrete economic meaning, (2) duality gives you a stopping criterion for iterative LP solvers, and (3) duality explains why so many combinatorial optimality conditions (max-flow = min-cut, complementary slackness in matching) take the form of “primal value equals dual value.”
The primal-dual pair
Consider the primal LP in standard form: \[ \text{(P)} \quad \max c^\top x \quad \text{s.t.} \quad A x \le b, \quad x \ge 0. \]
Its dual is: \[ \text{(D)} \quad \min b^\top y \quad \text{s.t.} \quad A^\top y \ge c, \quad y \ge 0. \]
The dual has one variable per primal constraint and one constraint per primal variable. The roles of \(b\) and \(c\), and of \(\le\) and \(\ge\), swap.
The dual of the dual is the original primal — duality is involutive.
Weak duality
Theorem (weak duality). For any primal-feasible \(x\) and dual-feasible \(y\), \[ c^\top x \le b^\top y. \]
Proof. From dual feasibility \(A^\top y \ge c\) and \(x \ge 0\): \[ c^\top x \le (A^\top y)^\top x = y^\top A x. \] From primal feasibility \(A x \le b\) and \(y \ge 0\): \[ y^\top A x \le y^\top b = b^\top y. \] Chain.
Consequence. Any dual-feasible \(y\) gives an upper bound on the primal optimum, and any primal-feasible \(x\) gives a lower bound on the dual optimum. The two bounds sandwich the common optimum.
Strong duality
Theorem (strong duality). If the primal has a finite optimum, so does the dual, and the two optimal values are equal.
The proof uses the separating hyperplane theorem, or constructively the simplex method (the final dual variables read off from the optimal tableau). Strong duality fails for some non-LP optimization (general non-convex problems can have a duality gap), but holds for any LP with a finite optimum.
The four possible primal-dual outcomes:
| Primal | Dual |
|---|---|
| Has finite optimum | Has finite optimum (equal) |
| Unbounded | Infeasible |
| Infeasible | Unbounded or infeasible |
| Infeasible (specifically) | Infeasible |
The mixed “infeasible–infeasible” case can occur but is rare in practice.
Complementary slackness
Theorem. If \(x^*\) is primal-optimal and \(y^*\) is dual-optimal, then for every \(i, j\): \[ y_i^* \cdot (b_i - (A x^*)_i) = 0, \qquad x_j^* \cdot ((A^\top y^*)_j - c_j) = 0. \]
That is: either the constraint is tight or its dual variable is zero. This is complementary slackness.
Practically: if a primal constraint has slack at the optimum, its dual variable must be zero (the constraint is not binding, so loosening it doesn’t help the objective). If a primal variable is zero at the optimum, the corresponding dual constraint may be slack.
This is the optimality condition that primal-dual algorithms drive toward, and it is the LP shadow of the much more general KKT conditions for convex optimization.
Shadow prices
The dual variable \(y_i^*\) has an economic interpretation: it is the marginal value of relaxing the \(i\)-th primal constraint. If \(b_i\) increases by \(\epsilon\) (a small amount), the primal optimum increases by approximately \(y_i^* \cdot \epsilon\).
In the diet problem, each primal constraint says “consume at least \(r_j\) units of nutrient \(j\)”; the dual variable \(y_j\) is the price you would pay per unit of nutrient \(j\) — exactly the marginal cost of meeting one more unit of that requirement.
Example: a diet LP and its dual
Primal (minimize cost). Two foods, two nutrients. Food A costs \(2\)/unit and contains \(1\) protein + \(3\) carbs per unit; food B costs \(3\)/unit and contains \(2\) protein + \(1\) carb. Require at least \(4\) protein and \(6\) carbs.
\[ \min\ 2x_1 + 3x_2 \quad \text{s.t.}\quad x_1 + 2x_2 \ge 4,\quad 3x_1 + x_2 \ge 6,\quad x_1,x_2 \ge 0. \]
Dual (maximize nutrient value). One dual variable per nutrient constraint, interpreted as the shadow price per unit of each nutrient:
\[ \max\ 4y_1 + 6y_2 \quad \text{s.t.}\quad y_1 + 3y_2 \le 2,\quad 2y_1 + y_2 \le 3,\quad y_1,y_2 \ge 0. \]
Solving both. At the primal optimum both constraints are tight:
\[ x_1 + 2x_2 = 4,\quad 3x_1 + x_2 = 6 \implies x_1 = \tfrac{8}{5},\; x_2 = \tfrac{6}{5},\; \text{cost} = \tfrac{34}{5}. \]
The dual constraints are similarly tight at optimality:
\[ y_1 + 3y_2 = 2,\quad 2y_1 + y_2 = 3 \implies y_1 = \tfrac{7}{5},\; y_2 = \tfrac{1}{5},\; \text{value} = \tfrac{34}{5}. \]
Primal cost \(=\) dual value \(= \tfrac{34}{5}\), confirming strong duality. The shadow price \(y_1 = \tfrac{7}{5}\) means one extra unit of protein requirement raises the minimum diet cost by \(\tfrac{7}{5}\); similarly \(y_2 = \tfrac{1}{5}\) for carbs. The tighter protein constraint is correspondingly more expensive.
Examples of duality
Max flow = min cut. The LP for maximum flow has a dual that, after some manipulation, is the LP for minimum cut. Strong duality of LP yields the celebrated max-flow min-cut theorem.
Matching = vertex cover (bipartite). König’s theorem (maximum matching = minimum vertex cover in bipartite graphs) is LP duality applied to the bipartite-matching LP. The constraint matrix is totally unimodular, so both LPs have integer optima.
Zero-sum games. A zero-sum game’s optimal mixed strategies are computed by an LP; its dual is the opposing player’s LP. Strong duality is the minimax theorem — the row player and column player can guarantee the same value.
Applications in algorithm design
- Stopping criterion for iterative solvers: when the duality gap \(b^\top y - c^\top x\) falls below tolerance, stop.
- Primal-dual algorithms: maintain primal and dual feasibility simultaneously, drive complementary slackness toward zero. Foundation of interior-point methods and many combinatorial approximation algorithms.
- Integrality gap analysis: bounding the integrality gap of an ILP often goes through the dual. Set-cover’s \(\Theta(\log n)\) gap, vertex cover’s \(2\), etc.
- Designing approximation algorithms: classical algorithms (Christofides for TSP, primal-dual for facility location) explicitly construct primal-dual pairs satisfying approximate complementary slackness.