Two views of one problem
Every constrained minimization, called the primal, has a partner called the dual, built from its Lagrangian. The dual is phrased in terms of the multipliers.
- The dual is found by minimizing the Lagrangian over the original variables.
- We then maximize the result over the multipliers.
Weak and strong duality
- Weak duality: the dual optimum is always a lower bound on the primal optimum.
- Strong duality: under conditions like convexity, the two optima are equal.
When strong duality holds, solving the dual solves the primal.
Why it is useful
The dual is sometimes easier to solve or reveals structure the primal hides. In support vector machines the dual form depends only on inner products of data, which opens the door to the kernel trick.
The duality gap, the difference between primal and dual optima, measures how far apart the two views are.
Key idea
The dual problem reframes a constrained primal in terms of multipliers, always lower bounding the primal and, under convexity, matching it exactly while often exposing useful structure.