Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a parametrized LP problem

find x, that minimizes F*x

such that Ax <=Bt+D

where t is a parameter.

And suppose C(t) is a set of all optimal solutions of LP with parameter t.

Let x_L(t) be a lexicographic minimum of C(t).

I interested on prooving that x_L(t) is a continoues function of t?

Did anyone meet such a statement in papers?

share|improve this question

1 Answer 1

You've chosen a somewhat limited form of "parametric LP" here. It's more common to allow $F$ to vary as $F=F_{0}+tF_{1}$. For that more general variety of parametric LP, the conjecture is false- it's easy to construct a counterexample. For example, consider

$\min tx_{1}+x_{2}$

$x_{1}+x_{2}=1$

$x \geq 0$

What happens as t varies from $t<1$ to $t=1$ to $t>1$?

You could also consider parametric changes in $A$- the conjecture is also false for that case.

Returning to the problem as stated:

It's easy to construct examples where the LP becomes infeasible at some values of $t$. You'll need to exclude such values of $t$.

Since this posting looks like it could well be a homework exercise, I'll simply outline an approach that you might use to prove this. First note that the basic feasible solutions (BFS's) for your parametric system of inequalities are (except at values of $t$ where a BFS vanishes or first appears) continuous functions of $t$. Also note that for each value of $t$, the set of optimal solutions is the convex hull of these BFS's. Finally, show that $x_{L}(t)$ is always at a BFS. Now, go back and think about what happens at those values of $t$ where BFS's vanish or appear.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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