2
|
3540 Views
|
2 Replies
|
2 Total Likes
View groups...
Share

# Stochastic root finding with Mathematica

Posted 10 years ago
 Are there any existing tools or packages for stochastic root finding with Mathematica, preferably in more than one dimension? The classical root finding problem seeks to approximate $x$ so that $f(x) = 0$, while minimizing the number of times $f$ needs to be evaluated. For example, Newton's method does this. The stochastic root finding problem differs in that we cannot compute $f(x)$ directly. We can only compute $f(x) + \eta$ where $\eta$ is a noise term with mean zero. A real-world example would be when $f(x)$ is computed with some Monte Carlo method. As a toy example, here's a small Monte Carlo integrator that computes $\int_0^x \sin^2 t \; dt$: f[x_] := Sin[x]^2 n = 1000; fun[x_?NumericQ] := With[{count = Round[n x]}, N@Total@UnitStep[f@RandomReal[x, count] - RandomReal[1, count]]/n ]  Two classes of methods I found are probabilistic bisection (only works in 1D) and the Robbins-Monro method. Robbins-Monro is related to Newton's method, but it's highly non-trivial as creating a usable iteration scheme involves making lots of choices, all of which can significantly impact the performance of the method. I am still researching the topic and would be interested in discussing with people who have had to solve similar problems in the past.
2 Replies
Sort By:
Posted 10 years ago
 It appears that NMinimize uses BlockRandom with a fixed seed, so any stochastic function passed to NMinimize will always produce exactly the same result. I can work around this, just observing how NMinimize works. Example: In:= f[x_?NumericQ] := (Sow@RandomReal[]; x^2) In:= Last@Reap@NMinimize[f[x], x] == Last@Reap@NMinimize[f[x], x] Out= True 
Posted 10 years ago
 I'd try NMinimize[f[x,...]^2, x,...] to see if that gives anything useful. Probably would go with Method->"DifferentialEvolution" as the first method to try.