<p>Okay I think I have figured this out! I am going to assume we have primal and dual problems:
<span class="math-container">\begin{array}?
(P) &amp;&amp;\max&amp; c^Tx &amp;&amp;&amp; (D) &amp;&amp;\min&amp; b^Ty \\
&amp;&amp;\text{s.t.}&amp; Ax \leq b &amp;&amp;&amp;  &amp;&amp; \text{s.t.}&amp; A^Ty \geq c \\
&amp;&amp;           &amp;  x \geq 0 &amp;&amp;&amp;  &amp;&amp;            &amp;    y \geq 0
\end{array}</span>
Which we can write in the equivalent forms (which are not directly duals of each other, but are related).
<span class="math-container">\begin{array}?
(P')        &amp;&amp;\max&amp; c^Tx &amp;&amp;&amp; (D')&amp;&amp;\min&amp; b^Ty \\
&amp;&amp;\text{s.t.}&amp; Ax+u = b &amp;&amp;&amp;   &amp;&amp; \text{s.t.}&amp; A^Ty - v = c \\
&amp;&amp;           &amp;  x, u \geq 0 &amp;&amp;&amp;  &amp;&amp;            &amp;    y, v \geq 0
\end{array}</span></p>
<p>Note that <span class="math-container">$\nu = c^T x^*$</span> and <span class="math-container">$c$</span> is constant, so we have that <span class="math-container">$\frac{\partial\nu}{\partial a_{ij}} = c^T\frac{\partial x^*}{\partial a_{ij}}.$</span> Here <span class="math-container">$\frac{\partial x^*}{\partial a_{ij}}$</span> is the (column) vector whose <span class="math-container">$j$</span>th entry is <span class="math-container">$\frac{\partial x^*_j}{\partial a_{ij}}$</span>. Similarly we have <span class="math-container">$\frac{\partial\nu}{\partial a_{ij}} = b^T\frac{\partial y^*}{\partial a_{ij}}.$</span></p>
<p>Finally, we note that <span class="math-container">$\nu = {y^*}^TAx^* - {v^*}^Tx^* = {y^*}^TAx^*$</span> since, by complimentary slackness, <span class="math-container">${v^*}^Tx^*=0$</span> for any optimal primal solution <span class="math-container">$x^*$</span> and optimal dual slack variables <span class="math-container">$v^*$</span>. Therefore,
<span class="math-container">\begin{align}
    \frac{\partial\nu}{\partial a_{ij}}
    &amp;= \frac{\partial}{\partial a_{ij}} \left({y^*}^TAx^*\right) \tag{1}\\
    &amp;= \left(\frac{\partial y^*}{\partial a_{ij}}\right)^TAx^* + y^*_ix^*_j +
            {y^*}^TA\left(\frac{\partial x^*}{\partial a_{ij}}\right) \tag{2}\\
    &amp;= \left(\frac{\partial y^*}{\partial a_{ij}}\right)^Tb + y^*_ix^*_j +
            c^T\left(\frac{\partial x^*}{\partial a_{ij}}\right) \tag{3}\\
    &amp;= \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}} &amp;= y^*_ix^*_j  \tag{5}\\
\Rightarrow \frac{\partial\nu}{\partial a_{ij}} &amp;= - y^*_ix^*_j  \tag{5}\\
\end{align}</span></p>

CC BY-SA 4.0
2023-09-06T00:26:16.053Z
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?
sd234
CC BY-SA 4.0
2023-09-06T22:43:00.873Z
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.
NaturalLogZ
CC BY-SA 4.0
2023-09-07T23:19:51.293Z
I agree. I must have been looking at an old version or something
sd234
CC BY-SA 4.0
2023-09-08T00:10:55.550Z
I did update the answer as this form is clearer and more useful, but the old version was still correct.
NaturalLogZ
CC BY-SA 4.0
2023-09-08T01:07:44.663Z
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!
sd234
CC BY-SA 4.0
2023-09-04T21:25:10.230Z
2023-09-06T22:52:59.147Z
2023-09-06T22:52:59.147Z
NaturalLogZ
<p>Let <span class="math-container">$u$</span> and <span class="math-container">$v$</span> be vectors of slack variables for the primal and dual, respectively. Thus <span class="math-container">$A x^* + u = b$</span> and <span class="math-container">$A^T y^* - v = c$</span>. Then we can see that
<span class="math-container">\begin{equation}
\nu = c^T x^* = (Ay^*-v)^Tx^* = {y^*}^T(Ax^*) - v^T x^* \tag{0}
\end{equation}</span>
And thus
<span class="math-container">\begin{align}
    \frac{\partial\nu}{\partial a_{ij}} 
    &amp;= \frac{\partial}{\partial a_{ij}}\left (y^*_ia_{ij}x^*_j \right) \tag{1}\\
    &amp;= \frac{\partial}{\partial a_{ij}}\left (y^*_ia_{ij}x^*_j \right) \tag{2}\\
    &amp;= 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}\\
    &amp;= 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}\\
    &amp;= -y^*_ix^*_j \tag{5}
