A Deeper Analysis of the Lagrange Multiplier Method

The Geometric Essence of the Lagrange Multiplier Method

The Meaning of the Lagrange Multiplier

Theorem1

The sensitivity interpretation of the multiplier: suppose f∗(c)f^*(c) is the extremum of ff under the constraint g(x,y)=cg(x,y)=c. Then

λ=−df∗dc\lambda = -\frac{df^*}{dc}

that is, the Lagrange multiplier λ\lambda (after taking the negative sign) gives the rate of change of the extremal value of the objective function when the right-hand side cc of the constraint changes by one unit.

In economics λ\lambda is called the shadow price, and it expresses the marginal value of a resource.

Inequality Constraints and the KKT Conditions

Theorem2

For the constrained optimisation problem with inequality constraints:

min⁡f(x)s.t.gi(x)≤0(i=1,…,m)\min f(x) \quad \text{s.t.} \quad g_i(x) \leq 0 \quad (i=1,\ldots,m)

the KKT conditions (the Karush-Kuhn-Tucker conditions) are necessary conditions for an extremum point:

  1. Stationarity: ∇f(x∗)+∑i=1mλi∇gi(x∗)=0\nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla g_i(x^*) = 0
  2. Primal feasibility: gi(x∗)≤0g_i(x^*) \leq 0
  3. Dual feasibility: λi≥0\lambda_i \geq 0
  4. Complementary slackness: λigi(x∗)=0\lambda_i g_i(x^*) = 0

The complementary slackness condition means: if the constraint gi<0g_i < 0 (it is not active), then λi=0\lambda_i = 0; and if λi>0\lambda_i > 0, then gi=0g_i = 0 (the constraint is active).

The Lagrange Duality

The Lagrange dual function

The primal problem: min⁡f(x)\min f(x) s.t. gi(x)≤0,hj(x)=0g_i(x) \leq 0, h_j(x)=0

The Lagrangian function: L(x,λ,μ)=f(x)+∑λigi(x)+∑μjhj(x)L(x, \lambda, \mu) = f(x) + \sum \lambda_i g_i(x) + \sum \mu_j h_j(x)

The dual function: g(λ,μ)=inf⁡xL(x,λ,μ)g(\lambda, \mu) = \inf_x L(x, \lambda, \mu)

The dual problem: max⁡λ≥0,μg(λ,μ)\max_{\lambda \geq 0, \mu} g(\lambda, \mu)

Weak duality theorem: the optimal value of the dual problem is ≤\leq the optimal value of the primal problem.

Strong duality theorem: in a convex optimisation problem (satisfying a constraint qualification), the optimal value of the dual problem equals that of the primal problem.

Worked Examples

Example 1: Computing the Shadow Price

Under the constraint x+y=cx + y = c, maximise f(x,y)=xyf(x,y) = xy. Find the optimal value f∗(c)f^*(c) and the Lagrange multiplier λ\lambda, and verify that λ=−df∗/dc\lambda = -df^*/dc.

the Lagrange multiplierthe shadow pricesensitivity

Approach:

The shadow price is the shadow value of the constraint, so the Lagrange multiplier is exactly the derivative of the optimal value with respect to the constant of the constraint — which is the identity to be verified here.

Steps:

  1. L=xy+λ(x+y−c)L = xy + \lambda(x+y-c)
  2. Lx=y+λ=0L_x = y+\lambda=0 and Ly=x+λ=0L_y = x+\lambda=0, giving x=y=−λx=y=-\lambda
  3. Substituting into the constraint: 2x=c2x=c, so x=y=c2x=y=\frac{c}{2} and λ=−c2\lambda = -\frac{c}{2}
  4. The optimal value f∗(c)=c24f^*(c) = \frac{c^2}{4}
  5. df∗dc=c2\frac{df^*}{dc} = \frac{c}{2}, while −λ=c2-\lambda = \frac{c}{2}, which verifies λ=−df∗dc\lambda = -\frac{df^*}{dc}

Answer: f∗(c)=c24f^*(c)=\frac{c^2}{4} and λ=−c2\lambda=-\frac{c}{2}, satisfying λ=−df∗dc\lambda=-\frac{df^*}{dc}.

Example 2: Applying the KKT Conditions

Use the KKT conditions to solve min⁡f(x,y)=x2+y2\min f(x,y) = x^2 + y^2 s.t. x+y≥1x + y \geq 1.

the KKT conditionsinequality constraintsquadratic programming

Approach:

The KKT conditions turn the inequality constraint into a system of equations with complementary slackness, and the complementary slackness also tells you whether the constraint is “active” or “not active”.

Steps:

  1. Standardising the constraint: g(x,y)=1−x−y≤0g(x,y) = 1 - x - y \leq 0
  2. L=x2+y2+λ(1−x−y)L = x^2+y^2 + \lambda(1-x-y)
  3. The KKT conditions:
    • ∇L=(2x−λ,2y−λ)=0\nabla L = (2x-\lambda, 2y-\lambda) = 0 ⟹ x=y=λ2x=y=\frac{\lambda}{2}
    • 1−x−y≤01-x-y \leq 0
    • λ≥0\lambda \geq 0
    • λ(1−x−y)=0\lambda(1-x-y) = 0
  4. If λ=0\lambda=0: x=y=0x=y=0, but 1−0−0=1>01-0-0=1>0, which violates primal feasibility.
  5. So λ>0\lambda>0, and complementary slackness gives 1−x−y=01-x-y=0, that is, x+y=1x+y=1
  6. Combining with x=y=λ2x=y=\frac{\lambda}{2}: 2⋅λ2=12\cdot\frac{\lambda}{2}=1, so λ=1\lambda=1 and x=y=12x=y=\frac{1}{2}
  7. The minimum f(12,12)=12f(\frac{1}{2},\frac{1}{2}) = \frac{1}{2}

Answer: the minimum value is 12\frac{1}{2}, attained at (12,12)(\frac{1}{2},\frac{1}{2}).


Exercises

Exercise 1

Use the KKT conditions to solve max⁡f(x,y)=xy\max f(x,y) = xy s.t. x2+y2≤1x^2 + y^2 \leq 1, x,y≥0x, y \geq 0.

the KKT conditionsinequality constraintsthe maximum value

Approach:

Standardise all the constraints in the form g≤0g \leq 0 and write out the four KKT conditions; complementary slackness tells you which constraints are active.

Steps:

  1. The constraints: g1=x2+y2−1≤0g_1 = x^2+y^2-1 \leq 0 and g2=−x≤0g_2 = -x \leq 0, g3=−y≤0g_3 = -y \leq 0
  2. L=xy+λ(x2+y2−1)−μx−νyL = xy + \lambda(x^2+y^2-1) - \mu x - \nu y
  3. Stationarity: Lx=y+2λx−μ=0L_x = y+2\lambda x-\mu=0, Ly=x+2λy−ν=0L_y = x+2\lambda y-\nu=0
  4. The solution must have x,y≥0x,y\geq0 and x2+y2≤1x^2+y^2\leq1; by symmetry the optimum has x=yx=y
  5. If the circular constraint is active (x2+y2=1x^2+y^2=1) and λ>0\lambda>0: with x=yx=y we get 2x2=12x^2=1, so x=y=12x=y=\frac{1}{\sqrt{2}} and f=12f=\frac{1}{2}
  6. Checking stationarity: Lx=12+2λ12=0L_x = \frac{1}{\sqrt{2}} + 2\lambda\frac{1}{\sqrt{2}} = 0 gives λ=−12\lambda = -\frac{1}{2}, which violates λ≥0\lambda\geq0 (the maximum is a different case from the minimum)
  7. For a maximum, the sign convention flips: use L=xy−λ(x2+y2−1)L = xy - \lambda(x^2+y^2-1) with λ≥0\lambda\geq0, and then λ=12>0\lambda=\frac{1}{2}>0 ✓
  8. Comparing with the boundary points (1,0)(1,0) and (0,1)(0,1), where f=0f=0, the maximum is 12\frac{1}{2}

Answer: the maximum value is 12\frac{1}{2}, attained at (12,12)(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}).

Exercise 2

Show that the shadow price of the constraint x+y≥4x + y \geq 4 in the problem of maximising f(x,y)=xyf(x,y) = \sqrt{xy} is 12\frac{1}{2}.

the shadow pricesensitivitythe maximum value

Approach:

Find the optimal value as a function of the constant of the constraint and differentiate it.

Steps:

  1. Under x+y=cx+y=c and by symmetry, the optimum is x=y=c2x=y=\frac{c}{2}
  2. The optimal value f∗(c)=c2⋅c2=c2f^*(c) = \sqrt{\frac{c}{2}\cdot\frac{c}{2}} = \frac{c}{2}
  3. df∗dc=12\frac{df^*}{dc} = \frac{1}{2}
  4. Hence the shadow price is df∗dc=12\frac{df^*}{dc} = \frac{1}{2} (the magnitude of the Lagrange multiplier)

Answer: the shadow price is 12\frac{1}{2}.


Summary

Symbols Used in This Article

SymbolTypePronunciation/ExplanationMeaning in This Article
λ\lambdaLagrange multiplierlambdaThe multiplier for an equality or inequality constraint
μ\muMultipliermuThe multiplier for an equality constraint
LLLagrangianLagrangianThe Lagrangian function
g(λ,μ)g(\lambda,\mu)Dual functiondual functionThe Lagrange dual function
f∗f^*Optimal valueoptimal valueThe optimal value of the constrained optimisation
ccRight-hand side of the constraintconstraint RHSThe right-hand side of the constraint
x∗x^*Extremum pointextremum pointThe extremum point of the optimisation

Found an issue with this content?

Tell us what could be improved.