Langrange duality
(9 hours to learn)
Summary
The Lagrange dual of a convex optimization problem is another convex optimization problem where the optimization variables are the Lagrange multipliers of the original problem. It leads to surprising relationships between seemingly different optimization problems. Duality is commonly used in approximation algorithms, since constraining the dual corresponds to relaxing the original problem.
Context
This concept has the prerequisites:
- convex optimization (Lagrange duality is a property of convex optimization problems.)
- Lagrange multipliers (The optimization variables in the dual problem are the Lagrange multipliers.)
Core resources (read/watch one of the following)
-Free-
→ Convex Optimization
A graduate-level textbook on convex optimization.
Other notes:
- See Section 3.3 for the definition of the convex conjuate and Section 4.3 for the definition of a linear program.
See also
- The KKT conditions characterize the optimal solutions to a convex optimization problem.
- Applications in machine learning and statistics:
- Support vector machines (SVMs) , a classification algorithm, use duality in the optimization.
- Variational inference , where an intractable distribution is approximated with a tractable one, can be thought of in terms of convex duality.
- The relationship between min-cut and max-flow is an example of Lagrange duality.