Lagrangian Duality

Optimization · Axiom Academy

Understanding the powerful relationship between primal and dual optimization problems Consider the constrained optimization problem (the "primal" problem): The Lagrangian combines the objective and constraints into a single function by introducing dual variables (Lagrange multipliers) λ and μ : Here, λ ≥ 0 are multipliers for inequality constraints, and μ (unrestricted) are multipliers for equality constraints. The Lagrangian encodes the entire optimization problem. The Lagrange dual function is obtained by minimizing the Lagrangian over x for fixed dual variables: The dual function g(λ,μ) represents the best lower bound on the optimal value p* achievable for given dual variables. It's a pointwise infimum of affine functions of (λ,μ). 3. The Dual Function is Always Concave A remarkable fact: g(λ,μ) is concave , regardless of whether the primal problem is convex! This means the dual problem will always be a concave maximization problem (equivalently, a convex minimization problem), even when the primal is non-convex. The weak duality theorem states that the optimal dual value d* provides a lower bound on the optimal primal value p*: This inequality holds always , for any optimization problem, regardless of convexity. The difference (p* - d*) is called the duality gap . Since g(λ,μ) provides lower bounds on p*, we seek the best lower bound by maximizing the dual function:

This is the written version of the interactive lesson above. See the full Optimization course.