KKT conditions for constrained optimization: Visual walkthrough

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

Shuru karne se pehle, teen seedhi-saadhi promises un symbols ke baare mein jo hum use karenge:

Jo prerequisites hum use karenge: Lagrange Multipliers (sirf equality waala ancestor), aur baad mein Convex Optimization aur Constraint Qualifications (LICQ, Slater).

Step 1 — Gradient kya hota hai, aur "downhill" ka matlab kya hai

KYA. Cost landscape $f (x, y)$ par kisi point par khade ho. Gradient $\nabla f$ woh single arrow hai jo point karta hai jahan ground sabse steep chadhai hai. Use palat do aur milta hai $- \nabla f$ : wo direction jis mein paani bahega — wo direction jo $f$ ko sabse zyada kam karta hai.

YEH tool kyun, koi aur kyun nahi? Hum pooch sakte the "kya is direction mein jaane se cost kam hogi?" hazaar directions ke liye. Yeh bahut mushkil hai. Gradient ek saath sab ka jawab deta hai. Pehle, seedhe words mein: ek direction $d$ bas ek chhota sa arrow hai jo bolta hai "kaun si side step karna hai" — jaise, "ek metre east aur aadha metre north." Us arrow ke saath ek tiny step lo aur cost (roughly) itni badlegi: $dot product \nabla f \cdot d = lengths ∣\nabla f ∣ ∣ d ∣ θ = angle between uphill arrow and step cos θ,$ ek single dot product jo dono arrows aur unke beech ke angle ka cosine multiply karta hai. Agar woh number negative hai (tum uphill arrow ke against zyada gaye us ke saath kam), tum downhill gaye. Toh gradient optimization ka compass hai; hum iske liye pahunchte hain kyunki yeh "kaun si taraf neeche hai" ko ek arrow mein compress kar deta hai.

PICTURE. Neeche nili curves level sets hain — barabar height ke rings, jaise ek contour map. Pale-yellow arrow $\nabla f$ hai (uphill, hamesha rings ke ⟂). Pink arrow $- \nabla f$ hai (downhill), wo direction jis mein ball roll karta hai jab kuch rokta nahi.

Figure — KKT conditions for constrained optimization

Step 2 — Free minimum: ball wahan rukta hai jahan ground flat ho

KYA. Koi fence nahi hone par, ball kahan aaram karta hai? Bilkul wahan jahan downhill kisi bhi jagah point nahi karta — jahan ground flat hai.

KYU. Agar $- \nabla f$ koi bhi nonzero arrow hota, ball use follow kar ke aur neeche ja sakta tha. Toh aaram ke liye us arrow ka gayab hona zaroori hai. Flatness hi condition $\nabla f = 0$ hai.

PICTURE. Bowl ke bottom par rings ek point mein simat jaati hain aur gradient arrow ki length zero ho jaati hai — ball ko push karne ke liye kuch nahi bachta.

Step 3 — Ek wire (equality): ball sirf us par slide kar sakta hai

KYA. Ab ball ko ek wire $h (x) = 0$ par force karo — ek curve jis par use rehna hi padega. Woh wire ke saath slide kar sakta hai lekin use chod nahi sakta.

KYUN gradient ko line up karna padta hai. $- \nabla f$ ko do parts mein tod do: woh part jo wire ke saath hai aur woh part jo wire ke across hai. Agar koi bhi downhill push wire ke saath chalta hai, ball us taraf slide karta hai aur $f$ kam karta hai — abhi araam nahi kar raha. Toh araam par, along-wire push zero hai. Yeh $\nabla f$ ko purely wire ke across point karne ke liye chhodta hai, yaani wire ke apne normal $\nabla h$ ke parallel. "Parallel" matlab ek dusre ka multiple hai:

$\nabla f (x^{*}) + μ \nabla h (x^{*}) = 0.$

Yeh bilkul ordinary Lagrange Multipliers hai.

