KKT Conditions

The KKT conditions are the rules that tell you when you have truly found the best answer to a problem that has constraints — like 'minimise cost, but do not exceed the budget' or 'maximise accuracy, but keep the model small enough to run on a phone.' They sit underneath most commercial optimization solvers, including the ones that tune hyperparameters, train support vector machines, and allocate resources in logistics. Learning them now sets up your later study of convex optimization and duality, and gives you the language to read optimisation papers and solver documentation without being lost.

Imagine you are standing on a hill in the dark, and your goal is to find the lowest point in a fenced-off area. Without a fence, you just walk downhill until you reach the bottom — that's unconstrained optimisation. But with a fence, you cannot cross it, so the best you can do might be up against the fence at some point where you are as low as you can go while staying inside. Now picture that the fence is not just a boundary but a physical wall, and you are a small ball. To find the lowest point you can reach, you roll downhill. When you hit the wall, you slide along it, and you stop when the wall is pushing back on you exactly as hard as the hill is pulling you down. That moment — where the push of the wall exactly balances the pull of the slope — is the mathematical heart of the KKT conditions. The conditions are a set of equations that describe that balance point, and they also tell you when the wall is irrelevant: if the lowest point inside the fence happens to be far from the fence, the wall exerts no force at all. In optimisation, the fence is called a constraint, the pull of the hill is the gradient of the objective, and the push of the wall is represented by a number called a multiplier.

Think of the hill and the wall as the simplest case of a constrained problem. The hill's slope pulls you in a certain direction — in mathematics, that pull is the derivative of the objective function. The wall stops you from going where the slope wants to take you. There are two possible outcomes. First, the lowest point inside the fence is not touching the fence at all; then the wall is irrelevant, and you just roll to the bottom of the hill. Second, the lowest point is right up against the wall; then you are stuck at the boundary, and the wall must be pushing back exactly enough to cancel the hill's pull. If the wall pushed any harder, you would be pushed back inside; if it pushed any less, you would roll through it. This balance is the 'stationarity' condition. The KKT conditions list all the situations where you are at a genuine stopping point — they are the 'first-order necessary conditions' for optimality. The analogy stops being exact when the hill is not smooth or when there are multiple walls: the real conditions require that the hill has a defined slope and that the walls are not arranged in a pathological way. Also, the wall analogy makes it seem like the multiplier is a physical force, but in optimisation it is just a number that measures how much the optimal answer would improve if the wall were moved a little. That number is called the dual variable or Lagrange multiplier. The conditions are named after William Karush, Harold Kuhn, and Albert Tucker, who formalised them in the mid-20th century.

The KKT conditions are a set of mathematical conditions that, if satisfied, tell you that a point is a candidate for the optimal solution of a constrained optimisation problem, involving one condition for the slope (stationarity), one for staying inside the allowed region (feasibility), one for the direction of the constraint force (dual feasibility), and one that says a constraint either binds or has a zero multiplier (complementary slackness).

You have notes on Lagrange multipliers, which fold equality constraints into the objective. The KKT conditions are the extension of that idea to inequality constraints — like 'x must be non-negative' instead of 'x must equal 3'. You also have notes on duality: the multipliers that appear in the KKT conditions are exactly the dual variables, and the dual problem is built from them. Convex optimisation and linear programming both rely on the KKT conditions; in convex problems, they are not just necessary but sufficient, which is a big part of why convex problems are so well-behaved. In machine learning, almost every training loop is an unconstrained optimisation of a loss, but regularisation (like L1 or L2) is often expressed as a constrained problem, and the KKT conditions show how the regularisation weight trades off against the loss. Your notes on gradient descent are about the algorithm that actually finds these points; the KKT conditions are the destination that algorithm is searching for.