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.
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.
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.
Should the midpoint of left- and right-unbounded intervals like [-inf,-1]
and [1,inf] also be NaN/undefined? Otherwise if I assume the midpoint of
[-inf,-1] is -inf then the bisection of X=[-inf,-1] would be
L=[-inf,-inf]=Empty/undefined and R=[-inf,-1].
Note that R equals X, so that bisecting R again leads to infinite
recursion,
which can easily cause a computer program to crash. I've run into this bug
several times in my interval-programming lifetime. Of course, lots of
tedious or defensive programming can prevent such program crashes. But
its a
bit of a pain and easy for programmers to get wrong.
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