Introduction
Every constrained optimization problem has a twin — its dual. The dual is always a concave maximization problem (easy to solve), its value is always a lower bound on the original, and for convex problems the two usually match exactly. Duality is how support vector machines are actually solved, and it is where the kernel trick comes from.