Linear programming is continuous

Question

Consider an arbitrary linear program:

$$\max \vec c \cdot \vec x$$

subject to:

$$\textbf{A}\cdot \vec x = 0, \quad \vec a \le \vec x \le \vec b$$

Assume that this program is feasible and bounded. Now suppose I perturb the bounds by small amounts:

$$\vec a' = \vec a + \delta \vec p, \quad \vec b' = \vec b + \delta \vec q$$

where $\vec p,\vec q$ are unit vectors and $\delta > 0$. Assume that the modified problem remains feasible and bounded.

Prove or disprove: For arbitrary $\epsilon > 0$, there exists a $\delta > 0$ such that there exist optimal solutions $\vec x, \vec x'$ to the original and perturbed linear programs (respectively) satisfying $|\vec x - \vec x'| < \epsilon$.

Extra: Is there a way to define uniform continuity in this context, such that Linear Programming is, or isn't, uniformly continuous?

Answer 1

The answer is no. Consider the probem $$x+y\to\max,$$ $$x\geq 0,\; y\geq 0,$$ $$x+y\leq 1.$$ It has infinitely many solutions. One of them is $(0,1)$. Now change the last inequality to $$x+(1+\epsilon)y=1.$$ The new problem has a unique solution $(1,0)$ which is not close to the solution of the first one.

One can also construct a counterexample with unique solution of the original problem:

Consider this $x\to\max$, under the restrictions $x\geq 0,\; y\geq 0$, $1\leq x+y\leq 1.$ The unique solution is $(1,0)$. Now you can perturb a little the last restriction, and you obtain a unique solution $(0,1)$.

Answer 2

You can get this kind of continuity if the optimal solution is nondegenerate in the following sense. Let the coefficient matrix be $m \times n$, and suppose there is a subset $B$ of $[1,\ldots,n]$ with cardinality $m$ (the "basic variables") such that the submatrix $A_B$ for columns in $B$ is invertible, and in your optimal solution the $x_j$ for $j \notin B$ are each equal to either $a_j$ or $b_j$, and the $x_j$ for $j \in B$ are strictly between $a_j$ and $b_j$.