Continuity of Lexicographic Minimum Solution of a parametrized LP problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T06:59:00Z http://mathoverflow.net/feeds/question/97385 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97385/continuity-of-lexicographic-minimum-solution-of-a-parametrized-lp-problem Continuity of Lexicographic Minimum Solution of a parametrized LP problem marksgl 2012-05-19T10:18:29Z 2012-06-16T23:22:00Z <p>Given a parametrized LP problem</p> <p>find x, that minimizes F*x</p> <p>such that Ax &lt;=Bt+D</p> <p>where t is a parameter.</p> <p>And suppose C(t) is a set of all optimal solutions of LP with parameter t.</p> <p>Let x_L(t) be a lexicographic minimum of C(t).</p> <p>I interested on prooving that x_L(t) is a continoues function of t?</p> <p>Did anyone meet such a statement in papers?</p> http://mathoverflow.net/questions/97385/continuity-of-lexicographic-minimum-solution-of-a-parametrized-lp-problem/97436#97436 Answer by Brian Borchers for Continuity of Lexicographic Minimum Solution of a parametrized LP problem Brian Borchers 2012-05-19T21:28:13Z 2012-05-19T21:28:13Z <p>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</p> <p>\$\min tx_{1}+x_{2}\$</p> <p>\$x_{1}+x_{2}=1\$</p> <p>\$x \geq 0\$</p> <p>What happens as t varies from \$t&lt;1\$ to \$t=1\$ to \$t>1\$? </p> <p>You could also consider parametric changes in \$A\$- the conjecture is also false for that case. </p> <p>Returning to the problem as stated:</p> <p>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\$.</p> <p>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. </p>