# KKT Conditions

The first-order necessary conditions for optimality with inequality constraints — stationarity, feasibility, dual feasibility and complementary slackness.

**Rests on:** Duality Primal and Dual, Lagrange Multipliers

**Leads to:** Convex Optimization

*Mathematical Foundations · Optimization*


## Why learn this

You often need to find the absolute best answer to a problem that comes with hard limits—like minimizing cost without exceeding a specific budget, or maximizing accuracy while keeping a model small enough to run on a phone. The KKT conditions are the set of rules that tell you whether you have truly found that best answer or if you can still improve by moving to a different spot. Without understanding these conditions, you cannot distinguish between a solution that is merely 'allowed' by the limits and one that is mathematically guaranteed to be the best possible option within those limits.


## The intuition

Imagine you are standing on a hill in the dark, trying to find the lowest possible point. You have two scenarios.

Scenario A: There is no fence. You simply walk downhill until the ground flattens out. The place where the slope becomes zero is your minimum. This is unconstrained optimisation.

Scenario B: There is a fence around part of the landscape, and you must stay inside it. You walk downhill just like before. Two things can happen:
1. You reach the flat bottom before you hit the fence. In this case, the lowest point is in the middle of the open space. The fence does not matter. You are at the true minimum, and the fence exerts no force on you.
2. You hit the fence before finding a flat spot. You slide along the fence until the ground flattens out *along the direction of the fence*. At this specific point, you are stuck: if you try to step off the fence into the forbidden zone, the ground rises (because of the hill and the fence). If you move along the fence in either direction, the ground goes up. 

At that stopping point on the fence, two things are balanced:
- The 'pull' of the hill pushing you downhill.
- The 'push' of the fence holding you back.

The KKT conditions check this balance. They verify that you are either at the flat bottom (where the pull is zero) or you are pressed against a constraint where the push of the constraint exactly cancels the pull of the hill.

A critical detail here is what happens when you are *not* touching the fence. If you are safely inside the allowed area, far from any boundary, the fence has no effect. In mathematical terms, we assign it a 'multiplier' (a weight) of zero. This means: "This constraint exists, but it is not active right now." When you *are* touching the fence, the multiplier is positive, representing how hard the fence is pushing.

The term 'complementary slackness' describes this exact behavior: for every constraint, either the constraint is tight (you are touching the wall, so there is 'push' or a non-zero multiplier) OR the constraint is loose (you are not touching it, so the multiplier is zero). You can never have both a positive push and a gap between you and the wall. One must be zero; they complement each other to sum to zero in terms of their interaction.


## An analogy

Think of the KKT conditions as a rulebook for a ball rolling down a bumpy landscape inside a cage.

The landscape has valleys (low points) and hills (high points). The cage bars are constraints.

If the lowest valley is clearly inside the cage, the ball rolls there. It never touches a bar. The 'force' from the bars is zero. The condition is satisfied because the slope of the land is zero at the bottom.

If the lowest valley is outside the cage, the ball rolls to the lowest point *on* the boundary of the cage it can reach. At this spot, the ball is pressed against a bar. The bar pushes back with a force equal to how much the ball wants to go through it. 

The 'complementary slackness' part is like saying: 'If there is space between the ball and the bar, the bar's force must be zero.' If there is a gap (slack), the force is zero. If the force is positive (the bar is pushing), there can be no gap; they are touching. This rule ensures we don't invent fake forces where no contact exists.

This analogy breaks down because real-world problems can have multiple balls and complex shapes, but it captures the core logic: balance of forces or absence of contact.


## Definition

The Karush-Kuhn-Tucker (KKT) conditions are a set of rules used to verify that you have found the optimal solution for a problem with limits that allow for flexibility (inequality constraints). They require that the slope of your goal is balanced by the strength of any active limits, and specifically include 'complementary slackness': this rule states that for any limit, either the limit is exactly met (binding), or its associated multiplier is zero; they cannot both be non-zero at the same time.


## How it connects

