# Stochastic root finding with Mathematica

Posted 9 years ago
3399 Views
|
2 Replies
|
2 Total Likes
|
 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 9 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[20]:= f[x_?NumericQ] := (Sow@RandomReal[]; x^2) In[21]:= Last@Reap@NMinimize[f[x], x] == Last@Reap@NMinimize[f[x], x] Out[21]= True 
Posted 9 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.