Duality Theory

Optimization · Axiom Academy

Discover the beautiful symmetry between primal and dual linear programs Given a primal maximization problem, we construct the dual minimization problem using transformation rules. Each constraint in the primal becomes a variable in the dual, and each variable in the primal becomes a constraint in the dual. The primal and dual are symmetric partners. If we take the dual of the dual, we get back the primal. Each element of one problem corresponds to an element of the other in a beautiful correspondence. Any feasible solution to the dual provides an upper bound on the optimal value of the primal (for maximization). This powerful property holds even if we don't know the optimal solutions. For linear programs, if the primal has an optimal solution, then so does the dual, and their optimal values are equal. This remarkable theorem is the cornerstone of linear programming theory. Dual variables have a beautiful economic meaning: they represent shadow prices or marginal values of resources. If we had one more unit of a resource, the dual variable tells us how much the objective value would increase.

This is the written version of the interactive lesson above. See the full Optimization course.