Linear Programming Duality

Suppose you are a factory manager. You choose how many units of each product to make in order to maximize profit, subject to limits on raw materials. That is a linear program: maximize a linear objective over variables constrained by linear inequalities.

Now suppose a supplier knocks on your door and says: "I'll buy all your raw materials. What's the minimum price per unit I must pay so you'd rather sell me the materials than run the factory?" Remarkably, that second question — minimize total payment subject to not undercutting any product's profit — has the exact same optimal value as the first. They are duals of each other.

This is not a coincidence or an approximation. It is the Strong Duality Theorem, proven in 1947 by John von Neumann and refined by David Gale, Harold Kuhn, and Albert Tucker. Every feasible linear program that is bounded has a dual that is also feasible and bounded, and primal optimum = dual optimum exactly. The dual is a built-in certificate: it says "you cannot possibly do better" and it proves it.

Below is a two-variable primal LP: maximize $c_1 x_1 + c_2 x_2$ subject to two resource constraints. Adjust the objective coefficients with the sliders. The shaded region is the feasible set; the red dot is the primal optimum. The dual provides an upper bound — drag to see it descend and meet the primal value exactly.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>c₁ = <span id="lc1">3</span> <input type="range" id="c1" min="1" max="9" value="3"></label>
  <label>c₂ = <span id="lc2">5</span> <input type="range" id="c2" min="1" max="9" value="5"></label>
  <label>R₁ = <span id="lr1">8</span> <input type="range" id="r1" min="2" max="12" value="8"></label>
  <label>R₂ = <span id="lr2">9</span> <input type="range" id="r2" min="2" max="12" value="9"></label>
</div>
<canvas id="cv" width="320" height="280"></canvas>
<div class="vals">
  <div class="val-box primal-box">{{primal_optimum}}: <b id="vprimal">—</b></div>
  <div class="val-box dual-box">{{dual_bound}}: <b id="vdual">—</b></div>
  <div class="val-box gap-box">{{gap}}: <b id="vgap">—</b></div>
</div>
<div class="optimum-detail" id="detail"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .5rem; line-height: 1.5; }
.dot-primal { color: #e63946; }
.controls { display: grid; grid-template-columns: 1fr 1fr; gap: .35rem .8rem; margin-bottom: .6rem; }
label { display: flex; align-items: center; gap: .4rem; font-size: .82rem; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 0; accent-color: #1d3557; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #f7f9fb; margin-bottom: .55rem; max-width: 100%; }
.vals { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
.val-box { flex: 1; min-width: 90px; padding: .35rem .6rem; border-radius: 7px; font-size: .82rem; text-align: center; }
.primal-box { background: #fde8ea; color: #7a111b; }
.dual-box   { background: #e0ecff; color: #0d2a5e; }
.gap-box    { background: #e6fae9; color: #0a5c23; font-weight: 700; }
.optimum-detail { font-size: .8rem; color: #555; min-height: 1.2em; }

// Code not found

Every position of the sliders produces a different LP, but the gap between the primal and dual is always zero. That closing gap is the Strong Duality Theorem made visible.

The precise status of LP duality: proven true (not a conjecture, not a Millennium Prize problem — a textbook theorem proven in 1947).

Here is the chain of results that makes duality work:

• Weak Duality (always holds): any feasible dual solution gives an upper bound on the primal optimum. This is trivial to prove — multiply the dual variables by the constraint rows and the bound falls out of the arithmetic.
• Strong Duality (the hard part): if the primal has an optimum, the dual does too, and they are equal. The original proof used the minimax theorem; later proofs go through the simplex method or Farkas' lemma.
• Complementary Slackness: at the optimum, for every primal variable either it is zero or its dual constraint is tight, and vice versa. This gives a practical test for optimality without re-solving the dual.

The key proof ingredient is Farkas' Lemma (1902): exactly one of two linear systems is feasible. From it you can show that if the primal optimum is bounded, the dual is feasible at the same value — no gap.

Contrast with integer programming: the moment you require variables to be whole numbers, the LP relaxation and its dual may have values strictly between the LP relaxation's optimum and the integer optimum. That gap — the integrality gap — is why integer programming is NP-hard while linear programming is polynomial. See also P vs NP for where that hardness barrier sits.

LP duality is not just theory — it is the engine inside many practical algorithms:

• Game theory: von Neumann's minimax theorem for zero-sum games is equivalent to LP duality. The optimal mixed strategy for each player is the primal/dual solution.
• Max-flow min-cut: the famous theorem (Ford-Fulkerson, 1956) is exactly the LP duality statement applied to a network flow LP. The minimum cut is the dual certificate for the maximum flow.
• Simplex pricing: the simplex method's "pricing" step uses the dual to decide which variable to enter the basis — without solving two programs separately.
• Support Vector Machines: training an SVM is a quadratic program whose dual reveals the support vectors and enables the kernel trick that powers modern ML classifiers.
• Sensitivity analysis: shadow prices — the dual variables at the optimum — measure how much the objective changes per unit of each resource. Operations researchers read these directly off the dual to guide decisions.
• Approximation algorithms: for many NP-hard problems (like set cover), the LP relaxation and its dual yield the best known approximation ratios, with the gap certified by duality.

Linear programming duality is one of the most satisfying results in optimization: every feasible bounded LP contains, hidden inside it, a second problem whose optimal value exactly equals the first. The strong duality theorem — proven in 1947 — is not a conjecture waiting to be resolved; it is a fact that you can use as a guarantee.

The deeper reason to care is what breaks when you leave the LP world. Require integer solutions and the dual gap can open up; require nonconvexity and even weak duality can fail. LP duality sits at the precise boundary where optimization becomes provably easy, and understanding that boundary is the first step toward understanding why harder problems are hard. As P vs NP reminds us, that boundary matters enormously.