KKT conditions for constrained optimization: Question bank

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

Shuru karne se pehle do reminders, taaki neeche har symbol already grounded ho:

Sahi hai ya galat — justify karo

TF1. Agar ek KKT point exist karta hai, to wo global minimum hona chahiye.

False — non-convex problems ke liye KKT sirf necessary hain, isliye ek KKT point maximum, saddle, ya local (global nahi) min ho sakta hai; sirf convexity unhe sufficient banata hai.

TF2. Equality multipliers

μ_{j}

non-negative hone chahiye.

False — sirf inequality multipliers

λ_{i} \geq 0

hote hain; equality multipliers

μ_{j}

sign mein free hote hain, bilkul ordinary Lagrange Multipliers ki tarah.

TF3. Kisi bhi feasible point par, complementary slackness

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

automatically hold karta hai.

False — ye ek condition hai jo KKT optimum par impose karta hai, har feasible point ke baare mein koi fact nahi; ek random feasible point mein

g_{i} < 0

ke saath nonzero

λ_{i}

ho sakta hai aur wo ise violate kar sakta hai.

TF4. Agar

g_{i} (x^{*}) < 0

(baad ko touch nahi kiya), to

λ_{i} = 0

True — slackness

λ_{i} g_{i} = 0

mein

g_{i} \neq = 0

ke saath

λ_{i} = 0

force hota hai; ek untouched baad koi push nahi karta.

TF5. Agar

λ_{i} > 0

, to corresponding constraint active hona chahiye.

True — slackness force karta hai

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

jab bhi

λ_{i} \neq = 0

; ek baad tabhi push back karta hai jab tum usse lean kar rahe ho.

TF6. Ek convex problem ke liye, saari chaar KKT conditions satisfy karna global minimum guarantee karta hai.

True —

f, g_{i}

convex aur

h_{j}

affine ke saath, KKT global min ke liye necessary aur sufficient hain.

TF7. Har wo point jahan

\nabla f (x^{*}) = 0

(

f

ka ek flat spot) ek KKT point hai.

False — ye tabhi KKT hai jab wo feasible bhi ho aur multipliers ko stationarity/slackness satisfy karne ke liye choose kiya ja sake; feasible region ke bahar ek flat spot solution hai hi nahi.

TF8. LICQ is liye zaroori hai ki KKT sufficient ho.

False — LICQ is liye zaroori hai ki KKT ek minimum par necessary ho; sufficiency convexity se aata hai, jo ek alag ingredient hai.

TF9. Agar dono fence

g_{1}, g_{2}

x^{*}

par inactive hain, to problem locally unconstrained jaisi behave karti hai.

True — inactive constraints ke zero multipliers hote hain aur wo stationarity se bahar ho jaate hain, isliye locally tum sirf

f

ke ek flat spot par ho.

TF10. Ek convex problem mein, KKT points unique hote hain.

False — convexity ek global optimum value guarantee karta hai lekin minimizer set poora flat region ho sakta hai (jaise ek segment par constant minimize karna), jisse bahut saare KKT points milte hain.

Error dhundo

SE1. "Maine

\nabla f = λ \nabla g

likha

g \leq 0

ke saath aur

λ < 0

mila, isliye problem ka koi solution nahi hai."

Sign galat hai:

g \leq 0

ke saath correct stationarity hai

\nabla f + λ \nabla g = 0

, yaani

\nabla f = - λ \nabla g

; pehle

\leq 0

form mein convert karne se flipped

λ

theek ho jaata hai.

SE2. "Optimum dhundne ke liye maine har constraint ko active set kiya aur resulting system solve kiya."

Ek truly-inactive constraint ko active force karna

λ < 0

deta hai, jo dual feasibility violate karta hai — wo negative value ek signal hai ki tumhara active-set guess galat hai, answer nahi.

SE3. "Point feasible hai aur

\nabla_{x} L = 0

, isliye wo optimal hai —

λ \geq 0

check karne ki zaroorat nahi."

Stationarity plus feasibility kaafi nahi hai;

λ_{i} \geq 0

check kiye bina tumne maximum dhundha hoga ya ek galat active-set case jo baad ke khilaaf galat taraf lean kar raha hai.

SE4. "Mere paas

g : x \geq 1

hai, isliye maine

\nabla g

λ \geq 0

ke saath seedha outward pointing use kiya."

Tumhe pehle

x \geq 1

1 - x \leq 0

mein rewrite karna hoga;

\leq 0

conversion skip karna silently us sign ko flip kar deta hai jis par

λ \geq 0

rule depend karta hai.

SE5. "Meri problem non-convex hai lekin mujhe ek KKT point mila, isliye maine use global minimum report kiya."

Non-convex problems ke liye KKT sirf necessary hai; tumhe saare KKT candidates (aur possibly boundary/infeasibility cases) compare karne honge kyunki kuch maxima ya saddles hote hain.

SE6. "LICQ mere optimum par fail ho gaya, isliye mera point actually minimum nahi ho sakta."

LICQ fail hone ka matlab sirf ye hai ki KKT multipliers exist nahi kar sakte ya unique nahi ho sakte — point phir bhi ek genuine minimum ho sakta hai; tum bas KKT se ise certify nahi kar sakte.

SE7. "Complementary slackness mujhe

λ_{i} g_{i} = 0

deta hai, isliye main hamesha

λ_{i} = 0

set kar sakta hoon."

Sirf jab

g_{i} < 0

; agar constraint active hai (

g_{i} = 0

) to product kisi bhi

λ_{i} \geq 0

ke liye zero hai, isliye tumhe

λ_{i}

ke liye solve karna hoga, ye assume nahi karna ki wo zero hai.

Kyun questions

WHY1.

λ_{i} \geq 0

kyun hona chahiye lekin

μ_{j}

koi bhi sign ho sakta hai?

Ek fence motion ko sirf ek taraf block karta hai (

g \leq 0

), isliye uska push ek taraf point karna chahiye (non-negative multiplier); ek taar (

h = 0

) dono taraf motion block karta hai, isliye uska multiplier dono direction mein pull kar sakta hai.

WHY2. Complementary slackness ek hi statement kyun hai jo "active vs inactive" ko unify karta hai?

Product

λ_{i} g_{i} = 0

force karta hai ki kam se kam ek factor vanish ho — ya

g_{i} = 0

(active) ya

λ_{i} = 0

(inactive) — dono cases ko ek equation mein capture karta hai.

WHY3. KKT ko constraint qualification ki zaroorat kyun hai?

Iske bina, active constraint gradients degenerate ho sakte hain (jaise fences ek cusp mein milna), aur phir koi multipliers exist nahi karte jo

- \nabla f

ko unke combination ke roop mein express kar sake, chahe true minimum par bhi.

WHY4. Convexity KKT ko necessary se sufficient kyun banata hai?

Ek convex problem mein sahi sign conditions ke saath ek stationary feasible point ke paas kahi bhi (sirf locally nahi) koi feasible descent direction nahi hota, isliye wo global minimum hona chahiye — Convex Optimization dekho.

WHY5. Geometrically,

- \nabla f

active constraint gradients ke cone ke andar kyun hona chahiye?

Agar

- \nabla f

(downhill pull) us cone ke bahar nikla, to koi feasible direction abhi bhi

f

reduce kar sakti; cone ke andar trap hona matlab har escape route ek constraint violate karta hai.

WHY6. Ek inactive constraint stationarity mein kuch contribute kyun nahi karta?

Uska multiplier slackness ke zariye zero force hota hai, isliye uska gradient term

\nabla_{x} L

se drop ho jaata hai — ek fence jo tum touch nahi kar rahe wo koi force nahi lagata.

WHY7. KKT conditions Support Vector Machines ke liye itni important kyun hain?

SVM ek convex program hai, isliye KKT sufficient hain; complementary slackness exactly support vectors (active constraints with

λ_{i} > 0

) ko pick out karta hai jo margin define karte hain.

WHY8. Duality KKT se kyun relate karta hai?

KKT stationarity exactly

\nabla_{x} L = 0

hai, aur

λ_{i} \geq 0

with slackness wo conditions hain jiske under primal aur dual optima coincide karte hain (strong duality).

Edge cases

EC1. Jab koi inequality constraints nahi hain, sirf equalities hain, to KKT conditions kya hain?

Wo ordinary Lagrange Multipliers mein collapse ho jaate hain:

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

feasibility

h_{j} = 0

ke saath, aur kisi bhi multiplier par koi sign restriction nahi.

EC2. Agar bilkul koi constraints nahi hain to KKT ka kya hota hai?

Stationarity reduce ho jaati hai

\nabla f (x^{*}) = 0

— plain unconstrained first-order condition, "flat ground" case.

EC3. Ek constraint active aur uska multiplier exactly zero hai (

g_{i} = 0

λ_{i} = 0

). Kya ye allowed hai?

Haan — ye "degenerate" ya weakly active case slackness satisfy karta hai; fence touch ho rahi hai lekin koi push nahi kar rahi, often ek sign ki optimum ek aisi boundary par baitha hai jo binding nahi hai.

EC4. Feasible region empty hai (constraints contradict karte hain). KKT kya kehta hai?

Kuch nahi — KKT ek feasible optimum presuppose karta hai; koi feasible point nahi hone se koi

x^{*}

test karne ke liye nahi hai, isliye poora framework apply nahi hota.

EC5. Objective feasible set par unbounded below hai. Kya phir bhi ek KKT point exist kar sakta hai?

Koi finite minimizer exist nahi karta, isliye koi KKT point nahi; stationarity ko ek balance chahiye hoga jo

f \to - \infty

hone par kabhi nahi hota.

EC6. Do fences

g_{1}, g_{2}

x^{*}

par identical gradients hain (linearly dependent). Kya toot jaata hai?

LICQ fail ho jaata hai, isliye multipliers

λ_{1}, λ_{2}

non-unique ya non-existent ho sakte hain — tum forces ko cleanly read off nahi kar sakte chahe point optimal bhi ho.

EC7. Kya ek KKT point

f

ka local maximum ho sakta hai?

Haan, non-convex problems ke liye — stationarity

\nabla_{x} L = 0

min/max ke liye symmetric hai, isliye KKT maxima aur saddles bhi pakadta hai jab tak convexity unhe rule out na kare.

EC8. Iska kya matlab hai agar projected gradient descent ek aise point par ruk jaata hai jahan projected gradient zero hai?

Usne constrained problem ka ek KKT point reach kar liya hai — descent direction poori tarah constraint projection se cancel ho gayi hai, stationarity plus slackness ko mirror karta hai.

Recall Sabse gehre trap ka ek-line summary

Do conditions jinhe log confuse karte hain: $λ_{i} \geq 0$ sign ke baare mein hai (fences ek taraf push karte hain), slackness $λ_{i} g_{i} = 0$ activity ke baare mein hai (fences sirf tab push karte hain jab touch ho) — ye alag rules hain, dono required hain.