# relation between solution of a linear program and its perturbation

I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$:

$$\max_j c' x_j$$

Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex of the convex polytope generated by these points.

Now, I perturb the linear function $c$ to $d$ such that $\lVert c -d\rVert_2 < \delta$, and perturb each point to $(y_1,y_2,\ldots,y_m)\in\mathbb{R}^n$ such that $\lVert x_j - y_j\rVert_2 < \epsilon$, and get the following perturbed linear program:

$$\max_j d' y_j$$

Suppose the solution of this perturbed LP is obtained at a point $y_{j_2}$. Are there any known upper bounds on $\lVert x_{j_1} - y_{j_2}\rVert_2$?

• There is no upper bound given only the conditions you specify, even if $y_i=x_i$ for all $i$. Consider a situation like $x_1=−x_2=M$ with $c=\frac{\delta}{3}$ and $d=−\frac{\delta}{3}$. Then the optimum jumps from $x_1$ to $x_2$ when switching from $c$ to $d$. In higher dimensions this can even happen if you require $c$ and $d$ to be normalized. So you would have to impose some stronger conditions to get a bound. Sep 24 '12 at 17:04
• What if we add an angle condition between $c$ and $d$, i.e. the angle is bounded? Any references on this problem will be appreciated. Sep 24 '12 at 18:53
• I'm afraid that won't help either. Let $n=m=2$, $x_1 = -x_2 = (M,0)$, $y_i = x_i$, and $c = -d = \left(\frac{\delta}{3},1\right)$. To say anything you would need to know that $c$ and $d$ relate to the $x_i$ and the $y_i$ in a way that somehow ruled out this kind of behavior. On the other hand, you certainly can say something about the objective value not changing by much; it is just the optimizer which can move drastically. Sep 24 '12 at 19:07