Re: Branch & bound for not everywhere defiend constraints
Nate Hayes wrote:
> Arnold Neumaier wrote:
>> Nate Hayes schrieb:
>>> According to Arnold, the center
>>> disk should be filled entirely with blue boxes representing "a huge,
>>> spurious undecided area, determined in an extremely inefficient
>>> way." There also should be "no information to be attached to the NaI
>>> that would help." However, it is just as easy to encode
>>> "TotallyUndefined" for
>>> evaluations like sqrt([-3,-1]) into the NaI as it is to encode
>>> "PossiblyUndefined" for evaluations like sqrt([-1,3]). As the
>>> picture shows, this easily allows the branch-and-bound algorithm to
>>> eliminate large areas of the center disk very efficiently.
>>>
>>> There remains a circle at radius 3 where some unnecessary effort
>>> still remains.
>>
>> Not only unneccesary effort. Much worse: there remains a spurious
>> circle that cannot be eliminated at all. This may matter in
>> applications!
>
> No. The circle is not accepted as any part of the solution set. It
> just represents some wasted effort.
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.
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) = x for function f can be reduced to
finding the zeros of
g(x) = f(x) - x = 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) <= eps ) accept x if not isNaN(g(x))
else bisect x
Over the input domain [-5,5], this algorithm correctly proves the
non-existence of a fixed point for f(x) = sqrt(x-1); it also proves the
existence of a fixed point within the interval [1.61803,1.61804] for f(x) =
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
