5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ 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. $\endgroup$
    – Noah Stein
    Commented Sep 24, 2012 at 17:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Abhishek Kumar
    Commented Sep 24, 2012 at 18:53
  • 2
    $\begingroup$ 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. $\endgroup$
    – Noah Stein
    Commented Sep 24, 2012 at 19:07

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

The magic words are Spielman and Teng.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .