10
$\begingroup$

There is an enormous amount of information about the common applied math problem of minimizing a function.. software packages, hundreds of books, research, etc. But I still have not found a good reference for the case where the function to be sampled is extremely expensive.

My specific problem is an applied one of computer science, where I have a simulation which has databases with a dozen parameters that affect voxel sizes, cache distribution, tree branching, etc. These numeric parameters don't affect the algorithm correctness, just runtime. I want to minimize runtime.

Thus, I can treat the problem like a black box minimization. My cost function is runtime, which I want to minimize. I don't have derivatives, and I can treat it like a black box. I have a decent starting point and even rough scales of each parameter. There can be interations and correlations between parameters and even noise in time measurements (luckily small.)

So why not just throw this into a standard least-squares minimization tool, using any package out there? Because my timing samples each take 8 hours to run.. so each data point is precious, and the algorithms I find tend to ignore this cost. A classic Levenberg-Marquand procedure freely "spends" samples and doesn't even remember the full history of each sample taken (instead updating some average statistics).

So my question is to ask for a pointer to iterative function minimization methods which use the minimum number of samples of the function. Ideally it would work where I could pass in a set of already-sampled locations and the value at each location, and the algorithm would spit out a single new location to take the next sample (which may be an exploratory sample, not a guess at a best minimum location, if the algorithm thinks it's worthwhile to test.)

I can likely take hundreds of samples, but only hundreds, and most multidimensional minimization methods expect to take millions.

Currently I am doing doing the minimization manually daily, using my own ad-hoc invention. I have say 40 existing timing samples to my 15-parameter model. I fit all my existing samples to a sum of independent quadratics (making the big initial assumption that each parameter is independent) then look at each of the N*(N-1)/2 ~=100 possible correlation coefficients of the full quadratic matrix. I find the few single matrix entries that when allowed to change from 0.0, give the best quadratic fit to my data, and allow those few entries to be their best least-squares fit. I also give locations with small (faster) values higher weight in the fit (a bit ad hoc, but useful to throw out behavior distant from the minimum) Once I have this matrix, I manually look at graphs in each of the major eigenvalue directions and eyeball locations which seem to need better sampling. I recombine all these guesses back into a new sample location. Each day, I tend to generate 4 new points, set up a run to test them over the next day, and repeat the whole thing again after the computation is done. Weekends get 10 point batches!

Thanks for any ideas! This question likely doesn't have a perfect "best" answer but I'm stuck at what strategy would work best when the evaluation cost is so huge.

Improve this question
$\endgroup$
10
  • 7
    $\begingroup$ First of all, this is the 10000th question on MO, so good on you. Second of all, have you looked at stuff such as that in (e.g.) Gershenfeld's book? books.google.com/books?id=lSTOh8U7NkkC&pg=PA156 $\endgroup$
    – Steve Huntsman
    Commented Aug 27, 2010 at 22:04
  • 1
    $\begingroup$ Here's one thing that should be asked: have you taken the trouble of determining reasonable first approximations of your parameters? If you've done that, Nelder-Mead or any of the stochastic optimization methods (e.g. differential evolution and simulated annealing) just might work. None of those assume differentiability of your objective function. $\endgroup$
    – J. M. isn't a mathematician
    Commented Aug 28, 2010 at 0:01
  • 2
    $\begingroup$ Using Levenberg-Marquardt on a function that is manifestly not a sum of squares is like using a butter knife to turn screws: it might work, but your way of proceeding is fundamentally wrong. $\endgroup$
    – J. M. isn't a mathematician
    Commented Aug 28, 2010 at 0:02
  • 2
    $\begingroup$ Here's something to chew on: instead of thinking of this as an pure optimization problem, think of this as design-of-experiments problem, but with a twist: you're trying to push one of the variables (your cost) to a desired value while mapping the space at the same time. Also, it is likely that your input parameters are correlated, so moving them independently wastes iterations. You want to project your input data down to a lower dimension space using a Partial Least Squares routine (which tells you the max covariance of your data) and move your variables in the latent variable space. $\endgroup$
    – Gilead
    Commented Aug 28, 2010 at 1:27
  • 2
    $\begingroup$ I should also add a caveat, since this question is "tagged" with the "global optimization" tag. I don't think any derivative-free method will be able to give you a certificate of global optimality unless it does an exhaustive search of problem space. In your case, it sounds like any method will be prohibitively expensive, so local optimality may be the best you can hope for (unless your black box problem is convex). I hope this helps! $\endgroup$
    – Gilead
    Commented Aug 28, 2010 at 1:48

5 Answers 5

Reset to default
4
$\begingroup$

I've read the paper, but never used the approach.

"Efficient Global Optimization of Expensive Black-Box Functions" by: Donald R. Jones, Matthias Schonlau, William J. Welch

PDF available from one of the page of an author.

Improve this answer
$\endgroup$
2
$\begingroup$

You haven't said so explicitly, but it sounds as though your function evaluations may also be noisy in that the function value is the result of a Monte Carlo simulation that incorporates random numbers. If that's the case then you definitely want to look at response surface modeling, since methods that attempt to approximate derivatives by finite differencing don't work in this situation and even pattern search methods like Nelder-Mead can be easily fooled by one bad function evaluation.

Improve this answer
$\endgroup$
0
$\begingroup$

Your problem seems typical of some that occur in the physical sciences (expensive experiments) and that are often attacked by Response Surface Modeling. This is a technique (connected to the statistics topic "design of experiments") that tries to build up a good model of the graph of an unknown function by means of a small number of function evaluations. The whole point of response surface modeling is to squeeze maximum information about the shape of the graph out of a small number of samples.

Arnold Neumaier has a webpage http://www.mat.univie.ac.at/~neum/glopt.html on global optimization where you may find useful links. You could also search the web with the keywords response surface optimization.

Improve this answer
$\endgroup$
0
$\begingroup$

Let me just add my voice to the others who have suggested the Nelder-Mead simplex method (which by the way is totally unrelated to the simplex algorithm for solving linear programs). I have heard that Nelder-Mead works surprisingly well in practice, although little is known about it theoretically.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, the "surprising" part is true. Despite advances in derivative-free methods, Nelder-Mead remains a competitive DFO algorithm, which is why it is still taught in many optimization courses. However, it is a heuristic and does not exploit the structure of the problem. Also, when a function is particularly expensive to evaluate, my view is that statistical methods (response surface modeling, particularly when projected into lower dimensional spaces) can help one avoid making unnecessary evaluations. Nelder-Mead was not designed with the goal of being parsimonious with function evaluations. $\endgroup$
    – Gilead
    Commented Sep 5, 2010 at 3:37
  • $\begingroup$ To add to Gilead's comment: as enthusiastic as I usually am with downhill simplex, it's still best thought of as a "not-so-quick and dirty" method; for a problem with a lot of independent variables, it is worth one's while to see what structure is exploitable in his problem instead of mindlessly feeding it to an optimizer. $\endgroup$
    – J. M. isn't a mathematician
    Commented Sep 5, 2010 at 9:58
0
$\begingroup$

You can try using this code.

Here is the paper that describes how it works.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .