The Lagrange Dual
Price the constraints instead of enforcing them, and a concave lower bound appears under any problem at all.
The idea
Lagrange duality attaches a price to each constraint of an optimization problem and, from the prices, produces lower bounds on its optimal value.
Attach a multiplier $\lambda_{i} \ge 0$ to each inequality constraint $f_{i}(x) \le 0$ and $\nu_{j}$ to each equality $h_{j}(x) = 0$. Instead of enforcing a constraint, charge $\lambda_{i} f_{i}(x)$ or $\nu_{j} h_{j}(x)$ for violating it. The objective plus the charges is the Lagrangian
$L(x, \lambda, \nu) = f_{0}(x) + \sum_{i=1}^{m} \lambda_{i} f_{i}(x) + \sum_{j=1}^{p} \nu_{j} h_{j}(x).$
At fixed prices, the smallest total any point can achieve is the Lagrange dual function
$g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu),$
the infimum running over the whole domain, feasible points and infeasible ones alike.
Two facts hold with no assumptions on the primal problem — not convexity, not even continuity.
Theorem (Weak duality).
Let $p^{\star}$ be the optimal value of the primal problem. Then the dual function $g$ is concave, and $g(\lambda, \nu) \le p^{\star} \quad \text{for every } \lambda \succeq 0 \text{ and every } \nu.$
The dual problem asks for the best of those bounds: maximize $g(\lambda,\nu)$ subject to $\lambda \succeq 0$. Its optimal value $d^{\star}$ satisfies $d^{\star} \le p^{\star}$, and the difference $p^{\star} - d^{\star}$ is the duality gap. In LP Duality the dual of a linear program was another linear program; the Lagrangian builds a dual for any problem at all.
Ways to work on it
- Walkthrough. Build the Lagrangian, minimize it into the dual function, and maximize that — then watch the recipe reproduce the LP dual.
- Proof. Why the dual function is concave and always a lower bound, with neither argument ever looking at the primal.
- Practice. Evaluate dual functions at given multipliers, and read off what weak duality does and does not promise.
- Hardest. Bound a combinatorial primal by its convex dual, and measure the duality gap.
Not sure where to start? Take the ten-question placement test.