Lagrange multipliers and KKT conditions
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.
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.
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.
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.
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.
Key insight: The method of Lagrange multipliers converts a constrained problem into an unconstrained one by introducing auxiliary variables, one for each constraint.
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.
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).
Key insight: KKT conditions are necessary for optimality in convex problems and sufficient under constraint qualifications. They are the foundation of all constrained optimization algorithms.