3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Michael
    Sep 28 '11 at 9:38
  • $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Sep 28 '11 at 10:11
  • $\begingroup$ 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. $\endgroup$ Sep 28 '11 at 10:31
  • $\begingroup$ Brendan, only now I realized that the last comment was yours. So, thank you too for the help! $\endgroup$
    – Michael
    Sep 28 '11 at 10:35
  • $\begingroup$ @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... $\endgroup$
    – Igor Rivin
    Sep 28 '11 at 10:42
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Michael
    Sep 28 '11 at 10:17
  • $\begingroup$ Nope; I don't think you can ensure a vertex solution with this---just a unique one. $\endgroup$
    – Suvrit
    Sep 28 '11 at 11:37
  • $\begingroup$ OK, so it does not suit to me... What I need is a vertex (even any vertex). Thank you in any case! $\endgroup$
    – Michael
    Sep 28 '11 at 11:43
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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