Re: Branch & bound for not everywhere defiend constraints
Dan Zuras Intervals wrote:
>> Date: Mon, 7 Sep 2009 12:21:31 -0400
>> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
>> Subject: Re: Branch & bound for not everywhere defiend constraints
>> To: STDS-1788@xxxxxxxxxxxxxxxxx
>>
>> Dan Zuras Intervals wrote:
>>>> . . .
>>>> Nate Hayes wrote:
>>>>> Arnold Neumaier wrote:
>>>>>> Nate Hayes schrieb:
>>>>>>> . . .
>>>>>>>
>>>>>>> There remains a circle at radius 3 where some unnecessary effort
>>>>>>> still remains.
>>>>>>
>>>>>> . . .
>>>>>
>>>>
>>>> I should also clarify:
>>>>
>>>> In the original Paving B example, the user is concerned about
>>>> f(x) > 0 or any f(x) that is not real. In either case,
>>>> something catastrophic may happen. In this Paving C example,
>>>> the center circle (and its entire area) represent f(x) not
>>>> real. If this information is valuable to the user, as
>>>> in Paving B, then the circle in Paving C represents zero wasted
>>>> effort and is actually an optimal covering.
>>>
>>> Nate,
>>>
>>> 3 minor points here. More in the way of questions than
>>> criticisms.
>>>
>>> Why is it that Paving C has the center circle grey (a color
>>> you have been using for f(x) > 0)? Shouldn't it be blue (in
>>> the NaI case) or yellow (in the empty case)?
>>
>> Yes. I think to be visually accurate (and not misleading), the area
>> of the circle *should* be tiled with blue color. This was part of my
>> recent point, i.e., that in this case the covering produced by the
>> NaI algorithm is 100% optimal with no wasted effort.
>
> And I see you explain how just below, but...
>
>>
>>> And, while the
>>> yellow case would tile as you have it & not waste any effort,
>>> how is the branch & bound written so as to prevent the blue
>>> case from continuing to bisect down to your epsilon limit as
>>> happened in your Paving B?
>>
>> This requires two NaIs: "TotallyUndefined" and "PossiblyUndefined".
>> For example, sqrt([-10,-4]) should return a "TotallyUndefined" NaI,
>> while sqrt([-3,5]) should return a "PossiblyUndefined" NaI. The
>> "PossiblyUndefined" NaI should also propagate over the
>> "TotallyUndefined" NaI. This allows the branch-and-bound algorithm
>> to add a check for isTotallyUndefined(f(x)) and therefore avoid
>> bisecting a large blue box into many small epsilon-sized blue boxes.
>
> Isn't another name for "TotallyUndefined", "Empty"?
> You define it to be true in exactly the same place
> as empty is true & you use it as others use empty.
>
> Are we just a name away from agreement?
Almost.
The difference is "Empty" doesn't propagate the same way as
"TotallyUndefined," since "Empty" may be absorbed by union operations
whereas "TotallyUndefined" is guaranteed to propagate all the way to the end
of a computation.
>
> Finally, while I'm not happy with the concept of global
> flags for any purpose, I agree that 'syntactic sugar' AKA
> 'decorations' attached to intervals may be of value.
Along this route, I think its important to distinguish: a "decorated
interval" is [double,double] plus a byte for state information. So the size
(in bits) of any decorated interval is by nature not going to be a
power-of-two, which means generally speaking it will not fit in one piece
into a hardware register or buss. For NaI, the information that would
otherwise be in the byte of a decorated interval is encoded into the payload
of the NaI. In this way, the size (in bits) of NaI can remain power-of-two.
So theoretically they may be similar concepts. In practice they have
different implementation consequences.
THis is why I believe both should be examined and considered.
>
> As for the naming of things, it could be that sufficiently
> many 'flavors' of 'syntactic sugar' could take the place
> of either or both of NaIs or empty for what we need them
> to do.
>
> We are having that discussion now. Let's see how it turns
> out.
Yes.
>
> Thanks for your explanations,
You're welcome!
Nate Hayes