Lagrange multipliers for constrained optimization

The Problem Setup

We want to optimize $f(\mathbf{x})$ subject to $g(\mathbf{x}) = c$ (equality constraint).

Why can't we just use unconstrained optimization? Because feasible points must satisfy $g(\mathbf{x}) = c$. We can only move along this constraint surface, not freely in all directions.

1. Form the Lagrangian: $\mathcal{L}(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda(g(\mathbf{x}) - c)$
2. Solve the system: $\nabla_{\mathbf{x}} \mathcal{L} = 0, \quad \frac{\partial \mathcal{L}}{\partial \lambda} = 0$

The scalar $\lambda$ is the Lagrange multiplier. The second equation recovers the constraint $g(\mathbf{x}) = c$.

Derivation from First Principles

Why does this work? Let's derive it geometrically.

At a constrained optimum $\mathbf{x}^*$:

• We must have $g(\mathbf{x}^*) = c$ (feasibility)
• Any small move $d\mathbf{x}$ that keeps us on the constraint must satisfy $\nabla g \cdot d\mathbf{x} = 0$ (staying tangent to the constraint surface)

Key insight: If we could improve $f$ by moving along the constraint, we're not at an optimum. So the gradient $\nabla f$ must have no component tangent to the constraint surface.

This means: $\nabla f(\mathbf{x}^*) = \lambda \nabla g(\mathbf{x}^*)$

for some scalar $\lambda$. Both gradients point perpendicular to the constraint surface.

Why introduce the Lagrangian? Rewrite the above as: $\nabla f(\mathbf{x}^*) - \lambda \nabla g(\mathbf{x}^*) = 0$

This is exactly $\nabla_{\mathbf{x}} \mathcal{L} = 0$ when we define $\mathcal{L}(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda(g(\mathbf{x}) - c)$.

The constraint $g(\mathbf{x}) = c$ becomes $\frac{\partial \mathcal{L}}{\partial \lambda} = 0$.

Why the minus sign? Convention. Could use plus; just affects the sign of $\lambda$.

\frac{\partial f}{\partial x} - \lambda \frac{\partial g}{\partial x} &= 0 \\ \frac{\partial f}{\partial y} - \lambda \frac{\partial g}{\partial y} &= 0 \\ g(x, y) &= c \end{align}$$ This is 3 equations in 3 unknowns: $x, y, \lambda$. **Physical interpretation of λ:** It's the ==shadow price== or ==sensitivity coefficient==. If we change $c$ to $c + \Delta c$, the optimal value changes by approximately $\lambda \Delta c$. In ML: λ tells you how much your loss would decrease if you relaxed a constraint. ## Worked Examples > [!example] Example 1: Minimize Distance to Origin on a Line > **Problem:** Minimize $f(x, y) = x^2 + y^2$ subject to $g(x, y) = x + y = 1$. **Why start here?** Geometrically clear: find the point on the line $x + y = 1$ closest to the origin. **Step 1:** Form Lagrangian $$\mathcal{L}(x, y, \lambda) = x^2 + y^2 - \lambda(x + y - 1)$$ **Why this form?** We want $f$ minus $\lambda$ times (constraint - constant). **Step 2:** Take partial derivatives $$\frac{\partial \mathcal{L}}{\partial x} = 2x - \lambda = 0 \implies x = \frac{\lambda}{2}$$ $$\frac{\partial \mathcal{L}}{\partial y} = 2y - \lambda = 0 \implies y = \frac{\lambda}{2}$$ $$\frac{\partial \mathcal{L}}{\partial \lambda} = -(x + y - 1) = 0 \implies x + y = 1$$ **Why these equations?** First two: gradients align. Third: constraint holds. **Step 3:** Solve From equations1 and 2: $x = y = \frac{\lambda}{2}$ Substitute into equation 3: $\frac{\lambda}{2} + \frac{\lambda}{2} = 1 \implies \lambda = 1$ Therefore: $x = y = \frac{1}{2}$ **Verification:** The point $(\frac{1}{2}, \frac{1}{2})$ is on the line. Distance to origin: $\sqrt{(\frac{1}{2})^2 + (\frac{1}{2})^2} = \frac{1}{\sqrt{2}} \approx 0.707$. By symmetry and convexity, this is the minimum. **Interpreting λ = 1:** If we move the line further from the origin (increase $c$ from 1 to 1.01), the minimum distance-squared increases by approximately $1 \times 0.01 = 0.01$. > [!example] Example 2: Maximize Area of Rectangle with Fixed Perimeter > **Problem:** Maximize $f(x, y) = xy$ (area) subject to $g(x, y) = 2x + y = 20$ (perimeter = 20). **Why this matters for ML?** This is the structure of resource allocation problems: maximize utility subject to budget constraints. **Step 1:** Lagrangian $$\mathcal{L}(x, y, \lambda) = xy - \lambda(2x + 2y - 20)$$ **Step 2:** Derivatives $$\frac{\partial \mathcal{L}}{\partial x} = y - 2\lambda = 0 \implies y = 2\lambda$$ $$\frac{\partial \mathcal{L}}{\partial y} = x - 2\lambda = 0 \implies x = 2\lambda$$ $$\frac{\partial \mathcal{L}}{\partial \lambda} = -(2x + 2y - 20) = 0 \implies x + y = 10$$ **Why are the first two equations symmetric?** Because $f$ and $g$ are symmetric in $x$ and $y$. **Step 3:** Solve From equations 1 and 2: $x = y = 2\lambda$ Substitute into equation 3: $2\lambda + 2\lambda = 10 \implies \lambda = 2.5$ Therefore: $x = y = 5$ **Physical check:** A square (5×5) has the maximum area (25) for a fixed perimeter (20). This is a classical result. **Interpreting λ = 2.5:** If we increase the perimeter constraint from 20 to 21, the maximum area increases by approximately 2.5 square units. (Actual: going from perimeter 20 to 21, optimal is 5.25×5.25 = 27.5625, gain is 2.5625≈ 2.5). > [!example] Example 3: SVM-Style Optimization (ML Application) > **Problem:** Minimize $f(w) = \frac{1}{2}||w||^2 = \frac{1}{2}(w_1^2 + w_2^2)$ subject to $g(w) = w_1 + 2w_2 = 4$. **Why this structure?** This mimics the SVM objective: minimize norm of weights subject to margin constraints. **Step 1:** Lagrangian $$\mathcal{L}(w_1, w_2, \lambda) = \frac{1}{2}(w_1^2 + w_2^2) - \lambda(w_1 + 2w_2 - 4)$$ **Step 2:** Derivatives $$\frac{\partial \mathcal{L}}{\partial w_1} = w_1 - \lambda = 0 \implies w_1 = \lambda$$ $$\frac{\partial \mathcal{L}}{\partial w_2} = w_2 - 2\lambda = 0 \implies w_2 = 2\lambda$$ $$\frac{\partial \mathcal{L}}{\partial \lambda} = -(w_1 + 2w_2 - 4) = 0 \implies w_1 + 2w_2 = 4$$ **Step 3:** Solve Substitute $w_1 = \lambda$ and $w_2 = 2\lambda$ into constraint: $$\lambda + 2(2\lambda) = 4 \implies 5\lambda = 4 \implies \lambda = \frac{4}{5}$$ Therefore: $w_1 = \frac{4}{5}, \quad w_2 = \frac{8}{5}$ **Check:** $||w||^2 = (\frac{4}{5})^2 + (\frac{8}{5})^2 = \frac{16 + 64}{25} = \frac{80}{25} = 3.2$ **Why this is minimum:** The objective is convex (quadratic), the constraint is linear, and we found the unique stationary point. ## Multiple Constraints For $m$ equality constraints $g_i(\mathbf{x}) = c_i$, use $m$ multipliers: $$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) - \sum_{i=1}^m \lambda_i(g_i(\mathbf{x}) - c_i)$$ Solve: $\nabla_{\mathbf{x}} \mathcal{L} = 0$ and $\frac{\partial \mathcal{L}}{\partial \lambda_i} = 0$ for all $i$. **Why the sum?** Each constraint adds one dimension to the null space we must respect. Each gradient $\nabla g_i$ must be balanced by $\nabla f$. > [!mistake] Common Mistake: Forgetting the Constraint Equation > **Wrong approach:** Solve only $\nabla_{\mathbf{x}} \mathcal{L} = 0$ and forget $\frac{\partial \mathcal{L}}{\partial \lambda} = 0$. **Why it feels right:** You see "take derivatives and set to zero" and apply it mechanically. **Why it's wrong:** You have $n+1$ unknowns ($n$ components of $\mathbf{x}$ plus $\lambda$) but only $n$ equations from $\nabla_{\mathbf{x}} \mathcal{L} = 0$. The system is underdetermined. **The fix:** Always include $\frac{\partial \mathcal{L}}{\partial \lambda} = 0$, which gives you back the constraint $g(\mathbf{x}) = c$. This provides the missing equation. > [!mistake] Common Mistake: Sign Confusion in the Lagrangian > **Wrong approach:** Use $\mathcal{L} = f + \lambda g$ vs. $\mathcal{L} = f - \lambda g$ inconsistently. **Why it feels right:** Different textbooks use different conventions, creating confusion. **Why it matters:** The sign affects the interpretation of $\lambda$. With $\mathcal{L} = f - \lambda(g - c)$, a positive $\lambda$ means $f$ increases as $c$ increases (for a maximum problem). With $\mathcal{L} = f + \lambda(g - c)$, the interpretation flips. **The fix:** Pick one convention (we use minus) and stick with it. The optimal $\mathbf{x}^*$ will be the same; only the sign of $\lambda$ changes. > [!mistake] Common Mistake: Using Lagrange Multipliers on Inequality Constraints > **Wrong approach:** Apply the basic Lagrange method to $g(\mathbf{x}) \leq c$ without modification. **Why it's tempting:** The method looks so clean, why not use it everywhere? **Why it fails:** The gradient condition $\nabla f = \lambda \nabla g$ assumes you're exactly on the constraint surface. With inequality constraints, the optimum might be in the interior where $g(\mathbf{x}) < c$, and the constraint doesn't "bind." **The fix:** Use ==KT (Karush-Kuhn-Tucker) conditions==, which extend Lagrange multipliers to inequality constraints with complementary slackness: $\lambda_i \geq 0$ and $\lambda_i(g_i(\mathbf{x}) - c_i) = 0$. If the constraint is inactive, $\lambda_i = 0$. ## Connection to Machine Learning **SVMs:** The core SVM optimization is: $$\min_{w, b} \frac{1}{2}||w||^2 \quad \text{s.t.} \quad y_i(w \cdot x_i + b) \geq 1 \quad \forall i$$ The Lagrangian introduces multipliers $\alpha_i$ for each constraint. After applying KT conditions, you get the dual problem, where only support vectors (points with $\alpha_i > 0$) matter. **Neural Network Regularization:** Adding a constraint $||w||^2 \leq C$ can be equivalently written as adding $\frac{\lambda}{2}||w||^2$ to the loss (the Lagrangian form). The multiplier $\lambda$ becomes the regularization strength. **Constrained RL:** In safe reinforcement learning, you maximize reward subject to safety constraints. Lagrange multipliers become policy parameters that balance task performance and constraint satisfaction. > [!recall]- Explain to a 12-Year-Old > Imagine you're on a mountain (your goal: reach the highest point = maximize profit), but there's a fence you can't cross (the constraint = your budget). If you're at the best spot on the fence, you can't walk along the fence and go uphill—you're already at the highest point the fence allows. Mathematically, "can't go uphill along the fence" means the uphill direction (gradient of profit) is perpendicular to the fence direction (gradient of constraint). Lagrange multipliers just give you a systematic way to find that special spot. The multiplier λ tells you: "If I moved the fence 1 meter away from me, my height would increase by λ meters." If λ is big, the fence is really holding you back! > [!mnemonic] GALS: Gradients Align, Lambda Scales > - **G**radients must align: $\nabla f \parallel \nabla g$ > - **A**dd a variable (Lambda) to enforce alignment > - **L**agrangian = objective - λ(constraint - constant) > - **S**olve the system: $\nabla_x \mathcal{L} = 0$ and $\partial_\lambda \mathcal{L} = 0$ ## Connections - [[Gradient Descent]] - unconstrained optimization method - [[KT Conditions]] - extension to inequality constraints - [[Support Vector Machines]] - uses Lagrangian duality for training - [[Regularization]] - equivalent to constrained optimization - [[Convex Optimization]] - when Lagrange method guarantees global optimum - [[Duality Theory]] - relationship between primal and dual problems - [[Penalty Methods]] - alternative approach via unconstrained optimization #flashcards/ai-ml What is the geometric condition at constrained optimum? :: The gradient of the objective function must be parallel to the gradient of the constraint function (both perpendicular to the constraint surface). What is the Lagrangian for minimizing f(x) subject to g(x) = c? ::: L(x, λ) = f(x) - λ(g(x) - c) What are the two conditions you solve in the Lagrange multiplier method? ::: (1) ∇ₓL = 0 (gradient with respect to x) and (2) ∂L/∂λ = 0 (recovers the constraint g(x) = c). What does the Lagrange multiplier λ represent? ::: The shadow price or sensitivity coefficient—how much the optimal objective value would change if you relaxed the constraint by one unit. For2D optimization with one constraint, how many equations do you solve? ::: 3 equations (two from∇ₓL = 0, one from ∂L/∂λ = 0) in 3 unknowns (x, y, λ). Why can't you apply basic Lagrange multipliers to inequality constraints? ::: Because the optimum might be in the interior where the constraint doesn't bind (g(x) < c), so the gradient alignment condition doesn't hold. What is the relationship between Lagrange multipliers and L2 regularization? ::: Minimizing f(x) subject to ||x||² ≤ C is equivalent to minimizing f(x) + (λ/2)||x||² (unconstrained), where λ is the Lagrange multiplier. In SVM optimization, what do non-zero Lagrange multipliers correspond to? ::: Support vectors—the training points that lie exactly on the margin boundary. ## 🖼️ Concept Map ```mermaid flowchart TD P[Constrained problem: max f x] -->|subject to| C[Constraint g x = c] C -->|restricts to| S[Constraint surface] S -->|feasible moves satisfy| T[grad g dot dx = 0] T -->|at optimum f cannot improve| G[grad f parallel to grad g] G -->|means| E[grad f = lambda grad g] E -->|rewritten as| L[Lagrangian L = f minus lambda times g minus c] L -->|stationarity| SX[grad_x L = 0] L -->|derivative wrt lambda| SL[dL/dlambda = 0 recovers constraint] SX --> SYS[Solve system: x, y, lambda] SL --> SYS E -->|scalar lambda is| SP[Shadow price / sensitivity] SP -->|value change| DV[delta f approx lambda times delta c] ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Lagrange multipliers ka basic idea yeh hai ki jab ap kisi function ko optimize karna chahte ho (maximize ya minimize), lekin apke pas kuch constraints hain (jaise budget limit ya resource limit), toh aap freely har direction mein nahi ja sakte. Aapko constraint surface pe hi rehna padega. > > Geometric intuition samajhiye: agar aap optimum point pe ho aur constraint ke saath-saath move karo, toh aapko uphill ya downhill nahi jana chahiye—warna woh optimum nahi tha! Iska matlab hai ki objective function ka gradient aur constraint function ka gradient parallel hone chahiye. Lagrange multiplier λek scaling factor hai jo bata hai kiagar aap constraint ko thoda relax karo (jaise budget 100 se101 karo), toh optimal value kitna improve hogi. > > Machine learning mein yeh technique bahut kaam ati hai—SVMs mein margin constraints handle karne ke liye, neural networks mein regularization ke liye (jahan weight size ko limit karna hota hai), aur safe RL mein jahan apko reward maximize karna hai lekin safety constraints maintain karni hain. Formula simple hai: Lagrangian banao (objective - λ × constraint), phir sab variables ke respect mein derivatives lo aur zero set karo. Result: apko optimal point aur λ ki value mil jaati hai. ![[audio/1.2.11-Lagrange-multipliers-for-constrained-optimization.mp3]]