Re: Branch & bound for not everywhere defiend constraints
Dan Zuras Intervals wrote:
>> Date: Sun, 6 Sep 2009 18:33:49 -0400
>> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
>> Subject: Re: Branch & bound for not everywhere defiend constraints
>> To: STDS-1788@xxxxxxxxxxxxxxxxx
>>
>>
>> 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, 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.
>
>>
>> Also, Alexandre's original fixed-point example (attached for
>> convenience) can be reformulated into a branch-and-bound problem;
>> the existence (or non-existence) of a fixed point f(x) =3D x for
>> function f can be reduced
>> to finding the zeros of
>>
>> g(x) =3D f(x) - x =3D 0.
>>
>> In this case, the problem can be solved entirely without decorated
>> intervals, i.e., ExpressionResult, or global/local flags, provided
>> NaI is used instead.
>>
>> For example, the branch-and-bound algorithm
>>
>> if ( g(x) > 0 ) delete x
>> else if ( g(x) < 0 ) delete x
>> else if ( wid(x) <=3D eps ) accept x if not isNaN(g(x))
>> else bisect x
>
> Next, I'm not sure I read the 3rd line of this correctly.
> Do you mean to say:
>
> else if (( width(x) <= eps ) and not isNaN(g(x))) accept x
>
> If so, does the NaI case continue to bisect along with the
> uncertain interval boundary or is there another test that
> prevents that?
Sorry, it should read
else if ( wid(x) <= eps ) { accept x if not IsNaN(g(x)) }.
To avoid the unnecessary bisections of blue boxes, one additional
isTotallyUndefined(g(x)) check should be added to the branch-and-bound
algorithm. This eliminates large blue boxes and prevents useless chopping
into tiny epsilon-sized blue boxes.
>
>>
>> Over the input domain [-5,5], this algorithm correctly proves the
>> non-existence of a fixed point for f(x) =3D sqrt(x-1); it also
>> proves the existence of a fixed point within the interval
>> [1.61803,1.61804] for f(x) =3D sqrt(x+1).
>>
>> As a side benefit, note the "syntactic sugar." In these examples,
>> g(x)
>> will never be empty. So subtle and innocent programming errors due to
>> empty set, such as fogetting g(x) > 0 is true if g(x) is empty,
>> won't occur.
>>
>> Nate Hayes
>>
>
> Finally, what does it mean to "forget g(x) > 0 is true
> if g(x) is empty"? And how CAN g(x) > 0 be true when
> g(x) is empty? Is this another example of your 'vacuous
> truth'? If so, what is the 'subtle & innocent programming
> error' committed in this case?
>
> Just curious...
I just refer to the original instance of your wetware example, where the
isEmpty(f(x)) check was in the wrong place, or how using the flags semantics
according to Vienna Proposal can lead to Paving A instead of Paving B if the
user isn't really careful. The whole "syntactic sugar" issue may only be a
minor part of the NaI debate. However, I think its pleasant icing on the
cake.
Nate Hayes