PICTURE. Nili rings (cost), peeli curve (wire $h = 0$ ). Resting point par cost-ring wire ke tangent hai — woh kiss karte hain. Wahan, $\nabla f$ (pink) aur $\nabla h$ (yellow-outline) ek hi line par hain, opposite directions mein point karte hain; number $μ$ hai ki ek dusre se kitni baar lamba hai.

Step 4 — Ek fence (inequality): sirf EK taraf forbidden

KYA. Wire ki jagah ek fence $g (x) \leq 0$ lagao. Crucial difference: ek taraf ( $g < 0$ ) khuli zameen hai jisme ball ja sakta hai; doosri taraf ( $g > 0$ ) forbidden hai. Ek fence sirf ek direction se push back karta hai.

KYU yeh sab kuch badal deta hai. Wire ke saath ball curve par trapped hai. Fence ke saath ball ke paas ghoomne ke liye poori region hai. Do bilkul alag resting scenarios saamne aate hain, jinhe hum Steps 5 aur 6 mein alag karte hain.

PICTURE. Pink shaded half forbidden hai ( $g > 0$ ); clear half feasible hai ( $g \leq 0$ ). Fence line $g = 0$ hai. Arrow $\nabla g$ forbidden side mein point karta hai (yahi woh direction hai jahan $g$ badhta hai).

Step 5 — Case A: fence inactive → yeh tha hi nahi jaise

KYA. Maan lo Step 2 ka free minimum already allowed region ke andar baith jaata hai ( $g < 0$ ). Toh fence ne kabhi koi farq nahi pada.

KYU multiplier zero hai. Hum resting condition likhenge $\nabla f + λ \nabla g = 0$ (wire ki tarah, ek multiplier $λ$ ). Lekin yahan ball flat ground par aaram karta hai, toh $\nabla f = 0$ , jo $λ \nabla g = 0$ force karta hai. Kyunki ek real fence par $\nabla g \neq = 0$ hai, hamein $λ = 0$ chahiye. Matlab: chhui nahi gayi fence koi force nahi laati.

PICTURE. Bowl ka asli bottom clear (feasible) territory mein padta hai; fence door, slack hai. Fence ke force arrow ki length zero hai.

Step 6 — Case B: fence active → wall push karti hai, aur sirf EK direction mein

KYA. Ab free minimum forbidden hai, toh ball roll karta hai jab tak woh fence se jam nahi jaata aur $g (x^{*}) = 0$ ke saath wahan ruk jaata hai.

KYU multiplier $\geq 0$ hona chahiye (yahi KKT ka dil hai). Fence ke khilaaf aaram par, $\nabla f$ fence ki push ko balance karta hai: $\nabla f (x^{*}) = - λ \nabla g (x^{*}) .$ Ball ke paas sirf feasible escape directions hain — wo directions jahan $g$ nahi badhta, yaani $\nabla g$ se door point karte hain. Ball ke sach mein stuck rahne ke liye, un escape directions mein se koi bhi downhill nahi ja sakta. Inequality work karne par, downhill arrow $- \nabla f$ fence mein point karna chahiye (same side as $+ \nabla g$ ), jo force karta hai: $λ \geq 0.$ Step 3 ki wire se compare karo, jahan $μ$ free tha: ek fence sirf ek direction block karta hai, toh uske multiplier ka sirf ek sign ho sakta hai. Ek negative $λ$ ka matlab hoga $- \nabla f$ khuli zameen mein point karta hai — lekin tab ball fence se roll off ho sakta tha aur aur neeche ja sakta tha. Toh genuine rest par $λ < 0$ impossible hai.

PICTURE. Ball fence par jam gaya hai. Downhill $- \nabla f$ (pink) forbidden zone mein point karta hai; fence ka inward normal $- \nabla g$ (yellow) use exactly cancel karta hai. Unki lengths $λ > 0$ factor se differ karti hain.

