Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 38 · Duality and KKT Conditions

Sensitivity and Shadow Prices

See what the Lagrange multiplier means: the rate at which the optimal value changes when a constraint is relaxed. Verify it with finite differences and a linear program.

Multipliers are not just a proof device. Each λ_i* has a practical meaning: it tells you how much the best value improves if you relax constraint i by one unit. Economists call it a shadow price. If a factory's machine-hours limit has shadow price 12 dollars per hour, then one more hour of machine time is worth 12 dollars, so you should rent it for less.

In this lesson you will define the perturbed problem, state the sensitivity rule, and check it with two examples.

The perturbed problem

Change the right-hand side of one constraint from 0 to u:

Text
minimize    f(x)
subject to  g(x) ≤ u

Let p*(u) be the optimal value as a function of u. Positive u means a looser rule; negative u means a tighter one. For a convex problem, p*(u) is a convex function of u.

The central rule: if strong duality holds and p*(u) is differentiable at u = 0, then

Text
dp*/du at u = 0  =  -λ*

Increasing u (loosening the rule) lowers the minimal cost by about λ* per unit. A constraint with λ* = 0 is not binding, so relaxing it saves nothing.

Even without differentiability, the dual gives a global bound: for every u,

Text
p*(u) ≥ p*(0) - λ* · u

This is a tangent-like line that stays below p*(u), which is exactly what convexity predicts.

Why it works

Let λ* be the optimal multiplier of the original problem (u = 0). With strong duality, the dual value is d(λ*) = p*(0), and by the definition of d as a minimum over x:

Text
p*(0) = d(λ*) ≤ f(x) + λ*·g(x)    for every x

Now take any x that is feasible for the perturbed problem, so g(x) ≤ u. Since λ* ≥ 0, we get λ*·g(x) ≤ λ*·u, and therefore p*(0) ≤ f(x) + λ*·u. Rearranging gives f(x) ≥ p*(0) - λ*·u. Taking the best such x yields the bound above.

Example 1: a closed form

Use the problem from the KKT lesson with a variable right-hand side:

Text
minimize    (x₁ - 2)² + (x₂ - 1)²
subject to  x₁ + x₂ ≤ u

For u ≤ 3 the constraint is active and the optimal point is (2 - t, 1 - t) with t = (3 - u)/2, so p*(u) = 2t² = (3 - u)²/2. At u = 2 the slope is -(3 - u) = -1, matching -λ* = -1.

Python Finite-difference check of the shadow price

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 should be near -0.095: the exact change is (0.9² - 1)/2 = -0.095, slightly smaller in size than λ × 0.1 = 0.1 because the curve p*(u) bends upward (convexity), exactly as the global bound says.

Example 2: a linear program

A workshop makes two products. Product X earns 3 dollars per unit and Y earns 2 dollars per unit. Constraints:

Text
labor:   x + y  ≤ 4     (hours)
paint:   x + 3y ≤ 9     (liters)
cap:     x      ≤ 3     (units of X the market takes)
         x, y ≥ 0

We maximize 3x + 2y. SciPy's linprog minimizes, so we minimize -3x - 2y. The HiGHS solver reports the multipliers (as "marginals") for each inequality: the derivative of the minimized objective with respect to the right-hand side.

Python Shadow prices from a linear program

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 optimal plan is x = 3, y = 1, profit 3·3 + 2·1 = 11. The paint constraint has slack 9 - 6 = 3 (inactive), so its shadow price is 0. Labor and the market cap are active: solving λ_labor + λ_cap = 3 (the profit per unit of x) and λ_labor = 2 (the profit per unit of y) gives shadow prices 2 and 1. The marginals printed by the solver are the negatives of these (because we minimized -profit), and the labor perturbation gains 2, as predicted.

Shadow prices are valid only for small changes. If you add many labor hours, a different set of constraints becomes active and the price changes. The function p*(u) is piecewise linear for an LP, and the shadow price is the slope of the current piece.

Reading multipliers in practice

  • A large λ_i* marks a bottleneck: improving that resource pays off the most.
  • λ_i* = 0 means the constraint has slack; do not spend money on it.
  • Compare λ_i* with the market price of the resource to decide whether to buy more.
  • Multipliers depend on units. If you measure labor in minutes instead of hours, λ shrinks by a factor of 60.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. For minimize f(x) subject to g(x) ≤ u, what is dp*/du at u = 0 (when it exists)?

    Loosening the constraint (raising u) lowers the minimum by about λ* per unit, so the derivative is negative.
  2. 2. A constraint has slack at the optimum. What is its shadow price?

    Complementary slackness forces λ = 0 for an inactive constraint, so relaxing it brings no benefit.
  3. 3. Why is p*(u) ≥ p*(0) - λ*·u true even when p* is not differentiable?

    Weak duality applied to the perturbed problem with the old multiplier gives this global lower bound.
  4. 4. In the workshop LP, labor has shadow price 2 dollars per hour. What is the best interpretation?

    The shadow price is the marginal value of the resource. Here it is the gain in profit per extra hour while the same constraints stay active.

Summary

  • The perturbed problem g(x) ≤ u has optimal value p*(u), which is convex in u.
  • dp*/du = -λ* at u = 0: the multiplier is the shadow price of the constraint.
  • p*(u) ≥ p*(0) - λ*·u holds globally, by duality.
  • Inactive constraints have zero shadow price; bottlenecks have large ones. Prices hold only while the same constraints stay active.

Next: Linear Programs