Worked examples — KKT conditions for constrained optimization

4.10.19 · D3 · Maths › Advanced Topics (Elite Level) › KKT conditions for constrained optimization

Shuru karne se pehle, vocabulary ko dobara anchor karte hain taaki kuch bhi bina explain ke use na ho.

Working recipe yaad karo (hum ise har example mein use karte hain):

1. Likho $\mathcal{L}=f+{\sum }_i{\lambda }_i{g}_i+{\sum }_j{\mu }_j{h}_j$ (pehle har $g$ ko $\le 0$ form mein daalo!).
2. ${\nabla }_x\mathcal{L}=0$ set karo (stationarity).
3. Guess karo ki kaun si inequalities active hain. Inactive ⇒ uska $\lambda =0$; active ⇒ uska $g=0$.
4. Solve karo. Phir verify karo: primal feasibility, $\lambda \ge 0$, slackness. Agar koi $\lambda <0$ aaye, to guess galat tha — doosra active-set try karo.

---

Scenario matrix

#	Cell (kya cheez ise alag banati hai)	Example
A	Saari inequalities inactive (interior min)	Ex 1
B	Ek inequality active, positive $\lambda$	Ex 2
C	Equality + inequality saath mein, $\mu <0$ (sign-free)	Ex 3
D	Galat active-set guess → $\lambda <0$ flag, phir repair	Ex 4
E	Do inequalities ek saath active (ek cone / corner)	Ex 5
F	Degenerate LICQ failure — multipliers exist hi nahi karte	Ex 6
G	Limiting case: constraint budget $\to$ answer ko smoothly move karta hai	Ex 7
H	Word problem (real units) ek active budget ke saath	Ex 8
I	Exam twist: non-convex, KKT ek maximum bhi pakad leta hai	Ex 9

In rows mein cover hai: har activity combination (inactive / ek active / do active), dono multiplier signs, qualification ki failure, ek limit, ek real-world model, aur ek non-convex trap.

---

Example A — sab kuch inactive (interior minimum)

1. Lagrangian. $\mathcal{L}=(x-2{)}^2+(y-1{)}^2+{\lambda }_1(x+y-10)+{\lambda }_2(-x)$. Yeh step kyun? Dono fences already $\le 0$ form mein hain, isliye hum bas unhe append karte hain.
2. Guess karo dono inactive ⇒ ${\lambda }_1={\lambda }_2=0$. Yeh step kyun? Sabse sasta possible outcome unconstrained minimum hai; pehle usse test karo.
3. Stationarity. ${\partial }_x\mathcal{L}=2(x-2)=0\Rightarrow x=2$; ${\partial }_y\mathcal{L}=2(y-1)=0\Rightarrow y=1$. Yeh step kyun? $\nabla f=0$ woh jagah hai jahan ground flat hai — kisi fence ki zaroorat nahi.
4. Feasibility check karo. $g_1=2+1-10=-7\le 0$ ✓, $g_2=-2\le 0$ ✓. Slackness ${\lambda }_i{g}_i=0$ ✓.

---

Example B — ek fence active (positive $\lambda$)

1. Lagrangian. $\mathcal{L}=x^2+y^2+\lambda (1-x-y)$. Yeh step kyun? Standard build; fence already $\le 0$ form mein hai.
2. Stationarity. $2x-\lambda =0,2y-\lambda =0\Rightarrow x=y=\lambda /2$. Yeh step kyun? Rest par, $\nabla f=(2x,2y)$ ko fence ke push $\lambda \nabla g=\lambda (-1,-1)$ se cancel hona chahiye.
3. Guess active ⇒ $g=0\Rightarrow x+y=1\Rightarrow 2x=1\Rightarrow x=y=\frac{1}{2}$. Yeh step kyun? Origin infeasible hai, isliye answer boundary par hi hona chahiye.
4. Multiplier. $\lambda =2x=1$. Check karo $\lambda =1\ge 0$ ✓ (dual feasibility).

---

Example C — equality + inequality, negative $\mu$

1. Lagrangian. $\mathcal{L}=x^2+y^2+\mu (x+y-2)+\lambda (0.5-x)$. Yeh step kyun? Equality ko free-sign $\mu$ milta hai; inequality ko $\lambda \ge 0$ milta hai.
2. Guess karo $g$ inactive ⇒ $\lambda =0$. Yeh step kyun? Akela wire hi ball ko $x>0.5$ wali jagah rok sakta hai.
3. Stationarity. $2x+\mu =0,2y+\mu =0\Rightarrow x=y$. $x+y=2$ ke saath: $x=y=1$. Yeh step kyun? Wire par, dono partials ek hi $\mu$ dete hain, jo symmetry force karta hai.
4. Multiplier & checks. $\mu =-2x=-2$. Check karo $g=0.5-1=-0.5\le 0$ ✓ (fence untouched). Slackness $\lambda g=0$ ✓. Yeh step kyun? Humne step 2 mein $g$ inactive assume kiya tha; woh assumption tabhi legitimate hai jab solved point actually $g<0$ satisfy kare — isliye hum back plug karke confirm karte hain, aur confirm karte hain ki slackness $\lambda g=0$ automatically hold hoti hai kyunki $\lambda =0$ hai.

