Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Branch & bound for not everywhere defiend constraints

Nate Hayes schrieb:

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
lose 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.
The problem is that one cannot know beforehand when the function is outside its domain, once the domain is not a simple box, and one 
does not know beforehand whether the information in the result is
useful or not.



However, in the Paving B example I gave earlier, the interval result is of
no use if the function is probed outside its domain. 

Alexandre Goldsztejn's observation even holds in your example if
the function value comes out positive when evaluated in "non-NaI" mode although the box is not completely inside its domain. Then the "non-NaI" mode eliminates the box. But the NaI mode is in this case completely noninformative since it returns NaI, and does not allow to eliminate 
the box.


If in a set covering problem the constraint of interest is never
satisfied close to the domain boundary but the latter is not
nicely aligned to the coordinate axes, the "non-NaI" mode allows
one to discard huge areas in a single evaluation.

But the NaI-implementation necessarily wastes a lot of bisections
to resolve that boundary in order to be able to get information
different from NaI that would allow one to make progress.

Moreover, in the NaI case, there is _no_way_ for programmers to
recover the lost information without implementing a "non-NaI" mode
themselves (and probably inefficiently).


In my opinion, this is the decisive argument.
Surely the future 1788 standard should not forbid a user to get the
required information easily if theory provides a way to get it easily.


Arnold Neumaier