KKT Conditions

Why Does This Exist?

Unconstrained optimization ends when the gradient vanishes. Constrained problems usually end somewhere the gradient does not vanish: on the boundary, where the objective still pulls outward and only the wall holds the point in place. Declaring "nonzero gradient, so keep going" at such a point walks straight through the wall.

Lagrange multipliers solve the equality case with tangency: parallel gradients, one multiplier per constraint. Real constraints are usually inequalities: budgets that may go unspent, weights that must stay nonnegative, margins with slack. Forcing every inequality to bind invents optima that are not there, and ignoring them walks through walls. The Karush Kuhn Tucker conditions add the missing switch: every inequality gets a multiplier, and complementary slackness turns the idle constraints off.

This page is the inequality upgrade of the Lagrange picture: the four-condition test plus the support-vector payoff. The equality-only machinery lives in Lagrange multipliers. The pricing view with primal dual gaps lives in Lagrangian duality. The full duality story with the SVM dual and the kernel trick lives in constrained optimisation and duality. The certificate-checker view with its own fixture lives in optimality conditions. Convexity background lives in convex optimization, and the linear-constraint special case in linear programming.

The one idea you need first

A constraint $g(x) \le 0$ is active at a candidate $x^{\star}$ when $g(x^{\star}) = 0$ (the point sits on the wall) and inactive when $g(x^{\star}) < 0$ (strictly inside). Only active walls push, and each push is priced by a multiplier $\lambda \ge 0$. Inactive walls push nothing and price zero. Combined with the Lagrange tangency idea, gradients parallel at the optimum, that is the whole page in one paragraph.

Think of It Like This

How It Actually Works

For minimizing $f_0(x)$ subject to $f_i(x) \le 0$ and $h_j(x) = 0$, with all functions differentiable, the KKT conditions on $(x^{\star}, \lambda^{\star}, \nu^{\star})$ are four checks. In plain words: $f_0$ is the objective, each $f_i$ is an inequality wall, each $h_j$ is an equality wall, each $\lambda_i$ prices one inequality wall, each $\nu_j$ prices one equality wall.

1. Stationarity — $\nabla f_0 + \sum_i \lambda_i \nabla f_i + \sum_j \nu_j \nabla h_j = 0$. The objective pull plus all wall pushes balance to zero.
2. Primal feasibility — $f_i(x^{\star}) \le 0$ and $h_j(x^{\star}) = 0$. The point obeys every wall.
3. Dual feasibility — $\lambda_i \ge 0$ for every inequality. Walls push back only, never pull.
4. Complementary slackness — $\lambda_i f_i(x^{\star}) = 0$ for every $i$. For each wall, either the price is zero or the wall is tight.

The fourth condition does the work. It says an idle constraint has no influence, so its price is zero, and a binding constraint carries a positive price. In an SVM the margin constraints of comfortably classified examples are inactive, so their multipliers are zero and those examples drop out of the solution entirely. Only the examples on the margin keep nonzero multipliers, and those are exactly the support vectors. Sparsity was forced by the mathematics, not chosen by the designer.

Worked example

Minimize $(x - 2)^2$ subject to $x \le 1$, written $g(x) = x - 1 \le 0$. The Lagrangian is $L = (x - 2)^2 + \lambda(x - 1)$, and stationarity reads $2(x - 2) + \lambda = 0$.

Guess the wall is active, so $x^{\star} = 1$. Then $2(1 - 2) + \lambda = 0$ gives $\lambda^{\star} = 2$, which satisfies $\lambda \ge 0$. Primal feasibility holds with equality ($1 - 1 = 0$), and slackness holds as $2 \times 0 = 0$. The certified constrained optimum has value $(1 - 2)^2 = 1$ with wall price 2. The diagram above draws exactly this: the pull of 2 against the price of 2.

The inactive guess correctly fails: $\lambda = 0$ would give $x = 2$, which violates $x \le 1$ and is rejected. And the multiplier prices the wall: loosen it to $x \le 1.1$ and the new optimum is $x = 1.1$ with value $(1.1 - 2)^2 = 0.81$, a drop of $0.19$ for $0.1$ of slack, about $\lambda \times 0.1$. Note the sign under this convention: for minimization with $\le$ walls, $df^{\star}/db = -\lambda$ where $b$ is the wall position, so loosening cuts the optimum. The equality page states the maximization mirror image.

Code

The point is the check: four numbers that certify the point, plus the shadow-price confirmation.

1def objective(x: float) -> float:2    return (x - 2.0) ** 23
4
5x, lam = 1.0, 2.06stat = 2 * (x - 2.0) + lam  # pull -2 against wall price +27print(round(stat, 6))  # -> 0.08print(x <= 1, lam >= 0, round(lam * (x - 1), 6))  # -> True True 0.09print(round(objective(1.0), 2), round(objective(1.1), 2))  # -> 1.0 0.81

Stationarity residual zero, feasibility, sign, and slackness all passing, and relaxing the wall to $1.1$ drops the value from $1.0$ to $0.81$, about $\lambda \times 0.1$ as priced.

Watch Out For

The Quick Version

• KKT certifies inequality-constrained optima with four checks: stationarity, primal feasibility, dual feasibility, complementary slackness.
• Complementary slackness is the switch: each wall either binds with a positive price or sits idle with price zero.
• Minimizing $(x - 2)^2$ left of $x = 1$ certifies $x^{\star} = 1$ with $\lambda^{\star} = 2$ and value $1$.
• Loosening the wall to $1.1$ drops the optimum to $0.81$, about $\lambda \times 0.1$, with sign $df^{\star}/db = -\lambda$.
• SVM support vectors are exactly the active set: margin constraints with positive multipliers.
• KKT is necessary in general and sufficient only under convexity plus a constraint qualification.
• Pair $\lambda \ge 0$ with minimization and $\le$ walls; test any implementation on the fixture above.

What to Read Next

• Lagrange Multipliers
• Convex Optimization
• Constrained Optimisation and Duality