---

Example D — galat guess khud flag karta hai ($\lambda <0$), phir repair

1. Galat guess: $g_1$ active ⇒ $x=5$, ${\lambda }_2=0$. Yeh step kyun? Woh self-correcting flag demonstrate karne ke liye jo parent note warn karta hai.
2. Stationarity. $\mathcal{L}=(x-3{)}^2+{\lambda }_1(x-5)+{\lambda }_2(-x)$, isliye $2(x-3)+{\lambda }_1-{\lambda }_2=0$. $x=5,{\lambda }_2=0$ par: $2(2)+{\lambda }_1=0\Rightarrow {\lambda }_1=-4$. Yeh step kyun? Assumed system solve karne par multiplier milta hai.
3. Flag padhna. ${\lambda }_1=-4<0$ dual feasibility violate karta hai — yeh active-set impossible hai. Ise discard karo. Yeh step kyun? Negative inequality multiplier mathematical tarike se chilla raha hai "is fence ko pull karna padega, lekin fences sirf push karti hain."
4. Correct guess: dono inactive. ${\lambda }_1={\lambda }_2=0\Rightarrow 2(x-3)=0\Rightarrow x=3$. Feasibility $0\le 3\le 5$ ✓, slackness ✓. Yeh step kyun? $g_1$ active rule out karne ke baad, ek hi remaining candidate active-set hai jo $\lambda \ge 0$ respect karta hai — "koi fence active nahi"; hum usse test karte hain aur woh chaar saare KKT conditions pass karta hai, isliye woh genuine optimum hai.

---

Example E — do fences ek saath active (corner / cone)

1. Lagrangian. $\mathcal{L}=(x+2{)}^2+(y+3{)}^2+{\lambda }_1(-x)+{\lambda }_2(-y)$. Yeh step kyun? Do inequalities, dono $\le 0$ form mein.
2. Guess dono active ⇒ $x=0,y=0$. Yeh step kyun? Dono fences target se origin ki taraf point karti hain; corner natural rest hai.
3. Stationarity. ${\partial }_x:2(x+2)-{\lambda }_1=0\Rightarrow {\lambda }_1=2(0+2)=4$; ${\partial }_y:2(y+3)-{\lambda }_2=0\Rightarrow {\lambda }_2=6$. Yeh step kyun? Har active fence apna push ${\lambda }_i$ supply karta hai $\nabla f$ ke us component ko cancel karne ke liye.
4. Checks. ${\lambda }_1=4\ge 0$, ${\lambda }_2=6\ge 0$ ✓. Dono $g_i=0$ hain isliye slackness ✓. Yeh step kyun? "Dono active" guess tabhi valid hai jab dono multipliers non-negative niklen (dual feasibility); hume har ${\lambda }_i\ge 0$ confirm karna hai, warna ek negative wala corner ko galat active-set flag karega.

---

Example F — degenerate: LICQ fail, koi multipliers nahi

1. $(0,0)$ par active gradients. Dono constraints wahan active hain ($g_1=g_2=0$). $\nabla g_1=(-3x^2,1)=(0,1)$ aur $\nabla g_2=(-3x^2,-1)=(0,-1)$. Yeh step kyun? KKT stationarity ko $\nabla f$ ka inki non-negative combination hona chahiye.
2. Stationarity attempt. $\nabla f=(1,0)$. Humein chahiye $(1,0)+{\lambda }_1(0,1)+{\lambda }_2(0,-1)=0$. Yeh step kyun? Required cancellation componentwise likhna.
3. Contradiction. $x$-component padhta hai $1+0=0$ — impossible. Koi ${\lambda }_1,{\lambda }_2$ exist nahi karte. Yeh step kyun? Dono active gradients vertical $(0,\pm 1)$ hain; woh linearly dependent hain aur koi horizontal direction span nahi karte, isliye woh kabhi $\nabla f$ ke horizontal $1$ ko cancel nahi kar sakte.
4. Diagnosis. LICQ fails: $\nabla g_1=-\nabla g_2$ linearly independent nahi hain (ek doosre ka scalar multiple hai). Isliye KKT yahan necessary nahi hain even though $(0,0)$ true optimum hai.

---

Example G — limiting behaviour: budget shift karna

1. General solve (active). Example B ki tarah: $x=y=c/2$, $\lambda =c$. Yeh step kyun? Geometry identical hai; sirf boundary line move hui hai.
2. Multiplier ka matlab. $\lambda =\frac{d{f}^{\ast }}{dc}$: yahan $f^{\ast }=2(c/2{)}^2=c^2/2$, isliye $\frac{d{f}^{\ast }}{dc}=c=\lambda$. Yeh step kyun? Multiplier sensitivity hai — ek unit se budget tight karne ki marginal cost (Duality and the Dual Problem ka bridge).
3. Limit $c\to 0^{+}$. $x=y\to 0$, $\lambda \to 0$: fence free minimum ke tangent ho jaati hai aur uska push smoothly vanish ho jaata hai — active se inactive ka ek graceful hand-off. Yeh step kyun? Yeh exactly limit mein complementary slackness hai: $\lambda g\to 0$ dono factors shrink hone se.
4. Case $c<0$. Ab origin already $x+y\ge c$ satisfy karta hai; constraint inactive hai, $\lambda =0$, answer $(0,0)$, $f=0$. Yeh step kyun? Negative budget ball ke peeche ki fence hai — irrelevant.

