# Linear Programming Sensitivity to Matrix

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?

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}

• I suspect you forgot some inequalities in the primal and/or dual (these LPs are not duals as stated). Which LPs did you mean, exactly? Commented Sep 6, 2023 at 0:26
• These LPs are duals as stated. Equality constraints in the primal correspond to free variables (ie NOT non-negative/non-positive) in the dual and vice versa. Commented Sep 6, 2023 at 22:43
• I agree. I must have been looking at an old version or something Commented Sep 7, 2023 at 23:19
• I did update the answer as this form is clearer and more useful, but the old version was still correct. Commented Sep 8, 2023 at 0:10
• Looks right to me. I guess you can replace Ax* by b and y*^T A by c in the third equality by complementary slackness. Thanks! Commented Sep 8, 2023 at 1:07

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 $$$$\nu = c^T x^* = (Ay^*-v)^Tx^* = {y^*}^T(Ax^*) - v^T x^* \tag{0}$$$$ 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}

• Thank you. But why is it obvious that $\frac{\partial x^*_j}{\partial a_{ij}} = - \frac{x^*_j}{a_{ij}}$? One could imagine that changes in $a_{ij}$ can affect $x$ in a somewhat more nuanced way that is not localized to just $x^*_j$, and therefore $x^*_j$ might go down by less than that... I suspect I'm wrong to worry about this, but I'm not quite sure why I'm wrong... Commented Sep 1, 2023 at 23:22
• Since we are assuming there is a unique optimal solution, we know it must be a basic feasible solution, and thus be associated with a basis. Assuming non-degeneracy this is the only optimal basis and, for a small enough change in $a_{ij}$ the optimal basis won't change. Thus $x^*_j$ is the only variable that can change to accommodate the change in $a_{ij}$. If the basis associated with $x^*$ is degenerate, I would suspect that $\frac{\partial\nu}{\partial a_{ij}$ does not exist. Commented Sep 2, 2023 at 0:35
• I think I can come up with a counterexample. Suppose the optimal basis is given by the following equations: $$x_1 - x_2 = 0$$ $$x_1 + x_2 = 1$$ Clearly, the solution is $x_1 =x_2 = 1/2$. Now suppose vary the coefficient of $x_1$ in the first equation, let's call it $a$, initially at $1$... $$a x_1 - x_2 = 0$$ $$x_1 + x_2 = 1$$ We can come up with a closed form solution to the above system as a function of $a$. In particular, $x_1 = \frac{1}{1+a}$. The derivative of $x$ w.r.t. $a$ is $- \frac{1}{(1+a)^2}$, which at $a=1$ is $-\frac{1}{4}$. This is not equal to $-x_1/a = -1/2$. Commented Sep 2, 2023 at 4:20
• Ah yes you are absolutely right, I was wrong. You would need to look at all of the basic variables (and the dual basic variables) as a function of $a$ and compute the derivate of ${y^*}^TAx^* - v^Tx^*$ more carefully. Commented Sep 3, 2023 at 20:06