Re: Branch & bound for not everywhere defiend constraints
Alexandre Goldsztejn wrote:
> Dear colleagues,
>
> Here is an example that shows IMO that NaI are not the best option for
> dealing with the evaluation of function over intervals that may not be
> included in their domain.
>
> Consider f(x)=sqrt(x-1). We wish to verify whether there is a fixed
> point or not inside a given interval xx.
>
> First, let us consider xx=[0.75,1.25]. Then
> f(xx)=sqrt([-0.25,0.25])=[0,0.5]. Because the intersection between xx
> and f(xx) is empty, we have proved that there is no fixed point inside
> xx.
>
> Second, let us consider xx=[0,2]. Then f(xx)=sqrt([-1,1])=[0,1].
> Although f(xx) is a subset of xx, we cannot conclude that there is a
> fixed point inside xx because sqrt was evaluated on an interval that
> is not included in its domain. And indeed, f has no fixed point in xx
> as shown by the attached graphic.
>
> The second case does show that we need to output the information that
> a function has potentially been evaluated on an interval that is not
> contained in its domain. However, if NaI are used to this purpose,
> then both the first and the second case will return NaI. Thus, we
> loose the interpretation of the first computation that allowed to
> prove the absence of fixed point in the interval.
>
> It would be quite harmful to require the user to duplicate his
> computations using different modes, or to switch between different
> modes depending on the purpose of his computation.
In this example, I don't see why the user would need to switch modes. Both
cases could be evaluated in "non-NaI" mode, and a flag could be checked,
i.e., the ExpressionResult template option described by Nehmeier and Prof.
Gudenberg would work well for both cases in this example.
However, in the Paving B example I gave earlier, the interval result is of
no use if the function is probed outside its domain. So the ExpressionResult
template in this case only adds implementation and performance overhead for
no added benefit (so I would not use it). These problems would also be
exacerbated if computing in data-parallel mode on some hypothetical VPU
hardware device.
Nate Hayes