Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: How do I bisect unbounded intervals?

On 01/12/2012 11:45 AM, N.M. Maclaren wrote:

On Jan 12 2012, Arnold Neumaier wrote:

On 01/12/2012 09:56 AM, N.M. Maclaren wrote:

On Jan 12 2012, Jean-Pierre Merlet wrote:


What we are doing in that case in ALIAS for system solving is to
choose a random number in the unbounded interval and to bisect the
interval at that point (for bounded intervals we have tried methods to
determine a bisection point that may be better than the mid-point but
have found none that were better on a significant number of examples
of our benchmarks, hence we are using the mid-point). ...


Something that might interest people is that, subject to reasonable
constraints, using random points is within a constant factor of optimal
even for bounded intervals. I suspect that you already know that :-)


According to which measure of optimality?


Performance, accuracy, what you will.


I haven't seen anything like this in the context of branch and bound.
Can you point to a reference? Maybe you refer to bisection for finding a univariate zero? 


The only thing that you are
sacrificing is deterministic measures of those in favour of with
probability one. Most computer scientists seem to think that is a
major theoretical or practical issue, but that's because they don't
understand probability.