KKT Conditions

Every optimization course begins with the same beautiful idea: at a smooth minimum the gradient is zero. Tilt the landscape and the ball rolls downhill; at the bottom it sits still. Gradient equals zero is the whole story — as long as nothing is in the way.

Add a wall. Now the ball might be pressed against a boundary and never reach the unconstrained minimum at all. The gradient at that point is not zero; it points into the wall. Yet the ball is still stuck. Something else must characterize optimality.

That something is the Karush-Kuhn-Tucker (KKT) conditions — four algebraic rules, published independently by William Karush in his 1939 master's thesis and by Harold Kuhn and Albert Tucker in 1951, that replace "gradient equals zero" with a complete description of a constrained optimum. They work for inequality constraints, equality constraints, or both, and they reduce to the familiar gradient condition the instant you remove all constraints.

KKT conditions are necessary for any local minimum of a smooth problem satisfying mild regularity (a constraint qualification). For convex problems they are also sufficient: a point satisfying all four conditions is guaranteed to be a global minimum, no search required. This sufficiency is why convex optimization — the engine behind support vector machines, portfolio theory, control systems and much of modern machine learning — is tractable at all.

The demo below shows a simple quadratic program: minimize $x^{2}$ + $y^{2}$ subject to x + y ≥ 1 and x ≥ 0, y ≥ 0. Drag the point on the 2-D plane and watch the four KKT conditions update in real time.

<div class="layout">
  <div class="canvas-wrap">
    <canvas id="c" width="260" height="260"></canvas>
    <div class="drag-hint">{{drag_hint}}</div>
  </div>
  <div class="panel">
    <div class="problem">
      <b>{{problem_label}}</b> minimize x² + y²<br>
      {{subject_to}}: x + y ≥ 1, x ≥ 0, y ≥ 0
    </div>
    <div class="coords" id="coords">(x, y) = (0.50, 0.50)</div>
    <div class="obj" id="obj">f = 0.5000</div>
    <div class="conditions" id="conditions"></div>
    <div class="legend">
      <span class="dot green"></span>{{legend_satisfied}} &nbsp;
      <span class="dot red"></span>{{legend_violated}}
    </div>
    <button id="snap" type="button">{{snap_btn}}</button>
  </div>
</div>

* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; font-size: 14px; color: #1a1a2e; background: #f8f9fb; }
.layout { display: flex; flex-wrap: wrap; gap: 14px; padding: 10px; align-items: flex-start; }
.canvas-wrap { position: relative; flex-shrink: 0; }
canvas { display: block; border-radius: 10px; border: 1px solid #c8d0de; background: #fff; cursor: crosshair; touch-action: none; }
.drag-hint { text-align: center; font-size: 11px; color: #778; margin-top: 4px; }
.panel { flex: 1; min-width: 200px; display: flex; flex-direction: column; gap: 10px; }
.problem { background: #eef2ff; border: 1px solid #c7d0f0; border-radius: 8px; padding: 8px 10px; line-height: 1.6; font-size: 13px; }
.coords { font-size: 13px; color: #444; }
.obj { font-size: 15px; font-weight: 700; color: #1d3557; }
.conditions { display: flex; flex-direction: column; gap: 6px; }
.cond { display: flex; align-items: flex-start; gap: 8px; background: #fff; border: 1px solid #d8dde8; border-radius: 8px; padding: 7px 10px; line-height: 1.5; }
.cond .icon { font-size: 16px; flex-shrink: 0; margin-top: 1px; }
.cond.ok { border-color: #4caf50; background: #f0faf0; }
.cond.fail { border-color: #e63946; background: #fff2f2; }
.cond-name { font-weight: 700; font-size: 12px; }
.cond-detail { font-size: 12px; color: #444; margin-top: 1px; }
.legend { font-size: 12px; color: #555; display: flex; align-items: center; gap: 4px; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.dot.green { background: #4caf50; }
.dot.red { background: #e63946; }
button { font: 600 13px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; width: 100%; }
button:hover { background: #16304d; }

// Code not found

At the constrained minimum (0.5, 0.5) all four conditions are green simultaneously. Move away and at least one turns red. Notice that complementary slackness ($\mu_i \cdot g_i = 0$) lights red the moment you lift a constraint that has a positive multiplier — the boundary is "active" there, and lifting it costs optimality.

Suppose we want to minimize f(x) subject to inequality constraints $g_{i}(x)$ ≤ 0 and equality constraints $h_{j}(x)$ = 0. The KKT conditions at a candidate point x* are four simultaneous requirements:

1. Stationarity — the gradient of the Lagrangian vanishes:

   $$\nabla f(x^*) + \sum_i \mu_i \nabla g_i(x^*) + \sum_j \lambda_j \nabla h_j(x^*) = 0$$

   This says the objective's pull is exactly balanced by the constraints' push.

2. Primal feasibility — x* actually satisfies all constraints: $g_{i}(x*)$ ≤ 0 for all i, $h_{j}(x*)$ = 0 for all j.

3. Dual feasibility — multipliers for inequality constraints are non-negative:

   $$\mu_i \ge 0 \quad \text{for all } i$$

   A negative multiplier would mean the constraint is pushing the wrong way.

4. Complementary slackness — each inequality constraint is either tight or its multiplier is zero:

   $$\mu_i \cdot g_i(x^*) = 0 \quad \text{for all } i$$

   If a constraint is not active (slack > 0) it cannot contribute to the optimality condition, so its multiplier must be zero.

Necessary vs. sufficient:

• Under a constraint qualification (e.g., the constraints are linear, or the active gradients are linearly independent — LICQ), KKT conditions are necessary: every local minimum satisfies them.
• For convex f and convex feasible sets, KKT conditions are sufficient: any point that satisfies them is a global minimum.

The proof of necessity uses the Farkas lemma — a theorem of alternatives that says if no feasible descent direction exists, then the KKT system has a solution. Sufficiency for convex problems follows from the fact that a stationary point of a convex function is already a global minimizer.

These conditions are the foundation of algorithms like the simplex method (for linear programming), interior-point methods, and sequential quadratic programming (SQP). They are also the dual certificate used in Lagrangian duality, letting us bound optimal values without solving the primal problem directly.

KKT conditions are not a mathematical curiosity — they are the working foundation of almost every practical optimizer:

• Support vector machines: the SVM training problem is a constrained quadratic program. Its KKT conditions produce the dual formulation and identify the support vectors — the training points where the margin constraint is active ($\mu_i > 0$).
• Portfolio optimization: Markowitz mean-variance portfolios maximize return subject to a risk budget. KKT conditions characterize the efficient frontier and justify why diversification works mathematically.
• Optimal control: Pontryagin's maximum principle is a continuous-time generalization of KKT. It says the control that minimizes a trajectory cost must satisfy a Hamiltonian stationarity condition — the same complementary slackness structure in function space.
• Economic equilibria: competitive market equilibria satisfy KKT conditions for each agent's utility-maximization problem. Shadow prices (dual variables) are exactly the KKT multipliers — they measure how much a constraint relaxation is worth.
• Interior-point methods: modern solvers for large linear and convex programs walk toward the KKT point along a central path, reaching optimality when all four conditions are satisfied to within a tolerance.

Wherever a practical problem asks "optimize subject to constraints," KKT conditions are the certificate that the answer is correct.

The story of KKT conditions is a story about what it means to be stuck against a wall in the best possible way. William Karush wrote it down in 1939 for his master's thesis, Kuhn and Tucker rediscovered and published it in 1951, and today those four conditions — stationarity, primal feasibility, dual feasibility, complementary slackness — underpin virtually every constrained optimizer ever built.

For general problems they are a necessary fingerprint: if a point is optimal, it must pass all four tests. For convex problems they are a complete certificate: pass all four and you are at the global minimum, guaranteed. That second fact is what makes machine learning, financial engineering, and large-scale control tractable — the solver doesn't need to search; it just needs to verify.

The next time an algorithm converges and declares victory, somewhere under the hood it has checked the KKT conditions and found them satisfied. The math that Karush wrote in a master's thesis is still quietly running the world.