# Global optimization problem, whats a good approach? Branch and bound method?

Problem: Given a 4-dimensional parameter space. We place bounds on the parameter, say, 0 to 100, so that we have a 4-dimensional rectangle as a search space.

We have a cost function that takes the 4d coordinate as input, and outputs a value from 0 to 1.

Initially, the search space is empty. We'd like to find the global maximum of the cost function within the search space.

An exhaustive search is much too computationally intensive.

Would a branch and bound method work? If so, what do I need to know about my cost function so that I can construct lower and upper bounds?

-
Branch and bound is typically used for discrete (integer) variables; is that what you have? – jbowman Jun 29 '12 at 18:02

I am aware that you can use branch and bound for global optimization of continuous real variables defined on closed domains like yours. Basically, one can divide the domain in two and find global optimum for the subdomains by using a recursive branch and bound approach. For some classes of functions, it is guaranteed that there will always exist a subdomain where the function is convex. In this case, the dividing procedure stops.

This link is useful for you:

http://see.stanford.edu/materials/lsocoee364b/17-bb_slides.pdf

Also, you might look for other techniques, such as interval methods for global optimization. There are books on this.

Also, it is worth to have a look on genectic algorithms. They can solve many complex problems with plausible quality, so I think your problem should not be difficult.

-