Duality

Every optimization problem has a shadow twin. Point a mirror at a maximization and you see a minimization; point it at the minimization and the maximization stares back. This is duality, one of the deepest and most useful ideas in the subject. The original problem is the primal; its mirror image is the dual; and the two are locked together so tightly that solving one solves the other — and either gives a running certificate of how good the other's answer is.

Take the factory from linear programming: maximize profit 3x + 2y subject to x + y \le 4 (cutting hours) and x + 3y \le 6 (assembly hours), with x, y \ge 0. Now change your seat. Instead of the factory owner choosing production, imagine an investor who wants to buy the whole workshop's time. They set a price u per cutting-hour and v per assembly-hour. To tempt the owner to sell rather than build, each product's resources must be priced to match its profit:

u + v \ge 3 \quad(\text{a table}), \qquad u + 3v \ge 2 \quad(\text{a chair}), \qquad u, v \ge 0.

The investor wants to pay as little as possible for the day's stock of hours:

\min \; 4u + 6v \quad\text{subject to the pricing constraints above.}

That is the dual. Its variables are prices on the primal's constraints — the value of one more unit of each scarce resource.

Weak duality: the two answers bracket each other

The first and easiest fact needs no cleverness at all. Take any production plan the owner can run, and any prices the investor can offer. Then

\underbrace{3x + 2y}_{\text{primal profit}} \;\le\; \underbrace{4u + 6v}_{\text{dual cost}}. For a primal maximization and its dual minimization, every primal-feasible objective value is \le every dual-feasible objective value: \mathbf{c}^{\!\top}\mathbf{x} \;\le\; \mathbf{b}^{\!\top}\mathbf{u}.

The picture makes it concrete. Primal-feasible profits pile up below the true optimum; dual-feasible costs pile up above it. Slide the two markers: no matter where you put them, the primal marker never passes the dual marker. The distance between them is the duality gap — a live measure of "how far from certain we still are".

Strong duality: the gap closes

For linear programs the bracket is not just a bound — it is tight. At the optimum the two answers meet exactly.

If a linear program has a finite optimum, so does its dual, and their optimal values are equal: \max \mathbf{c}^{\!\top}\mathbf{x} = \min \mathbf{b}^{\!\top}\mathbf{u}. The duality gap is zero.

Check it. The primal optimum was (x, y) = (4, 0) with profit 12. Solve the dual: at (u, v) = (3, 0) the constraints hold (3 + 0 \ge 3, 3 + 0 \ge 2) and the cost is 4(3) + 6(0) = 12. Primal profit = dual cost = 12. The mirror is exact.

Better still, the dual solution explains the primal. The price u = 3 is the shadow price of a cutting-hour: one more cutting-hour would raise the maximum profit by \$3. The price v = 0 says an extra assembly-hour is worth nothing — and indeed the optimal plan uses only 4 of the 6 assembly-hours, leaving 2 idle. That link is no coincidence.

At the optimum, primal and dual can't both have slack on a matched pair: A resource you don't fully use is worth nothing at the margin; a resource with positive value must be exhausted.

Duality is everywhere once you know its face. The max-flow / min-cut theorem says the greatest flow you can push through a pipe network equals the capacity of its cheapest bottleneck "cut" — a maximization and a minimization that are secretly the same LP and its dual. The same pattern links a game's best attacking strategy to its best defence (von Neumann's minimax theorem), a shortest path to a taut-string "potential", and in economics, an optimal production plan to the prices that support it. Whenever you meet a "the most you can gain = the least they can charge" theorem, duality is almost certainly underneath.