Sensitivity & Shadow Prices

The multiplier you computed is a price: what one more unit of budget is worth.

The idea

Sensitivity analysis asks how the optimal value of a problem changes when its constraints are tightened or loosened, and the optimal dual multipliers answer the question.

Perturb the right-hand sides of a problem in standard form: replace each $f_{i}(x) \le 0$ by $f_{i}(x) \le u_{i}$ and each $h_{j}(x) = 0$ by $h_{j}(x) = v_{j}$, and write $p^{\star}(u,v)$ for the optimal value of the perturbed problem. A positive $u_{i}$ loosens constraint $i$ and can only help; a negative one tightens it and can only hurt.

Two results tie the optimal multipliers $\lambda^{\star}, \nu^{\star}$ to that function. If strong duality holds and the dual optimum is attained, then for every $u$ and $v$, of any size,

$p^{\star}(u,v) \ge p^{\star} - \lambda^{\star T}u - \nu^{\star T}v.$

If in addition $p^{\star}$ is differentiable at the origin, then $\lambda^{\star}_{i} = -\partial p^{\star}(0,0) / \partial u_{i}$.

So an optimal multiplier is a price — the shadow price of its constraint: the rate at which the optimal value falls per unit of loosening. If constraint $i$ limits a resource, $\lambda^{\star}_{i}$ is the most that one more unit of that resource is worth paying for. A tight constraint with a large multiplier is the one worth relaxing; a constraint with $\lambda^{\star}_{i} = 0$ can be loosened without improving the optimal value at all.

Ways to work on it

• Walkthrough. Compute an optimum and its multiplier, perturb the constraint, and check the predicted change against the truth.
• Proof. Why one multiplier bounds every perturbed problem at once, and why the bound is one-sided.
• Practice. Price a production constraint, a curved one, and a constraint that is slack at the optimum.
• Hardest. Carry out sensitivity analysis at a kink, where the optimal value has no derivative.

Not sure where to start? Take the ten-question placement test.