Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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 '12 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 '12 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 '12 at 19:07

2 Answers 2

I think that Igor refers to "smoothed analysis", which has been invented by Spielman and Teng to explain the performance of the simplex method. However, their result does not make a statement about how the optimal solution changes by the perturbation. Furthermore, for their result - a polynomial upper bound for the running-time of simplex, where the randomness is over the perturbation - it is crucial that the matrix describing the linear constraints is perturbed.

Without any further information about the polytope and how the objective function is perturbed (e.g., randomly or deterministically), it seems to be impossible to say anything useful - see Noah's comment, for instance.

share|improve this answer

The magic words are Spielman and Teng.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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