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?


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.