gen-define-lagrangian-duality-and-give-one-short-worked-example-fa20

Define Lagrangian duality and give one short worked example.

# Lagrangian Duality ## Definition **Primal Problem:** ``` minimize f(x) subject to g_i(x) ≤ 0, i = 1,...,m h_j(x) = 0, j = 1,...,p ``` **Lagrangian:** L(x, λ, ν) = f(x) + Σᵢ λᵢg_i(x) + Σⱼ νⱼh_j(x) where λᵢ ≥ 0 are inequality multipliers and νⱼ are equality multipliers. **Dual function:** g(λ, ν) = inf_x L(x, λ, ν) **Dual Problem:** ``` maximize g(λ, ν) subject to λ ≥ 0 ``` **Key property:** Weak duality always holds: g(λ, ν) ≤ p* (optimal primal value). Under certain conditions (e.g., convexity + constraint qualifications), strong duality holds: g(λ*, ν*) = p*. ## Worked Example **Primal:** ``` minimize x² subject to x ≥ 1 ``` **Step 1:** Form Lagrangian with g(x) = 1 - x ≤ 0: L(x, λ) = x² + λ(1 - x) **Step 2:** Find dual function (minimize over x): ∂L/∂x = 2x - λ = 0 ⟹ x = λ/2 g(λ) = (λ/2)² + λ(1 - λ/2) = λ²/4 + λ - λ²/2 = **λ - λ²/4** **Step 3:** Solve dual (maximize g(λ) for λ ≥ 0): dg/dλ = 1 - λ/2 = 0 ⟹ λ* = 2 g(2) = 2 - 1 = **1** **Verification:** Primal optimum: x* = 1, f(x*) = 1. Strong duality holds! ✓