Re: How do I bisect unbounded intervals?
On 2012-01-12 19:40:28 -0600, Nate Hayes wrote:
> 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.
The standard could include informative text about bisection,
so that the programmer doesn't misuse some operation provided
by the standard.
> 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.
The advantage of NaN (for unbounded intervals) is that the user would
normally detect that something is wrong by simple testing. The user
could then replace NaN by any adequate value for his application.
> 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.
Without even mentioning infinite recursion, using the midpoint in
multiple precision with a large exponent range on large (even bounded)
intervals may yield very inefficient code, that could take several
years to complete or could consume all the machine's resources
(perhaps one can see that as infinite recursion after all). However
such large intervals would probably come from unbounded intervals.
So, NaN would again be a good idea for unbounded intervals.
Note: on its domain (i.e. when the result it not NaN at Level 2),
the midpoint function should be monotonic.
> 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.
This may be a good idea. And this would mean that the following
property would hold at Level 2: u < midpoint([u,v]) < v.
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)