Re: Branch & bound for not everywhere defiend constraints
Arnold Neumaier wrote:
> 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.
No. In the Paving B example, it is known before the branch-and-bound
algorithm begins that the interval result will never be of any use if a
domain violation occurs (with exception, see below).
>
>
>> 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.
Sometimes in a set-covering problem, this can occur. It could be overcome by
the several NaIs idea. For example, if a function is possibly undefined but
also strictly positive, this information can be encoded in the NaI.
In other types of problems, such as finding intersection of two parametric
functions, this is not an issue.
>
> 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).
This argument depends on what information may or may not be encoded in the
NaI and what is the user trying to accomplish.
It also cuts both ways and potentially holds true for the non-NaI approach,
as well. The 128-bit SSE registers on existing Intel computers, for example,
don't allocate a unique flag for each floating-point value in the register,
i.e., all of the floating-point values share a common flag (Section 4.10.4
of the AMD Architecture Programmer's Manual even recommends using NaN
payloads to identify which element in a vector processing operation caused
the trouble). With the trend being in the direction of large vector
processing units, I don't think it's wise to assume a unique flag will
always be available to associate with each interval. Even if they were,
having to rely on flags in this type of computational environment comes with
potential memory, clock-cycle and bandwith limitations. If 1788 decrees
flags must be the solution, it may create a situation where hardware
vendors -- in order gain competitive advantage -- will look to
non-conforming alternatives. And then, well, so much for a standard.
I think there is a lot to be potentially gained by further investigating the
several NaIs idea together with a NaI-mode approach. I think there also is a
lot to be potentially lost by dismissing the idea prematurely.
Nate Hayes