Karush–Kuhn–Tucker Conditions

Karush-Kuhn-Tucker conditions are first-order optimality conditions for constrained optimization problems with equality and inequality constraints.

Problem Form

For a minimization problem:

$$\underset{x}{\min }f(x)$$

subject to:

$$g_i(x)\le 0,h_j(x)=0$$

KKT describes when a candidate solution can be optimal using the objective, constraints, and Lagrange multipliers.

Constrained optimization appears throughout Machine Learning, especially when model parameters or probabilities must satisfy equality, inequality, or normalization constraints.

Conditions

The main KKT conditions are:

• Primal feasibility: the solution satisfies the original constraints.
• Dual feasibility: inequality multipliers are nonnegative.
• Complementary slackness: an inactive constraint has zero multiplier, and an active constraint may have positive multiplier.
• Stationarity: the gradient of the Lagrangian is zero at the optimum.

Intuition

At an unconstrained optimum, the objective gradient is zero. With constraints, the optimum can occur at a boundary. KKT says the objective gradient must be balanced by a weighted combination of active constraint gradients.

Slater’s Condition

Slater’s condition is a regularity condition for convex optimization. If a convex problem has a strictly feasible point for its inequality constraints, then strong duality holds and KKT conditions are sufficient for optimality under standard assumptions.

An affine function has the form $f(x)=Ax+b$. It is linear plus an offset, so its graph does not need to pass through the origin.

One-line Interview Answer

KKT conditions generalize the zero-gradient rule to constrained optimization by combining feasibility, stationarity, dual feasibility, and complementary slackness.