About the mathematical proof of shadow price

Question

I have a LP problem like:

\begin{align} \min &\quad z = c^T x \\ s.t. &\quad Ax\le b \\ &\quad x\ge 0 \end{align}

Assume the optimal solution of this problem is $x^*$ and the dual optimal solution which is also called shadow price is $y^*$.

A general explanation of shadow price $y^*$ is when we increase $b_i$ to $b_i'$, the objective value $z^*$ will increase by $y_i^* * (b_i' - b_i)$.

My question is, considering $z^* = z^*(b)$ a function of $b$, does $\frac{\partial z^*}{\partial b_i}$ exist and $= y_i^*$? Is there any rigorous proof?

Answer 1

It is true that $y^*$ is a subgradient of $z^*()$ at $b.$ With two key qualifications, $y^*$ is the gradient of $z^*()$ at $b.$ The two qualifications are (1) that $x^*$ is nondegenerate and (2) that small but nonzero changes in $b$ will not render the problem infeasible. This is proved in a variety of LP textbooks.

The underlying logic is that if a change $\Delta b$ to $b$ is sufficiently small that the optimal basis remains optimal, then the change in $z^*$ is $y^{*'}\Delta b,$ which is easy to prove. If the change is enough to force a pivot, then the change to the optimal value is bounded below by $y^{*'}\Delta b,$ because $y^*$ remains a feasible solution to the dual. (You are changing the objective function but not the constraints of the dual.) If the change makes the primal problem infeasible, we treat its objective value as $+\infty$ and the bounded below statement (trivially) applies.

In the case of a degenerate solution, it is possible that an arbitrarily small change to $b$ in a certain direction can force a pivot. When the primal is degenerate, the dual has multiple optima, and a small move can cause you to jump from one dual solution to another.