0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

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