10
$\begingroup$

There are many well known numerical methods for solving equations of the type $$ f(x) = 0, \quad x \in \mathbb{R}^n,$$ e.g. bisection method, Newton's method, etc.

In my application $f(x)$ is calculated with a stochastic method (the result is an average).

Are there any numerical equation solving methods that handle this situation well? Links to any discussion of similar situations are also appreciated.

The precision to which I can calculate $f(x)$ depends strongly on $x$, and I might easily hit a wall where I can't increase the precision without increasing the computation time significantly. So I can't ignore the fact that the result from $f$ is not precise. This will also impact the precision to which $x$ can be found in practice.

$\endgroup$
  • $\begingroup$ What do you know about the noise / precision: does each $f(x)$ come with an error bar, or does the time just hit a wall ? (Can't you just set a time limit ?) Also, there are many methods for minimizing noisy functions e.g. $f(x)^2$, easier than root-finding in $\mathbb{R}^n$ . $\endgroup$ – denis Aug 29 '13 at 14:22
  • $\begingroup$ @Denis I do have a rough estimate of the precision, but it's quite rough, and it may heavily depend on $x$. I'm working on that aspect too and might post a question eventually ($f$ is an average calculated using MCMC). I specifically need root-finding here, not optimization, but you're right that minimizing $f(x)^2$ is the same as solving $f(x) = 0$ if the method does indeed find the global minimum. Do you have any references saying that this is a good approach here, and also any references for noisy optimization? Wouldn't this approach be detrimental to the precision of the result? $\endgroup$ – Szabolcs Aug 29 '13 at 14:32
  • $\begingroup$ the picture on Numerical Recipes p. 474 shows why root-finding in even 2d is tough. On noisy optimization, I'll pass; there are many many methods (more than test cases), ask experts here. $\endgroup$ – denis Aug 29 '13 at 14:42
  • $\begingroup$ @Denis Well, yes, it tough, but it's what I need. I have the advantage of having a proof that there's either one root or no roots at all. $\endgroup$ – Szabolcs Aug 29 '13 at 14:45
10
$\begingroup$

This is the stochastic root-finding problem, as in The stochastic root-finding problem: Overview, solutions, and open questions.

$\endgroup$
0
$\begingroup$

The keyword here is stochastic approximation which refers both to root finding and optimization. As usual, knowing the keyword makes it easy to find lots of resources. Here's the Wikipedia page for a start.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.