Lagrange multipliers and KKT conditions
Finding the best point is harder when you are only allowed to stand on a curve or inside a fence. The trick is to watch where the level curves just touch the constraint.
Pick a problem and slide the point along the constraint, or press Auto-play. At the optimum the level curve just touches the constraint and the two gradient arrows line up.
Slide a point along the constraint (white curve). At the constrained optimum, the gradients of f (∇f) and g (∇g) become parallel, satisfying ∇f = λ∇g.
In constrained optimization, we seek the best value of an objective function subject to constraints. Lagrange multipliers handle equality constraints by finding points where the objective's gradient is parallel to the constraint's gradient. The KKT conditions generalize this to inequality constraints.
At the constrained optimum, the level curve of the objective is tangent to the constraint curve. This means ∇f = λ∇g: the gradients are parallel. Slide along the constraint to find where this happens.
Key insight: The Lagrange multiplier λ measures the rate of change of the optimal value with respect to the constraint. It is the "shadow price" of relaxing the constraint.
Change the angle to move a point around the constraint curve and watch the objective rise and fall above it. The constrained optimum is the peak or trough of that profile.
Left: the constraint circle with a moving point. Right: the value of f restricted to the constraint, plotted against angle. The maximum (√2 at θ=π/4) and minimum (-√2 at θ=5π/4) are the constrained optima where ∇f = λ∇g.
Visualize the objective function restricted to the constraint. As a point travels along the constraint curve, the objective value rises and falls. The constrained optimum is the peak (or trough) of this restricted function.
Key insight: The method of Lagrange multipliers converts a constrained problem into an unconstrained one by introducing auxiliary variables, one for each constraint.
Hover over each constraint to see whether it is active at the optimum and what its multiplier λ is. Inactive constraints always get λ = 0.
The KKT conditions are necessary for optimality in constrained optimization with inequality constraints. At the optimum, active constraints (on the boundary) can have positive multipliers, while inactive constraints must have zero multipliers (complementary slackness).
The Karush-Kuhn-Tucker conditions extend Lagrange multipliers to inequality constraints. At the optimum, each constraint is either active (binding) or inactive, and complementary slackness says λ·g = 0 for each constraint.
Key insight: KKT conditions are necessary for optimality under constraint qualifications and sufficient in convex problems. They are the foundation of all constrained optimization algorithms.
Spot a mistake or have an idea?