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 06:33 AM, Nate Hayes wrote:

Vincent Lefevre wrote:

BTW, on a similar subject, the middle of [-inf,inf] should be NaN
(IEEE 754) or undefined. Though 0 appears as the center of symmetry
at Level 2, it is not the only one at Level 1 (every real number
could be seen as the middle).





This is very interesting to me, since it relates to a recurring source of
bugs I've often run into when writing interval branch-and-bound (B&B)
algorithms.

A naive user might complain profusely about this, though. For example, they
may expect they should be able to simply specify an unbounded interval like
[-inf,+inf] for the initial interval X_0 and that the B&B algorithm would
then find all solutions in this domain.


This indeed happens in some of our branch and bound software,
e.g., GloptLab (see http://www.mat.univie.ac.at/~dferi/gloptlab.html )



It begs the question: is the user's expectation realistic? In other words,
how does one bisect an unbounded interval?
We split intervals at a safeguarded midpoint; in particular, it is zero when the interval is Entire. It is the standard midpoint only if the interval has a reasonable size. For example, [1,1e15] is split at 1e8 rather than at the midpoint since the latter is almost useless in B&B.