You have notes on Lagrange multipliers, which handle constraints that must be exactly equal to a value (like 'x = 5'). The KKT conditions are the extension of that idea to inequality constraints (like 'x ≤ 5'). You also have notes on duality: the multipliers in KKT are the dual variables, which tell you how much the best answer would improve if you relaxed a constraint slightly.


## The mathematics

The KKT conditions are a set of rules used to check whether a point is the best possible solution (the minimum) for a problem where you want to minimize a value, subject to limits on what values are allowed. These limits come in two types: inequalities (like 'x must be less than or equal to 5') and equalities (like 'x must equal 2').

To use the KKT conditions, we first write down the problem in a standard form. We want to minimize a function f(x). We have inequality constraints written as g_i(x) ≤ 0 for i = 1 to m. This means each constraint function g_i must be zero or negative at the solution. We also have equality constraints written as h_j(x) = 0 for j = 1 to p.

We introduce special numbers called Lagrange multipliers. For each inequality constraint g_i, we assign a multiplier λ_i (read 'lambda sub i'). For each equality constraint h_j, we assign a multiplier μ_j (read 'mu sub j').

The KKT conditions consist of four parts that must all be true at the optimal point x:

1. Stationarity: This condition ensures that there is no direction you can move to decrease the value of f(x) while staying within the allowed region. Mathematically, it says that the gradient (the vector of slopes) of the objective function plus the weighted sum of the gradients of the constraints equals zero. The formula is:
   ∇f(x) + Σ_i λ_i ∇g_i(x) + Σ_j μ_j ∇h_j(x) = 0
   Here, ∇f(x) is the gradient of f at x. ∇g_i(x) is the gradient of the i-th constraint function. The symbol Σ means 'sum over all'. So we add up λ_1 times the gradient of g_1, plus λ_2 times the gradient of g_2, and so on for all inequalities, and similarly for the equalities with μ.

2. Primal Feasibility: The point x must actually satisfy all the original constraints. This means:
   g_i(x) ≤ 0 for every i from 1 to m.
   h_j(x) = 0 for every j from 1 to p.
   You cannot pick a point that breaks the rules.

3. Dual Feasibility: The multipliers for the inequality constraints must be non-negative. This means:
   λ_i ≥ 0 for every i from 1 to m.
   The multipliers for equality constraints (μ_j) can be any real number; they have no sign restriction.

4. Complementary Slackness: This condition links the multiplier to whether the constraint is 'active' (tight) or 'inactive' (loose). It states that for each inequality constraint i:
   λ_i * g_i(x) = 0.
   Because we know g_i(x) ≤ 0 and λ_i ≥ 0, their product can only be zero if at least one of them is zero. This leads to two cases:
   - If the constraint is inactive (g_i(x) < 0), then λ_i must be 0. The constraint is not touching the solution, so it doesn't push on it.
   - If the constraint is active (g_i(x) = 0), then λ_i can be any non-negative number. The constraint is holding the solution in place.

If a point satisfies all four conditions, and if the problem has certain convexity properties (which we assume here for simplicity), then that point is the global minimum.


## A worked example

Let us work through a specific example to see how the KKT conditions identify the optimal point.

Problem: Minimize f(x) = (x - 3)^2 subject to the constraint x ≥ 1.

First, we must write the constraint in the standard form g(x) ≤ 0. The inequality x ≥ 1 is equivalent to 1 - x ≤ 0. So we define:
   g(x) = 1 - x.
Our problem is now: Minimize f(x) subject to g(x) ≤ 0.

We introduce a Lagrange multiplier λ for the constraint g(x).

The KKT conditions are:
1. Stationarity: f'(x) + λ * g'(x) = 0
2. Primal Feasibility: g(x) ≤ 0
3. Dual Feasibility: λ ≥ 0
4. Complementary Slackness: λ * g(x) = 0

Let's find the derivatives:
   f(x) = (x - 3)^2, so f'(x) = 2(x - 3).
   g(x) = 1 - x, so g'(x) = -1.

Now we apply the conditions.

