most recent 30 from http://mathoverflow.net 2013-05-18T18:52:16Z http://mathoverflow.net/feeds/question/6449 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6449/searching-global-minima-fast pacificmoth 2009-11-22T09:46:27Z 2009-11-22T19:46:18Z

<p>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?</p> <p> 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| &lt; 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.</p>

http://mathoverflow.net/questions/6449/searching-global-minima-fast/6461#6461 Martin M. W. 2009-11-22T13:39:56Z 2009-11-22T13:45:40Z

<p>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 <a href="http://en.wikipedia.org/wiki/No%5Ffree%5Flunch%5Fin%5Fsearch%5Fand%5Foptimization" rel="nofollow">no free lunch theorem</a>.</p> <p>But for some classes of functions an upper bound could be helpful, so you might want to provide more details of your situation.</p>