KKT conditions for constrained optimization: Exercises

Before we start, one shared vocabulary reminder so no symbol appears unearned. Two of the symbols carry index letters: throughout this page == $i$ runs over the inequality constraints== ( $i = 1 \dots m$ , the fences) and == $j$ runs over the equality constraints== ( $j = 1 \dots p$ , the wires).

The recurring recipe, which you will apply again and again:

Level 1 — Recognition

Exercise 1.1

State the four KKT conditions for the problem $min f (x)$ s.t. $g_{i} (x) \leq 0$ , $h_{j} (x) = 0$ . Name each.

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$ and $h_{j} (x^{*}) = 0$ .
Dual feasibility: $λ_{i} \geq 0$ .
Complementary slackness: $λ_{i} g_{i} (x^{*}) = 0$ for every $i$ .

Exercise 1.2

For each statement, say true or false and give the one-line reason. (a) Equality multipliers $μ_{j}$ must be $\geq 0$ . (b) If a constraint is inactive at the optimum, its multiplier is $0$ . (c) For a convex problem, KKT are only necessary, never sufficient.

Recall Solution 1.2

(a) False. Only inequality multipliers $λ_{i} \geq 0$ ; equality $μ_{j}$ are free in sign (a wire can push either way). (b) True. Inactive means $g_{i} (x^{*}) < 0$ ; complementary slackness $λ_{i} g_{i} = 0$ then forces $λ_{i} = 0$ . (c) False. For a convex problem KKT are necessary AND sufficient for a global minimum.

Exercise 1.3

Convert to standard $g (x) \leq 0$ form and write the stationarity term for the constraint: $x_{1} + 2 x_{2} \geq 4$ .

Recall Solution 1.3

Move everything to one side so the constraint reads "something $\leq 0$ ": $x_{1} + 2 x_{2} \geq 4 ⟺ 4 - x_{1} - 2 x_{2} \leq 0 ⟹ g (x) = 4 - x_{1} - 2 x_{2} .$ Its gradient is $\nabla g = (- 1, - 2)$ , so the stationarity contribution is $λ (- 1, - 2)$ with $λ \geq 0$ . If you had forgotten to flip, your $λ$ would come out with the wrong sign.

Level 2 — Application

Exercise 2.1

Minimize $f (x) = (x - 1)^{2}$ subject to $x \geq 3$ . Find $x^{*}$ , $λ$ , and $f (x^{*})$ .

Recall Solution 2.1

Standard form: $g = 3 - x \leq 0$ , so $\nabla g = - 1$ . $L = (x - 1)^{2} + λ (3 - x)$ . Stationarity: $2 (x - 1) - λ = 0$ . The unconstrained min is $x = 1$ , which violates $x \geq 3$ — so the fence must be active: $g = 0 \Rightarrow x = 3$ . Then $λ = 2 (x - 1) = 2 (3 - 1) = 4 \geq 0$ ✓. Slackness ✓ ( $g = 0$ ). Answer: $x^{*} = 3$ , $λ = 4$ , $f = (3 - 1)^{2} = 4$ .

Exercise 2.2

Minimize $f (x, y) = x^{2} + y^{2}$ subject to $x + 2 y \geq 5$ . Find the point and $λ$ .

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 = λ$ . The origin is infeasible, so try active: $x + 2 y = 5 \Rightarrow λ /2 + 2 λ = 5 \Rightarrow \frac{5 λ}{2} = 5 \Rightarrow λ = 2$ . Then $x = 1, y = 2$ . Check $λ = 2 \geq 0$ ✓, slackness ✓. Answer: $(1, 2)$ , $λ = 2$ , $f = 1 + 4 = 5$ .

Reading the figure below. The violet line is the fence $x + 2 y = 5$ ; the shaded band above it is the feasible region ( $x + 2 y \geq 5$ ). The magenta arcs are level circles of $f = x^{2} + y^{2}$ (points of equal cost, growing outward from the origin). The optimum $(1, 2)$ in magenta is where the smallest such circle first touches the feasible band — the closest point of the line to the origin. The orange arrow is $- \nabla f$ (the downhill pull), and notice it points straight along the fence's normal: that is stationarity made visible — the pull is exactly cancelled by the fence's push.

Figure — KKT conditions for constrained optimization

Exercise 2.3

