Primer on Lagrangians
You typically have a function f(x) to optimize (minimize or maximize), subject to constraints:
- Equality constraints: gi(x)=0, for i=1,…,m.
- Inequality constraints: hj(x)≤0, for j=1,…,n.
The Idea
Lagrange multipliers introduce additional variables (multipliers) to incorporate constraints into the objective function. This creates a single "augmented" function, the Lagrangian:
L(x,λ)=f(x)+i=1∑mλigi(x),
where λi are the Lagrange multipliers for the equality constraints.
Procedure
-
Construct the Lagrangian:
Combine f(x) and gi(x) into L(x,λ).
-
Stationary Points:
Find critical points by solving:
∂x∂L=0and∂λ∂L=gi(x)=0.
This ensures gradients of the objective and constraints are aligned.
-
Solve:
Solve the system of equations to find x and λ.
Inequality Constraints (KKT Conditions)
For inequality constraints hj(x)≤0, introduce slackness conditions:
L(x,λ,μ)=f(x)+i=1∑mλigi(x)+j=1∑nμjhj(x),
where μj≥0. The KKT conditions are:
- ∇xL=0,
- gi(x)=0,
- hj(x)≤0,
- μjhj(x)=0 (complementary slackness).
Geometric Insight
The Lagrange multiplier λi measures the rate of change of the optimal f(x) with respect to the constraint gi(x). Think of it as a "shadow price" or sensitivity factor.