KKT conditions for constrained optimization: Exercises

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

Shuru karne se pehle, ek shared vocabulary reminder taaki koi symbol achanak na aaye. Do symbols mein index letters hain: is poore page mein == $i$ inequality constraints par run karta hai== ( $i = 1 \dots m$ , the fences) aur == $j$ equality constraints par run karta hai== ( $j = 1 \dots p$ , the wires).

Baar baar use hone wali recipe, jise tum baar baar apply karoge:

Level 1 — Recognition

Exercise 1.1

Problem $min f (x)$ s.t. $g_{i} (x) \leq 0$ , $h_{j} (x) = 0$ ke liye chaar KKT conditions state karo. Har ek ka naam bolo.

Recall Solution 1.1

Stationarity: $\nabla f (x^{*}) + \sum_{i} λ_{i} \nabla g_{i} (x^{*}) + \sum_{j} μ_{j} \nabla h_{j} (x^{*}) = 0$ .
Primal feasibility: $g_{i} (x^{*}) \leq 0$ aur $h_{j} (x^{*}) = 0$ .
Dual feasibility: $λ_{i} \geq 0$ .
Complementary slackness: har $i$ ke liye $λ_{i} g_{i} (x^{*}) = 0$ .

Exercise 1.2

Har statement ke liye true ya false bolo aur ek-line ka reason do. (a) Equality multipliers $μ_{j}$ necessarily $\geq 0$ hone chahiye. (b) Agar optimum par ek constraint inactive hai, toh uska multiplier $0$ hota hai. (c) Ek convex problem ke liye, KKT sirf necessary hain, sufficient kabhi nahi.

Recall Solution 1.2

(a) False. Sirf inequality multipliers $λ_{i} \geq 0$ hote hain; equality $μ_{j}$ sign mein free hain (ek wire dono taraf push kar sakti hai). (b) True. Inactive ka matlab $g_{i} (x^{*}) < 0$ hai; complementary slackness $λ_{i} g_{i} = 0$ phir $λ_{i} = 0$ force karta hai. (c) False. Ek convex problem ke liye KKT necessary AND sufficient hain global minimum ke liye.

Exercise 1.3

Standard $g (x) \leq 0$ form mein convert karo aur constraint ke liye stationarity term likho: $x_{1} + 2 x_{2} \geq 4$ .

Recall Solution 1.3

Sab kuch ek side move karo taaki constraint "something $\leq 0$ " padhe: $x_{1} + 2 x_{2} \geq 4 ⟺ 4 - x_{1} - 2 x_{2} \leq 0 ⟹ g (x) = 4 - x_{1} - 2 x_{2} .$ Iska gradient $\nabla g = (- 1, - 2)$ hai, isliye stationarity contribution $λ (- 1, - 2)$ hai jahan $λ \geq 0$ . Agar tum flip karna bhool jaate, toh tumhara $λ$ galat sign ke saath aata.

Level 2 — Application

Exercise 2.1

$f (x) = (x - 1)^{2}$ ko minimize karo subject to $x \geq 3$ . $x^{*}$ , $λ$ , aur $f (x^{*})$ find karo.

Recall Solution 2.1

Standard form: $g = 3 - x \leq 0$ , isliye $\nabla g = - 1$ . $L = (x - 1)^{2} + λ (3 - x)$ . Stationarity: $2 (x - 1) - λ = 0$ . Unconstrained min $x = 1$ hai, jo $x \geq 3$ violate karta hai — isliye fence active honi chahiye: $g = 0 \Rightarrow x = 3$ . Phir $λ = 2 (x - 1) = 2 (3 - 1) = 4 \geq 0$ ✓. Slackness ✓ ( $g = 0$ ). Answer: $x^{*} = 3$ , $λ = 4$ , $f = (3 - 1)^{2} = 4$ .

Exercise 2.2

$f (x, y) = x^{2} + y^{2}$ ko minimize karo subject to $x + 2 y \geq 5$ . Point aur $λ$ find karo.

Recall Solution 2.2

