| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
On Jan 12 2012, Arnold Neumaier wrote:
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?
That's a problem, because it's a generic result in probability and informatics, and not anything specific to interval methods. Yes, the usual example is bisection, but that's only the most trivial one. All you have to do is to work out the expected information increase, and then it applies to ANY method which relies on a monotonic increase in that. The constraint is that the sequence of expected increases doesn't approach zero any faster than the optimal sequence. Now, doing that in practice can be tricky - but the tricky cases are precisely those where it is tricky to work out an optimal strategy! Regards, Nick Maclaren.