\end{align}</span></p>

CC BY-SA 4.0
2023-09-01T23:22:24.483Z
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...
sd234
CC BY-SA 4.0
2023-09-02T00:35:17.777Z
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.
NaturalLogZ
CC BY-SA 4.0
2023-09-02T04:20:42.767Z
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$.
sd234
CC BY-SA 4.0
2023-09-03T20:06:17.650Z
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.
NaturalLogZ
CC BY-SA 4.0
2023-09-01T18:03:44.570Z
2023-09-01T23:29:04.253Z
2023-09-01T23:29:04.253Z
NaturalLogZ
<p>Consider a linear program in the following standard form:
<span class="math-container">\begin{align*}
&amp;\max  c^T x &amp;\\
&amp;\mbox{subject to:}\\
&amp;A x \preceq b\\
&amp;x \succeq 0
\end{align*}</span></p>
<p>Its dual is
<span class="math-container">\begin{align*}
&amp;\min  b^T y &amp;\\
&amp;\mbox{subject to:}\\
&amp;A^T y \succeq c\\
&amp;y \succeq 0
\end{align*}</span></p>
<p>Let <span class="math-container">$x^*$</span> and <span class="math-container">$y^*$</span> be optimal primal and dual solutions, respectively. Let <span class="math-container">$\nu = c^T x^* = b^T y^*$</span> 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 <span class="math-container">$b$</span> and <span class="math-container">$c$</span> at that point, and we have <span class="math-container">$$\frac{\partial \nu}{\partial c_j} = x^*_j$$</span> and <span class="math-container">$$\frac{\partial \nu}{\partial b_i} = y^*_i.$$</span> The proof of these facts is also quite simple.</p>
<p>What I wasn't able to find, however, was an authoritative and simple treatment of sensitivity with respect to entries of the matrix <span class="math-container">$A$</span>. In particular, suppose we modify just the a single entry <span class="math-container">$a_{ij}$</span> of the matrix <span class="math-container">$A$</span>. What is the partial derivative of <span class="math-container">$\nu$</span> with respect to <span class="math-container">$a_{ij}$</span>, in the non-degenerate case (i.e., where <span class="math-container">$\nu$</span> is differentiable)? Playing around with it, I'm pretty sure the answer is the following:</p>
<p><span class="math-container">$$\frac{\partial \nu}{\partial a_{ij}} = - y^*_i x^*_j$$</span></p>
<p>I even have the outlines of a (sketchy) &quot;proof&quot;, though it is not as simple or &quot;clean&quot; 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.</p>
<p>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?</p>

<reference-request><optimization><linear-programming><convex-optimization>
Linear Programming Sensitivity to Matrix
sd234
# Linear Programming Sensitivity to Matrix

(Asked by: username_0 on 2023-08-31)

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?

**Tags:** reference-request, optimization, linear-programming, convex-optimization

---

## 2 answers

### Answer by username_1 on 2023-09-04. Score: 1 | Accepted answer

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}

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: I agree. I must have been looking at an old version or something  
> **username_1**: I did update the answer as this form is clearer and more useful, but the old version was still correct.  
> **username_0**: 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!  

---

### Answer by username_1 on 2023-09-01. Score: 1

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}

> **Comments:**
> **username_0**: 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...  
> **username_1**: 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.  
> **username_0**: 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$.  
> **username_1**: 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.  

---

