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

Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\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.

Improve this answer
$\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
    Commented Sep 28, 2011 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
    Commented Sep 28, 2011 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$
    – Brendan McKay
    Commented Sep 28, 2011 at 10:31
  • $\begingroup$ Brendan, only now I realized that the last comment was yours. So, thank you too for the help! $\endgroup$
    – Michael
    Commented Sep 28, 2011 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
    Commented Sep 28, 2011 at 10:42
2
$\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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Sep 28, 2011 at 10:17
  • $\begingroup$ Nope; I don't think you can ensure a vertex solution with this---just a unique one. $\endgroup$
    – Suvrit
    Commented Sep 28, 2011 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
    Commented Sep 28, 2011 at 11:43
  • 1
    $\begingroup$ The link to springerlink.com is broken, but the article can be found at doi:10.1007/BFb0121017 (Zbl 0588.90058). $\endgroup$
    – The Amplitwist
    Commented Dec 18, 2022 at 13:22
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.

Improve this answer
$\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.