2
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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}

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – sd234
    Sep 6, 2023 at 0:26
  • $\begingroup$ 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. $\endgroup$ Sep 6, 2023 at 22:43
  • $\begingroup$ I agree. I must have been looking at an old version or something $\endgroup$
    – sd234
    Sep 7, 2023 at 23:19
  • $\begingroup$ I did update the answer as this form is clearer and more useful, but the old version was still correct. $\endgroup$ Sep 8, 2023 at 0:10
  • $\begingroup$ 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! $\endgroup$
    – sd234
    Sep 8, 2023 at 1:07
1
$\begingroup$

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}

$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$
    – sd234
    Sep 1, 2023 at 23:22
  • $\begingroup$ 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. $\endgroup$ Sep 2, 2023 at 0:35
  • $\begingroup$ 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$. $\endgroup$
    – sd234
    Sep 2, 2023 at 4:20
  • $\begingroup$ 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. $\endgroup$ Sep 3, 2023 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.