6 ms·

The Simplex Solution: Why it works so well

acbart 4y ago
This article, unless I'm missing something, doesn't actually explain why the algorithm works so well. It just gives the back story that led to the journal paper explaining it.
- npalli 4y ago
  The article discusses how the two mathematicians (Spielman and Teng) came up with Smoothed Analysis for Algorithms (as opposed to Worst case) which gives insight into why Simplex works well. We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity https://arxiv.org/abs/cs/0111050 https://arxiv.org/abs/cs/0111050 The two authors won the Godel prize in 2008 for this work.
- deleted 4y ago
  [deleted]
- adhesive_wombat 4y ago
  It doesn't even seem to say what the algorithm does, just that it's very commonly used. I had completely forgotten I used to solve by hand at school until I looked it up: the article didn't jog that memory at all.
Invictus0 4y ago
I had never heard of this: I thought they were talking about the Nelder-Mead simplex algorithm. https://en.wikipedia.org/wiki/Simplex_algorithm https://en.wikipedia.org/wiki/Simplex_algorithm
- odiroot 4y ago
  I still have the trauma from failing that during my first year at my uni.
- 7thaccount 4y ago
  I assume they just mean the main algorithm behind linear programming. Other methods are interior point I think and maybe barrier? It truly is massively important and something companies use all the time.
  - wenc 4y ago
    The Simplex method for solving LPs is fundamental to linear programming and is still widely used. Interior point and barrier at the same thing. Interior point is a worst-case polynomial algorithm, while simplex is worst-case exponential. Despite this, the simplex algorithm remains competitive on the average case.
- anonymousiam 4y ago
  This is taught in undergrad college-level statistics. Back when I learned it, it was referred to as the Simplex Tableau. https://dl.acm.org/doi/pdf/10.1145/87252.88081 https://dl.acm.org/doi/pdf/10.1145/87252.88081
spullara 4y ago
Should be updated with (2003)
- wenc 4y ago
  Yes, smoothed analysis has been around for a long time -- it's not new.
dmarchand90 4y ago
Does anyone have a good resource for learning more about a method? I'm looking for something that's relatively accessible yet still sufficiently technical (programmer technical, not mathematically robust technical)
- adhesive_wombat 4y ago
  Specifically for this method, it is (or used to be) included in UK A-level "decision maths", which also includes things like Dijkstra's algorithm. Those textbooks (and other resources, they invented YouTube since then), which include examples and methods might be a good start?
d--b 4y ago
Never had much luck with simplex in practice. BGFS optimizers worked much better for me…
- YetAnotherNick 4y ago
  They don't even solve the same problem. Simplex works with only linear objective, BGFS works with only unconstrained R^n domain. You possibly cannot have a non trivial problem in which both are true.
  - wenc 4y ago
    This is a common confusion. Both OP and GP are talking about two different simplex methods. Simplex refers to two algorithms: [1] Simplex method for solving LPs, initially proposed by George Dantzig. [2] Nelder-Mead Simplex method, which is a derivative-free algorithm for nonlinear functions. The article refers to [1] whereas the GP probably referred to [2]. Nelder-Mead simplex only requires function evaluations, which makes it amenable to situations where the derivative evaluations are impossible or the function evaluations are expensive (like a simulation). BFGS approximates the Hessian (2nd order derivative) and will generally outperform Nelder Mead unless derivatives are not available or if the terrain has lots of local optima or saddle points. [1] https://en.wikipedia.org/wiki/Simplex_algorithm https://en.wikipedia.org/wiki/Simplex_algorithm [2] https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method
ad1032 4y ago
This has been fascinating me recently. I've been trying to implement it as a general 'engine control' solver in the game Space Engineers. It seems to be a perfect tool for the task but actually turning it into working code seems to exceed my skills.

This article, unless I'm missing something, doesn't actually explain why the algorithm works so well. It just gives the back story that led to the journal paper explaining it.

npalli 4y ago
The article discusses how the two mathematicians (Spielman and Teng) came up with Smoothed Analysis for Algorithms (as opposed to Worst case) which gives insight into why Simplex works well. We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity https://arxiv.org/abs/cs/0111050 https://arxiv.org/abs/cs/0111050 The two authors won the Godel prize in 2008 for this work.
deleted 4y ago
[deleted]
adhesive_wombat 4y ago
It doesn't even seem to say what the algorithm does, just that it's very commonly used. I had completely forgotten I used to solve by hand at school until I looked it up: the article didn't jog that memory at all.

Invictus0 4y ago

I had never heard of this: I thought they were talking about the Nelder-Mead simplex algorithm. https://en.wikipedia.org/wiki/Simplex_algorithm https://en.wikipedia.org/wiki/Simplex_algorithm

odiroot 4y ago
I still have the trauma from failing that during my first year at my uni.
7thaccount 4y ago
I assume they just mean the main algorithm behind linear programming. Other methods are interior point I think and maybe barrier? It truly is massively important and something companies use all the time.
- wenc 4y ago
  The Simplex method for solving LPs is fundamental to linear programming and is still widely used. Interior point and barrier at the same thing. Interior point is a worst-case polynomial algorithm, while simplex is worst-case exponential. Despite this, the simplex algorithm remains competitive on the average case.
anonymousiam 4y ago
This is taught in undergrad college-level statistics. Back when I learned it, it was referred to as the Simplex Tableau. https://dl.acm.org/doi/pdf/10.1145/87252.88081 https://dl.acm.org/doi/pdf/10.1145/87252.88081

spullara 4y ago

Should be updated with (2003)

wenc 4y ago
Yes, smoothed analysis has been around for a long time -- it's not new.

dmarchand90 4y ago

Does anyone have a good resource for learning more about a method? I'm looking for something that's relatively accessible yet still sufficiently technical (programmer technical, not mathematically robust technical)

adhesive_wombat 4y ago
Specifically for this method, it is (or used to be) included in UK A-level "decision maths", which also includes things like Dijkstra's algorithm. Those textbooks (and other resources, they invented YouTube since then), which include examples and methods might be a good start?

d--b 4y ago

Never had much luck with simplex in practice. BGFS optimizers worked much better for me…

YetAnotherNick 4y ago
They don't even solve the same problem. Simplex works with only linear objective, BGFS works with only unconstrained R^n domain. You possibly cannot have a non trivial problem in which both are true.
- wenc 4y ago
  This is a common confusion. Both OP and GP are talking about two different simplex methods. Simplex refers to two algorithms: [1] Simplex method for solving LPs, initially proposed by George Dantzig. [2] Nelder-Mead Simplex method, which is a derivative-free algorithm for nonlinear functions. The article refers to [1] whereas the GP probably referred to [2]. Nelder-Mead simplex only requires function evaluations, which makes it amenable to situations where the derivative evaluations are impossible or the function evaluations are expensive (like a simulation). BFGS approximates the Hessian (2nd order derivative) and will generally outperform Nelder Mead unless derivatives are not available or if the terrain has lots of local optima or saddle points. [1] https://en.wikipedia.org/wiki/Simplex_algorithm https://en.wikipedia.org/wiki/Simplex_algorithm [2] https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method

ad1032 4y ago

This has been fascinating me recently. I've been trying to implement it as a general 'engine control' solver in the game Space Engineers. It seems to be a perfect tool for the task but actually turning it into working code seems to exceed my skills.