Minimize $f (x) = x^{2}$ subject to $- 2 \leq x \leq 2$ (i.e. $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$ . Try both inactive ( $λ_{1} = λ_{2} = 0$ ): $2 x = 0 \Rightarrow x = 0$ . Check $- 2 \leq 0 \leq 2$ ✓, slackness ✓. Answer: $x^{*} = 0$ , both $λ = 0$ , $f = 0$ . The marble sits at the bottom, touching no wall.

Level 3 — Analysis

Exercise 3.1

Minimize $f = x^{2} + y^{2}$ subject to $h : x + y = 2$ and $g : y \geq x$ (i.e. $x - y \leq 0$ ). Find $(x, y)$ , $μ$ , $λ$ .

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$ . Try $g$ inactive ( $λ = 0$ ): $2 x + μ = 0$ , $2 y + μ = 0 \Rightarrow x = y$ . With $x + y = 2 \Rightarrow x = y = 1$ . Check $g = x - y = 0 \leq 0$ ✓ (in fact exactly on the fence, still feasible), slackness ✓ ( $λ = 0$ ). Solve $μ$ : $2 (1) + μ = 0 \Rightarrow μ = - 2$ . Answer: $(1, 1)$ , $μ = - 2$ , $λ = 0$ . Note $μ < 0$ is perfectly legal — equality multipliers have no sign restriction.

Exercise 3.2

Consider $min f = x$ subject to $g_{1} = x^{2} \leq 0$ . The only feasible point is $x = 0$ . Show that LICQ fails here, and discuss whether KKT can be certified.

Recall Solution 3.2

Feasibility: $x^{2} \leq 0$ forces $x = 0$ (a single point). At $x^{*} = 0$ the constraint is active ( $g_{1} = 0$ ). LICQ check: the active gradient is $\nabla g_{1} = 2 x = 0$ at $x^{*} = 0$ . A set containing the zero vector is linearly dependent, so LICQ fails. Stationarity attempt: $\nabla f + λ \nabla g_{1} = 1 + λ \cdot 0 = 1 \neq = 0$ for any $λ$ . So no multiplier makes stationarity hold, even though $x = 0$ is the (only, hence optimal) feasible point. This is exactly the situation the parent note warns about: without a constraint qualification, KKT need not hold at an optimum. Answer: LICQ fails; KKT stationarity is unsatisfiable here; the multiplier does not exist.

Exercise 3.3

Minimize $f = x^{2} + y^{2}$ subject to $g = (x - 2)^{2} + y^{2} - 1 \leq 0$ (a disk centred at $(2, 0)$ of radius $1$ ). Find the optimum by geometry, then verify with KKT.

Recall Solution 3.3

Geometry: we want the point of the disk closest to the origin. The disk's nearest point to $(0, 0)$ lies on the line from origin to centre $(2, 0)$ , at distance (centre distance) $-$ (radius) $= 2 - 1 = 1$ . So $x^{*} = (1, 0)$ . KKT check: $\nabla f = (2 x, 2 y)$ , $\nabla g = (2 (x - 2), 2 y)$ . Try active: $g = 0$ . Stationarity: $2 x + λ \cdot 2 (x - 2) = 0$ and $2 y + λ \cdot 2 y = 0$ . Second equation: $2 y (1 + λ) = 0$ . Since $λ \geq 0$ , $1 + λ > 0$ , so $y = 0$ . With $y = 0$ , active: $(x - 2)^{2} = 1 \Rightarrow x = 1$ or $x = 3$ . First 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 fails (this is the farthest point, a maximum). Answer: $(1, 0)$ , $λ = 1$ , $f = 1$ .

Reading the figure below. The violet circle is the fence boundary $(x - 2)^{2} + y^{2} = 1$ ; the shaded disk is the feasible region. The two magenta arcs are cost circles of $f$ . The dashed navy line through the origin and the centre $(2, 0)$ pierces the disk at two points: the near point $(1, 0)$ in magenta (the minimum, $λ = 1$ ) and the far point $(3, 0)$ in orange (a maximum, whose $λ = - 3$ fails dual feasibility and is rejected). Both solve stationarity — only the sign of $λ$ tells them apart.

Level 4 — Synthesis

Exercise 4.1

Minimize $f (x, y) = (x - 2)^{2} + (y - 2)^{2}$ subject to $x + y \leq 2$ , $x \geq 0$ , $y \geq 0$ . Find the optimum with full case analysis.

Recall Solution 4.1

Constraints: $g_{1} = x + y - 2 \leq 0$ , $g_{2} = - x \leq 0$ , $g_{3} = - y \leq 0$ . Unconstrained min is $(2, 2)$ , but $g_{1} (2, 2) = 2 > 0$ → infeasible, so $g_{1}$ is active. Assume only $g_{1}$ active ( $λ_{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$ . Then $λ_{1} = - 2 (x - 2) = - 2 (1 - 2) = 2 \geq 0$ ✓. Check other fences: $x = 1 \geq 0$ ✓, $y = 1 \geq 0$ ✓ (both inactive, $λ_{2} = λ_{3} = 0$ consistent). Slackness ✓. Answer: $(1, 1)$ , $λ_{1} = 2$ , $f = (1 - 2)^{2} + (1 - 2)^{2} = 2$ . The target $(2, 2)$ is pulled back to the closest point on the diagonal fence $x + y = 2$ ; the corner fences never come into play.

Exercise 4.2

Projection onto the probability simplex (1-D warm-up for SVM-style problems). Minimize $\frac{1}{2} ∥ x - a ∥^{2}$ for $x = (x_{1}, x_{2})$ , given data $a = (0.8, - 0.3)$ , subject to $x_{1} + x_{2} = 1$ and $x_{1}, x_{2} \geq 0$ . Find the projection.

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})$ . Try both $g$ inactive: stationarity $(x_{1} - 0.8) + μ = 0$ , $(x_{2} + 0.3) + μ = 0$ . So $x_{1} = 0.8 - μ$ , $x_{2} = - 0.3 - μ$ . Sum $= 1$ : $0.5 - 2 μ = 1 \Rightarrow μ = - 0.25$ . Then $x_{1} = 0.8 + 0.25 = 1.05$ , $x_{2} = - 0.3 + 0.25 = - 0.05$ . But $x_{2} < 0$ violates $x_{2} \geq 0$ ! So $g_{2}$ must be active. Now $g_{2}$ active ( $x_{2} = 0$ ), $g_{1}$ inactive ( $λ_{1} = 0$ ): From $h$ : $x_{1} = 1$ . Stationarity in $x_{2}$ : $(x_{2} + 0.3) + μ - λ_{2} = 0 \Rightarrow 0.3 + μ - λ_{2} = 0$ . Stationarity in $x_{1}$ : $(x_{1} - 0.8) + μ = 0 \Rightarrow 0.2 + μ = 0 \Rightarrow μ = - 0.2$ . Then $λ_{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$ . The projection snaps the negative coordinate to the boundary.

Level 5 — Mastery

Exercise 5.1

Derive the hard-margin SVM dual, KKT-style. For a linearly separable dataset, the SVM primal is $min_{w, b} \frac{1}{2} ∥ w ∥^{2} s.t. y_{i} (w^{⊤} x_{i} + b) \geq 1, i = 1 \dots N .$ Write the constraints in standard form, form the Lagrangian, apply stationarity, and state what complementary slackness says about support vectors.

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)) .$ Stationarity in $w$ : $\nabla_{w} L = w - \sum_{i} α_{i} y_{i} x_{i} = 0 \Rightarrow w = i \sum α_{i} y_{i} x_{i}$ . Stationarity in $b$ : $\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$ .

