How to maximize non-analytic function over space of variables

Question

I have a very simple question that I thought there might be a solution online but I couldn't find one yet.

I have a (non-mathematical i.e. non-analytical) function that computes a value F based on a set of variables a,b,c,d that come from a set of files/databases/online crawling and I want to find the set of variables a,b,c,d that maximizes F. Searching the whole space of a,b,c,d is not feasible, and using differentials / derivatives is not possible since F is not analytical. I would really appreciate a pointer to which packages/algorithms I could use please, or just how to get started. Much of what I've seen online about python optimization seems to be about analytical/math functions (f(x) = x^2 + ...) and not more non-analytical problems.

For example:

def F(a,b,c,d):
   ... a lot of computations from databases, etc using 
   a,b,c,d that are different float values ...
   returns output # output is a float

Now, for all values of a,b,c,d where each has possible values let's say [0, 0.1, 0.2, ... 1.0]. The values are discrete and I don't need extreme precision in my optimization.

Now, I want to find the set of values a,b,c,d that gives me the highest F.

Oh, and I have no maximization constraints on either F, a, b, c, d..

Answer 1

For a non-analytic function you could explore the parameter space with a genetic algorithm or similar evolutionary computation. Then look for maxima or "hills" within the resultant space to find the solution that maximizes your function. I would suggest using a library rather than writing it yourself; DEAP looks quite promising.

Answer 2

You've broken down your problem very well. This is, as you seem to know, space search.

I don't know about libraries for doing this in any language except Prolog (where it's actually the language itself that is the solution engine), but one of the most generally useful space search algorithms is "A star" search, also known as "heuristic-guided optimization". Your problem looks like it lends itself to a nice neighbor of A-star search called "greedy best-first search".

You basically start with some set of parameters, call F on those parameters, and then tweak each parameter a bit to see how F changes. You head "uphill", accepting the tweak that makes F increase by the greatest amount and potentially setting aside the "other" paths to be searched later. This greedily moves you toward a "hilltop" - a local maximum. Once you reach the local maximum you can try searching again from some random combination of parameters. You can even use something like simulated annealing to decrease the amount you tweak the parameters by as time goes on - at first searching very chaotically, and then settling down once you know the vague problem terrain.

The only way to guarantee an optimal result is to do a complete search, like BFS, but there are many good ways to make it very probabalistically likely you get an optimal result out. Which one will give you the best results fastest depends on F: the hill climbing I presented here is best if the mapping between inputs and outputs is at least close to a contiguous topology with few discontinuities.