Standard form: $g = 5 - x - 2 y \leq 0$ , $\nabla g = (- 1, - 2)$ . $L = x^{2} + y^{2} + λ (5 - x - 2 y)$ . Stationarity: $2 x - λ = 0$ , $2 y - 2 λ = 0 \Rightarrow x = λ /2, y = λ$ . Origin infeasible hai, isliye active try karo: $x + 2 y = 5 \Rightarrow λ /2 + 2 λ = 5 \Rightarrow \frac{5 λ}{2} = 5 \Rightarrow λ = 2$ . Phir $x = 1, y = 2$ . Check $λ = 2 \geq 0$ ✓, slackness ✓. Answer: $(1, 2)$ , $λ = 2$ , $f = 1 + 4 = 5$ .

Neeche wali figure padhna. Violet line fence $x + 2 y = 5$ hai; uske upar shaded band feasible region hai ( $x + 2 y \geq 5$ ). Magenta arcs $f = x^{2} + y^{2}$ ke level circles hain (equal cost ke points, origin se baahir badhte hue). Magenta mein optimum $(1, 2)$ woh jagah hai jahan sabse chhota aisa circle pehli baar feasible band ko touch karta hai — line ka origin ke sabse kareeb wala point. Orange arrow $- \nabla f$ hai (downhill pull), aur notice karo ki woh fence ke normal ke bilkul saath point karta hai: yahi stationarity visually dikhti hai — pull exactly fence ke push se cancel ho jaata hai.

Figure — KKT conditions for constrained optimization

Exercise 2.3

$f (x) = x^{2}$ ko minimize karo subject to $- 2 \leq x \leq 2$ (yaani $g_{1} = x - 2 \leq 0$ , $g_{2} = - x - 2 \leq 0$ ).

Recall Solution 2.3

$L = x^{2} + λ_{1} (x - 2) + λ_{2} (- x - 2)$ . Stationarity: $2 x + λ_{1} - λ_{2} = 0$ . Dono inactive try karo ( $λ_{1} = λ_{2} = 0$ ): $2 x = 0 \Rightarrow x = 0$ . Check $- 2 \leq 0 \leq 2$ ✓, slackness ✓. Answer: $x^{*} = 0$ , dono $λ = 0$ , $f = 0$ . Marble neeche baith jaata hai, kisi wall ko touch nahi karta.

Level 3 — Analysis

Exercise 3.1

$f = x^{2} + y^{2}$ ko minimize karo subject to $h : x + y = 2$ aur $g : y \geq x$ (yaani $x - y \leq 0$ ). $(x, y)$ , $μ$ , $λ$ find karo.

Recall Solution 3.1

$g = x - y \leq 0$ , $\nabla g = (1, - 1)$ ; $\nabla h = (1, 1)$ . $L = x^{2} + y^{2} + μ (x + y - 2) + λ (x - y)$ . Stationarity: $2 x + μ + λ = 0$ , $2 y + μ - λ = 0$ . $g$ inactive try karo ( $λ = 0$ ): $2 x + μ = 0$ , $2 y + μ = 0 \Rightarrow x = y$ . $x + y = 2$ ke saath $\Rightarrow x = y = 1$ . Check $g = x - y = 0 \leq 0$ ✓ (actually exactly fence par hai, phir bhi feasible), slackness ✓ ( $λ = 0$ ). $μ$ solve karo: $2 (1) + μ = 0 \Rightarrow μ = - 2$ . Answer: $(1, 1)$ , $μ = - 2$ , $λ = 0$ . Note karo $μ < 0$ bilkul legal hai — equality multipliers par koi sign restriction nahi hoti.

Exercise 3.2

Consider karo $min f = x$ subject to $g_{1} = x^{2} \leq 0$ . Sirf ek feasible point hai $x = 0$ . Dikhao ki LICQ yahan fail ho jaata hai, aur discuss karo ki KKT certify ho sakta hai ya nahi.

Recall Solution 3.2

