11
$\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.

Improve this question
$\endgroup$
4
  • $\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, 2013 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, 2013 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, 2013 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, 2013 at 14:45

2 Answers 2

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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