5
$\begingroup$

I am working on a problem that involves finding optimal parameter values for a black-box system. This system consists of 6 inputs and produces a single output. I can compare the returned values to observed values to determine whether the system is well calibrated based on the parameter values I specified.

The main problem that I am having is that I do not know how these parameters are used in the black-box system to produce the output. The parameters may be correlated so changing the value of one parameter may affect the way the others behave in the system.

Since I do not know the function I am not sure how to optimize this problem efficiently.

Question: what are some methods for optimization when the function is unknown?


Edits:

The variable types are each a vector of real numbers but we can make some assumptions if it is is helpful.

The cost to run the black-box system is only time. Let's say that it takes 10 seconds to run the system but I happen to have five black boxes -- so if I can run my algorithm in parallel then I can cut down the run time. If the algorithm runs sequentially then I don't gain anything by having the extra boxes (expect perhaps choosing different starting positions).

For this problem I am interested in learning about how to solve this type of problem -- not trying to brute force my way to a solution. That is to say I am less interested in obtaining an answer and more finding out how I would obtain the the answer. I think it is easy to say that given sufficient resources (time, processing power) that simply generating many many random numbers and choosing the combination that gives the best result is the simplest (and probably worst) approach.

$\endgroup$
  • 1
    $\begingroup$ You have a lot of options. Could you clarify what the variable types are here (I suspect just a vector of real numbers for input and single real number for output - but this is critical, if any values are discrete integers, it changes what may work)? Could you also clarify what it costs you to call the black box - i.e. how many calls per second it could cope with? Also, how much you value your own time understanding more sophisticated optimisation approaches compared with simpler more brute-force approaches. $\endgroup$ – Neil Slater Sep 8 '15 at 18:08
  • $\begingroup$ I've amended the post to address your questions. If things are still ambiguous I can try to clarify them. $\endgroup$ – Ellis Valentiner Sep 8 '15 at 18:35
  • $\begingroup$ Hmm 1 call per 2 seconds may not be fast enough for simple generic solvers. Your premise in the question that there is a single optimal way how to find an answer is not necessarily correct. Random guessing is surprisingly efficient with the amount of unknowns you present so far. Can we make some assumptions such as function is continuous and differentiable everywhere, and has some general global shape (so we worry about local minima close to global minimum, not trying to find deepest valley in the Alps)? $\endgroup$ – Neil Slater Sep 8 '15 at 18:39
  • $\begingroup$ Sure. Let's assume that the function is continuous and differentiable. I suspect the global shape is Gaussian -- or at least unimodal. $\endgroup$ – Ellis Valentiner Sep 8 '15 at 18:52
3
$\begingroup$

There are lots of function optimising routines that could be applied, based on the description so far. Random search, grid search, hill-climbing, gradient descent, genetic algorithms, simulated annealing, particle swarm optimisation are all possible contenders that I have heard of, and I am probably missing a few.

The trouble is, starting with next to zero knowledge of the black box, it is almost impossible to guess a good candidate from these search options. All of them have strengths and weaknesses. To start with, you seem to have no indication of scale - should you be trying input parameters in any particular ranges? So you might want to try very crude searches through a range of magnitudes (positive and negative values) to find the area worth searching. Such a grid search is expensive - if you have $k$ dimensions and want to search $n$ different magnitudes, then you need to call your black box $n^k$ times.

This can be done in parallel though, and given you are confident that the function is roughly unimodal, you can start with a relatively low number of n (maybe check -10, -1, 0, +1, +10 for 15625 calls to your function taking roughly 8 hours 40 mins using 5 boxes). You may need to repeat with other params once you know whether you have found a bounding box for the mode or need to try yet more values, so this process could take a while longer - potentially days if the optimal value for param 6 is more like 20,000. You could also refine more closely, once you have a potential mode you might want to define another grid of values to search based around. This basic grid search might be my first point of attack on a black box system where I had no clue about parameter meaning, but some confidence that the black box output had a rough unimodal form.

Given the speed of response you should be storing all input and output values in a database for faster lookup and better model building later. No point repeating a call taking 10 seconds when a cache could look it up in 1 millisecond.

Once you have some range of values you think that a mode might be in, then it is time to pick a suitable optimiser.

Given the information so far, I would be tempted to run either more grid search (with a separate linear scaling between values of each param) and/or a random search, constrained roughly to the boxes defined by the set of $2^6$ corner points around the best result found in initial order-of-magnitude search.

At that point you could also consider graphing the data, to see if there is any intuition about which other algorithms could perform well.

With the possibility of parallel calls, then gradient descent might be a reasonable guess, because you can get approximate gradients by adding a small offset to each param and dividing difference that causes in the output by it. In addition, gradient descent (or simple hill climbing) has some chance of optimising with less calls to evaluate the function than approaches that rely on many iterations (simulated annealing) or lots of work in parallel (particle swarm or genetic algorithms). Gradient descent optimisers as used in neural networks, with additions like Nesterov momentum or RMSProp, can cope with changes in function output "feature scale" such as different sizes and heights of peaks, ridges, saddle points.

However, gradient descent and hill climbing algorithms are not robust against all function shapes. A graph or several of what your explorations are seeing may help you to decide on a different approach. So keep all the data and graph it in case you can get clues.

Finally, don't rule out random brute-force search, and being able to just accept "best so far" under time constraints. With low knowledge of the internals of the black box, it is a reasonable strategy.

|improve this answer|||||
$\endgroup$
2
$\begingroup$

Since no one has mentioned bayesian optimization yet: "Bayesian optimization is a sequential design strategy for global optimization of black-box functions."

At the bottom of that wikipedia page are links to several bayesian optimization libraries like:

Besides libraries using bayesian optimization there are also libraries using TPE (trees of parzen estimators), like hyperopt.

Here's an image of fmfn's bayesian optimizer optimizing a non-linear 2d function. As you can see, a point close to the global optimum is found after relatively few iterations and the system tests more points in more promising (red) areas than in less promising (blue) areas - making it more efficient than random search:

bayesian optimization of a 2d function (full animation)

|improve this answer|||||
$\endgroup$
-1
$\begingroup$

Here is a solution.

A mathematical method is described in this paper

|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ Link-only answers are discouraged; summarize what about these resources answers the question $\endgroup$ – Sean Owen May 18 '16 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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