Lagrange multipliers for constrained optimization

1.2.11 · AI-ML › Calculus & Optimization Basics

The Problem Setup

Hum $f(\mathbf{x})$ optimize karna chahte hain, subject to $g(\mathbf{x})=c$ (equality constraint).

Hum seedha unconstrained optimization kyun nahi use karte? Kyunki feasible points ko $g(\mathbf{x})=c$ satisfy karna padta hai. Hum sirf is constraint surface ke saath move kar sakte hain, sabhi directions mein freely nahi.

1. Lagrangian banao: $\mathcal{L}(\mathbf{x},\lambda )=f(\mathbf{x})-\lambda (g(\mathbf{x})-c)$
2. Ye system solve karo: ${\nabla }_{\mathbf{x}}\mathcal{L}=0,\frac{\partial \mathcal{L}}{\partial \lambda }=0$

Scalar $\lambda$ hi Lagrange multiplier hai. Doosri equation constraint $g(\mathbf{x})=c$ wapas laati hai.

Derivation from First Principles

Ye kaam kyun karta hai? Ise geometrically derive karte hain.

Constrained optimum ${\mathbf{x}}^{\ast }$ par:

• $g({\mathbf{x}}^{\ast })=c$ hona chahiye (feasibility)
• Koi bhi chhota move $d\mathbf{x}$ jo hume constraint par rakhe, use satisfy karna hoga $\nabla g\cdot d\mathbf{x}=0$ (constraint surface ke tangent rehna)

Key insight: Agar hum constraint ke saath move karke $f$ improve kar sakte, to hum optimum par nahi hain. Isliye gradient $\nabla f$ ka constraint surface ke tangent koi component nahi hona chahiye.

Iska matlab hai: $\nabla f({\mathbf{x}}^{\ast })=\lambda \nabla g({\mathbf{x}}^{\ast })$

kisi scalar $\lambda$ ke liye. Dono gradients constraint surface ke perpendicular point karte hain.

Lagrangian kyun introduce karte hain? Upar wala rewrite karo: $\nabla f({\mathbf{x}}^{\ast })-\lambda \nabla g({\mathbf{x}}^{\ast })=0$

Ye exactly ${\nabla }_{\mathbf{x}}\mathcal{L}=0$ hai jab hum define karte hain $\mathcal{L}(\mathbf{x},\lambda )=f(\mathbf{x})-\lambda (g(\mathbf{x})-c)$.

Constraint $g(\mathbf{x})=c$ ban jaata hai $\frac{\partial \mathcal{L}}{\partial \lambda }=0$.

Minus sign kyun? Convention hai. Plus bhi use kar sakte hain; sirf $\lambda$ ka sign change hoga.

\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}$$ Ye 3 unknowns mein 3 equations hain: $x, y, \lambda$. **λ ki physical interpretation:** Ye ==shadow price== ya ==sensitivity coefficient== hai. Agar hum $c$ ko $c + \Delta c$ kar dein, to optimal value approximately $\lambda \Delta c$ se change hogi. ML mein: λ batata hai ki agar constraint relax karo to tumhara loss kitna decrease hoga. ## Worked Examples > [!example] Example 1: Minimize Distance to Origin on a Line > **Problem:** $f(x, y) = x^2 + y^2$ minimize karo, subject to $g(x, y) = x + y = 1$. **Yahan se kyun shuru karein?** Geometrically clear hai: line $x + y = 1$ par wo point dhundho jo origin se sabse kareeb ho. **Step 1:** Lagrangian banao $$\mathcal{L}(x, y, \lambda) = x^2 + y^2 - \lambda(x + y - 1)$$ **Ye form kyun?** Hum chahte hain $f$ minus $\lambda$ times (constraint - constant). **Step 2:** Partial derivatives lo $$\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$$ **Ye equations kyun?** Pehli do: gradients align karte hain. Teesra: constraint hold karta hai. **Step 3:** Solve karo Equations 1 aur 2 se: $x = y = \frac{\lambda}{2}$ Equation 3 mein substitute karo: $\frac{\lambda}{2} + \frac{\lambda}{2} = 1 \implies \lambda = 1$ Isliye: $x = y = \frac{1}{2}$ **Verification:** Point $(\frac{1}{2}, \frac{1}{2})$ line par hai. Origin se distance: $\sqrt{(\frac{1}{2})^2 + (\frac{1}{2})^2} = \frac{1}{\sqrt{2}} \approx 0.707$. Symmetry aur convexity se, ye minimum hai. **λ = 1 ki interpretation:** Agar line ko origin se aur door move karein (yaani $c$ 1 se 1.01 karo), to minimum distance-squared approximately $1 \times 0.01 = 0.01$ se increase hoga. > [!example] Example 2: Maximize Area of Rectangle with Fixed Perimeter > **Problem:** $f(x, y) = xy$ (area) maximize karo, subject to $g(x, y) = 2x + y = 20$ (perimeter = 20). **ML mein ye kyun matter karta hai?** Ye resource allocation problems ka structure hai: budget constraints ke subject to utility maximize karo. **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$$ **Pehli do equations symmetric kyun hain?** Kyunki $f$ aur $g$ dono $x$ aur $y$ mein symmetric hain. **Step 3:** Solve karo Equations 1 aur 2 se: $x = y = 2\lambda$ Equation 3 mein substitute karo: $2\lambda + 2\lambda = 10 \implies \lambda = 2.5$ Isliye: $x = y = 5$ **Physical check:** Ek square (5×5) ka maximum area (25) hota hai fixed perimeter (20) ke liye. Ye ek classical result hai. **λ = 2.5 ki interpretation:** Agar perimeter constraint 20 se 21 karein, to maximum area approximately 2.5 square units badhega. (Actual: perimeter 20 se 21 karne par, optimal 5.25×5.25 = 27.5625 hai, gain 2.5625 ≈ 2.5 hai). > [!example] Example 3: SVM-Style Optimization (ML Application) > **Problem:** $f(w) = \frac{1}{2}||w||^2 = \frac{1}{2}(w_1^2 + w_2^2)$ minimize karo, subject to $g(w) = w_1 + 2w_2 = 4$. **Ye structure kyun?** Ye SVM objective mimick karta hai: margin constraints ke subject to weights ka norm minimize karo. **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 karo $w_1 = \lambda$ aur $w_2 = 2\lambda$ constraint mein substitute karo: $$\lambda + 2(2\lambda) = 4 \implies 5\lambda = 4 \implies \lambda = \frac{4}{5}$$ Isliye: $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$ **Ye minimum kyun hai:** Objective convex hai (quadratic), constraint linear hai, aur humne unique stationary point find kar liya. ## Multiple Constraints $m$ equality constraints $g_i(\mathbf{x}) = c_i$ ke liye, $m$ multipliers use karo: $$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) - \sum_{i=1}^m \lambda_i(g_i(\mathbf{x}) - c_i)$$ Solve karo: $\nabla_{\mathbf{x}} \mathcal{L} = 0$ aur $\frac{\partial \mathcal{L}}{\partial \lambda_i} = 0$ sabhi $i$ ke liye. **Sum kyun?** Har constraint null space mein ek dimension add karta hai jise hume respect karna hota hai. Har gradient $\nabla g_i$ ko $\nabla f$ se balance karna padta hai. > [!mistake] Common Mistake: Forgetting the Constraint Equation > **Galat approach:** Sirf $\nabla_{\mathbf{x}} \mathcal{L} = 0$ solve karo aur $\frac{\partial \mathcal{L}}{\partial \lambda} = 0$ bhool jao. **Ye sahi kyun lagta hai:** Tum "derivatives lo aur zero set karo" dekhte ho aur mechanically apply karte ho. **Ye galat kyun hai:** Tumhare paas $n+1$ unknowns hain ($\mathbf{x}$ ke $n$ components plus $\lambda$) lekin sirf $\nabla_{\mathbf{x}} \mathcal{L} = 0$ se $n$ equations milte hain. System underdetermined ho jaata hai. **Fix:** Hamesha $\frac{\partial \mathcal{L}}{\partial \lambda} = 0$ include karo, jo tumhe constraint $g(\mathbf{x}) = c$ wapas deta hai. Ye missing equation provide karta hai. > [!mistake] Common Mistake: Sign Confusion in the Lagrangian > **Galat approach:** $\mathcal{L} = f + \lambda g$ vs. $\mathcal{L} = f - \lambda g$ inconsistently use karo. **Ye sahi kyun lagta hai:** Alag-alag textbooks alag conventions use karte hain, confusion create hoti hai. **Ye kyun matter karta hai:** Sign $\lambda$ ki interpretation affect karta hai. $\mathcal{L} = f - \lambda(g - c)$ ke saath, positive $\lambda$ ka matlab hai $f$ badhta hai jab $c$ badhta hai (maximum problem ke liye). $\mathcal{L} = f + \lambda(g - c)$ ke saath, interpretation flip ho jaati hai. **Fix:** Ek convention choose karo (hum minus use karte hain) aur usi par tikay raho. Optimal $\mathbf{x}^*$ same rahega; sirf $\lambda$ ka sign change hoga. > [!mistake] Common Mistake: Using Lagrange Multipliers on Inequality Constraints > **Galat approach:** Basic Lagrange method ko $g(\mathbf{x}) \leq c$ par bina modification ke apply karo. **Ye tempting kyun lagta hai:** Method itna clean lagta hai, phir ise har jagah kyun nahi use karein? **Ye fail kyun hota hai:** Gradient condition $\nabla f = \lambda \nabla g$ assume karta hai ki tum exactly constraint surface par ho. Inequality constraints ke saath, optimum interior mein ho sakta hai jahan $g(\mathbf{x}) < c$, aur constraint "bind" nahi karta. **Fix:** ==KT (Karush-Kuhn-Tucker) conditions== use karo, jo Lagrange multipliers ko inequality constraints tak extend karte hain complementary slackness ke saath: $\lambda_i \geq 0$ aur $\lambda_i(g_i(\mathbf{x}) - c_i) = 0$. Agar constraint inactive hai, to $\lambda_i = 0$. ## Connection to Machine Learning **SVMs:** Core SVM optimization ye hai: $$\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$$ Lagrangian har constraint ke liye multipliers $\alpha_i$ introduce karta hai. KT conditions apply karne ke baad, dual problem milta hai, jahan sirf support vectors (points jahan $\alpha_i > 0$) matter karte hain. **Neural Network Regularization:** Constraint $||w||^2 \leq C$ add karna equivalently loss mein $\frac{\lambda}{2}||w||^2$ add karne ke barabar hai (Lagrangian form). Multiplier $\lambda$ regularization strength ban jaata hai. **Constrained RL:** Safe reinforcement learning mein, tum safety constraints ke subject to reward maximize karte ho. Lagrange multipliers policy parameters ban jaate hain jo task performance aur constraint satisfaction ko balance karte hain. > [!recall]- Ek 12-Saal Ke Bachche Ko Samjhao > Socho tum ek pahaad par ho (tumhara goal: sabse uuncha point reach karna = profit maximize karna), lekin ek fence hai jise tum cross nahi kar sakte (constraint = tumhara budget). Agar tum fence par sabse achhe spot par ho, to tum fence ke saath walk karke aur uupar nahi ja sakte—tum pehle se us highest point par ho jo fence allow karta hai. Mathematically, "fence ke saath uupar nahi ja sakte" ka matlab hai ki uupar jaane wali direction (profit ka gradient) fence direction (constraint ka gradient) ke perpendicular hai. Lagrange multipliers sirf tumhe us special spot ko dhundhne ka systematic tarika dete hain. Multiplier λ batata hai: "Agar maine fence ko mujhse 1 meter door kar diya, to meri height λ meters badhegi." Agar λ bada hai, to fence sach mein tumhe rok rahi hai! > [!mnemonic] GALS: Gradients Align, Lambda Scales > - **G**radients align karne chahiye: $\nabla f \parallel \nabla g$ > - **A**lignment enforce karne ke liye ek variable (Lambda) add karo > - **L**agrangian = objective - λ(constraint - constant) > - **S**ystem solve karo: $\nabla_x \mathcal{L} = 0$ aur $\partial_\lambda \mathcal{L} = 0$ ## Connections - [[Gradient Descent]] - unconstrained optimization method - [[KT Conditions]] - inequality constraints tak extension - [[Support Vector Machines]] - training ke liye Lagrangian duality use karta hai - [[Regularization]] - constrained optimization ke equivalent - [[Convex Optimization]] - jab Lagrange method global optimum guarantee karta hai - [[Duality Theory]] - primal aur dual problems ka relationship - [[Penalty Methods]] - unconstrained optimization ke through alternative approach #flashcards/ai-ml Constrained optimum par geometric condition kya hai? :: Objective function ka gradient, constraint function ke gradient ke parallel hona chahiye (dono constraint surface ke perpendicular hote hain). f(x) ko g(x) = c ke subject to minimize karne ka Lagrangian kya hai? ::: L(x, λ) = f(x) - λ(g(x) - c) Lagrange multiplier method mein tum kaunsi do conditions solve karte ho? ::: (1) ∇ₓL = 0 (x ke respect mein gradient) aur (2) ∂L/∂λ = 0 (constraint g(x) = c wapas laata hai). Lagrange multiplier λ kya represent karta hai? ::: Shadow price ya sensitivity coefficient—agar constraint ek unit se relax ho, to optimal objective value kitna change hoga. Ek constraint ke saath 2D optimization mein tum kitni equations solve karte ho? ::: 3 equations (do ∇ₓL = 0 se, ek ∂L/∂λ = 0 se) 3 unknowns mein (x, y, λ). Tum inequality constraints par basic Lagrange multipliers kyun apply nahi kar sakte? ::: Kyunki optimum interior mein ho sakta hai jahan constraint bind nahi karta (g(x) < c), isliye gradient alignment condition hold nahi hoti. Lagrange multipliers aur L2 regularization ka kya relationship hai? ::: f(x) minimize karna subject to ||x||² ≤ C, f(x) + (λ/2)||x||² (unconstrained) minimize karne ke equivalent hai, jahan λ Lagrange multiplier hai. SVM optimization mein non-zero Lagrange multipliers kya correspond karte hain? ::: Support vectors—wo training points jo exactly margin boundary par hain. ## 🖼️ 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] ```