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:

Core resources (read/watch one of the following)

-Free-

Convex Optimization
A graduate-level textbook on convex optimization.
Authors: Stephen Boyd,Lieven Vandenberghe
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: Applications in algorithms: