Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 38 · Constrained Optimization and Lagrange

Lagrange Multipliers for Equality Constraints

Solve constrained problems with Lagrange multipliers: the gradient condition, geometric meaning, the Lagrangian and worked examples verified with sympy and numpy.

So far the minimizer was free to go anywhere. Real problems come with rules: a budget must be spent exactly, probabilities must add to 1, a design must have a fixed volume. This chapter handles constraints. We start with the cleanest case: equality constraints, solved with the method of Lagrange multipliers.

The problem

Text
minimize    f(x)
subject to  h(x) = 0

Think of h(x) = 0 as a curve (or surface) along which you must stay. You cannot reach the unconstrained minimum of f if it lies off the curve. Instead you look for the lowest point on the curve.

The geometric idea

Draw level curves of f and the constraint curve. Walk along the constraint. As long as you cross level curves, f is changing, so you can still improve. At the best point, the constraint curve just touches a level curve without crossing it. There they share a tangent line, so their normals point the same way. The normal to a level curve of f is ∇f; the normal to the constraint is ∇h. So at the optimum

Text
∇f(x*) = -λ ∇h(x*)

for some number λ (the sign convention is a choice). λ is the Lagrange multiplier.

The Lagrangian

Package everything in one function:

Text
L(x, λ) = f(x) + λ h(x)

The conditions ∇ₓL = 0 and ∂L/∂λ = 0 say exactly "∇f + λ∇h = 0 and h(x) = 0". So you solve ∇L = 0 as a system of n + 1 equations in n + 1 unknowns.

Example 1: closest point on a line

Minimize f(x, y) = x² + y² subject to x + y = 2. Then ∇f = (2x, 2y) and ∇h = (1, 1). The equations: 2x + λ = 0, 2y + λ = 0, x + y = 2. The first two give x = y = -λ/2, and the third gives x = y = 1 and λ = -2. The minimum value is 2.

Python Solving the Lagrange system with sympy

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The solver returns x = 1, y = 1, λ = -2 and the value 2, matching the hand calculation.

Example 2: a nonlinear constraint

Find the largest value of x + y on the unit circle x² + y² = 1. Maximizing x + y equals minimizing -(x + y). The conditions give -1 + 2λx = 0 and -1 + 2λy = 0, so x = y, and then x² + y² = 1 gives x = y = ±1/√2. The maximum of x + y is √2 at (1/√2, 1/√2).

Python Check by brute force on the circle

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Parameterizing the circle by an angle removes the constraint, and the brute-force scan agrees with the multiplier result.

What the multiplier means

At the optimum, λ measures sensitivity: if you loosen the constraint from h(x) = 0 to h(x) = ε, the optimal value changes at the rate -λ per unit ε (with the sign convention above). In Example 1, change the rule to x + y = 2 + ε; the new minimum is (2 + ε)²/2, whose derivative at ε = 0 is 2 = -λ. Economists call the multiplier a shadow price: how much you would pay to relax the rule.

Python Multiplier as sensitivity

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Several constraints and linear systems

With constraints h₁, ..., h_p use one multiplier each: L = f + Σ λⱼhⱼ. For a quadratic objective with linear constraints, the optimality conditions form one linear system, called the KKT system:

Text
[ Q   Aᵀ ] [ x ]   [ -c ]
[ A   0  ] [ λ ] = [  b ]

for minimize ½xᵀQx + cᵀx subject to Ax = b.

Python Equality-constrained quadratic as one linear system

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line prints (near) zeros: the stationarity condition holds. For convex f (here Q is positive definite), a point that satisfies these equations is the global solution.

The multiplier method finds stationary points. For non-convex f or non-linear h, a stationary point may be a maximum or a saddle, so check second-order conditions or compare values.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. At an optimum on a constraint h(x) = 0, the gradients ∇f and ∇h are

    The constraint curve touches a level curve of f, so their normals point along the same line.
  2. 2. The Lagrangian for minimizing f subject to h(x) = 0 is

    L(x, λ) = f(x) + λh(x); setting its partial derivatives to zero gives the conditions.
  3. 3. In 'minimize x² + y² subject to x + y = 2', the minimizer is

    By symmetry and the Lagrange equations, x = y = 1.
  4. 4. The multiplier λ can be read as

    It is the sensitivity of the optimal value to the constraint level.

Summary

  • At a constrained optimum, ∇f is parallel to ∇h: ∇f + λ∇h = 0 together with h(x) = 0.
  • The Lagrangian L = f + λh turns the problem into solving ∇L = 0.
  • The multiplier measures how much the optimal value changes if the constraint is relaxed.
  • Quadratic objectives with linear equality constraints reduce to a single linear system.

Next: Inequality Constraints and Active Sets