Timeline for Robust black box function minimization with extremely expensive cost function
Current License: CC BY-SA 2.5
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18, 2016 at 23:37 | comment | added | Jules | Look at Bayesian optimisation. | |
| May 18, 2016 at 23:08 | answer | added | Paul | timeline score: 0 | |
| Sep 5, 2010 at 3:27 | comment | added | Darsh Ranjan | Your life is going to be a lot simpler if you can slightly violate the "black box" model for your cost function. How reasonable that is depends on how complicated your program is. Best case scenario: by analyzing your algorithms, you can write down a formula for the runtime as a function of your parameters and some unknown system-related constants. Then by running your program, you can determine the values for those constants that fit the observations best and end up with a good approximate formula for the runtime. This doesn't exactly answer your question, but it's worth thinking about. | |
| Sep 5, 2010 at 1:57 | answer | added | umar | timeline score: 0 | |
| Sep 5, 2010 at 1:15 | answer | added | Brian Borchers | timeline score: 2 | |
| Sep 1, 2010 at 18:07 | vote | accept | MathMonkey | ||
| Aug 28, 2010 at 11:33 | answer | added | Marius Overholt | timeline score: 0 | |
| Aug 28, 2010 at 8:13 | comment | added | Gerhard Paseman | What minimization results will satisfy you? If a back-of-the envelope calculation shows that each pass needs an hour, do you still want to try to find the parameters that will acheive that? Also, are there any opportunities to profile the code and find bottlenecks that might be relieved by code redesign? Gerthard "Ask Me About System Design" Paseman, 2010.08.28 | |
| Aug 28, 2010 at 2:21 | comment | added | J. M. isn't a mathematician | He did mention he had an ad hoc approach; I have a feeling it can somehow be algorithmized; and then used in conjunction with an appropriate optimization method to his satisfaction. In any event, no matter what optimization method the OP finally settles on. not having any good/reasonable initial values for the parameters will only result in an aimless wandering of the parameter space. | |
| Aug 28, 2010 at 1:48 | comment | added | Gilead | 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! | |
| Aug 28, 2010 at 1:41 | comment | added | Gilead | That way, your sampling becomes more intelligent, because with a PLS model, you can now simultaneous move all 15 of your inputs in the direction of maximum covariance. In a sense you are doing this already with your eigenvalue method (which can be shown to correspond to a Principal Components Analysis) -- you are on the right track there; what PLS buys you is the ability to relate your runtime to inputs, all in latent variable space. I wish I could point you to a paper or something but references elude me. This method is known to statisticians who work in the area of chemometrics. | |
| Aug 28, 2010 at 1:27 | comment | added | Gilead | 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. | |
| Aug 28, 2010 at 0:02 | comment | added | J. M. isn't a mathematician | 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. | |
| Aug 28, 2010 at 0:01 | comment | added | J. M. isn't a mathematician | 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. | |
| Aug 27, 2010 at 23:48 | answer | added | dls | timeline score: 4 | |
| Aug 27, 2010 at 22:04 | comment | added | Steve Huntsman | 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 | |
| Aug 27, 2010 at 21:16 | history | asked | MathMonkey | CC BY-SA 2.5 |