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.

