Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Tetrits, just checking FTIA...

Ralph Baker Kearfott wrote:

Nate et al,

Just to be a bit picky; also, please clarify:

On 4/11/2010 11:08, Nate Hayes wrote:

Dan Zuras Intervals wrote:



One thing to keep in mind is that interval branch-and-prune methods
are an application of the Nested Intervals Theorem, which says the
intersection of infinitely many nested intervals over a non-empty
compact (closed and bounded) domain is a non-empty set. If the width
of the nested intervals are decreasing, the intersection is a unique
real number.


Actually, the widths have to be decreasing at a particular rate.  For
example, take

\x_i = [1-1/2^i,2+1/2^i]

The intervals are nested and their widths are decreasing, but the
intersection is [1,2], not a point.

In any case, I don't think this fact was entirely relevant to
your point.


So it is not possible that an empty interval can ever arise in a
divide-and-conquer method so long as the original input domain meets
these criteria.



I'm not sure I understand the context you are describing.  In
particular, what if I use an interval Newton method or constraint
propagation to reduce the size of the box, and this results in a box which
has empty intersection with the original box.  That original box
would then be considered to be fathomed, but we may wish to
use our standardized arithmetic to detect that the intersection
is empty.   Similarly, during constraint propagation (an integral
part of many branch and bound algorithms), an empty interval
may be produced as an intermediate result, and it is possible we
don't detect it immediately.


In Dan's post he talks about the "tower" of decorations produced by
evaluating nested intervals in the domain [-2,2]:
   [-2,2] \supseteq [1,2] \supseteq [1,1] \supseteq [empty].
My only point is no "straightforward" bisection of the domain [-2,2] will
produce [empty], since by Nested Intervals Theorem, e.g., [1,1] would be the
unique real number.

I was not talking about the nested intervals
   f([-2,2]) \supseteq f([1,2]) \supseteq ...,
which, I think you are mentioning in your examples.
Sorry! I should have clarified.





Now, Nested Intervals Theorem does _not_ hold if the input domain is
empty or unbounded. So these probably are the kinds of examples we
realistically will want to examine very closely.



???


If an interval is empty, no nested sequence of intervals produces a
non-empty interval. The sequence of nested intervals
   [a1,+oo) \supseteq [a2,+oo) \supseteq ...
also has an empty intersection.

Nate