Case A: Assume the constraint is inactive. This means g(x) < 0, which implies x > 1.
   From Complementary Slackness, if g(x) < 0, then λ must be 0.
   Substitute λ = 0 into the Stationarity condition:
   f'(x) + 0 * (-1) = 0
   f'(x) = 0
   2(x - 3) = 0
   x = 3.
   Now check Primal Feasibility for this candidate point x = 3:
   g(3) = 1 - 3 = -2.
   Is -2 ≤ 0? Yes. So the constraint is indeed inactive (loose).
   Check Dual Feasibility: λ = 0, and 0 ≥ 0. This holds.
   So x = 3 is a valid KKT point.

Case B: Assume the constraint is active. This means g(x) = 0, which implies x = 1.
   From Complementary Slackness, if g(x) = 0, λ can be any non-negative number. We need to find λ using Stationarity.
   Substitute x = 1 into the Stationarity condition:
   f'(1) + λ * g'(1) = 0
   Calculate f'(1): 2(1 - 3) = 2(-2) = -4.
   Calculate g'(1): -1.
   So: -4 + λ * (-1) = 0
   -4 - λ = 0
   λ = -4.
   Now check Dual Feasibility: We require λ ≥ 0. But we found λ = -4, which is negative.
   Therefore, this case yields no valid solution because it violates the sign rule for the multiplier.

Conclusion:
The only point that satisfies all KKT conditions is x = 3.
At x = 3, the value of the function is f(3) = (3 - 3)^2 = 0.
Since the unconstrained minimum of (x-3)^2 is at x=3, and x=3 satisfies the constraint x ≥ 1, the constraint does not limit us. The multiplier λ is 0, confirming that the constraint is not 'pushing' on the solution. If we had started with a constraint like x ≤ 2, the active case would have yielded a positive λ, indicating the constraint was binding.


## From scratch, in Python

```python
def check_kkt(f_deriv, g_list, g_deriv_list, x, active_threshold=1e-6):
    """
    Check KKT conditions for a single variable, given derivative functions.
    f_deriv: derivative of objective (callable)
    g_list: list of functions that return the constraint value (≤0 means satisfied)
    g_deriv_list: list of derivatives of the constraint functions
    x: candidate point
    Returns a dict with booleans for each condition.
    """
    # Stationarity: find lambda for each active constraint
    grad_f = f_deriv(x)
    lambdas = []
    for g, g_deriv in zip(g_list, g_deriv_list):
        val = g(x)
        if val > 0:
            return {'primal_feasible': False, 'stationarity': None, 'dual_feasible': None, 'complementary_slackness': None}
        if abs(val) < active_threshold:
            # Active constraint: solve f'(x) + lambda*g'(x) = 0
            gd = g_deriv(x)
            if abs(gd) < 1e-12:
                lambda_i = 0  # degenerate, assume
            else:
                lambda_i = -grad_f / gd
            lambdas.append(lambda_i)
        else:
            lambdas.append(0.0)
    # Stationarity: sum(lambda_i * g_deriv) + grad_f = 0 (we already set lambdas to satisfy this exactly)
    stationarity = True
    # Dual feasibility: all lambdas >= 0
    dual_feasible = all(l >= 0 for l in lambdas)
    # Complementary slackness: lambda_i * g_i(x) = 0 already enforced by construction, but check
    comp_slack = all(abs(l * g(x)) < 1e-6 for l, g in zip(lambdas, g_list))
    primal_feasible = all(g(x) <= 1e-12 for g in g_list)
    return {'primal_feasible': primal_feasible, 'stationarity': stationarity, 'dual_feasible': dual_feasible, 'complementary_slackness': comp_slack}

# Example: minimise (x-3)^2 subject to x >= 1 (i.e., 1 - x <= 0)
def f_deriv(x):
    return 2*(x - 3)
def g1(x):
    return 1 - x
def g1_deriv(x):
    return -1

for x_test in [1, 3]:
    result = check_kkt(f_deriv, [g1], [g1_deriv], x_test)
    print(f"x = {x_test}: {result}")
```


