KKT conditions

The Karush-Kuhn-Tucker conditions generalise the first-order optimality conditions of unconstrained problems to the constrained case. They are necessary at any optimum of a smooth problem with regular constraints, and they are sufficient under convexity. KKT is the test every analytic solution to a constrained problem must pass.

The four KKT conditions

For the canonical problem min f(x) s.t. g_i(x) ≤ 0, h_j(x) = 0, the KKT conditions at a local optimum x* with multipliers (λ*, ν*) are:

1. Stationarity: ∇f(x*) + Σ λᵢ* ∇g_i(x*) + Σ νⱼ* ∇h_j(x*) = 0.
2. Primal feasibility: g_i(x*) ≤ 0, h_j(x*) = 0.
3. Dual feasibility: λᵢ* ≥ 0.
4. Complementary slackness: λᵢ* g_i(x*) = 0 for all i.

Reading complementary slackness

Either the constraint is active (g_i(x*) = 0, λᵢ ≥ 0) or it is slack (g_i(x*) < 0, λᵢ = 0). Constraints that don't bind have zero shadow price. Constraints that bind have positive shadow price. This split is the single most useful interpretation of KKT in any real-world finance problem.

When are KKT necessary?

KKT are necessary at any local optimum where a constraint qualification holds — typically the linear-independence constraint qualification (LICQ): the gradients of active constraints are linearly independent. For convex problems satisfying Slater's condition, KKT are necessary and sufficient.

Long-only minimum-variance — full KKT analysis

min (1/2) wᵀΣw s.t. 1ᵀw = 1, w ≥ 0. KKT:

1. Stationarity: Σw* - ν 1 - λ* = 0, where λ ≥ 0 is the multiplier on w ≥ 0.
2. Primal: 1ᵀw* = 1, w* ≥ 0.
3. Dual: λ* ≥ 0.
4. Slackness: λᵢ* wᵢ* = 0 — for each asset, either weight is zero (constraint binds) or multiplier is zero (constraint slack).

The active set A = {i : wᵢ* = 0} — the names with binding non-negativity — is a key combinatorial object. Active-set methods, branch-and-bound, and most QP solvers iterate by guessing A and checking KKT.

Markowitz with budget and target return

min (1/2) wᵀΣw s.t. 1ᵀw = 1, μᵀw = R_target. Two equality constraints, two multipliers ν₁, ν₂. Stationarity: Σw* = ν₁ 1 + ν₂ μ, so w* = Σ⁻¹(ν₁ 1 + ν₂ μ). Plug into the two constraints to solve for (ν₁, ν₂). This is the textbook closed-form for the efficient frontier — derived from KKT in three lines.

Duality recovers the same answer

For convex problems, the KKT conditions characterise the saddle point of the Lagrangian. Solving the dual problem and then recovering the primal via stationarity gives the same answer as direct KKT. For some problems the dual is cleaner — SVM is the classical example.

Numerical solvers and KKT

Active-set, interior-point, and SQP (sequential quadratic programming) solvers all converge to KKT points. They differ in how they update the active set and the multipliers. Modern interior-point methods are dominant for QPs and conic programs; SQP for general non-linear problems.

KKT failure modes

• No constraint qualification: KKT may fail to hold even at a true optimum. Pathological constraint sets (e.g., a single point feasibility) cause this.
• Non-convex problem: KKT identifies local optima, not global ones. The same point can be a KKT point and not a global minimum.
• Numerical: solvers report 'KKT residuals' — if they're large, the solver hasn't converged.