Linear Programming Sensitivity to Matrix

Question

Consider a linear program in the following standard form: \begin{align*} &\max c^T x &\\ &\mbox{subject to:}\\ &A x \preceq b\\ &x \succeq 0 \end{align*}

Its dual is \begin{align*} &\min b^T y &\\ &\mbox{subject to:}\\ &A^T y \succeq c\\ &y \succeq 0 \end{align*}

Let $x^*$ and $y^*$ be optimal primal and dual solutions, respectively. Let $\nu = c^T x^* = b^T y^*$ be the optimal value. Suppose for simplicity that the optimal solutions are unique (i.e., we have non-degeneracy for both primal and dual). It is well known from basic sensitivity analysis that the optimal value is differentiable with respect to $b$ and $c$ at that point, and we have $$\frac{\partial \nu}{\partial c_j} = x^*_j$$ and $$\frac{\partial \nu}{\partial b_i} = y^*_i.$$ The proof of these facts is also quite simple.

What I wasn't able to find, however, was an authoritative and simple treatment of sensitivity with respect to entries of the matrix $A$. In particular, suppose we modify just the a single entry $a_{ij}$ of the matrix $A$. What is the partial derivative of $\nu$ with respect to $a_{ij}$, in the non-degenerate case (i.e., where $\nu$ is differentiable)? Playing around with it, I'm pretty sure the answer is the following:

$$\frac{\partial \nu}{\partial a_{ij}} = - y^*_i x^*_j$$

I even have the outlines of a (sketchy) "proof", though it is not as simple or "clean" as I would like. I'm reluctant to spend significant time and effort on this, since such a basic fact should certainly be known and written down clearly in a book somewhere.

Does anyone know a simple proof of this fact, or can point me to a reference which provides such a proof? Or am I way off base here?

Answer 1

Okay I think I have figured this out! I am going to assume we have primal and dual problems: \begin{array}? (P) &&\max& c^Tx &&& (D) &&\min& b^Ty \\ &&\text{s.t.}& Ax \leq b &&& && \text{s.t.}& A^Ty \geq c \\ && & x \geq 0 &&& && & y \geq 0 \end{array} Which we can write in the equivalent forms (which are not directly duals of each other, but are related). \begin{array}? (P') &&\max& c^Tx &&& (D')&&\min& b^Ty \\ &&\text{s.t.}& Ax+u = b &&& && \text{s.t.}& A^Ty - v = c \\ && & x, u \geq 0 &&& && & y, v \geq 0 \end{array}

Note that $\nu = c^T x^*$ and $c$ is constant, so we have that $\frac{\partial\nu}{\partial a_{ij}} = c^T\frac{\partial x^*}{\partial a_{ij}}.$ Here $\frac{\partial x^*}{\partial a_{ij}}$ is the (column) vector whose $j$th entry is $\frac{\partial x^*_j}{\partial a_{ij}}$. Similarly we have $\frac{\partial\nu}{\partial a_{ij}} = b^T\frac{\partial y^*}{\partial a_{ij}}.$

Finally, we note that $\nu = {y^*}^TAx^* - {v^*}^Tx^* = {y^*}^TAx^*$ since, by complimentary slackness, ${v^*}^Tx^*=0$ for any optimal primal solution $x^*$ and optimal dual slack variables $v^*$. Therefore, \begin{align} \frac{\partial\nu}{\partial a_{ij}} &= \frac{\partial}{\partial a_{ij}} \left({y^*}^TAx^*\right) \tag{1}\\ &= \left(\frac{\partial y^*}{\partial a_{ij}}\right)^TAx^* + y^*_ix^*_j + {y^*}^TA\left(\frac{\partial x^*}{\partial a_{ij}}\right) \tag{2}\\ &= \left(\frac{\partial y^*}{\partial a_{ij}}\right)^Tb + y^*_ix^*_j + c^T\left(\frac{\partial x^*}{\partial a_{ij}}\right) \tag{3}\\ &= \left(\frac{\partial\nu}{\partial a_{ij}}\right) + y^*_ix^*_j + \left(\frac{\partial \nu}{\partial a_{ij}}\right) \tag{4}\\ \Rightarrow - \frac{\partial\nu}{\partial a_{ij}} &= y^*_ix^*_j \tag{5}\\ \Rightarrow \frac{\partial\nu}{\partial a_{ij}} &= - y^*_ix^*_j \tag{5}\\ \end{align}

Answer 2

Let $u$ and $v$ be vectors of slack variables for the primal and dual, respectively. Thus $A x^* + u = b$ and $A^T y^* - v = c$. Then we can see that \begin{equation} \nu = c^T x^* = (Ay^*-v)^Tx^* = {y^*}^T(Ax^*) - v^T x^* \tag{0} \end{equation} And thus \begin{align} \frac{\partial\nu}{\partial a_{ij}} &= \frac{\partial}{\partial a_{ij}}\left (y^*_ia_{ij}x^*_j \right) \tag{1}\\ &= \frac{\partial}{\partial a_{ij}}\left (y^*_ia_{ij}x^*_j \right) \tag{2}\\ &= a_{ij}y^*_i\frac{\partial x^*_j}{\partial a_{ij}} + a_{ij}y^*_i\frac{\partial y^*_i}{\partial a_{ij}}x^*_j + y^*_ix^*_j \tag{3}\\ &= a_{ij}y^*_i\frac{-x^*_j}{a_{ij}} + a_{ij}y^*_i\frac{-y^*_i}{a_{ij}}x^*_j + y^*_ix^*_j \tag{4}\\ &= -y^*_ix^*_j \tag{5} \end{align}