Branch & bound for not everywhere defiend constraints
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}.
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'
Arnold Neumaier