1
$\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. Let $\vec x$ be an optimal solution.

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 exists an optimal solution $\vec x'$ to the perturbed linear program defined above 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.