## The same thing, with a framework

```python
import numpy as np
from scipy.optimize import minimize

# Use SciPy's constrained optimizer, which internally uses KKT-like conditions
def objective(x):
    return (x - 3)**2

def constraint(x):
    return x - 1  # must be >= 0, so we use 'ineq' type

con = {'type': 'ineq', 'fun': constraint}
res = minimize(objective, x0=0, method='SLSQP', constraints=con)
print(res.x, res.fun, res.success)

# The solver checks KKT conditions to decide when to stop.
```


## What the code does

This code defines a function that checks whether a candidate point satisfies the KKT conditions for a one-variable problem. The function takes the derivative of the objective, a list of constraint functions and their derivatives, and the candidate x. It computes the gradient of the objective at x, and for each constraint it checks if the constraint is violated (then it returns not feasible). For constraints that are active (value close to zero), it solves for the multiplier lambda using the stationarity equation. It then checks that all lambdas are non-negative (dual feasibility) and that the product of lambda and the constraint value is zero (complementary slackness). The example uses f(x) = (x-3)^2 with constraint 1 - x ≤ 0. At x=1, the constraint is active, lambda comes out as -4, so dual feasibility fails. At x=3, the constraint is inactive, lambda is zero, and all conditions hold.


## Common misconceptions

**KKT conditions are always sufficient** — If a point satisfies the KKT conditions, then it must be the global optimum.

The KKT conditions are necessary for optimality (under certain regularity conditions), but not sufficient in general. For nonconvex problems, a point that satisfies KKT could be a local minimum, a local maximum, or a saddle point. In fact: Only for convex problems (where the objective is convex and the feasible set is convex) do the KKT conditions become sufficient for global optimality. In deep learning, the loss landscape is nonconvex, so KKT points are just candidates, and you need additional checks.

**Multipliers must be positive** — The Lagrange multipliers for constraints must be positive numbers because they are like costs.

The sign depends on the formulation. For a minimisation problem with constraints written as g(x) ≤ 0, the multipliers must be non-negative. But if you write the constraint as g(x) ≥ 0, the multiplier changes sign. For equality constraints, multipliers can be any real number. In fact: The sign convention is a matter of formulation. The important thing is that the multiplier has the correct sign so that the constraint force points inward, which is what 'dual feasibility' checks.

**Complementary slackness means constraints are either / or** — Complementary slackness says that a constraint is either active or inactive, and that is always true.

Complementary slackness specifically says that the product λ_i * g_i(x) = 0. This means if g_i(x) is not zero (constraint inactive), then λ_i must be zero. But the converse is not true: λ_i can be zero even when the constraint is active (degenerate case). In fact: Complementary slackness is a mathematical product condition, not a simple binary statement. It prevents a constraint from mattering when it is not active.

**KKT conditions are an algorithm** — You can run the KKT conditions like gradient descent to find the optimum.

The KKT conditions are a set of equations that define optimality, not an iterative update rule. They are used to check a candidate solution or to derive algorithms, but they do not tell you how to search. In fact: Algorithms like SQP or interior-point methods solve a sequence of problems that gradually satisfy the KKT conditions; the conditions are the destination, not the path.

**Constraints must be differentiable** — The KKT conditions apply to any constrained optimisation problem.

The KKT conditions require that the objective and constraint functions are differentiable and that a constraint qualification (like linear independence of active constraint gradients) holds. If the functions have kinks or the gradients are not linearly independent, the conditions may not apply. In fact: There are generalisations (like FJ conditions) that handle some non-smooth cases, but the classical KKT conditions assume smoothness and a constraint qualification.


## In short

The KKT conditions are the rules for checking whether a point is the best solution to a problem with inequality constraints. The four conditions are: stationarity (the slope is balanced by the constraints), primal feasibility (the point obeys all constraints), dual feasibility (multipliers have the correct sign), and complementary slackness (constraints that are not active have zero multipliers). They are necessary for optimality in general and sufficient when the problem is convex. They underpin most constrained optimisation solvers and appear in SVM training, regularisation, RL with safety constraints, and constrained hyperparameter tuning.


