gen-briefly-explain-lagrangian-duality-and-one-common-misconcept-8c6a

Briefly explain Lagrangian duality and one common misconception about it.

# Lagrangian Duality **Core Idea:** Lagrangian duality transforms a constrained optimization problem (the "primal") into an alternative problem (the "dual") that provides bounds on the optimal value. For a primal problem: - Minimize f(x) subject to constraints g(x) ≤ 0, h(x) = 0 We form the Lagrangian L(x, λ, ν) = f(x) + λᵀg(x) + νᵀh(x) and define the dual function as the minimum over x. The dual problem maximizes this dual function over λ ≥ 0, ν. **Key property:** The dual optimal value always lower bounds the primal optimal (weak duality). Under certain conditions (like convexity), they're equal (strong duality). ## Common Misconception **"Strong duality always holds"** - Many assume that the primal and dual optimal values are always equal. In reality, strong duality requires specific conditions: - **Convexity** of the problem (convex objective, convex inequality constraints, affine equality constraints) - **Constraint qualifications** like Slater's condition (existence of a strictly feasible point) For non-convex problems, there's often a "duality gap" where the dual provides only a loose bound, which is why dual methods can't always solve general optimization problems.