KKT conditions for constrained optimization

WHAT problem are we solving?

WHY this form? Any problem can be massaged into it: $g(x)\ge 0$ becomes $-g(x)\le 0$ ; maximizing $f$ is minimizing $-f$ . So this single template covers all smooth constrained optimization.

HOW we derive KKT — from Lagrange to inequalities

Step 1: Recall equality-only Lagrange

With only $h_j(x)=0$ , the minimum sits where the gradient of $f$ is a combination of constraint gradients: $\nabla f(x^*) + \sum_j \mu_j \nabla h_j(x^*) = 0.$

Why? If $\nabla f$ had any component along the constraint surface, you could slide that way and decrease $f$ while staying feasible. So at a minimum $\nabla f$ must be ⟂ to the surface, i.e. a combination of the $\nabla h_j$ (the normals).

Step 2: Add an inequality $g(x)\le 0$

Two cases for each inequality at the optimum:

Inactive ( $g_i(x^*)<0$ , strictly inside): the fence isn't touched. Locally it's as if the constraint doesn't exist → its multiplier must be $0$ .
Active ( $g_i(x^*)=0$ , on the fence): it behaves like an equality, but with a sign restriction.

Why the sign? To stay feasible we can only move where $g_i$ decreases or stays ( $g_i\le0$ ). For $x^*$ to be a minimum, $f$ must not decrease in any feasible direction. Pushing into the fence, $-\nabla g_i$ points to the feasible interior; $\nabla f$ must point "outward" to block escape. This forces the multiplier $\lambda_i \ge 0$ .

Formula The KKT conditions

$x^*$ (with multipliers $\lambda_i\ge0$ , $\mu_j$ ) satisfies:

Stationarity: $\displaystyle \nabla f(x^*)+\sum_i \lambda_i \nabla g_i(x^*)+\sum_j \mu_j \nabla h_j(x^*)=0$
Primal feasibility: $g_i(x^*)\le0,\quad h_j(x^*)=0$
Dual feasibility: $\lambda_i\ge0$
Complementary slackness: $\lambda_i\, g_i(x^*)=0\quad\forall i$

Define the Lagrangian $\;\mathcal{L}(x,\lambda,\mu)=f(x)+\sum_i\lambda_i g_i(x)+\sum_j\mu_j h_j(x)$ ; then stationarity is just $\nabla_x\mathcal{L}=0$ .

Why complementary slackness ( $\lambda_i g_i = 0$ )?

It's the unifying statement of Step 2. Either:

$g_i<0$ (inactive) → forces $\lambda_i=0$ , or
$\lambda_i>0$ (active multiplier) → forces $g_i=0$ .

Both can't be "loose" at once. The product being zero encodes "a fence only pushes back when you're touching it."

A subtle but essential ingredient: Constraint Qualification

WHY needed? If the active gradients are degenerate (e.g. two fences meeting in a cusp), the multipliers may not exist even though $x^*$ is optimal. LICQ guarantees the multipliers exist and are unique.

Worked Examples

Worked example Example 1 — one active inequality

Minimize $f(x,y)=x^2+y^2$ s.t. $g=x+y-1\le 0$ ... wait, the unconstrained min $(0,0)$ has $g(0,0)=-1\le0$ , feasible! So the constraint is inactive, $\lambda=0$ , answer $(0,0)$ .

Now flip it: minimize $x^2+y^2$ s.t. $g = 1-x-y\le 0$ (i.e. $x+y\ge1$ ). Lagrangian: $\mathcal L = x^2+y^2+\lambda(1-x-y)$ .

Stationarity: $2x-\lambda=0,\;2y-\lambda=0\Rightarrow x=y=\lambda/2$ . Why? set $\nabla_x\mathcal L=0$ .
Guess active: $g=0\Rightarrow x+y=1\Rightarrow 2x=1\Rightarrow x=y=\tfrac12$ . Why? try the boundary first since the origin is now infeasible.
Then $\lambda=2x=1\ge0$ ✓ dual feasibility. Complementary slackness ✓ ( $g=0$ ). Answer: $(\tfrac12,\tfrac12)$ , $f=\tfrac12$ . Origin is excluded; the ball rests on the fence.

Common Mistakes (Steel-manned)

Active Recall

Recall The four KKT conditions (cover and recite)

Stationarity $\nabla_x\mathcal L=0$ · 2. Primal feasibility ( $g\le0,h=0$ ) · 3. Dual feasibility ( $\lambda\ge0$ ) · 4. Complementary slackness ( $\lambda_i g_i=0$ ).

Recall Why must

$\lambda_i\ge0$ ? Because a feasible move keeps $g_i\le0$ ; for $x^*$ to be a min, $\nabla f$ must oppose escape into the feasible region, forcing the multiplier non-negative. Equality multipliers have no such restriction.

