Re: Branch & bound for not everywhere defined constraints
P1788
Getting back to work after getting an infection that I am fairly sure
was the dreaded swine flu. (I used to wake up in the night going
"Oink!") It has left me quite weak.
On 5 Sep 2009, at 13:33, Corliss, George wrote:
This thread reminds me of a discussion that MIGHT be slightly
related: Tagged intervals.
I changed the subject line back to what it was before George renamed it.
IMO George is talking SERIOUS good sense here. This discussion has
made me repent in sackcloth and ashes -- well, to some extent -- of
the straightforward set-theory view I took of evaluating the range in
Motion 6 rationale, §3.5.4.
The issue I'm addressing is: how to handle partial (= not everywhere
defined) explicit real functions f. For simplicity assume f is
defined by straight-line code, in terms of elementary (library)
functions e. Here are my thoughts.
A.
Take Nate's illuminating example of using branch-and-bound to find a
subset S1 (as large as practicable within some resource constraints)
of the set
S = { x | f(x) is defined and <= 0 },
where it is assumed that f is NOT everywhere defined.
Let ff denote the interval extension of f, defined by whatever code
you have written for f.
It seems to me the search process really only has 3 cases, apart from
the termination criterion that Nate calls eps(X). Given a nonempty
box X:
CASE CONCLUDE
(1) ff is possibly not everywhere defined
on X, but ff(X) > 0 . X is disjoint from
S. Reject X.
(2) ff is everywhere defined on X
and ff(X) <= 0 X \subseteq S. Add X
to S1.
(3) Anything else Mark X indeterminate
if eps(X) is true,
else subdivide X and
recurse.
Case (1) implies f(x) > 0 at all points in X where f is defined. It
includes the case where ff(X) is empty, which does not need special
treatment. (Someone said Nate's assumption that ff always computes
the exact range isn't needed for defining the algorithm. I agree --
it makes the process more efficient in general, but that's all.)
B.
It's essential to have some way to report that f is
"possiblyUndefined" somewhere on X. The basic scheme is to make each
interval elementary function ee, of which ff is composed, clever
enough to report this when (preferably only when, but that's a QoI
matter) its input argument -- regarded as a box -- fails to be
contained in its domain.
IF f is undefined at some point of X,
THEN evaluating ff(X) will report "possiblyUndefined".
(The converse is usually false, i.e. this scheme is inherently
overcautious.)
My point, which I hadn't fully appreciated when I wrote Motion 6
rationale, is
B1. Sometimes, if "possiblyUndefined" is reported one
isn't much interested to know the value of ff(X).
B2. Sometimes one just wants to know ff(X) and is unconcerned
whether "possiblyUndefined" was reported or not.
B3. But sometimes one wants ff(X) AND one wants to know
whether "possiblyUndefined" was reported.
[There are also applications where "reverse operations" are
appropriate, but following Vienna 3.9-3.11, these will be implemented
as entirely different library functions, so aren't relevant here.]
Case B1 is typical in validated solution of ODEs. It occurs when
checking ff(X) \subseteq X, to apply a fixed-point theorem. Only if
"possiblyUndefined" was NOT raised is the theorem applicable, so when
it IS raised, the value of ff(X) is of no use.
Case B2, if I understand aright, is typical in a simple branch-and-
bound method for global minimisation.
Case B3 was new to me, and is required in Nate's application, to
check case (1) above.
In Motion 6 I required one _always_ returns the value ff(X), which is
unwarranted as it precludes possibilities associated with case B1.
Sorry.
C.
So how to report "possiblyUndefined"? Surely Nate is right and we
should assume:
The action is in massively data-parallel applications,
on vector-processors, or SIMD processor arrays. Or think of component-
wise operations on large arrays in MATLAB.
A single global "possiblyUndefined" flag is useless -- assuming we
need to know "possiblyUndefined" on a component-wise basis. In my
cases B1-B3 above:
- In case B1, instead of returning the actual ff(X) value
we can return a special value meaning "possiblyUndefined".
(This value would be one of the flavours of NaI.)
No extra storage or tags required.
- In case B2, we can put the interval library functions
into a different mode that just ignores "possiblyUndefined".
Or have a separate library for the purpose -- is that the
so-called "two op-codes solution"?
Again, no extra storage or tags required. And in this case,
no NaI, of whatever flavour, required (I think).
- But in case B3, there's no way round extra storage.
D.
Apart from the discredited single flag, I see 2 ways to solve the
case B3 problem. Both have been proposed in these discussions.
D1. "Decorate" intervals as described by George.
Return status data in the extra fields.
D2. Have a separate interval library, where status data
is returned in extra output argument(s) of the functions;
these arguments therefore constitute the "extra storage".
This is the method adopted in the Bronnimann, Melquiond,
Pion draft C++ interval standard.
I agree with George that KISS rules out D1 as far as P1788 is
concerned. For one thing: a basic interval in "double" format is 16
bytes wide. Is P1788 going to decorate it with an extra byte, say,
and offer the world an IEEE standard data-type of width 17 bytes? We
should be a laughing stock.
A disadvantage of D2 is its huge clumsiness for the programmer. y =
a*b + c has to be converted to something like
v1 = times(a,b,flag)
y = plus(v1,c,flag)
If my function is defined by a page or two of code, I cannot convert
it reliably to that form by hand. Such a scheme can only handle "toy"
applications, until someone has written a code-conversion tool.
I hope Hilaire Belloc's immortal words don't apply to us:
Physicians of the utmost fame [that's us, except for
the fees part]
Were called at once, but when they came
They answered, as they took their fees,
"There is no cure for this disease".
E.
Would my possibly utopian idea of a "pointer to flag" work in the
vector/SIMD situation?
Namely, neither the compiler writer not the user wants a
"possiblyUndefined" flag to be global. Ideally it should live in the
stack frame ("the calling program") from which interval function ff
is called.
Suppose ff is vectorised, i.e. each elementary operation acts
component-wise on vectors of fixed length n to produce an output of
length n.
- In the calling program, define a flag array FLAG of length n,
initialised to 0.
- Call a system-function that stores the address of FLAG in a
register pFLAG known to all the library functions.
- Call ff. Each vector operation, say ww = uu op vv, is coded so that
it records the status component-wise in FLAG. That is, if
uu[i] op vv[i] raises "possiblyUndefined",
then by indirection through pFLAG, it sets FLAG[i] to 1.
On return from ff, the array FLAG (which is local to the calling
program) equals 1 in exactly those components for which the
calculation raised "possiblyUndefined".
Nate, is such a scheme efficiently implementable? If so, it seems to
handle cases B1, B2 and B3 above without the tags on intervals, or
extra (explicit) output arguments of operations, required by
solutions D1, D2 above.
Best wishes
John