Re: How do I bisect unbounded intervals?
> From: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>
> To: "Vincent Lefevre" <vincent@xxxxxxxxxx>,
> "stds-1788" <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: How do I bisect unbounded intervals?
> Date: Wed, 11 Jan 2012 23:33:52 -0600
>
> 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.
>
> . . .
>
> It begs the question: is the user's expectation realistic? In other words,
> how does one bisect an unbounded interval? As Vincent notes above, trying to
> bisect [-inf,inf] into two touching but non-overlapping intervals L and R is
> inherently an undefined operation, it seems.
>
> . . .
>
> As a programmer, how should I handle this situation? And what should be the
> correct standard behavior for a B&B algorithm like SIVIA if the user
> supplies an unbounded input domain?
>
> Nate
I believe I agree with Nate here. Or, at least, with what
Nate seems to be driving at. That is, that it is reasonable
for a user to expect to be able to bisect intervals whether
they are bound or not.
I would even go so far as to suggest that we provide standard
methods for doing so. For bound intervals these methods
might reduce to bisection. And I can see many possible &
reasonable generalizations to unbound intervals. One could
bisect them pseudo logrithmically. Or arithmetically by
producing one bound interval (using +/-Fmax as endpoints) &
one unbound interval (the remaining piece). Or simply come
up with special case rules like:
[-oo,oo] --> [-oo,0] \union [0,oo]
[x,oo] --> [x,mid] \union [mid,oo]
where mid = x + (Fmax - x)/2 for x >= 0
or mid = (Fmax + x)/2 for x <= 0
[-oo,x] --> [-oo,mid] \union [mid,x]
where mid = (-Fmax + x)/2 for x >= 0
or mid = x - (Fmax + x)/2 for x <= 0
being careful to compute mid in a way that avoids overflow,
of course.
If we want to define functions for this I suppose we could
call them leftBisection(xx) & rightBisection(xx).
If someone wants to come up with rules that always work even
for unbound intervals, I have a number of suggestions.
But I suspect Nate has done some of this work already.
And I have NO idea what to do with Kaucher bisections. :-)
Yours,
Dan