[HN Gopher] The Simplex Solution: Why it works so well
       ___________________________________________________________________
        
       The Simplex Solution: Why it works so well
        
       Author : haltingproblem
       Score  : 29 points
       Date   : 2022-06-18 14:38 UTC (8 hours ago)
        
 (HTM) web link (www.technologyreview.com)
 (TXT) w3m dump (www.technologyreview.com)
        
       | acbart wrote:
       | 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.
        
         | adhesive_wombat wrote:
         | 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.
        
         | npalli wrote:
         | 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
         | 
         | The two authors won the Godel prize in 2008 for this work.
        
         | [deleted]
        
       | spullara wrote:
       | Should be updated with (2003)
        
       | Invictus0 wrote:
       | I had never heard of this: I thought they were talking about the
       | Nelder-Mead simplex algorithm.
       | 
       | https://en.wikipedia.org/wiki/Simplex_algorithm
        
         | anonymousiam wrote:
         | This is taught in undergrad college-level statistics. Back when
         | I learned it, it was referred to as the Simplex Tableau.
        
         | 7thaccount wrote:
         | 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.
        
         | odiroot wrote:
         | I still have the trauma from failing that during my first year
         | at my uni.
        
       | d--b wrote:
       | Never had much luck with simplex in practice. BGFS optimizers
       | worked much better for me...
        
         | YetAnotherNick wrote:
         | 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.
        
       | dmarchand90 wrote:
       | 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 wrote:
         | Specifically for this method, it is (or used to be) included in
         | A-level "decision maths", which also includes things like
         | Dijkstra's algorithm.
         | 
         | Those textbooks, which include examples and methods might be a
         | good start?
        
       ___________________________________________________________________
       (page generated 2022-06-18 23:01 UTC)