Recall When are KKT sufficient for a global min?

When the problem is convex ( $f$ , $g_i$ convex; $h_j$ affine).

Recall Feynman: explain to a 12-year-old

You roll a marble in a bowl, but there are walls. The marble stops at the lowest spot it can reach. If it stops away from a wall, the ground there is flat. If it stops against a wall, the wall is pushing on it — and a wall only pushes when you're touching it (that's "complementary slackness"). KKT is just the rulebook that says: at the stopping place, the downhill pull is exactly balanced by flat ground plus the walls you're leaning on.

Connections

Lagrange Multipliers — the equality-only special case ( $\lambda=0$ everywhere, only $\mu$ ).
Convex Optimization — where KKT become necessary and sufficient.
Duality and the Dual Problem — $\lambda,\mu$ are the dual variables; strong duality ↔ KKT.
Support Vector Machines — KKT + slackness identify the support vectors (active constraints).
Gradient Descent and Projected Gradient — algorithmic cousins for finding KKT points.
Constraint Qualifications (LICQ, Slater) — when multipliers are guaranteed to exist.

Flashcards

What is the standard form of a constrained optimization problem for KKT?

\min f(x)

s.t.

g_i(x)\le0

and

h_j(x)=0

State the stationarity condition.

\nabla f + \sum_i\lambda_i\nabla g_i + \sum_j\mu_j\nabla h_j = 0

, i.e.

\nabla_x\mathcal L=0

What is complementary slackness and what does it mean?

\lambda_i g_i(x^*)=0

for all

i

; an inequality multiplier is nonzero only if that constraint is active (

g_i=0

Which KKT multipliers must be non-negative?

Only the inequality multipliers

\lambda_i\ge0

; equality multipliers

\mu_j

are free in sign.

When are KKT conditions sufficient for a global minimum?

When the problem is convex:

f

and

g_i

convex,

h_j

affine.

What is a constraint qualification (e.g. LICQ) and why is it needed?

It ensures multipliers exist; LICQ requires active inequality + equality constraint gradients to be linearly independent at

x^*

A negative

\lambda

appears in your solution — what does it tell you?

Your active-set guess is wrong; that constraint should actually be inactive (or you have a max/saddle, not a min).

Geometrically, what does stationarity say at the optimum?

-\nabla f

lies in the cone spanned by active constraint gradients — every descent direction is blocked.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho tum ek ball ho jo cost ko minimize karna chahti ho — yaani neeche girna chahti ho. Lekin tum ek playground ke andar ho jiske around fences (inequality constraints $g\le0$ ) aur kuch wires (equality constraints $h=0$ ) hain. Ball kahan rukegi? Ya to wahan jahan ground bilkul flat hai (unconstrained minimum), ya phir kisi fence se chipak ke jahan se aage badhna possible hi nahi. KKT conditions bas isi "rukne wali jagah" ka precise mathematical rulebook hain.

Char conditions yaad rakho — S P D C: Stationarity ( $\nabla_x\mathcal L=0$ , yaani downhill pull aur fences ka push balance ho jaye), Primal feasibility (constraints satisfy ho), Dual feasibility ( $\lambda_i\ge0$ , sirf inequality wale multipliers), aur Complementary slackness ( $\lambda_i g_i=0$ ). Slackness ka matlab simple hai: ek fence tabhi push karta hai jab tum usse touch kar rahe ho. Agar tum fence se door ho ( $g<0$ ), to uska multiplier $\lambda=0$ .

Sabse common galti: log socht hain saare multipliers non-negative hone chahiye. Galat! Sirf $\lambda$ (inequality) $\ge0$ hota hai, $\mu$ (equality) kisi bhi sign ka ho sakta hai — bilkul normal Lagrange ki tarah. Doosri galti: har constraint ko active maan ke solve karna. Hamesha cases test karo — agar tumhe $\lambda<0$ mile, to samajh jao tumhara active-set guess galat tha.

Kyun matter karta hai? Convex problems mein (jaise SVM, machine learning ke optimization) KKT conditions necessary aur sufficient hoti hain — yaani inhe solve kar lo to global minimum guaranteed mil jaata hai. Isiliye SVM mein "support vectors" wahi points hote hain jinka constraint active hai aur $\lambda>0$ . KKT poori modern optimization ki backbone hai.

KKT conditions for constrained optimization

WHAT problem are we solving?

HOW we derive KKT — from Lagrange to inequalities

Step 1: Recall equality-only Lagrange

Step 2: Add an inequality $g(x)\le 0$

Why complementary slackness ( $\lambda_i g_i = 0$ )?

A subtle but essential ingredient: Constraint Qualification

Worked Examples

Common Mistakes (Steel-manned)

Active Recall

Connections

Flashcards

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced Topics (Elite Level)

Connections