If a point is strictly on the correct side ( $y_{i} (w^{⊤} x_{i} + b) > 1$ ), then $g_{i} < 0$ , forcing $α_{i} = 0$ — it does not appear in $w$ .
Only points on the margin ( $y_{i} (w^{⊤} x_{i} + b) = 1$ ) may have $α_{i} > 0$ . These are the support vectors — the only data that define the boundary. This is the KKT interpretation of the whole SVM: the separating plane is a weighted sum of just its support vectors. (Substituting $w = \sum α_{i} y_{i} x_{i}$ back into $L$ yields the classic dual in $α$ .)

Exercise 5.2

Why KKT ⇒ global optimum here. In Ex 5.1, argue that the KKT point is the global minimum, and name the constraint qualification that guarantees multipliers exist.

Recall Solution 5.2

The objective $\frac{1}{2} ∥ w ∥^{2}$ is convex (quadratic, positive semidefinite Hessian), and each constraint $g_{i} = 1 - y_{i} (w^{⊤} x_{i} + b)$ is affine in $(w, b)$ (hence convex). A problem with convex objective and affine constraints is a convex program. For convex programs, KKT are necessary AND sufficient for a global minimum — so any point satisfying the four conditions is the global optimum. Constraint qualification: Slater's condition asks for a strictly feasible point — some $(w, b)$ with every constraint holding strictly, i.e. $y_{i} (w^{⊤} x_{i} + b) > 1$ for all $i$ . This is not the same as mere separability: separability only guarantees a point with $y_{i} (w^{⊤} x_{i} + b) \geq 1$ (equality allowed on the margin), whereas Slater needs strict inequality everywhere. However, if the data is separable we can always scale $(w, b)$ up to open a strict gap (multiply by any factor $> 1$ once the margin is positive), producing a strictly feasible point — so separability implies Slater here, but only after this rescaling step, not by definition. (Additionally, because the constraints are affine, even weaker linear constraint qualifications apply.) Slater guarantees the dual multipliers $α_{i}$ exist and strong duality holds, which is exactly what lets us solve the dual instead of the primal.

Exercise 5.3

Connect to algorithms. Explain in two sentences how projected gradient descent enforces KKT at its fixed point, using Ex 4.2's projection as the mechanism.

Recall Solution 5.3

Projected gradient takes a downhill step $x - η \nabla f$ and then projects back onto the feasible set — exactly the operation we solved by KKT in Ex 4.2 (project onto the simplex, snapping negatives to $0$ ). At a fixed point the gradient step is undone entirely by the projection, which is precisely the statement that $- \nabla f$ lies in the normal cone of the feasible set — the geometric form of KKT stationarity plus complementary slackness.