Lagrangian Duality

Lagrangian duality is a technique in optimization theory that transforms a constrained optimization problem into an unconstrained one by incorporating constraints into the objective function via Lagrange multipliers — scalar variables that price the violation of each constraint. The resulting Lagrangian function L(x, λ) = f(x) + λᵀg(x) yields, for any fixed λ ≥ 0, a lower bound on the optimal value of the primal (original) problem. The dual problem maximizes this lower bound over λ.

When strong duality holds — when the primal and dual optima coincide — the dual provides both a global lower bound and, at the optimum, a complete characterization of the primal solution. The KKT conditions express the first-order necessary conditions for optimality in terms of the Lagrangian's derivatives, and strong duality makes them sufficient under mild regularity conditions (convexity and constraint qualification). In convex programs, strong duality holds generically (Slater's condition), making Lagrangian duality a central computational and theoretical tool.

The economic interpretation is direct: Lagrange multipliers are shadow prices — the marginal value of relaxing each constraint by one unit. A multiplier of zero means the constraint is inactive (not binding the optimum); a positive multiplier means the constraint is tight and the objective would improve if the constraint were relaxed. In this sense, mechanism design and social choice problems that embed individual constraints into collective objectives are Lagrangian duality problems in disguise. The prices that clear markets are Lagrange multipliers. The tension between local and global optimization runs through the entire framework.