KKT Conditions

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.

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.

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.

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.

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.