Feasibility: $x^{2} \leq 0$ force karta hai $x = 0$ (ek single point). $x^{*} = 0$ par constraint active hai ( $g_{1} = 0$ ). LICQ check: active gradient hai $\nabla g_{1} = 2 x = 0$ at $x^{*} = 0$ . Zero vector wale set mein linearly dependent hote hain, isliye LICQ fail ho jaata hai. Stationarity attempt: $\nabla f + λ \nabla g_{1} = 1 + λ \cdot 0 = 1 \neq = 0$ kisi bhi $λ$ ke liye. Isliye koi multiplier stationarity hold nahi kar sakta, chahe $x = 0$ woh (sirf, hence optimal) feasible point hi kyun na ho. Yahi situation hai jiske baare mein parent note warn karta hai: constraint qualification ke bina, KKT optimum par hold nahi karna padta. Answer: LICQ fail; KKT stationarity yahan unsatisfiable hai; multiplier exist nahi karta.

Exercise 3.3

$f = x^{2} + y^{2}$ ko minimize karo subject to $g = (x - 2)^{2} + y^{2} - 1 \leq 0$ (radius $1$ wala disk centred at $(2, 0)$ ). Geometry se optimum find karo, phir KKT se verify karo.

Recall Solution 3.3

Geometry: hum disk ka woh point chahte hain jo origin ke sabse kareeb ho. Disk ka origin $(0, 0)$ ke kareeb wala point, origin se centre $(2, 0)$ tak ki line par hai, distance (centre distance) $-$ (radius) $= 2 - 1 = 1$ par. Isliye $x^{*} = (1, 0)$ . KKT check: $\nabla f = (2 x, 2 y)$ , $\nabla g = (2 (x - 2), 2 y)$ . Active try karo: $g = 0$ . Stationarity: $2 x + λ \cdot 2 (x - 2) = 0$ aur $2 y + λ \cdot 2 y = 0$ . Doosri equation: $2 y (1 + λ) = 0$ . Kyunki $λ \geq 0$ , $1 + λ > 0$ , isliye $y = 0$ . $y = 0$ ke saath, active: $(x - 2)^{2} = 1 \Rightarrow x = 1$ ya $x = 3$ . Pehli equation: $2 x + 2 λ (x - 2) = 0$ .

$x = 1$ : $2 + 2 λ (- 1) = 0 \Rightarrow λ = 1 \geq 0$ ✓ → valid KKT point, $f = 1$ .
$x = 3$ : $6 + 2 λ (1) = 0 \Rightarrow λ = - 3 < 0$ ✗ dual feasibility fail (yeh sabse door wala point hai, ek maximum). Answer: $(1, 0)$ , $λ = 1$ , $f = 1$ .

Neeche wali figure padhna. Violet circle fence boundary $(x - 2)^{2} + y^{2} = 1$ hai; shaded disk feasible region hai. Do magenta arcs $f$ ke cost circles hain. Origin aur centre $(2, 0)$ se hoti dashed navy line disk ko do points par pierce karti hai: magenta mein near point $(1, 0)$ (minimum, $λ = 1$ ) aur orange mein far point $(3, 0)$ (ek maximum, jiska $λ = - 3$ dual feasibility fail karta hai aur reject ho jaata hai). Dono stationarity solve karte hain — sirf $λ$ ka sign inhe alag karta hai.

Level 4 — Synthesis

Exercise 4.1

$f (x, y) = (x - 2)^{2} + (y - 2)^{2}$ ko minimize karo subject to $x + y \leq 2$ , $x \geq 0$ , $y \geq 0$ . Full case analysis ke saath optimum find karo.

Recall Solution 4.1

