On 2012-01-11 23:33:52 -0600, 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.
B&B algorithms require as input an initial interval X_0. The algorithm
then
proceeds by recursively bisecting X_0 into sets of non-overlapping nested
intervals X_1, X_2, ... X_n and then evaluating some interval extention
of a
real function f to find all of the f(X_i) that contain zero, say. In his
book, Luc Jaulin calls this the SIVIA algorithm for Set Inversion Via
Interval Analysis. Because of the Nested Intervals Theorem, if X_0 is
closed
and bounded then X_0 can always be bisected into two sub-intervals L and
R
that are also closed and bounded, and so on. However, this requires the
user
to specify an initial X_0 that is closed and bounded.
Well, first I would say that the name and description of the function
should match what it really does and what it is intended for.
If the function is called "middle", it should return the middle.
If the function is designed for bisection, it should have another
name, and perhaps not always be the middle, even when the middle
is well-defined. Perhaps instead of returning a floating-point
value, the function should return a list of intervals (e.g.
two intervals).
Also, there can be significant differences between Level 1 and Level 2.
And I think that for bisecting, a spec would be more interesting at
Level 2.
For instance, what if the interval is of the form [u,v] where u and v
are two consecutive floating-point numbers?
And what if the interval is bounded but very large?
What would be the best point for splitting in general? Doesn't this
depend on the application? What about considering for some cases the
geometric mean instead of the middle (arithmetic mean)? Shouldn't
special rules be considered for very large intervals (possibly
unbounded) or very small intervals (e.g. 2 consecutive floating-point
numbers)?