Welcome to MathOverflow

Question

5

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$?

flag	asked Sep 24 at 16:46 Abhishek Kumar 75●4

4

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. – Noah Stein Sep 24 at 17:04

1

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. – Abhishek Kumar Sep 24 at 18:53

1

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. – Noah Stein Sep 24 at 19:07

Igor Rivin · Answer 1 · 2012-09-24 19:59:26Z UTC

1

The magic words are Spielman and Teng.

answered Sep 24 at 19:59

Igor Rivin
31.1k●3●37●71

relation between solution of a linear program and its perturbation

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.