Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

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.

share|improve this answer
    
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 '09 at 19:40
1  
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 '09 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 '09 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 '09 at 13:46
    
Thanks again. Appreciate your input. –  pacificmoth Nov 23 '09 at 20:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.