the KKT conditions
/ K-K-T, spelled out; Karush-Kuhn-Tucker /
Lagrange multipliers handle constraints that must hold exactly (an equality, 'stay ON the fence'). But many real constraints are one-sided: a budget you may not EXCEED, a stress that must not be too high, a probability that cannot go negative. The KKT conditions extend the multiplier idea to these inequality constraints — they are the master first-order test that a solution of a general constrained optimization problem must satisfy.
For minimizing f(x) subject to equalities h_j(x) = 0 and inequalities g_i(x) <= 0, the KKT conditions package four requirements at an optimum x*. (1) Stationarity: the gradient of the Lagrangian vanishes, grad f + sum lambda_j grad h_j + sum mu_i grad g_i = 0 — a balance of forces. (2) Primal feasibility: x* actually satisfies all the constraints. (3) Dual feasibility: the inequality multipliers are nonnegative, mu_i >= 0 (a constraint can only PUSH the solution one way). (4) COMPLEMENTARY SLACKNESS: for each inequality, mu_i * g_i(x*) = 0 — meaning either the constraint is ACTIVE (tight, g_i = 0, the fence is touched and its multiplier may be positive) or it is INACTIVE (slack, g_i < 0, the fence is irrelevant and its multiplier is zero). That last condition is the heart of the matter: it automatically figures out WHICH constraints are binding at the optimum.
The KKT conditions are the theoretical foundation of essentially all constrained optimization — interior-point methods, active-set methods, SVM training, and economic equilibria are all, at bottom, ways to solve the KKT system. For a CONVEX problem satisfying a constraint qualification, the KKT conditions are both necessary AND sufficient: any KKT point is a global optimum. The honest caveats: for non-convex problems they are only necessary (a KKT point need not be a minimum), and they require a constraint qualification (such as linear independence of active-constraint gradients) to be guaranteed at the optimum — pathological constraint geometries can break them. Getting the sign convention and the direction of the inequalities right is a notorious source of bugs.
Minimize f(x) = x^2 subject to x >= 1 (i.e. g(x) = 1 - x <= 0). The optimum is x = 1, the constraint is ACTIVE (g = 0), and its multiplier mu = 2 > 0 satisfies complementary slackness mu * g = 0. If instead the constraint were x >= -1, the unconstrained min x = 0 is feasible, the constraint is INACTIVE, so mu = 0 — the fence never mattered.
Complementary slackness: a constraint is tight (mu>0) or irrelevant (mu=0).
KKT points are global optima only when the problem is convex (and a constraint qualification holds); for non-convex problems KKT is merely necessary, so a KKT point can be a saddle or even a maximum. Sign conventions matter: inequality multipliers must be nonnegative, and getting g_i <= 0 versus >= 0 backwards is a classic mistake.