Timeline for Linear programming - uniqueness of optimal solution
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 29, 2011 at 11:54 | comment | added | Michael | Yes, I need any vertex of the polytope due to its properties that I want to use: at every vertex there are at least d constraints that hold with equality. | |
| Sep 29, 2011 at 7:52 | comment | added | Brendan McKay | @Igor: If he just wants any vertex, you are right. I thought he wanted a vertex optimizing some objective function, which is what my suggestion will achieve. | |
| Sep 28, 2011 at 10:42 | comment | added | Igor Rivin | @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, 2011 at 10:35 | comment | added | Michael | Brendan, only now I realized that the last comment was yours. So, thank you too for the help! | |
| Sep 28, 2011 at 10:32 | vote | accept | Michael | ||
| Sep 28, 2011 at 10:31 | comment | added | Brendan McKay | 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, 2011 at 10:14 | vote | accept | Michael | ||
| Sep 28, 2011 at 10:14 | |||||
| Sep 28, 2011 at 10:11 | comment | added | Igor Rivin | 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, 2011 at 9:38 | comment | added | Michael | 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, 2011 at 9:07 | history | answered | Igor Rivin | CC BY-SA 3.0 |