Step 7 — Dono cases ko fuse karna: complementary slackness

KYA. Steps 5 aur 6 do branches hain. KKT inhe ek elegant equation mein bottle karta hai: $λ g (x^{*}) = 0.$

KYU yeh dono capture karta hai. Ek product exactly tab zero hota hai jab ek factor zero ho:

Agar $g < 0$ (inactive), product $λ = 0$ force karta hai — woh Step 5 hai.
Agar $λ > 0$ (real push), product $g = 0$ force karta hai — woh Step 6 hai.

Woh kabhi dono "loose" nahi ho sakte ( $λ > 0$ aur $g < 0$ ) — woh ek wall hogi jo ek ball ko push kar rahi hai jise woh touch nahi kar rahi. Impossible.

PICTURE. Ek do-branch fork: baayi path (inactive, $λ = 0$ ) aur daayein path (active, $g = 0$ ) dono ek single node $λ g = 0$ mein funnel hoti hain.

Step 8 — Kaafi saari fences aur wires stack karna: cone of forces

KYA. Real problems mein kai fences aur kai wires hoti hain. Inhe bundle karne se pehle, seedhe-saadhe words mein bookkeeping fix karte hain taaki koi naya symbol chhupta na rahe:

Fences ko number karo $g_{1}, g_{2}, \dots, g_{m}$ — har inequality ke liye ek $g_{i}$ , apne non-negative multiplier $λ_{i} \geq 0$ ke saath. Chhota subscript $i$ bas ek name-tag hai jo $i = 1, \dots, m$ run karta hai.
Wires ko number karo $h_{1}, h_{2}, \dots, h_{p}$ — har equality ke liye ek $h_{j}$ , apne sign-free multiplier $μ_{j}$ ke saath. Subscript $j$ runs $j = 1, \dots, p$ .

Toh $\sum_{i}$ matlab "har fence par add karo" aur $\sum_{j}$ matlab "har wire par add karo." Yeh haath mein leke hum har push aur pull ko ek bookkeeping object mein bundle karte hain, Lagrangian:

KYU "cone." Har active fence ek push $λ_{i} \nabla g_{i}$ contribute karta hai jisme $λ_{i} \geq 0$ hai — apne normal ke saath ek non-negative amount. Kai arrows ke non-negative amounts add karne se ek wedge-shaped region banta hai jise cone kehte hain. Rule kehta hai: $- \nabla f$ (downhill) us cone ke andar rehna chahiye. Agar woh hai, ball trapped hai — har downhill direction kisi na kisi wall se blocked hai.

PICTURE. Do active fence-normals $\nabla g_{1}, \nabla g_{2}$ (yellow) ek shaded cone open karte hain. Downhill arrow $- \nabla f$ (pink) us mein andar baitha hai — trapped. Yeh woh "geometric soul" hai jo parent note ne mention kiya tha.

Step 9 — "Trapped" kahaan "global best" ke SAME hai? (convex + Slater)

KYA. Ab tak sab kuch local tha — ball ruk gaya, lekin kya yeh kaheen bhi lowest point hai? Ek convex problem ke liye, ek mild regularity condition ke saath, jawab haan hai.

KYU convexity ise seal karta hai. Convex ka matlab landscape ek single smooth bowl hai (koi secondary dips nahi) aur har feasible region ek solid, dent-free blob hai. Aise world mein "yahan koi downhill escape nahi" ek local trick nahi ho sakta — sirf ek basin hai. Do precise statements:

KKT ⟹ global minimum (sufficiency): ek convex problem ke liye ( $f, g_{i}$ convex, $h_{j}$ affine), koi bhi point jo charon KKT conditions satisfy karta hai woh global minimum hai — koi extra assumption nahi chahiye.
Global minimum ⟹ KKT (necessity): optimum par multipliers exist karne ki guarantee ke liye tumhe abhi bhi ek constraint qualification chahiye. Convex-friendly wala hai Slater's condition: koi strictly feasible point exist karta hai (sab $i$ ke liye $g_{i} (x) < 0$ ). Slater strong duality bhi deliver karta hai, inhi $λ$ 's ko dual problem se jodta hai.

