Re: How do I bisect unbounded intervals?
> From: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>
> To: <rbk@xxxxxxxxxxxxx>
> Cc: "N.M. Maclaren" <nmm1@xxxxxxxxx>,
> "stds-1788" <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: Re: How do I bisect unbounded intervals?
> Date: Thu, 12 Jan 2012 19:40:28 -0600
>
> Baker Kearfott wrote:
>
> > P-1788:
> >
> > Although I find this topic interesting and am glad it is
> > being discussed, I now wish to express a personal opinion
> > about its relevance to P-1788. Namely, in my own
> > view, I think specifying a "bisection point" in a
> > branch and bound algorithm is too application specific to
> > be a part of our standard. I think specifying "midpoint"
> > is well within the scope, in which case we may wish to specify
> > what is returned for unbounded intervals (just so it will
> > be known and standard across platforms; however, IMO specifying
> > "random" in such cases won't help in portability and reproducibility).
> > However, specifying "bisection point" different from midpoint, and
> > designed to be good for branch and bound algorithms, seems a bit
> > of a stretch of the scope.
>
>
> Ok.
>
> Perhaps in that case we can at least consider a definition for our
> "midpoint" operation that does not lead unsuspecting users into some of
> these well-known traps and pitfalls? For example, if the midpoint of any
> unbounded interval would be some finite Level 2 datum or NaN, then this may
> accomplish that.
>
> In my experience simple midpoint bisection works amazingly well for a large
> class of B&B problems. I suspect many users will be tempted to just use the
> "midpoint" operation to design thier own algorithms. So defining the
> operation in such a way that it does not easily allow results that can lead
> to infinite recursion, this may at least force users to think about how to
> design thier own bisection algorithms more carefully.
>
> Nate
>
> P.S.
>
> May I even be so bold as to suggest the "midpoint" of any interval [u,v]
> could be NaN if u and v are two adjacent Level 2 datums, regardless if u and
> v are both finite or not? The rationale: this also avoids infinite recursion
> in naive B&B algorithms if midpoint of [u,v] is otherwise defined to be u or
> v.
I agree with Baker that a random point is bad for
reproducibility.
If we are to generalize this discussion into something
more appropriately standardizable like a definition of
midpoint, I think failing on too narrow [u,v] or even
[u,u] would be unreasonable from the user's perspective.
But Nate, as the B&B guy in the room, I'm sure you have
working stopping criteria other than blowing up when an
interval gets too narrow. What's wrong with using
width(xx) > 0? Actually I suspect you actually use
width(xx) > eps where eps > 0. Both work in the sense
of preventing infinite recursions & both allow one to
use a more reasonable definition of midpoint.
If we want to confine our discussion to a definition
of midpoint (even if we acknowledge that it needs to
work for B&B) then a pseudo arithmetic midpoint of
[lo,hi] could be something like:
midpoint([lo,hi]) = 0, if lo == -oo & hi == +oo
(lo + Fmax)/2, if lo > -oo & hi == +oo
(-Fmax + hi)/2, if lo == -oo & hi < +oo
(lo + hi)/2, otherwise.
where all arithmetic operations are carried out in a
manner that avoids overflow (easy to do).
Someone suggested an information theory midpoint. In
floating-point this is quite close to a geometric mean
in that it finds that floating-point number for which
the number of representable numbers between lo & mid
is nearly equal to the number between mid & hi.
There is merit in this but I would not give it the name
"midpoint". Perhaps "split".
But that's about all I can say about it & still be on
the topic of standardizable things. :-)
Enjoy,
Dan