---

Example H — word problem (real units)

1. Model. Minimize karo $f=x^2+2y^2$ s.t. $g:6-x-y\le 0$. ($x,y\ge 0$ abhi ignore karo; baad mein check karenge.) Yeh step kyun? "Kam se kam 6 tonnes" ko $\le 0$ form mein translate karo.
2. Lagrangian & stationarity. $\mathcal{L}=x^2+2y^2+\lambda (6-x-y)$. ${\partial }_x:2x-\lambda =0$, ${\partial }_y:4y-\lambda =0$. Yeh step kyun? Har product ki marginal cost ko same contract push $\lambda$ ke against balance karo.
3. Guess active ($6-x-y=0$). $2x=\lambda =4y$ se $\Rightarrow x=2y$. Phir $2y+y=6\Rightarrow y=2,x=4$. Yeh step kyun? Contract demanding hai; sabse sasta feasible plan boundary par baithta hai.
4. Multiplier & checks. $\lambda =2x=8\ge 0$ ✓. $x=4\ge 0,y=2\ge 0$ ✓. Slackness ✓. Yeh step kyun? Poora "active" guess tabhi tikta hai jab multiplier non-negative ho aur produce ki gayi amounts physically valid hon (no negative tonnage); hum solved values back plug karte hain feasibility, dual feasibility, aur slackness confirm karne ke liye plan par trust karne se pehle.

---

Example I — exam twist: non-convex, KKT ek maximum pakad leta hai

1. Interior stationary point. $\mathcal{L}=-x^2+{\lambda }_1(x-1)+{\lambda }_2(-x-1)$. Dono inactive guess karo (${\lambda }_1={\lambda }_2=0$): $f^{\prime }(x)=-2x=0\Rightarrow x=0$. Feasibility $-1\le 0\le 1$ ✓, slackness ✓ — isliye $x=0$ chaar saare KKT conditions pass karta hai. Yeh step kyun? Yeh dikhane ke liye ki KKT ek aise point par hold kar sakta hai jo minimum nahi hai.
2. $x=0$ identify karo. $f(0)=0$, lekin nearby $f(\pm 0.1)=-0.01<0$: isliye $x=0$ $f$ ka ek local maximum hai, phir bhi KKT pass kiya. Yeh step kyun? Kyunki problem non-convex hai, KKT sirf necessary hain, sufficient nahi — woh min aur max mein fark nahi bata sakte (parent-note ki galti concrete ho gayi).
3. Boundary case $x=1$ (fence $g_1$ active). $g_1=0\Rightarrow x=1$, ${\lambda }_2=0$ set karo. Stationarity $-2x+{\lambda }_1-{\lambda }_2=0\Rightarrow -2(1)+{\lambda }_1=0\Rightarrow {\lambda }_1=2\ge 0$ ✓. Slackness ${\lambda }_1{g}_1=0$ ✓ (kyunki $g_1=0$). Yeh step kyun? Right-hand corner ko apne active-set ke taur par test karo; KKT point count hone ke liye dual feasibility satisfy karni chahiye.
4. Boundary case $x=-1$ (fence $g_2$ active). $g_2=0\Rightarrow x=-1$, ${\lambda }_1=0$ set karo. Stationarity $-2(-1)+0-{\lambda }_2=0\Rightarrow 2-{\lambda }_2=0\Rightarrow {\lambda }_2=2\ge 0$ ✓. Slackness ✓. Yeh step kyun? Symmetry se left corner mirror case hai; confirm karo ki woh bhi valid KKT point hai.
5. Values compare karke decide karo. KKT-satisfying points hain $x\in \{-1,0,1\}$ with $f=\{-1,0,-1\}$. Sabse chota chunno: $x=\pm 1$, $f=-1$. Yeh step kyun? Jab KKT sufficient nahi hote, woh sirf candidates list karte hain — tumhe har KKT point par $f$ evaluate karni hai aur true minimum dhundhne ke liye sabse chota chunna hai.

---

Wrap-up

Recall Humne kaun se cells cover kiye?

A interior-inactive · B one-active ($\lambda >0$) · C equality with $\mu <0$ · D wrong-guess flag · E two-active corner · F LICQ failure · G limiting budget · H word problem · I non-convex catches a max. Activity ka har combination, dono signs, degeneracy, ek limit, real units, aur convex-vs-non-convex distinction.

Recall Multiplier "sensitivity" idea aage kahan le jaata hai?

$\lambda =d{f}^{\ast }/dc$ Duality and the Dual Problem ka seed hai aur yahi wajah hai ki Support Vector Machines apne support vectors active KKT constraints se read karte hain. Optimization method: Gradient Descent and Projected Gradient.

Back to the parent topic.