Constraints: $g_{1} = x + y - 2 \leq 0$ , $g_{2} = - x \leq 0$ , $g_{3} = - y \leq 0$ . Unconstrained min $(2, 2)$ hai, lekin $g_{1} (2, 2) = 2 > 0$ → infeasible, isliye $g_{1}$ active hai. Sirf $g_{1}$ active assume karo ( $λ_{2} = λ_{3} = 0$ ): $L = (x - 2)^{2} + (y - 2)^{2} + λ_{1} (x + y - 2)$ . Stationarity: $2 (x - 2) + λ_{1} = 0$ , $2 (y - 2) + λ_{1} = 0 \Rightarrow x = y$ . Active: $x + y = 2 \Rightarrow x = y = 1$ . Phir $λ_{1} = - 2 (x - 2) = - 2 (1 - 2) = 2 \geq 0$ ✓. Baaki fences check karo: $x = 1 \geq 0$ ✓, $y = 1 \geq 0$ ✓ (dono inactive, $λ_{2} = λ_{3} = 0$ consistent). Slackness ✓. Answer: $(1, 1)$ , $λ_{1} = 2$ , $f = (1 - 2)^{2} + (1 - 2)^{2} = 2$ . Target $(2, 2)$ diagonal fence $x + y = 2$ par kareeb wale point par pull back ho jaata hai; corner fences kabhi play mein nahi aatein.

Exercise 4.2

Probability simplex par projection (SVM-style problems ke liye 1-D warm-up). $\frac{1}{2} ∥ x - a ∥^{2}$ minimize karo $x = (x_{1}, x_{2})$ ke liye, given data $a = (0.8, - 0.3)$ , subject to $x_{1} + x_{2} = 1$ aur $x_{1}, x_{2} \geq 0$ . Projection find karo.

Recall Solution 4.2

$h = x_{1} + x_{2} - 1 = 0$ ; $g_{1} = - x_{1} \leq 0$ , $g_{2} = - x_{2} \leq 0$ . $L = \frac{1}{2} (x_{1} - 0.8)^{2} + \frac{1}{2} (x_{2} + 0.3)^{2} + μ (x_{1} + x_{2} - 1) + λ_{1} (- x_{1}) + λ_{2} (- x_{2})$ . Dono $g$ inactive try karo: stationarity $(x_{1} - 0.8) + μ = 0$ , $(x_{2} + 0.3) + μ = 0$ . Isliye $x_{1} = 0.8 - μ$ , $x_{2} = - 0.3 - μ$ . Sum $= 1$ : $0.5 - 2 μ = 1 \Rightarrow μ = - 0.25$ . Phir $x_{1} = 0.8 + 0.25 = 1.05$ , $x_{2} = - 0.3 + 0.25 = - 0.05$ . Lekin $x_{2} < 0$ violate karta hai $x_{2} \geq 0$ ! Isliye $g_{2}$ active honi chahiye. Ab $g_{2}$ active ( $x_{2} = 0$ ), $g_{1}$ inactive ( $λ_{1} = 0$ ): $h$ se: $x_{1} = 1$ . $x_{2}$ mein stationarity: $(x_{2} + 0.3) + μ - λ_{2} = 0 \Rightarrow 0.3 + μ - λ_{2} = 0$ . $x_{1}$ mein stationarity: $(x_{1} - 0.8) + μ = 0 \Rightarrow 0.2 + μ = 0 \Rightarrow μ = - 0.2$ . Phir $λ_{2} = 0.3 + μ = 0.3 - 0.2 = 0.1 \geq 0$ ✓. Check $x_{1} = 1 \geq 0$ ✓. Answer: $x^{*} = (1, 0)$ , $μ = - 0.2$ , $λ_{1} = 0$ , $λ_{2} = 0.1$ . Projection negative coordinate ko boundary par snap kar deta hai.

Level 5 — Mastery

Exercise 5.1

Hard-margin SVM dual derive karo, KKT-style. Linearly separable dataset ke liye, SVM primal yeh hai: $min_{w, b} \frac{1}{2} ∥ w ∥^{2} s.t. y_{i} (w^{⊤} x_{i} + b) \geq 1, i = 1 \dots N .$ Constraints ko standard form mein likho, Lagrangian form karo, stationarity apply karo, aur batao ki complementary slackness support vectors ke baare mein kya kehta hai.

Recall Solution 5.1