## Where this is used

The KKT conditions are not an algorithm you run directly, but they are the stopping criteria and the theoretical grounding for almost every constrained optimisation solver. In machine learning, they appear in several concrete places. 

**Hyperparameter tuning with constraints:** When you tune a model, you often have a budget — say, 'the model must be under 5 MB for a mobile app.' You could frame this as a constrained optimisation: minimise validation loss subject to model size ≤ 5 MB. The KKT conditions tell you whether your current model is at the boundary of the constraint and how much you would gain by relaxing it. In practice, you might use Bayesian optimisation with a constraint, and the solver internally checks KKT-like conditions to decide when to stop.

**Support vector machines (SVMs):** SVM training is a constrained quadratic program: maximise the margin subject to the constraint that all training points are correctly classified (or within a slack). The KKT conditions are used in the SMO algorithm to decide which points to optimise; the algorithm checks complementary slackness to identify support vectors and to stop when all conditions are satisfied to within a tolerance.

**Regularisation as constrained optimisation:** L2 regularisation is often written as adding a penalty to the loss, but it is equivalent to solving a constrained problem: minimise loss subject to ||weights||² ≤ C. The KKT conditions show that the optimal weights sit on the boundary of the ball when the constraint is active, and the regularisation strength is directly related to the multiplier. This gives an interpretation of why larger C (weaker penalty) allows larger weights.

**Reinforcement learning with constraints:** In real-world RL, you often have safety constraints — 'do not let the robot tip over' — and you want to maximise reward subject to the constraint. Constrained policy optimisation uses KKT conditions to derive update rules that keep the policy inside the feasible set.

**Large language models and small models:** During fine-tuning, you might want to constrain the model to stay close to the original weights to avoid catastrophic forgetting (a trust region). Techniques like proximal policy optimisation (PPO) for RLHF use a KL-divergence constraint between the new and old policy; the KKT multiplier on that constraint is exactly the adaptive penalty coefficient that controls how aggressively the model can move. In small on-device models, you often have constraints on memory and latency; you may formulate the architecture search as a constrained problem and use KKT to check whether you are at the limit of the memory budget.

**Retrieval-augmented generation (RAG):** In RAG, you retrieve documents and then feed them to the LLM. There is no direct optimisation with KKT, but the concept appears in the retrieval ranking: if you frame the retrieval as optimising a relevance score subject to a latency constraint, the KKT conditions can characterise when a faster but less accurate retriever is optimal. More commonly, you might use constrained optimisation to prune the embedding dimension while maintaining a minimum retrieval quality.

**Agentic systems:** Agents plan a sequence of tool calls. If the agent has a budget of total steps or cost, you can formulate the plan as an optimisation with constraints; KKT conditions would describe when the budget is binding and how much performance you lose or gain by changing it. In practice, agents use heuristics, but the underlying theory informs the design of planners that reason about trade-offs.

**Everyday applied ML:** In any industry problem with a hard constraint (budget, safety limit, legal threshold), a data scientist might use a constrained optimisation library (e.g., SciPy's SLSQP, or CVXPY for convex problems). The solver returns a solution that satisfies the KKT conditions to within a tolerance, and the 'dual variables' it reports can tell you how much the objective would improve if you relaxed the constraint. For example, a fraud detection system might have a constraint that the false positive rate must be under 1%; the KKT multiplier tells you how much more fraud you could catch if you allowed 1.1%.

**In development:** A developer who needs to solve a constrained optimisation typically writes code like the NumPy/SciPy example above — declaring the objective and constraints and calling `minimize`. The solver then internally checks the KKT conditions to decide convergence. If done badly — for example, ignoring dual feasibility — the solver might stop at a non-optimal point, giving an answer that violates the constraint or misses a better solution.


---

Read this on the web: https://basavapurushottam.com/learn-ai/kkt-conditions
