KKT conditions for constrained optimization — Hinglish notes

4.10.19 · Maths › Advanced Topics (Elite Level)

HUM kaun si problem solve kar rahe hain?

YE form kyun? Koi bhi problem isme convert ho sakti hai: $g (x) \geq 0$ ban jaata hai $- g (x) \leq 0$ ; $f$ ko maximize karna hai toh $- f$ minimize karo. Toh ye akela template saari smooth constrained optimization problems cover karta hai.

KKT kaise derive karte hain — Lagrange se inequalities tak

Step 1: Sirf equality wala Lagrange yaad karo

Sirf $h_{j} (x) = 0$ ke saath, minimum wahan hota hai jahan $f$ ka gradient, constraint gradients ka combination ho: $\nabla f (x^{*}) + \sum_{j} μ_{j} \nabla h_{j} (x^{*}) = 0.$

Kyun? Agar $\nabla f$ ka koi component constraint surface ke saath hota, toh tum us direction mein slide karke $f$ decrease kar sakte the aur feasible bhi rehte. Toh minimum par $\nabla f$ surface ke ⟂ hona chahiye, yaani $\nabla h_{j}$ (normals) ka combination.

Step 2: Ek inequality $g (x) \leq 0$ add karo

Optimum par har inequality ke liye do cases hote hain:

Inactive ( $g_{i} (x^{*}) < 0$ , strictly andar): fence touch nahi hui. Locally aisa lagta hai jaise constraint exist hi nahi karta → uska multiplier $0$ hona chahiye.
Active ( $g_{i} (x^{*}) = 0$ , fence par): ye equality ki tarah behave karta hai, lekin ek sign restriction ke saath.

Sign kyun? Feasible rehne ke liye hum sirf wahan ja sakte hain jahan $g_{i}$ decrease ho ya same rahe ( $g_{i} \leq 0$ ). $x^{*}$ minimum ho, iske liye $f$ kisi bhi feasible direction mein decrease nahi hona chahiye. Fence mein push karte waqt, $- \nabla g_{i}$ feasible interior ki taraf point karta hai; $\nabla f$ ko "bahar" point karna chahiye taaki escape block ho. Isse multiplier $λ_{i} \geq 0$ hone ki majboori aati hai.

Complementary slackness ( $λ_{i} g_{i} = 0$ ) kyun?

Ye Step 2 ka unifying statement hai. Ya toh:

$g_{i} < 0$ (inactive) → $λ_{i} = 0$ force hota hai, ya
$λ_{i} > 0$ (active multiplier) → $g_{i} = 0$ force hota hai.

Dono ek saath "loose" nahi ho sakte. Product ka zero hona encode karta hai — "ek fence tab hi push back karta hai jab tum use touch kar rahe ho."

Ek subtle lekin zaroori ingredient: Constraint Qualification

Kyun zaroori hai? Agar active gradients degenerate hain (jaise do fences ek cusp mein milti hain), toh multipliers exist hi na karein chahe $x^{*}$ optimal ho. LICQ guarantee karta hai ki multipliers exist karte hain aur unique hain.

Worked Examples

Common Mistakes (Steel-manned)

Active Recall

Recall Chaar KKT conditions (cover karke recite karo)

Stationarity $\nabla_{x} L = 0$ · 2. Primal feasibility ( $g \leq 0, h = 0$ ) · 3. Dual feasibility ( $λ \geq 0$ ) · 4. Complementary slackness ( $λ_{i} g_{i} = 0$ ).

Recall

$λ_{i} \geq 0$ kyun hona chahiye? Kyunki ek feasible move $g_{i} \leq 0$ rakhta hai; $x^{*}$ minimum ho iske liye $\nabla f$ ko feasible region mein escape oppose karna chahiye, isse multiplier non-negative hone ki majboori aati hai. Equality multipliers mein aisi koi restriction nahi hai.

Recall KKT global minimum ke liye sufficient kab hote hain?

Jab problem convex ho ( $f$ , $g_{i}$ convex; $h_{j}$ affine).

Recall Feynman: ek 12 saal ke bacche ko samjhao

Tum ek marble ek bowl mein roll karte ho, lekin walls hain. Marble sabse neeche ruk jaati hai jahan tak ja sake. Agar wo kisi wall se door rukti hai, wahan zameen flat hai. Agar wo kisi wall ke saath rukti hai, wall use push kar rahi hai — aur wall tab hi push karti hai jab tum use touch kar rahe ho (yahi "complementary slackness" hai). KKT bas wo rulebook hai jo kehta hai: ruk jaane ki jagah par, downhill pull bilkul flat zameen aur jin walls se tum tike ho unke balance mein hota hai.

Connections

Lagrange Multipliers — sirf equality wala special case ( $λ = 0$ everywhere, sirf $μ$ ).
Convex Optimization — jahan KKT necessary aur sufficient ban jaate hain.
Duality and the Dual Problem — $λ, μ$ dual variables hain; strong duality ↔ KKT.
Support Vector Machines — KKT + slackness support vectors (active constraints) identify karte hain.
Gradient Descent and Projected Gradient — KKT points dhundne ke liye algorithmic cousins.
Constraint Qualifications (LICQ, Slater) — jab multipliers exist karne ki guarantee ho.

Flashcards

KKT ke liye constrained optimization problem ki standard form kya hai?

min f (x)

s.t.

g_{i} (x) \leq 0

aur

h_{j} (x) = 0

Stationarity condition batao.

\nabla f + \sum_{i} λ_{i} \nabla g_{i} + \sum_{j} μ_{j} \nabla h_{j} = 0

, yaani

\nabla_{x} L = 0

Complementary slackness kya hai aur iska kya matlab hai?

λ_{i} g_{i} (x^{*}) = 0

for all

i

; ek inequality multiplier nonzero tab hi hota hai jab wo constraint active ho (

g_{i} = 0

Kaun se KKT multipliers non-negative hone chahiye?

Sirf inequality multipliers

λ_{i} \geq 0

; equality multipliers

μ_{j}

sign mein free hain.

KKT conditions global minimum ke liye sufficient kab hote hain?

Jab problem convex ho:

f

aur

g_{i}

convex,

h_{j}

affine.

Constraint qualification (jaise LICQ) kya hai aur kyun zaroori hai?

Ye ensure karta hai ki multipliers exist karein; LICQ require karta hai ki

x^{*}

par active inequality + equality constraint gradients linearly independent hon.

Tumhare solution mein ek negative

λ

aaya — ye kya batata hai?

Tumhara active-set guess galat hai; wo constraint actually inactive honi chahiye (ya tumhare paas min ki jagah max/saddle hai).

Geometrically, stationarity optimum par kya kehta hai?

- \nabla f

active constraint gradients ke span hone wale cone mein hota hai — har descent direction blocked hai.