Searching global minima fast?

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.

-

You need more information to do anything useful. (An upper bound on the global minimum isn't very special--you can sample your function at any point to get one.) Without additional restrictions on your function you're still in the realm of the no free lunch theorem.

But for some classes of functions an upper bound could be helpful, so you might want to provide more details of your situation.

-
Thanks Martin. 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. – pacificmoth Nov 22 2009 at 19:40
A fact like that would require additional hypotheses on the class of functions you're optimizing. (See the "no free lunch" argument linked above.) Can you say anything more about your application? – Martin M. W. Nov 22 2009 at 20:43
Actually I am not sure what kind of prior information I should be checking. It is probably not invariant to solution space permutation (the NFL condition as you suggested). Maybe not sub-modular either. Do you have any suggestions on the properties that I should be looking for? On the other hand, I'm not looking for a polynomial global minimum solver. Instead, it would be good enough to me if any polynomial approximate solver can be improved, e.g. from N<sup>2</sup> to N logN, when the upper bound information or any prior information provided. – pacificmoth Nov 23 2009 at 0:59
Nothing like that springs to mind. (My intuition is also that there are limits to the practical speed-up a bound can give you, because otherwise you could, without knowing any nontrivial bound, probably try out a well-chosen series of potential bounds. But I won't try to make that precise.) Maybe someone else can help more... Good luck with your optimization. – Martin M. W. Nov 23 2009 at 13:46
Thanks again. Appreciate your input. – pacificmoth Nov 23 2009 at 20:03