Asymmetric bisection

Question

I have this problem which I believe is pretty simple, however I'm not finding anything online.

I need to find a zero of a function numerically. I know that $f(0)<0$ and $f(1)>0$ and that $f(x)$ is continuous in this interval. I can do bisection and find numerically the zero to the desired accuracy.

However, the time that it takes to evaluate the function $f(x)$ numerically is different if $f(x)<0$ or $f(x)>0$. Let's say that for $f(x)<0$ the time needed for evaluation is $1$ and for $f(x)>0$ it's $C$, with $C>1$. At this point it's convenient not to look at the halfway point anymore, i.e. $f(1/2)$, but I would save some time by choosing a point a bit closer to $0$, since evaluation of $f$ is more likely to be faster. What is the optimal point to choose in a situation like this, so that I can do bisection in the fastest way possible?

Edit: I am only interested in a bisection method, I know in principle there are more effective ways using derivatives of $f$. However, since my $f$ is in practice a boolean function which is true at $f(0)$ and becomes false somewhere between $x=0$ and $x=1$, and I want to find this point, I can only do bisection.

Answer 1

Here's intuition. I can't quite seem to find the probabilistic argument that shows it minimizes expected computation cost.

Assume the unknown root is uniformly distributed in the unit interval. Assume that the best strategy is to choose your evaluation point dividing the interval in the ratio $(1-r):r$. When $C=1$ you want $r= 1/2$. For larger $C$, $r$ should approach $0$. I suggest $$ \frac{1-r}{r} = C $$ which leads to $$ r = \frac{1}{1+C}. $$ You apply the same ratio recursively to each subinterval in your binary search.

Whether or not you can justify this, it's a very easily implementable heuristic.

In your particular application you might be able to do better if you also use the actual values for $f$ at the endpoints to choose the division point, assuming that values smaller in absolute value are likely to be nearer to the unknown root.

Answer 2

If you have access to the derivate of $f$, you could use Newton's method

If not, a simple method would be to assume that $f$ is linear and then test where the root is supposed to be. For example let say :

$$f(0) = -4 , f(1) = 1$$

You might want to say maybe $f(x)=5x-4$ so next value to check would be $f(4/5)$, iterating this step will lead you to the root.

Good luck =)

Answer 3

The optimal answer depends on the probabilities of the $-/+$ outcomes of the function. Let us simply assume that they are proportional to the size of the subintervals, which we denote as the fraction $x$. this amounts to say that the solution is uniformly distributed in any interval.

When you perform a test, the average time spent is thus $x+(1-x)C$. Then the initial interval is reduced to a size $x$ or $1-x$, and this will influence the search depth (assuming that a constant accuracy is required). At this stage, the computation becomes tricky; if you take constant depth for all searches, the initial interval will reduce by $x^k(1-x)^{d-k}$ following a binomial distribution. I don't know if computing the expectation is tractable. But here the depth is not even constant, and the distribution is harder to compute.

IMO, the computation should be done numerically, using a complete traversal of the decision tree, for different values of $x$.