Calculus×Computing
ES

KKT conditions

Level AdvancedDifficulty ★★★★★Concept⌖ Open in the map

What is it?

Lagrange multipliers for inequality constraints hj(x)≤0h_j(x) \le 0: multipliers are non-negative, and each is zero unless its constraint is active (complementary slackness). For convex problems the KKT conditions are necessary and sufficient.

Formulas

∇f(x∗)+∑jμj∇hj(x∗)=0,μj≥0,μj hj(x∗)=0\nabla f(x^\ast) + \sum_j \mu_j \nabla h_j(x^\ast) = 0, \quad \mu_j \ge 0, \quad \mu_j\,h_j(x^\ast) = 0

Where it shows up in computing

  • Operations research and logistics★★★★★fundamentalOptimization and systems

    Interior-point and active-set solvers are algorithms for satisfying the KKT conditions.

  • Trajectory optimization and MPC★★★★★frequentRobotics and control

    Nonlinear programming solvers used in model predictive control (IPOPT, SQP) iterate towards a KKT point.

Where it shows up in AI

  • Support vector machines★★★★★fundamentalAI and machine learning

    Complementary slackness is why only the support vectors (points on or inside the margin) get non-zero weight.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

ℒ AI and machine learning

⇄ Optimization and systems

⚙ Robotics and control

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.

↑ ↓ to navigate · ↵ · Esc