Introduction

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.

Try It: Verify the Optimum

The demo below shows a simple quadratic program: minimize x2x^{2} + y2y^{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 the red point</div>
  </div>
  <div class="panel">
    <div class="problem">
      <b>Problem:</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>satisfied &nbsp;
      <span class="dot red"></span>violated
    </div>
    <button id="snap" type="button">Snap to optimum (0.5, 0.5)</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; }

// KKT demo: minimize f(x,y) = x^2 + y^2
// Constraints in standard form g_i(x) <= 0:
//   g1 = 1 - x - y <= 0   (i.e. x + y >= 1)
//   g2 = -x <= 0          (i.e. x >= 0)
//   g3 = -y <= 0          (i.e. y >= 0)
//
// KKT stationarity: grad_f + sum mu_i * grad_g_i = 0
//   grad_f = [2x, 2y]
//   grad_g1 = [-1,-1],  grad_g2 = [-1,0],  grad_g3 = [0,-1]
//   => 2x - mu1 - mu2 = 0  i.e.  mu1 + mu2 = 2x
//   => 2y - mu1 - mu3 = 0  i.e.  mu1 + mu3 = 2y
//
// Optimal point: x*=0.5, y*=0.5
//   Active: g1=0 (x+y=1 tight), Inactive: g2=-0.5<0, g3=-0.5<0
//   CS: mu2=0, mu3=0 => mu1=2*0.5=1 ✓, dual: mu1=1>=0 ✓

const canvas = document.getElementById('c');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const PAD = 30;
const SCALE = (W - 2*PAD) / 2.0; // maps [0,2] -> pixel width

let px = 0.5, py = 0.5;

function toCanvas(mx, my) {
  return [PAD + mx * SCALE, H - PAD - my * SCALE];
}
function toMath(cx, cy) {
  return [(cx - PAD) / SCALE, (H - PAD - cy) / SCALE];
}

// Active-set KKT multiplier computation.
// We enumerate all 2^3=8 active-set subsets, solve the stationarity system for each, and pick the best feasible solution.
function solveKKT(x, y) {
  const g = [1-x-y, -x, -y];
  // Gradients of g_i
  const dg = [[-1,-1], [-1,0], [0,-1]];
  const gf = [2*x, 2*y];
  const EPS = 1e-6;

  let best = null, bestScore = Infinity;

  for (let mask = 0; mask < 8; mask++) {
    const active = [0,1,2].filter(i => mask & (1<<i));
    const mu = [0, 0, 0];
    let statRes = 999;

    if (active.length === 0) {
      // Stationarity: gf = 0
      statRes = Math.sqrt(gf[0]*gf[0] + gf[1]*gf[1]);
    } else if (active.length === 1) {
      const i = active[0];
      // mu_i * dg[i] = -gf  (least-squares, 2 eqs, 1 unknown) (least-squares, 2 eqs, 1 unknown)
      const AtA = dg[i][0]*dg[i][0] + dg[i][1]*dg[i][1];
      const Atb = -gf[0]*dg[i][0] - gf[1]*dg[i][1];
      const m = Atb / AtA;
      if (m < -EPS) continue; // dual infeasible
      mu[i] = Math.max(0, m);
      const sx = gf[0] + mu[i]*dg[i][0];
      const sy = gf[1] + mu[i]*dg[i][1];
      statRes = Math.sqrt(sx*sx + sy*sy);
    } else if (active.length === 2) {
      const [i, j] = active;
      // [dg[i] | dg[j]] * [mi; mj] = -gf  (2x2 system)
      const a00 = dg[i][0], a01 = dg[j][0];
      const a10 = dg[i][1], a11 = dg[j][1];
      const det = a00*a11 - a01*a10;
      if (Math.abs(det) < 1e-12) continue;
      const b0 = -gf[0], b1 = -gf[1];
      const mi = (b0*a11 - b1*a01) / det;
      const mj = (a00*b1 - a10*b0) / det;
      if (mi < -EPS || mj < -EPS) continue;
      mu[i] = Math.max(0, mi); mu[j] = Math.max(0, mj);
      const sx = gf[0] + mu[i]*dg[i][0] + mu[j]*dg[j][0];
      const sy = gf[1] + mu[i]*dg[i][1] + mu[j]*dg[j][1];
      statRes = Math.sqrt(sx*sx + sy*sy);
    } else {
      // 3 active constraints, overdetermined; skip
      continue;
    }

    if (statRes > 0.02) continue;
    const pfOk = g.every(gi => gi <= 0.001);
    const dualOk = mu.every(m => m >= -EPS);
    const cs = mu.map((m, i) => m * g[i]);
    const csOk = cs.every(v => Math.abs(v) < 0.001);

    const score = statRes + (pfOk ? 0 : 10) + (dualOk ? 0 : 10) + (csOk ? 0 : 5);
    if (score < bestScore) {
      bestScore = score;
      best = { mu, statRes, pfOk, dualOk, csOk, g, cs };
    }
  }

  if (!best) {
    // Fallback: report raw failures
    const mu = [0,0,0];
    const cs = [0,0,0];
    return { mu, statRes: 999, pfOk: false, dualOk: false, csOk: false, g, cs };
  }
  return best;
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Feasible region: x+y>=1, x>=0, y>=0 (clipped to [0,2]x[0,2])
  ctx.save();
  ctx.beginPath();
  const pts = [[1,0],[2,0],[2,2],[0,2],[0,1]];
  pts.forEach(([a,b], idx) => {
    const [cx2, cy2] = toCanvas(a, b);
    idx === 0 ? ctx.moveTo(cx2, cy2) : ctx.lineTo(cx2, cy2);
  });
  ctx.closePath();
  ctx.fillStyle = 'rgba(100,160,240,0.13)';
  ctx.fill();
  ctx.strokeStyle = '#4a7fc1'; ctx.lineWidth = 1.5;
  ctx.stroke();
  ctx.restore();

  // Axes
  ctx.save();
  ctx.strokeStyle = '#ccc'; ctx.lineWidth = 1;
  const [o1x,o1y] = toCanvas(0,0), [e1x,e1y] = toCanvas(2,0);
  const [o2x,o2y] = toCanvas(0,0), [e2x,e2y] = toCanvas(0,2);
  ctx.beginPath(); ctx.moveTo(o1x,o1y); ctx.lineTo(e1x,e1y); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(o2x,o2y); ctx.lineTo(e2x,e2y); ctx.stroke();
  ctx.fillStyle = '#999'; ctx.font = '11px system-ui';
  ctx.fillText('x', e1x-4, e1y+14);
  ctx.fillText('y', e2x-16, e2y+5);
  for (let v = 0; v <= 2; v += 0.5) {
    const [tx,ty] = toCanvas(v,0); ctx.fillText(v.toFixed(1), tx-8, ty+12);
    const [ty2x,ty2y] = toCanvas(0,v); ctx.fillText(v.toFixed(1), ty2x-20, ty2y+4);
  }
  ctx.restore();

  // Objective contours f = r^2
  ctx.save();
  for (const r of [0.25,0.5,0.707,1.0,1.25,1.5]) {
    ctx.beginPath();
    ctx.arc(...toCanvas(0,0), r*SCALE, 0, 2*Math.PI);
    ctx.strokeStyle = 'rgba(180,80,80,0.2)'; ctx.lineWidth = 1;
    ctx.stroke();
  }
  ctx.restore();

  // Constraint boundary x+y=1
  ctx.save();
  ctx.setLineDash([5,4]);
  ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 1.5;
  ctx.beginPath(); ctx.moveTo(...toCanvas(0,1)); ctx.lineTo(...toCanvas(1,0));
  ctx.stroke(); ctx.setLineDash([]);
  ctx.restore();

  // Optimal point marker
  const [ox, oy] = toCanvas(0.5, 0.5);
  ctx.save();
  ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 1.5;
  ctx.beginPath(); ctx.arc(ox, oy, 5, 0, 2*Math.PI);
  ctx.fillStyle = 'rgba(29,53,87,0.15)'; ctx.fill(); ctx.stroke();
  ctx.fillStyle = '#1d3557'; ctx.font = 'bold 10px system-ui';
  ctx.fillText('x*', ox+7, oy-5);
  ctx.restore();

  // Current (draggable) point
  const [cpx, cpy] = toCanvas(px, py);
  ctx.save();
  ctx.fillStyle = '#e63946';
  ctx.beginPath(); ctx.arc(cpx, cpy, 7, 0, 2*Math.PI); ctx.fill();
  ctx.strokeStyle = '#fff'; ctx.lineWidth = 1.5; ctx.stroke();
  ctx.restore();
}

const fmt = v => v.toFixed(3);

function updatePanel() {
  document.getElementById('coords').textContent =
    `(x, y) = (${px.toFixed(3)}, ${py.toFixed(3)})`;
  document.getElementById('obj').textContent =
    `f(x, y) = ${(px*px + py*py).toFixed(4)}`;

  const k = solveKKT(px, py);
  const mu = k.mu;
  const g = k.g;
  const cs = k.cs;

  const defs = [
    {
      label: 'Stationarity',
      ok: k.statRes < 0.02,
      detail: `‖∇L‖ = ${fmt(k.statRes)}  (μ₁=${fmt(mu[0])}, μ₂=${fmt(mu[1])}, μ₃=${fmt(mu[2])})`
    },
    {
      label: 'Primal feasibility',
      ok: k.pfOk,
      detail: `g₁=1−x−y=${fmt(g[0])}≤0,  g₂=−x=${fmt(g[1])}≤0,  g₃=−y=${fmt(g[2])}≤0`
    },
    {
      label: 'Dual feasibility',
      ok: k.dualOk,
      detail: `μ₁=${fmt(mu[0])}≥0,  μ₂=${fmt(mu[1])}≥0,  μ₃=${fmt(mu[2])}≥0`
    },
    {
      label: 'Complementary slackness',
      ok: k.csOk,
      detail: `μ₁g₁=${fmt(cs[0])},  μ₂g₂=${fmt(cs[1])},  μ₃g₃=${fmt(cs[2])}`
    }
  ];

  const cEl = document.getElementById('conditions');
  cEl.innerHTML = '';
  for (const d of defs) {
    const div = document.createElement('div');
    div.className = 'cond ' + (d.ok ? 'ok' : 'fail');
    div.innerHTML =
      `<span class="icon">${d.ok ? '✓' : '✗'}</span>` +
      `<div><div class="cond-name">${d.label}</div>` +
      `<div class="cond-detail">${d.detail}</div></div>`;
    cEl.appendChild(div);
  }
}

function update() { draw(); updatePanel(); }

// Drag / touch handling
let dragging = false;
function getPos(e) {
  const r = canvas.getBoundingClientRect();
  const ex = e.touches ? e.touches[0].clientX : e.clientX;
  const ey2 = e.touches ? e.touches[0].clientY : e.clientY;
  return toMath(ex - r.left, ey2 - r.top);
}
canvas.addEventListener('mousedown',  e => { dragging = true;  const [mx,my]=getPos(e); px=Math.max(0,Math.min(2,mx)); py=Math.max(0,Math.min(2,my)); update(); });
canvas.addEventListener('mousemove',  e => { if(!dragging)return; const [mx,my]=getPos(e); px=Math.max(0,Math.min(2,mx)); py=Math.max(0,Math.min(2,my)); update(); });
canvas.addEventListener('mouseup',    () => { dragging = false; });
canvas.addEventListener('touchstart', e => { e.preventDefault(); dragging=true;  const [mx,my]=getPos(e); px=Math.max(0,Math.min(2,mx)); py=Math.max(0,Math.min(2,my)); update(); }, {passive:false});
canvas.addEventListener('touchmove',  e => { e.preventDefault(); if(!dragging)return; const [mx,my]=getPos(e); px=Math.max(0,Math.min(2,mx)); py=Math.max(0,Math.min(2,my)); update(); }, {passive:false});
canvas.addEventListener('touchend',   () => { dragging = false; });

document.getElementById('snap').addEventListener('click', () => { px=0.5; py=0.5; update(); });

update();

// Self-verify at optimum (runs in the sandboxed iframe console)
const _k = solveKKT(0.5, 0.5);
console.assert(_k.statRes < 0.02,   'KKT stationarity must hold at (0.5,0.5)');
console.assert(_k.pfOk,             'KKT primal feasibility must hold at (0.5,0.5)');
console.assert(_k.dualOk,           'KKT dual feasibility must hold at (0.5,0.5)');
console.assert(_k.csOk,             'KKT complementary slackness must hold at (0.5,0.5)');
console.log('KKT verified at (0.5,0.5): mu=', _k.mu.map(m=>m.toFixed(4)));
Result
Console

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 (μi⋅gi=0\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.

The Real Theory

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

  1. Stationarity — the gradient of the Lagrangian vanishes:

    ∇f(x∗)+∑iμi∇gi(x∗)+∑jλj∇hj(x∗)=0\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: gi(x∗)g_{i}(x*) ≤ 0 for all i, hj(x∗)h_{j}(x*) = 0 for all j.

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

    μi≥0for all i\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:

    μi⋅gi(x∗)=0for all i\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.

Where It Matters

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 (μi>0\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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/kkt-conditions/Content licensed under CC BY-NC 4.0.