6
$\begingroup$

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?

$\endgroup$

2 Answers 2

7
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ I misstated the question, sorry. Your answer made me see the issue. Can you please look at the updated question? $\endgroup$
    – valle
    Jan 30, 2017 at 20:42
  • $\begingroup$ @becko: My second example disproves the new conjecture. $\endgroup$ Jan 31, 2017 at 7:57
  • $\begingroup$ The correct conditions that ensure continuity are stated in the answer of Robert Israel. $\endgroup$ Jan 31, 2017 at 7:59
  • $\begingroup$ I don't understand the second example. How exactly do you perturb the last restriction? $\endgroup$
    – valle
    Jan 31, 2017 at 13:28
  • 1
    $\begingroup$ 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)$. $\endgroup$ Jan 31, 2017 at 19:52
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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