I'm looking for methods for optimizing stochastic functions. By stochastic functions I mean functions whose output is a random variable, such that every time an evaluation is made F(x), with the same value of x, the result is a random value of some, probably unknown distribution. In a sense is like trying to optimize f(x), a deterministic function, but you cannot evaluate f, but intead some other noisy functionF(x) = f(x) + e, where e~Y is some random variable, with unknown properties (I can alleviate this un-knowledge if necessary). Examples of this kind fo functions are simulations and functions in real life with measure errors.
So far I've found what's called stochastic approximation algorithms, which attempt to solve the problem, but seem to only be good for functions f(x) that have nice properties, like global convexity. I'm dealing with stochastic functions that are multi-modal and with non-global structure, so standard gradient descent methods don't do, even if we remove the noise source.
One alternative that's been suggested to me is to simply run a metaheuristic, but do 30 or more evaluations of F(x) in each step in order to approximate f(x) as best as possible, and then assume I've removed the noise. Even though I think this can possible work, I also think there has to be a better method, that doesn't involve running 30 or 40 times the number of function evaluations, specially because each evaluation consists of a simulation (hence the stochastic nature) which is already a lengthy process.
My guess is that by making some modifications to standard multi-modal optimization techniques (metaheuristics and such) which remove the effective sampling bias introduced by techniques such as elitism, we can expect the algorithm, even with noisy samples, to converge on the long run towards a good enough local optimum, without needing to evaluate 30 or more times each sample. However, I have no theoretical or practical proof of this assumption.
Can anyone supply links or resources in this topic?
This sounds like an inverse problem that has no unique best answer. Have you looked at the literature on this specific area?
Hi Alejandro,
You might find previous work on handling dynamic optimisation landscapes useful, since these approaches also have to deal with the problem of objective values changing between solution evaluations. An overview in the context of evolutionary algorithms is:
T. T. Nguyen, S. Yang and J. Branke. Evolutionary dynamic optimization: A survey of the state of the art. Swarm and Evolutionary Computation 6pp. 1-24. 2012. Available: http://www.sciencedirect.com/science/article/pii/S2210650212000363
Michael
Perhaps something like M. H. Jones, K.P. "White Stochastic Approximation with Simulated Annealing as an Approacch to Global Discrete Event Simulation Optimization" ( http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.143.7561 ) might help. I haven't tried it but it seems to be a reasonable combination of stochastic approximation and simulated annealing. Close to a minimum and for low 'temperature' parameter it should work like stochastic approximation for a convex f; for higher temperatures a descent along estimated gradients is perturbed by jumps. -- Still I would suppose that it is not optimal with respect to the number of evaluations. If you have more information on f it might be reasonable to simultaneously learn a model (splines?) for f and minimize it.
If the problem is the noise itself, consider the use of stochastic metrics as your new objective functions. These metrics (Downside risk or worst case, among others) are widely used in economics. They will not help you overcome the difficulty of having to evaluate your function on different scenarios (and hence, of having to perform several simulations), but they should provide a more robust solution in the context of noise. You can find information about some of these metrics in "Guillén-Gosálbez, G., Grossmann, I.E. Optimal design and planning of sustainable chemical supply chains under uncertainty. AIChE Journal 2009, 55 (1), pp. 99-121".
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs