3

Let $x^*$ be the solution of the following LP:

$$ \begin{array}{c l} \underset {x} {\mathrm{minimize}} & c^{\mathrm{T}} x\\ \mathrm{subject~to}~& A x = b. \end{array} $$

Let $\hat{x}^*$ be the solution of

$$ \begin{array}{c l} \underset {x} {\mathrm{minimize}} & c^{\mathrm{T}} x\\ \mathrm{subject~to}~& A x = b + \Delta b. \end{array} $$

What is the relationship between $x^*$ and $\hat{x}^*$? For example:

  1. Can we derive $\hat{x}^*$ based on $x^*$ without solving the second LP? or

  2. Can we obtain any upper/lower bounds on $c^{\mathrm{T}} \hat{x}^*$?

Ryan
  • 655
  • 3
    HINT : dual variables. – Kuifje Feb 09 '23 at 09:19
  • Question: is $A$ full rank? If so you can simply apply a changement of variables such that defining $z=x-y$ with $Ay=\Delta b$ then solve for $c^T(z+y)$ instead with $y$ fixed. You'd get the same question with a shift, which doesn't affect the minimization. – Omer Feb 14 '23 at 15:14
  • $x\ge 0$, right, because you said this is an LP? – Alex K Feb 14 '23 at 20:53
  • @Omer Thanks very much. Yes, if $A$ has full row rank, $\Delta b$ is in the range space of $A$, and we can translate the solution :-) – Ryan Feb 15 '23 at 04:39
  • @AlexK Thanks so much for your comments. In the current stage, I only consider a very special case with equality constraints. But I will consider more general cases later. – Ryan Feb 15 '23 at 04:43

0 Answers0