Yeh "necessary aur sufficient (Slater ke under)" fact hi woh reason hai ki kyun Support Vector Machines aur dusre Convex Optimization models ek KKT point par trust kar sakte hain, aur kyun Gradient Descent and Projected Gradient jaisi solvers true optimum tak converge karti hain.

PICTURE. Left: ek wiggly non-convex landscape jahan ek KKT point ek shallow false dip mein baitha hai (ek mere saddle/max ko bhi flag karta hai). Right: ek clean convex bowl jahan ek KKT point hi global floor hai.

Ek-picture summary

Upar sab kuch, ek single board par: ball active fences ke khilaaf aaram kar raha hai, downhill pushes ke cone mein trapped hai, inactive fences zero force ke saath lati hain, aur charon KKT stamps label kiye hue hain jahan woh rehte hain.

Recall Poore walkthrough ki Feynman retelling

Ek marble ek uneven floor par neeche roll karta hai sabse low spot ki taraf jo woh reach kar sake, lekin fences hain. Pehle maine seekha ki marble hamesha seedha downhill roll karna chahta hai — woh arrow $- \nabla f$ hai. Khuli zameen par woh sirf wahan rukta hai jahan floor flat ho. Use wire par rakho aur woh tab tak slide karta hai jab tak downhill push wire ke along nahi, sideways-into wire chalti hai. Fences zyada tricky hain: ek fence sirf ek side block karta hai, toh woh sirf push kar sakti hai, kabhi pull nahi — isliye uska number $λ$ negative nahi ja sakta. Agar marble fence se door rukta hai, us fence ne kuch nahi kiya ( $λ = 0$ ); agar woh ek ke khilaaf rukta hai, fence definitely push kar rahi hai ( $g = 0$ ). "Sirf wahan push karo jahan touch karo" ek neat line hai: $λ g = 0$ . Aur bilkul marble ko playground ke andar actually rehna padta hai poore time — woh "primal feasibility" hai. Books rakhne ke liye, hum cost plus sab pushes ko ek function $L$ mein pile karte hain aur uska $x$ -gradient zero set karte hain. Kaafi fences ek corner par milte hue, unki pushes ek wedge mein add ho jaati hain (ek cone), aur marble exactly tab stuck hota hai jab downhill us wedge ke andar point kare — provided koi fence ka koi degenerate, direction-less edge na ho (yahi LICQ forbid karta hai). Finally, agar poora floor ek smooth bowl hai (convex) aur koi strictly-inside point hai (Slater), "yahan stuck" matlab "kahin bhi sabse low." Yahi poori KKT story hai.

Recall

$μ$ negative kyun ho sakta hai par $λ$ nahi? Ek wire ( $h = 0$ ) dono sides forbid karti hai, toh woh kisi bhi taraf kheench sakti hai → $μ$ sign mein free. Ek fence ( $g \leq 0$ ) sirf ek side forbid karta hai, toh woh sirf ek taraf push kar sakta hai → $λ \geq 0$ (yeh "dual feasibility" hai).

Recall

$λ g = 0$ kya forbid karta hai? Combination $λ > 0$ aur $g < 0$ — ek wall jo ek ball ko push kar rahi hai jise woh touch nahi kar rahi. Dono mein se ek hamesha zero hona chahiye.

Recall LICQ kyun insist karta hai ki gradients linearly independent hon?

Kyunki balance argument secretly har $\nabla g_{i} \neq = 0$ chahiye tha aur normals ka ek line par collapse na hona chahiye tha. Linear independence dono guarantee karta hai, toh cone full-dimensional hota hai aur honest multipliers exist karte hain aur unique hote hain.