Find global minimum of discretely defined function

Question

I have a four parameter function for which I do not have the mathematical form because it is actually the result of several separate processes. In its simplest form it can be thought of as a black box which returns a value that depends on the values of the parameters a,b,c,d it is called with. This is what it looks like:

def my_func(a, b, c, d):
    # Make lots of calculations here to come up with 'func_value',
    # which depends on the values of the parameters given a,b,c,d.
    func_value = x(a, b, c, d)
    return func_value

The space of those four parameters is restricted not only in range but it is also discrete. This means that the parameters can have certain values:

a = [0.004, 0.006, 0.008, 0.010, ...]
b = [0.2, 0.25, 0.3, 0.35, ...]
c = [0.0, 0.01, 0.02, 0.03, ...]
b = [10.1, 10.2, 10.3, 10.4, ...]

and not those in between (ie: they vary in steps).

I need to find the global minimum for this function, ie: the set composed of those particular parameters values [a_i,b_j,c_k,d_l] that returns the minimum value possible for my_func.

I know of the existence of algorithms such as scipy.optimize.anneal or genetic algorithms like those defined in DEAP, PyBrain or Pyevolve that should be applicable to this kind of optimization problems.

What I'm not sure of is which one I could use having in mind the restrictions imposed by my code, ie: multiple (four) parameters function with no mathematical form, restricted and discrete spaces for the parameters.

Reviewing all of those methods can take a lot of time, so any pointers as to what I should probably be trying to apply will be much appreciated.

Answer 1

All "hill-climbing" algorithms depend on the assumption that small changes in the input result in (typically) small changes in the output. Your description of the problem includes absolutely no restrictions on the form of the function graph (except for your interest in probabilistic hill climbing, which implies that it does apply to your domain). You couldn't use hill climbing on a cryptographic hash function, for example.

But the best algorithm depends largely on additional characteristics of the problem:

1. Simulated annealing starts with large "jumps" that get progressively smaller, the idea being that you end up on the largest "hill" (or valley, since you formulate your goal as a minimum) before your jumps get too small and you get trapped there.

2. The genetic algorithm is good when the different parameters, or groups of them, are semi-independent of each other. The idea is that the small groups of parameters can be independently optimized by local hill-climbing, and the recombination function may bring together several optimized sub-groups to produce a super-solution. It is useless if all parameters are tightly coupled.

Other algorithms are similarly best suited to different problem profiles. (And unfortunately, your problem description doesn't seem to include the relevant properties.)

In short: While a mathematical formula is not a requirement, you do need some understanding of how the graph of your function behaves, and any projection invariants (quantities that contribute to x but do not depend on all four parameters a, b, c, d). This last will also be helpful for speeding up the calculation of the function's values, which as you say is extremely expensive. I would suggest you at least graph some low-resolution slices across your search space. They might give you some ideas.

PS. If the quality of the solution is more important than calculation time, you could always implement several approaches, run them in parallel, and keep the best solution.

Answer 2

As you mentioned it is a common optimization problem. The mathematical formula is very rarely required, since in practice we rarely have it. One important feature which simplifies a lot is the convexity of the function (again you don't need to think of it in terms of mathematical formulas but rather if the global maximum is unique).

For the beginning I would suggest one of following classical algorithms:

• http://en.wikipedia.org/wiki/Simulated_annealing
• http://en.wikipedia.org/wiki/Tabu_search
• http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms