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

Is it possible to build such an objective function for a given set of constraints, so that there will be only one optimal solution?

My general problem is to get any vertex of a polytope formed by a set of given linear constraints. I need this in polynomial time.

If I use the ellipsoid method, I'll get an optimal solution for any objective function in polynomial time, BUT, this solution won't be necessary a vertex.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

A random objective will work. I don't think there is any (cheap) deterministic way of doing this. On the other hand, I don't really understand your issue with the ellipsoid method. Your solution will be on a lower-dimensional face of your polytope, so iterating your ellipsoid method at most $d$ times you will get a vertex, so you stay polynomial.

share|improve this answer
    
Igor, thanks. You mean iterating the ellipsoid with any objective every time? In that case, every iteration will lead to decrease in dimension (at least one constraint will hold with equality), so finally I'll end with dimension 0, i.e., vertex. Correct? –  Michael Sep 28 '11 at 9:38
    
Well, your objective function cannot be constant in the subspace you have arrived into, but checking the active equality constraints is cheap, so having checked them, you can pick an objective function $c^t x$ where $c$ lies in the subspace you are in. Then, as you say, you will end end up with dimension $0$ after at most $d$ steps. –  Igor Rivin Sep 28 '11 at 10:11
    
After finding one optimal point, perturb the objective function by a random very small amount, then solve again. With high probability, the new solution will an optimal vertex. –  Brendan McKay Sep 28 '11 at 10:31
    
Thanks a lot Igor, I think this will solve my problem. –  Michael Sep 28 '11 at 10:32
    
Brendan, only now I realized that the last comment was yours. So, thank you too for the help! –  Michael Sep 28 '11 at 10:35
show 3 more comments

It you add a quadratic perturbation to the linear objective, then you will end up getting a unique solution. This idea is described more rigorously in Normal solutions of linear programs

In a nutshell, say the objective function is $c^Tx$. To this we add $\epsilon x^Tx$ as the perturbation, then (here comes the catch), for small enough $\epsilon$, the perturbed problem solves the original problem. In fact, from among all the solutions to the original LP, the perturbed problem picks one of smallest $\ell_2$-norm.

share|improve this answer
    
Thank you Survit, I'll look at this paper. But can I be sure that returned solution (with the smallest L-2 norm) will be a vertex of the original polytope? –  Michael Sep 28 '11 at 10:17
    
Nope; I don't think you can ensure a vertex solution with this---just a unique one. –  Suvrit Sep 28 '11 at 11:37
    
OK, so it does not suit to me... What I need is a vertex (even any vertex). Thank you in any case! –  Michael Sep 28 '11 at 11:43
add comment

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.