5 ms·

Surprising limits discovered in quest for optimal solutions

43 points by theafh 5y ago

TuringTest 5y ago
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.
solarmist 5y ago
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 5y ago
  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.
  - solarmist 5y ago
    Ok, makes sense. I was thinking about it where the coefficients of the polynomial were the variables. That said I know nothing about optimization theory.

43 points by theafh 5y ago

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.

solarmist 5y ago

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 5y ago
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.
- solarmist 5y ago
  Ok, makes sense. I was thinking about it where the coefficients of the polynomial were the variables. That said I know nothing about optimization theory.