Re: Branch & bound for not everywhere defiend constraints
Arnold Neumaier wrote:
> Nate Hayes wrote:
> [in: Motion P1788/M007.01_NaI: NO, several NaIs please]
>
>
>> in order to find a subset
>> S := { x in X | f(x) <= 0, x is real, f(x) is real }.
>> We define the branch-and-bound method as
>> if isEmpty(f(X')) then delete X' // yellow
>> else if f(X') > 0 then delete X' // gray
>> else if f(X') <= 0 then accept X' // green
>> else if eps(X') then mark X' indeterminate // blue
>> else bisect X'
>> where X' is any sub-box of X and eps(X') is a function to determine
>> if the sub-box meets tolerance criteria or not.
>
> Under the conditions of the Vienna proposal (and of Motion 6),
> the above code is semantically invalid since its correct behavior
> cannot be proved from the specification
> f(X):= hull{ f(x) | x in X, f(x) defined}.
I agree. It is why I have objected to these definitions in the past and
suggested something along the lines
f(X) := { y in R | x in X, x in R, f(x) = y }.
Or else inclusion of a mode that allows users to choose which of the two
definitions controls the behavior and result of interval operations.
> Correct is the following code, which uses Section 3.4 of the
> Vienna proposal that must be considered whenever existence
> statements are made (also in existence from an interval Newton
> operator):
>
> if isEmpty(f(X')) delete X'
> else if inf(f(X')) > 0 delete X'
> else if PossiblyUndefined bisect or save X'
> else if f(X') <= 0 accept X'
> else bisect save X'
Yes, but this requires global/local flags, which I think are to be avoided
in data-parallel computing environments. In the context of this type of
algorithm, the interval result is of no use when PossiblyUndefined is set,
anyways. So it is better to return a "PossiblyUndefined" (or in some cases
perhaps a "TotallyUndefined") NaI instead.
Nate Hayes