I am minimizing a highly non-linear function. If I know the global minimum is at most some value, is this information helpful to design a faster algorithm than random restart?
If we know an upper bound B so far, can we prove something like this, with a high probability, within M local minima visits, we will reach a local minimum B', and we have |B'-G| < eta|B-G|, where G is the unknown global minimum. And M is some polynomial function of eta, and maybe the dimension of the solution space.
