mathematics//optimization//duality
Duality is the correspondence that pairs every optimization problem, the primal, with a second problem over prices attached to its constraints, the dual, whose optimum bounds the primal's; it is used to prove that a solution is optimal, to measure how far an approximate solution can be from the best, and to read what each constraint is worth in units of cost. Each constraint gets a price, its **Lagrange multiplier** or **shadow price**: how much the optimal cost would fall if that constraint were relaxed by one unit.
Duality is the correspondence that pairs every optimization problem, the primal, with a second problem over prices attached to its constraints, the dual, whose optimum bounds the primal's; it is used to prove that a solution is optimal, to measure how far an approximate solution can be from the best, and to read what each constraint is worth in units of cost. Each constraint gets a price, its Lagrange multiplier or shadow price: how much the optimal cost would fall if that constraint were relaxed by one unit.
L(x,λ)=f(x)+λ⊤g(x),λ≥0,d⋆=maxλ≥0 minx L(x,λ) ≤ p⋆\mathcal L(x,\lambda)=f(x)+\lambda^{\top}g(x),\qquad \lambda\ge0,\qquad d^\star=\max_{\lambda\ge0}\,\min_{x}\,\mathcal L(x,\lambda)\;\le\;p^\starL(x,λ)=f(x)+λ⊤g(x),λ≥0,d⋆=λ≥0maxxminL(x,λ)≤p⋆
The primal minimizes fff subject to g(x)≤0g(x)\le0g(x)≤0 with optimal value p⋆p^\starp⋆; charging λ\lambdaλ per unit of violation and letting xxx roam freely gives a lower bound for every λ\lambdaλ, and the best such bound is the dual value d⋆d^\stard⋆. In the 2 by 2 assignment of the Hungarian algorithm note the row and column constants add up to 4, which is a dual solution, and the crossed assignment that costs 4 meets it, which proves it optimal.
The dual never exceeds the primal (weak duality), so any feasible plan and any dual solution together bracket the optimum, and the gap between them is a certificate. For convex problems the gap closes to zero under mild conditions (strong duality), and for linear programs it always does when a solution exists.
The prices carry decisions. In a refinery's MPC the multiplier of a compressor-power limit that the optimum leans on says how much margin an extra kilowatt would earn per hour, which is the number an investment in a larger compressor needs.
Prices decentralize. In the auction algorithm the task prices are dual variables and each agent's bid is a step of dual ascent: no one needs the whole problem, only the prices, which is how markets and distributed fleets coordinate.
Solvers use it constantly. Interior-point methods solve primal and dual together and stop when the gap is small; branch and bound reports a gap in the same spirit. The estimation-control duality between the Kalman filter and the LQR is a different correspondence that shares the word.