# Linear programming is continuous

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?

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)$.

• I misstated the question, sorry. Your answer made me see the issue. Can you please look at the updated question? – becko Jan 30 '17 at 20:42
• @becko: My second example disproves the new conjecture. – Alexandre Eremenko Jan 31 '17 at 7:57
• The correct conditions that ensure continuity are stated in the answer of Robert Israel. – Alexandre Eremenko Jan 31 '17 at 7:59
• I don't understand the second example. How exactly do you perturb the last restriction? – becko Jan 31 '17 at 13:28
• Replace the last restriction by $1\leq y+(1-\epsilon)x$ and $x+y\leq 1$. Together with $x\geq 0$, $y\geq 0$ the only feasible point is $(0,1)$. – Alexandre Eremenko Jan 31 '17 at 19:52

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