Generalizing Lagrange
The Karush Kuhn Tucker conditions extend Lagrange multipliers to problems with inequality constraints. They give necessary conditions a solution must meet, and sufficient ones when the problem is convex.
The four conditions
- Stationarity: the Lagrangian gradient vanishes at the optimum.
- Primal feasibility: the solution satisfies all constraints.
- Dual feasibility: multipliers for inequalities are non negative.
- Complementary slackness: each multiplier times its constraint slack is zero.
Complementary slackness
This last condition is the heart of the idea. For each inequality, either the constraint is active, meaning tight, or its multiplier is zero.
- An inactive constraint exerts no force, so its multiplier is zero.
- An active constraint can have a positive multiplier.
In support vector machines, complementary slackness is exactly why only the support vectors have nonzero multipliers.
Key idea
The KKT conditions extend Lagrange to inequalities through stationarity, feasibility, and complementary slackness, which forces each constraint to be either active or carry a zero multiplier.