Message Boards Message Boards

Stochastic root finding with Mathematica

Posted 11 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.

POSTED BY: Szabolcs Horvát
2 Replies

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 BY: Szabolcs Horvát

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.

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract