TheoremProved

Strong duality in linear programming

Statement

Consider the primal linear program $\min\ c^\top x$ subject to $Ax \ge b,\ x \ge 0$ , and its dual $\max\ b^\top y$ subject to $A^\top y \le c,\ y \ge 0$ . If either program has an optimal solution, so does the other, and their optimal values are equal: $c^\top x^* = b^\top y^*$ .

Why is it true?

Weak duality always holds: any feasible dual value is a lower bound on any feasible primal value, like a buyer's offer never exceeding a seller's true worth of the resources. Strong duality says this gap closes exactly at the optimum — the dual variables behave like fair 'shadow prices' for each constrained resource, so that valuing every resource at its shadow price reproduces the primal's best possible cost with no slack left over.

Proof sketch

The standard proof runs through Farkas' lemma: assume the primal has optimal value $z^*$ but the dual's feasible region cannot reach it; then the system 'dual feasible and $b^\top y > z^*$ ' is infeasible, so by Farkas' lemma there is a certificate showing this would force a primal-feasible point with objective below $z^*$ , a contradiction. Equivalently, one separates the epigraph of the primal value function from the origin by a hyperplane, whose normal vector supplies the dual optimal $y^*$ .

Stated by

stated 1947John von Neumann

Topics that use this theorem

Linear programming Convex optimization

Related theorems

Karush–Kuhn–Tucker conditions Local minima of convex functions are global

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

George B. Dantzig (1963). Linear Programming and Extensions
John von Neumann, Oskar Morgenstern (1944). Theory of Games and Economic Behavior