# Linear programming - uniqueness of optimal solution

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.

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.

• 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? 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. 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. Sep 28 '11 at 10:31
• Brendan, only now I realized that the last comment was yours. So, thank you too for the help! Sep 28 '11 at 10:35
• @Brendan: Why do you need to find an optimal point in the first place? As I suggest in my answer, just a random objective should work fine. I assumed the OP wanted to avoid randomness for some reason... Sep 28 '11 at 10:42

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.

• 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? Sep 28 '11 at 10:17
• Nope; I don't think you can ensure a vertex solution with this---just a unique one. 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! Sep 28 '11 at 11:43

You can still use simplex algorithm. More precisely, its phase I produces a vertex by solving another linear programming problem by simplex algorithm (but there an initial solution is trivial).

Of course, worst-case complexity of simplex algorithm is exponential but it is polynomial on average and you should be unlucky to encounter the worst case.