0
$\begingroup$

Just a quick question. So I'm taking a course in linear optimization, and one of the things that we're going over obviously is the simplex method. I just started the class so I may not be seeing the whole picture here, but I'm wondering why the method is so convoluted. In calculus classes we've gone over optimization problems and from what I understand, it wouldn't be much more work to just do the calculus instead of the simplex algorithm. Anyway, insight would be much appreciated!

$\endgroup$
2
$\begingroup$

Linear optimization can be interpreted as finding the highest points of an $n$-dimensional polyhedron. One of these points is necessarily a vertex, so it doesn't make sense to check anything other than the vertices. So the calculus approach would be just to check all the vertices and see which one is highest, right?

Unfortunately, the amount of vertices in your average linear optimization problem generally grows exponentially in the number of dimensions. This makes the calculus approach unusable very fast.

The simplex algorithm works by starting at any vertex, then moving from vertex to vertex along edges, always going up. There may be exponentially many vertices, but usually we only ever meet a linear amount of them before we reach the top of the polyhedron, so we save a huge bunch of processing time.

$\endgroup$
  • 1
    $\begingroup$ The simplex method is efficient in practice, but the worst case complexity is exponential. $\endgroup$ – copper.hat Jul 18 '16 at 14:24
  • $\begingroup$ @McFry I suppose that does make sense. I guess the tedious nature of it is a bit annoying to me. Thank you for the helpful explanation though! $\endgroup$ – Darpan Ganatra Jul 18 '16 at 14:28
  • $\begingroup$ @copper.hat That's why I said "usually". $\endgroup$ – Anon Jul 18 '16 at 14:32
  • 1
    $\begingroup$ In 1984 a big advance in efficient LP solving came about by traversing the interior of the feasible set rather than the vertices. $\endgroup$ – copper.hat Jul 18 '16 at 14:38

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.