Intuition The one core ideaYou want the lowest point of a landscape, but you're locked inside a fenced yard. The KKT conditions are the exact rulebook for "the ball has stopped" — the downhill pull is either cancelled by flat ground, or blocked by the fences you're leaning on. Everything below is the vocabulary you need before that sentence makes full sense.
This page builds every symbol used in the parent KKT note from absolute zero. Read it top to bottom: each item uses only the ones above it.
Definition Standing assumption: everything is smooth (C 1 f g i h j continuously differentiable (C 1 Why this matters: the whole KKT story is built from the arrows ∇ f ∇ g i ∇ h j exist if the functions are differentiable. At a sharp kink there is no single well-defined slope, so no gradient — and the arguments below would collapse. Keep this in your back pocket: no smoothness, no gradients, no KKT.
Definition Objective functionf f cost . We write f ( x ) x
Picture a landscape. The horizontal floor is where your input lives; the height above each spot is f
Worked example Reading figure s01The blue rings are contours — each ring links all points of equal cost, like height lines on a hiking map. Rings packed close = steep; rings far apart = gentle. The yellow dot at the centre is the valley floor , the single lowest cost. As you walk outward across rings, f is the definition of "minimum": the spot no ring encircles from below.
Why the topic needs it: the entire game is "find the lowest reachable height." Without a cost function there is nothing to minimize.
Definition The optimal pointx ∗ x ∗ x winning input — the point where f x ∗ = arg min f argument (input) that achieves the minimum." Careful: min f cost (a number, the height of the valley floor); x ∗ location that achieves it (the coordinates on the floor). In figure s01 the height of the yellow dot is min f position of the yellow dot is x ∗ at x ∗
x ∈ R n x point — a list of n R R n n ∈
n = 1 x n = 2 x = ( x , y ) n = 3
Why the topic needs it: the ball can be anywhere in this space. Constraints will carve out the part where it's allowed to be, and the winner x ∗
min x ∈ R n f ( x ) min over all points x R n f ( x ) x min what we're free to choose .
Now we forbid part of the yard.
Definition Inequality constraintg i ( x ) ≤ 0 g i g i ( x ) ≤ 0 fence : the curve where g i ( x ) = 0
Definition Equality constrainth j ( x ) = 0 h j ( x ) = 0 wire you must slide along, no leaving it.
Definition The subscriptsi j i = 1 … m m j = 1 … p p g 3
Worked example Reading figure s02The red line is a fence's border, where g = 0 g ≤ 0 x + y ≥ 1 yellow line is a wire, where h = 0 green dot sits on the yellow wire and inside the pink allowed band, so it satisfies both at once: that is what "feasible" looks like. Notice the sign story: on the fence border g = 0 g < 0 g > 0
Definition Feasible pointA point is feasible if it obeys every fence and every wire at once. Feasible = "legally allowed to stand here." The optimum x ∗
Why the ≤ 0 Any inequality can be pushed into this shape: g ( x ) ≥ 0 − g ( x ) ≤ 0 x + y ≥ 1 1 − x − y ≤ 0
≤ ≥ Why it feels right: they both just carve the yard.
The fix: the sign of the multiplier (§6) is tied to the ≤ 0 first , then apply KKT, or every sign flips.
This is the star of KKT, so we build it carefully. (Recall the standing C 1 ∇ f
Intuition Why we need a new tool here"Minimum" means "you can't decrease f which direction decreases f , and by how much. That direction is exactly what the gradient measures — no other single tool answers "which way is downhill and how steep?"
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 ) . ∇ steepest increase of f
Worked example Reading figure s03Same blue contour rings as before. At the white dot the green arrow is ∇ f higher cost — the steepest way up . The red arrow is − ∇ f down , the direction a released ball rolls. Two things to notice: (1) both arrows are perpendicular to the contour ring they start on — uphill is always "straight across" the height lines; (2) at the valley floor of figure s01 the gradient still exists — it is just the zero vector ∇ f = 0
∇ f uphill → so − ∇ f downhill (steepest descent — the direction a rolling ball wants to go, and the engine of Gradient Descent and Projected Gradient ).Where the ground is flat , every partial is zero, so the gradient is the zero vector ∇ f = 0
∇ g i out of the allowed region (toward larger g i g i > 0
Why the topic needs it: KKT is entirely a statement about arrows — where − ∇ f
a ⋅ b a = ( a 1 , … , a n ) b = ( b 1 , … , b n ) dot product is a single number, built by multiplying matching coordinates and adding:
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 if the arrows roughly agree in direction, negative if they oppose, and zero if they meet at a right angle.
Definition Perpendicular ⟂Two arrows are perpendicular (⟂) exactly when their dot product is 0 a ⋅ b = 0 ( 1 , 0 ) ⋅ ( 0 , 1 ) = 1 ⋅ 0 + 0 ⋅ 1 = 0
Intuition Why "flat along a wire" means perpendicularAlong a wire h = 0 tangent to the wire. If ∇ f f ∇ f perpendicular to the wire — i.e. parallel to the wire's own gradient ∇ h Lagrange Multipliers .
Before we can talk about which fence-arrows matter, we must know which fences you are actually touching at a point.
Definition Active vs inactive fenceAt a point x ∗
g i ( x ∗ ) < 0 inactive (you're not touching that fence — it plays no role locally).g i ( x ∗ ) = 0 active (leaning on it — it can push back).
Only active fences can push, so only their gradients ∇ g i
Definition Linear combinationA linear combination of arrows v 1 , … , v k c 1 v 1 + c 2 v 2 + … c i
Definition Cone (of active constraint gradients)Take the gradients ∇ g i active fences only (the ones just defined). If we mix them with non-negative weights (c i ≥ 0 cone . Picture the active fence-normal arrows fanning out; the cone is everything you can build by adding them with positive amounts.
Worked example Reading figure s04The two red arrows are the outward gradients ∇ g 1 ∇ g 2 active fences you're leaning on at the optimum x ∗ yellow wedge is their cone: every arrow you can make as c 1 ∇ g 1 + c 2 ∇ g 2 c 1 , c 2 ≥ 0 green arrow is − ∇ f inside the yellow wedge — that is the picture of the ball being trapped: the only downhill direction is a positive mix of "into the fences," which the fences forbid.
Intuition Geometric soul, restated with the vocabulary now in handAt the KKT optimum x ∗ − ∇ f inside the cone of the active fence-gradients (the cone just defined above, drawn in figure s04). Every escape direction that lowers f
Why non-negative weights? A fence can only push , never pull. Push = a ≥ 0 λ i ≥ 0
Definition Lagrange multipliersμ j λ i
μ j h j either way (you can be shoved from both sides of a wire), so μ j free in sign — positive, negative, or zero.λ i g i one way (outward), so λ i ≥ 0 active fences push, so an inactive fence has λ i = 0
Common mistake "All multipliers must be≥ 0 Why it feels right: you memorized λ i ≥ 0 The fix: only 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 , not a distance: g i = 0 g i < 0 a fence only pushes when your slack is used up (you're touching it). Either g i = 0 λ i = 0
g i ( x ∗ ) < 0 Why it feels right: more negative feels like "deeper in."
The fix: g i constraint function , not a ruler. Its numeric value depends on how you wrote the constraint (scale it by 2 and every value doubles). All KKT reads off it is the sign / whether it is zero , not a true geometric distance.
Definition The LagrangianL ( x , λ , μ ) = f ( x ) + ∑ i λ i g i ( x ) + ∑ j μ j h j ( x ) . f plus a penalty term for each constraint, weighted by its multiplier. The ∑ i i
Once packaged this way, the messy "stationarity" condition of KKT collapses to one clean line: ∇ x L = 0 x Duality and the Dual Problem .
Definition Convex function / setA function is convex if its graph is a bowl — the straight line between any two points on it never dips below the graph. A set is convex if the straight segment between any two of its points stays inside. See Convex Optimization .
Intuition Why convexity mattersFor a bowl there is exactly one valley and no false bottoms. So for a convex problem, KKT don't just suggest a candidate — they guarantee the global minimum. Non-convex landscapes have many dips, so KKT can also flag maxima and saddles.
Definition Constraint qualification — the fine print that makes KKT validKKT are only guaranteed to hold at an optimum x ∗ constraint qualification (a regularity condition on the constraints) is satisfied. Two standard ones:
LICQ (Linear Independence Constraint Qualification): the gradients of all active fences and all wires at x ∗ linearly independent — no one of them is a linear combination of the others. Picture the active arrows pointing in genuinely different directions, not stacked on top of each other or squashed into a lower dimension.Slater's condition (for convex problems): there exists at least one strictly feasible point — a point where every inequality is slack (g i ( x ) < 0
Intuition Why we need a qualification at allIf the active fence-gradients are degenerate — say two fences meeting in a sharp cusp so their arrows line up — the multipliers λ i fail to exist even though x ∗ Constraint Qualifications (LICQ, Slater) .
These foundations combine directly in the flagship application, Support Vector Machines , where every symbol above reappears.
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.
What smoothness do f , g i , h j Continuously differentiable (C 1 ∇ f , ∇ g i , ∇ h j
What does x ∈ R n A point = a list of n
What is x ∗ min f x ∗ = arg min f location (input); min f cost (the number/height it achieves).
What does f ( x ) The cost / height at point x
Convert "x + y ≥ 1 1 − x − y ≤ 0 ≤ 0
What does the gradient ∇ f − ∇ f ∇ f uphill ; − ∇ f downhill .
At the valley floor, does the gradient vanish or cease to exist? It still exists — it is the zero vector ∇ f = 0
Write the dot product formula and the perpendicular test. a ⋅ b = ∑ k a k b k a ⋅ b = 0
What makes a fence "active" vs "inactive" at x ∗ Active: g i ( x ∗ ) = 0 g i ( x ∗ ) < 0
What is a cone of gradients, and why non-negative weights? All sums of active fence-arrows with weights ≥ 0
Which multipliers are ≥ 0 Fence (inequality) multipliers λ i ≥ 0 μ j
Is g i ( x ∗ ) < 0 No — it's a signed constraint value (slack); KKT only cares about its sign / whether it's zero.
State complementary slackness in words. A fence only pushes when its slack is used up: λ i g i = 0
Why is convexity the golden property? One valley, no false bottoms → KKT become sufficient for the global minimum.
State one constraint qualification. LICQ — active fence and wire gradients are linearly independent at x ∗
What breaks if the constraint qualification fails? Multipliers may not exist even at a true optimum, so KKT can be inapplicable.
