4.10.19 · D1KKT conditions for constrained optimization
Tum ek landscape ka sabse nichla point dhundna chahte ho, lekin tum ek fenced yard ke andar band ho. KKT conditions exactly woh rulebook hai jo batata hai "ball ruk gayi hai" — downhill pull ya toh flat ground se cancel ho rahi hai, ya woh fences rok rahi hain jine tum lean kar rahe ho. Neeche sab kuch woh vocabulary hai jo tumhe chahiye taaki woh sentence poora samajh aaye.
Yeh page har woh symbol build karta hai jo the parent KKT note mein use hote hain, bilkul zero se. Isko upar se neeche padho: har item sirf unhi cheezon ka use karta hai jo usse pehle aaye hain.
Definition Standing assumption: sab kuch smooth hai (C 1 f g i h j continuously differentiable (C 1 Kyun matter karta hai: poori KKT story arrows ∇ f ∇ g i ∇ h j exist karte hain jab functions differentiable hon. Ek sharp kink par koi ek well-defined slope nahi hoti, toh koi gradient nahi — aur neeche ke arguments collapse ho jaate. Isko apne dimag mein rakho: no smoothness, no gradients, no KKT.
Definition Objective functionf f cost . Hum likhte hain f ( x ) x
Ek landscape ki imagine karo. Horizontal floor woh jagah hai jahan tumhara input rehta hai; har jagah ke upar ki height f
Worked example Figure s01 padhnaBlue rings contours hain — har ring un sabhi points ko jodti hai jo equal cost par hain, jaise hiking map par height lines hoti hain. Paas-paas rings = steep; door-door rings = gentle. Center mein yellow dot valley floor hai, sabse kam cost ka ek point. Jab tum rings ke paas se bahar jaate ho, f
Yeh topic kyun chahiye isse: poora game hai "sabse nichla reachable height dhundo." Cost function ke bina kuch bhi minimize karne ko nahi hai.
x ∗ x ∗ x winning input ke liye — woh point jahan f x ∗ = arg min f argument (input) jo minimum achieve karta hai." Dhyan raho: min f cost hai (ek number, valley floor ki height); x ∗ location hai jo use achieve karta hai (floor par coordinates). Figure s01 mein yellow dot ki height min f position x ∗ x ∗
x ∈ R n x point hai — n R R n n ∈
n = 1 x n = 2 x = ( x , y ) n = 3
Yeh topic kyun chahiye isse: ball is space mein kahin bhi ho sakti hai. Constraints us part ko carve out kar denge jahan woh allowed hai, aur winner x ∗
min x ∈ R n f ( x ) R n x min , f ( x ) min x kya hum choose karne ke liye free hain .
Ab hum yard ka kuch hissa forbid karte hain.
Definition Inequality constraintg i ( x ) ≤ 0 g i g i ( x ) ≤ 0 fence se bordered hai: woh curve jahan g i ( x ) = 0
Definition Equality constrainth j ( x ) = 0 h j ( x ) = 0 wire jis par tum slide karte ho, use chhod nahi sakte.
i j i = 1 … m m j = 1 … p p g 3
Worked example Figure s02 padhnaRed line ek fence ki border hai, jahan g = 0 g ≤ 0 x + y ≥ 1 Yellow line ek wire hai, jahan h = 0 Green dot yellow wire par aur pink allowed band ke andar baithta hai, toh woh dono ek saath satisfy karta hai: yahi "feasible" dikhta hai. Sign story notice karo: fence border par g = 0 g < 0 g > 0
Definition Feasible pointEk point feasible hai agar woh har fence aur har wire ek saath maanta ho. Feasible = "yahan khana legally allowed hai." Optimum x ∗
≤ 0 g ( x ) ≥ 0 − g ( x ) ≤ 0 x + y ≥ 1 1 − x − y ≤ 0
≤ ≥ Kyun sahi lagta hai: dono bas yard carve karte hain.
Fix: multiplier ka sign (§6) ≤ 0 convert karo , phir KKT apply karo, nahi toh har sign flip ho jaayega.
Yeh KKT ka star hai, toh hum ise carefully build karte hain. (Upar wala C 1 ∇ f
Intuition Yahan naya tool kyun chahiye"Minimum" ka matlab hai "kisi bhi chhoti step se f kaun si direction f , aur kitni. Woh direction exactly wahi hai jo gradient measure karta hai — koi doosra single tool "kaun si taraf downhill hai aur kitna steep?" ka jawab nahi deta.
Definition Partial derivative∂ x k ∂ f k x k f ∂ d f
∇ f ( x ) ∇ f ( x ) = ( ∂ x 1 ∂ f , ∂ x 2 ∂ f , … , ∂ x n ∂ f ) . ∇ f steepest increase ki direction mein point karta hai; uski length batati hai kitna steep hai.
Worked example Figure s03 padhnaSame blue contour rings jaise pehle. White dot par green arrow ∇ f up . Red arrow − ∇ f down , woh direction jis taraf ek released ball roll karna chahegi. Do cheezein notice karo: (1) dono arrows us contour ring ke perpendicular hain jis par woh start hote hain — uphill hamesha height lines ke "seedha paar" hota hai; (2) figure s01 ke valley floor par gradient phir bhi exist karta hai — woh bas zero vector hai ∇ f = 0
∇ f uphill point karta hai → toh − ∇ f downhill point karta hai (steepest descent — woh direction jis taraf rolling ball jaana chahti hai, aur Gradient Descent and Projected Gradient ka engine).Jahan ground flat hai, har partial zero hai, toh gradient zero vector hai ∇ f = 0
∇ g i bahar point karta hai (bade g i g i > 0
Yeh topic kyun chahiye isse: KKT completely arrows ke baare mein ek statement hai — − ∇ f
a ⋅ b a = ( a 1 , … , a n ) b = ( b 1 , … , b n ) dot product ek single number hai, matching coordinates multiply karke add karne se banta hai:
a ⋅ b = ∑ k = 1 n a k b k = a 1 b 1 + a 2 b 2 + ⋯ + a n b n . ∑ k = 1 n k = 1 , 2 , … , n positive hota hai agar arrows roughly direction mein agree karein, negative agar oppose karein, aur zero agar right angle par milein.
Definition Perpendicular ⟂Do arrows perpendicular (⟂) hain exactly jab unka dot product 0 a ⋅ b = 0 ( 1 , 0 ) ⋅ ( 0 , 1 ) = 1 ⋅ 0 + 0 ⋅ 1 = 0
Intuition "Wire ke along flat hone" ka matlab perpendicular kyun haiWire h = 0 tangent hain. Agar ∇ f f ∇ f perpendicular hona chahiye — yaani wire ke apne gradient ∇ h Lagrange Multipliers ka seed hai.
Isse pehle ki hum baat karein ki kaun se fence-arrows matter karte hain, hume pata hona chahiye ki ek point par tum actually kaun si fences ko touch kar rahe ho.
Definition Active vs inactive fencePoint x ∗
g i ( x ∗ ) < 0 inactive (tum woh fence touch nahi kar rahe — locally koi role nahi).g i ( x ∗ ) = 0 active (iske upar lean kar rahe — push back kar sakta hai).
Sirf active fences push kar sakti hain, toh sirf unke gradients ∇ g i
Definition Linear combinationArrows v 1 , … , v k linear combination koi bhi sum c 1 v 1 + c 2 v 2 + … c i
Definition Cone (of active constraint gradients)Sirf active fences ke gradients ∇ g i non-negative weights (c i ≥ 0 cone kehte hain. Active fence-normal arrows fanning out ki imagine karo; cone woh sab kuch hai jo tum positive amounts se add karke bana sakte ho.
Worked example Figure s04 padhnaDo red arrows outward gradients ∇ g 1 ∇ g 2 active fences ke jo tum optimum x ∗ Yellow wedge unka cone hai: har woh arrow jo tum c 1 ∇ g 1 + c 2 ∇ g 2 c 1 , c 2 ≥ 0 Green arrow − ∇ f andar land karta hai — yahi ball ke trapped hone ki picture hai: ek hi downhill direction hai jo "fences ke andar" ka positive mix hai, jise fences forbid karti hain.
Intuition Geometric soul, vocabulary ke saath restatedKKT optimum x ∗ − ∇ f cone ke andar baith jaata hai (wahi cone jo abhi upar defined hua, figure s04 mein draw hai). Har woh escape direction jo f
Non-negative weights kyun? Ek fence sirf push kar sakti hai, kabhi pull nahi. Push = uske outward arrow ka ≥ 0 λ i ≥ 0
Definition Lagrange multipliersμ j λ i
μ j h j dono taraf push kar sakti hai (tum wire ke dono sides se dhakele ja sakte ho), toh μ j sign mein free hai — positive, negative, ya zero.λ i g i ek taraf push karti hai (outward), toh λ i ≥ 0 active fences push karti hain, toh inactive fence ka λ i = 0
Common mistake "Saare multipliers≥ 0 Kyun sahi lagta hai: tumne λ i ≥ 0 Fix: sirf fence multipliers λ i Wire multipliers μ j
Definition Complementary slacknessλ i g i ( x ∗ ) = 0 i λ i i g i ( x ∗ ) g i ( x ∗ ) signed constraint value hai, distance nahi: g i = 0 g i < 0 ek fence tabhi push karti hai jab tumhara slack khatam ho jaaye (tum ise touch kar rahe ho). Ya toh g i = 0 λ i = 0
g i ( x ∗ ) < 0 Kyun sahi lagta hai: zyada negative lagta hai "deeper in."
Fix: g i constraint function hai, ruler nahi. Uski numeric value is par depend karti hai ki tumne constraint kaise likhi (ise 2 se scale karo aur har value double ho jaati hai). KKT sirf sign / whether it is zero se matlab rakhta hai, koi true geometric distance nahi.
Definition The LagrangianL ( x , λ , μ ) = f ( x ) + ∑ i λ i g i ( x ) + ∑ j μ j h j ( x ) . f plus har constraint ke liye ek penalty term , uske multiplier se weighted. ∑ i i
Intuition Bundle kyun karein?Is tarah package ho jaane ke baad, KKT ki messy "stationarity" condition ek clean line mein collapse ho jaati hai: ∇ x L = 0 x Duality and the Dual Problem ko power deta hai.
Definition Convex function / setEk function convex hai agar uska graph ek bowl hai — uske kisi bhi do points ke beech ki seedhi line graph ke neeche kabhi nahi jaati. Ek set convex hai agar uske kisi bhi do points ke beech ka seedha segment andar rahe. Dekho Convex Optimization .
Intuition Convexity kyun matter karti haiBowl ke liye exactly ek valley hai aur koi false bottoms nahi. Toh ek convex problem ke liye, KKT sirf ek candidate suggest nahi karta — woh global minimum guarantee karta hai. Non-convex landscapes mein kai dips hote hain, toh KKT maxima aur saddles bhi flag kar sakta hai.
Definition Constraint qualification — fine print jo KKT ko valid banata haiKKT sirf tabhi optimum x ∗ constraint qualification (constraints par ek regularity condition) satisfy ho. Do standard ones:
LICQ (Linear Independence Constraint Qualification): x ∗ active fences aur saare wires ke gradients linearly independent hain — unme se koi bhi baaki ke linear combination nahi hai. Imagine karo active arrows genuinely alag directions mein point kar rahe hain, ek doosre ke upar stacked nahi ya kisi lower dimension mein squashed nahi.Slater's condition (convex problems ke liye): kam se kam ek strictly feasible point exist karta hai — ek aisa point jahan har inequality slack ho (g i ( x ) < 0
Intuition Qualification ki zaroorat kyun haiAgar active fence-gradients degenerate hain — jaise do fences ek sharp cusp mein milti hain toh unke arrows line up ho jaate hain — toh multipliers λ i exist karna fail kar sakte hain even though x ∗ Constraint Qualifications (LICQ, Slater) .
Yeh foundations directly flagship application Support Vector Machines mein combine hoti hain, jahan upar ke har symbol dobara aata hai.
gradient nabla f uphill arrow
optimal point x star arg min
constraints g fences and h wires
perpendicular and dot product
linear combination and cone
multipliers lambda and mu
convexity and constraint qualification
Cover the right side and recite before moving to the main note.
f , g i , h j Continuously differentiable (C 1 ∇ f , ∇ g i , ∇ h j
x ∈ R n Ek point = n
x ∗ min f x ∗ = arg min f location hai (input); min f cost hai (woh number/height jo woh achieve karta hai).
f ( x ) Point x
"x + y ≥ 1 1 − x − y ≤ 0 ≤ 0
Gradient ∇ f − ∇ f ∇ f uphill point karta hai; − ∇ f downhill point karta hai.
Valley floor par, kya gradient vanish hota hai ya exist karna band ho jaata hai? Woh phir bhi exist karta hai — woh zero vector hai ∇ f = 0
Dot product formula aur perpendicular test likho. a ⋅ b = ∑ k a k b k a ⋅ b = 0
x ∗ Active: g i ( x ∗ ) = 0 g i ( x ∗ ) < 0
Gradients ka cone kya hai, aur non-negative weights kyun? Active fence-arrows ke saare sums ≥ 0
Kaun se multipliers ≥ 0 Fence (inequality) multipliers λ i ≥ 0 μ j
Kya g i ( x ∗ ) < 0 Nahi — yeh ek signed constraint value hai (slack); KKT sirf uske sign / whether it's zero se matlab rakhta hai.
Complementary slackness ko words mein bolo. Ek fence tabhi push karti hai jab uska slack khatam ho jaaye: λ i g i = 0
Convexity golden property kyun hai? Ek valley, no false bottoms → KKT global minimum ke liye sufficient ban jaate hain.
Ek constraint qualification bolo. LICQ — x ∗
Agar constraint qualification fail ho toh kya toot jaata hai? Multipliers exist hi nahi kar sakte even at a true optimum, toh KKT applicable nahi ho sakta.
