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


Your Answer


Browse other questions tagged or ask your own question.