[HN Gopher] Surprising limits discovered in quest for optimal so...
       ___________________________________________________________________
        
       Surprising limits discovered in quest for optimal solutions
        
       Author : theafh
       Score  : 29 points
       Date   : 2021-11-01 14:22 UTC (8 hours ago)
        
 (HTM) web link (www.quantamagazine.org)
 (TXT) w3m dump (www.quantamagazine.org)
        
       | solarmist wrote:
       | This result seems bizarre.
       | 
       | You can always increase the dimension of an equation in trivial
       | ways.
       | 
       | Why would injection of a dummy variable into a quadratic, to make
       | it cubic, make it more tractable?
       | 
       | *edit: a couple of notes from the article that point towards
       | hints, maybe?
       | 
       | "Could they do it for cubic optimization problems that carry the
       | simplifying condition that they incorporate no constraints?"
       | 
       | "Knowing that both "apple" and "orange" appear would make you
       | more confident, but you could still be wrong (Orange is a company
       | too). A third term like "melon" introduces a cubic relationship
       | and might allow you to confidently conclude the text is talking
       | about produce."
       | 
       | Seems like it's related to context, there maybe too little
       | context in a quadratic equation to optimize it well.
        
         | adrian_b wrote:
         | The results are not about the number of variables, but about
         | the degree of the polynomial that is the optimization target.
         | 
         | To increase the degree of a polynomial, adding a dummy variable
         | does not help.
         | 
         | You need to add at least one term to the polynomial that is the
         | product of 3 variables.
         | 
         | I do not see how you can add such a term without changing the
         | value of the function that must be optimized. If you add a
         | dummy variable and you add a term that is the product of 2
         | variables with the dummy variable, then the optimizer will find
         | an optimal solution for a non-zero value of the dummy variable,
         | which will offer no hint about the optimum for the original
         | polynomial.
        
       | TuringTest wrote:
       | My company makes a living by algorithmically finding solutions to
       | complex applied mathematical problems.
       | 
       | Theoretically, the best thing to do is to find an optimal
       | solution to the problem -even if it is a local optimum- as this
       | means that you can stop looking for more.
       | 
       | However, in practice, the user in many cases will not care
       | whether the algorithm will approximate the optimal solution a few
       | more decimal places; what matters is that the solution does not
       | have any major drawbacks, so that it can be safely used for its
       | intended purpose; and that it is better of what one expert could
       | find in the same time by hand. That's the reason why approximate
       | algorithms are used so often.
       | 
       | Under those constraints, you're better off with an anytime
       | algorithm with a good heuristic, which gives a viable good-enough
       | suboptimal solution fast, and which can be left running while the
       | expert analyzes the best solution found so far, to decide if it
       | is acceptable.
        
       ___________________________________________________________________
       (page generated 2021-11-01 23:02 UTC)