Standard form: $g_{i} = 1 - y_{i} (w^{⊤} x_{i} + b) \leq 0$ , multipliers $α_{i} \geq 0$ . $L = \frac{1}{2} ∥ w ∥^{2} + \sum_{i} α_{i} (1 - y_{i} (w^{⊤} x_{i} + b)) .$ $w$ mein stationarity: $\nabla_{w} L = w - \sum_{i} α_{i} y_{i} x_{i} = 0 \Rightarrow w = i \sum α_{i} y_{i} x_{i}$ . $b$ mein stationarity: $\frac{\partial L}{\partial b} = - \sum_{i} α_{i} y_{i} = 0 \Rightarrow i \sum α_{i} y_{i} = 0$ . Complementary slackness: $α_{i} (1 - y_{i} (w^{⊤} x_{i} + b)) = 0$ .

Agar ek point strictly correct side par hai ( $y_{i} (w^{⊤} x_{i} + b) > 1$ ), toh $g_{i} < 0$ , jo $α_{i} = 0$ force karta hai — woh $w$ mein appear nahi karta.
Sirf margin par wale points ( $y_{i} (w^{⊤} x_{i} + b) = 1$ ) ka $α_{i} > 0$ ho sakta hai. Yeh support vectors hain — sirf yahi data boundary define karta hai. Yeh poore SVM ka KKT interpretation hai: separating plane sirf apne support vectors ka weighted sum hai. ( $w = \sum α_{i} y_{i} x_{i}$ ko $L$ mein wapas substitute karne se $α$ mein classic dual milta hai.)

Exercise 5.2

KKT ⇒ yahan global optimum kyun. Ex 5.1 mein, argue karo ki KKT point global minimum hai, aur woh constraint qualification naam karo jo guarantee karta hai ki multipliers exist karte hain.

Recall Solution 5.2

Objective $\frac{1}{2} ∥ w ∥^{2}$ convex hai (quadratic, positive semidefinite Hessian), aur har constraint $g_{i} = 1 - y_{i} (w^{⊤} x_{i} + b)$ affine hai $(w, b)$ mein (hence convex). Convex objective aur affine constraints wala problem ek convex program hai. Convex programs ke liye, KKT necessary AND sufficient hain global minimum ke liye — isliye chaar conditions satisfy karne wala koi bhi point the global optimum hai. Constraint qualification: Slater's condition ek strictly feasible point maangta hai — koi $(w, b)$ jahan har constraint strictly hold kare, yaani saare $i$ ke liye $y_{i} (w^{⊤} x_{i} + b) > 1$ . Yeh mere separability ke same nahi hai: separability sirf ek point ki guarantee karta hai jahan $y_{i} (w^{⊤} x_{i} + b) \geq 1$ ho (margin par equality allowed), jabki Slater ko har jagah strict inequality chahiye. Lekin, agar data separable hai toh hum hamesha $(w, b)$ ko scale up kar sakte hain strict gap kholne ke liye (jab ek baar margin positive ho, kisi bhi factor $> 1$ se multiply karo), ek strictly feasible point produce karte hue — isliye separability implies Slater yahan, lekin sirf is rescaling step ke baad, by definition nahi. (Iske alawa, kyunki constraints affine hain, aur bhi weak linear constraint qualifications apply hoti hain.) Slater guarantee karta hai ki dual multipliers $α_{i}$ exist karte hain aur strong duality hold hoti hai, jo exactly yeh allow karta hai ki hum primal ki jagah dual solve kar sakein.

Exercise 5.3

Algorithms se connect karo. Do sentences mein explain karo ki projected gradient descent apne fixed point par KKT kaise enforce karta hai, Ex 4.2 ke projection ko mechanism ke roop mein use karte hue.

Recall Solution 5.3

Projected gradient ek downhill step $x - η \nabla f$ leta hai aur phir feasible set par project karta hai — exactly woh operation jo humne KKT se Ex 4.2 mein solve kiya tha (simplex par project karo, negatives ko $0$ par snap karo). Fixed point par gradient step projection se bilkul undo ho jaata hai, jo precisely yeh statement hai ki $- \nabla f$ feasible set ke normal cone mein lie karta hai — yeh KKT stationarity plus complementary slackness ki geometric form hai.