Binary predicates
Ralph Baker Kearfott wrote:
[Re: Disjoint, subset, & interior, or more...???]
On 10/3/2010 17:54, Dan Zuras Intervals wrote:
But back to the technical issue, I am not convinced by
Arnold's big 3: disjoint, subset,& interior. I'm OK with
the first two but the 3rd bothers me.
.
I believe Baker is correct that someone should make some
sort of unifying or simplifying motion on this matter.
And I feel eminently unqualified to do so.
A couple of other people have expressed similar sentiments. I am willing
to actually make that motion, just to move things along, if Arnold is still
unwilling to formally register and participate officially. However, it may
add to the confusion if such a motion is put forward before 13.04, 20,
and 21 are
processed. What do you think?
Attached is a position paper on the subject, ready for discussion and
voting. Thus you or anyone else may turn it into a motion.
Arnold Neumaier
Binary predicates involving intervals
-------------------------------------
Position paper by Arnold Neumaier (Vienna)
October 11, 2010
Proposed is that, consistent with Motion 3. the standard shall require
for every supported idatatype operations resulting in a truth value
True or False, embodying the six predicates
x in A (x belongs to A)
x interior A (all z in some neighborhood of x belong to A)
A disjoint B (for all real x: never x in A and x in B)
A subset B (for all real x: x in A implies x in B)
A interior B (for all real x: x in A implies x interior B)
A equal B (for all real x: x in A if and only if x in B)
with their standard mathematical interpretation given in parentheses,
including the handling of Empty and of unbounded intervals.
Here A and B are intervals, and x is a real number; in a 754-conforming
implementation, x in A and x interior A shall evaluate to False if
x is +Inf, -Inf, qNaN, or sNaN.
No other binary relations between intervals or between an interval
and a real shall be required.
A small list of optional binary relations may be specified in the
standard so that, if provided by an implementation, they have a
well-defined behavior. (This list might be empty, or consist of a few
of the relations defined in Motion 13.04.)
Proposed is also that the final standard text defines the value of
these predicates also for decorated intervals and for bare decorations.
(One natural possibility for doing so is suggested in Section 5 of
the Rationale.)
Rationale
---------
1. Past use and necessity
1.1. The proposed relations (and only these) have been frequently used
in the past in applications of interval methods.
1.2. Four of them (subset, interior, in, and the second interior)
are indispensible in applications to verified optimization,
verified solving of nonlinear systems of equations and constraint
satisfaction problems, and the verified solution of differential
equations:
No code for proving existence (of solutions of systems of equations
and/or inequalities, or of ODEs) can work without either subset or
interior, and both versions are actually in use in a number of current
verification tools. Moreover, one needs to check whether the center
used in an existence test is in the interval of interest, and for some
tests if it is interior.
1.3. Similarly, verification of nonexistence is always based on checking
disjointness of intervals. But the predicate disjoint is not
indispensible since one can check for disjointness by computing the
intersection and then checking it for being empty.
The predicate equal also doesn't play an indispensible role in working
code.
But both equal and disjoint facilitate debugging of code under
development.
2. Grounding in traditional mathematics
2.1. All proposed predicates have standard set-theoretic/topological
definitions with a century-long tradition in mathematics.
They are easy to define and easy to remember since no new terminology
must be learnt. This ensures that the semantics comes across clearly
and unambiguously.
All proposed predicates vectorize, by and-ing or or-ing the
componentwise evaluation.
2.2. Tampering with these definitions only introduces confusion and
possible sources of errors. In particular, Empty must be a subset of,
interior to, and disjoint to any interval, Entire must be interior to
Entire, and [1,Inf] must be interior to [0,Inf] although only one
bound differs.
2.3. The set-theoretic/topological interpretation is needed for full
consistency with Motion 3, which specifies that intervals are the
closed and connected sets of real numbers in the standard topology of
the reals.
2.4. It is also needed to match the relations as they occur in
mathematical theorems deducing existence or nonexistence, which are of
crucial importance for verificrtion techniques in optimization, linear
and nonlinear systems of equations, constraint satisfaction problems,
and differential equations.
The only comparisons in the assumptions of the known theorems that
produce existence statements are of the form
x in B, or x interior B. (1)
z in B, or z interior B, (2)
A subset B, or A interior B, (3)
and that produce nonexistence statements are of the form (2) or
A disjoint B; (4)
On the other hand, conclusions of theorems involving solutions are
typically of the form
x in A, or x interior A. (5)
Here in all cases x is an unknown point about which information is
desired, z is a chosen point, B is a chosen domain, and A a computed
range enclosure.
3. Executable definition
3.1. A possible branch-free and 754-conforming implementation for bare
intervals, with Empty represented as [qNaN,qNaN], is as follows,
using A=[al,au], B=[bl,bu]:
A disjoint B
~( au>=bl && bu>=al )
A subset B
( al>=bl && au<=bu ) || isEmpty(A)
A interior B
~( bl-al>=0 || au-bu>=0 || isEmpty(B) ) || isEmpty(A)
A equal B
( al==bl && au==bu ) || ( isEmpty(A) && isEmpty(B) )
x in A
x>=al && x<=au && isFinite(x)
x interior A
x>al && x<au && isFinite(x)
Here ~ stands for ''not''.
|| means an ''or'' that does not need to evaluate the alternative
if the first argument is already True.
Similarly, && means an ''and'' that does not need to evaluate the
alternative if the first argument is already False.
Of course, there are a number of equivalent rewritings, and implementors
are not bound to the particular versions given.
3.2. Reasoning for the correctness of A interior B:
If A is empty, this is True.
Hence assume A is nonempty.
Then the value is that of the first operand.
If B is empty, this is false, and the expression correctly evaluates
to False.
Hence assume A and B are nonempty.
Then the value is opposite to that of z:=(bl-al>=0 || au-bu>=0).
If the first difference is NaN then al and bl are both -Inf;
otherwise the first inequality is equivalent to bl>=al, and fails
iff bl<al.
If the second difference is NaN then au and bu are both +Inf;
otherwise the second inequality is equivalent to au>=bu, and fails
iff au<bu.
Therefore:
If both differences are NaN then A and B are Entire, z is False,
and the expression evaluates to True.
If only the first difference is NaN, z is False (and the expression
is True) iff au<bu. But the lower bounds are both -Inf, so this
defines the interior correctly.
The same argument applies if only the second difference is NaN.
But if neither difference is NaN then z is False (and the
expression is True) iff both inequalities are False, i.e.,
both bl<al and au<bu. Again, this matches the definition of
interior.
4. Behavior under overestimation
4.1. For interval computations, a predicate and its negation are not on
equal footing, since false positives and false negatives have
different consequences.
4.2. The standard must ensure that a positive answer that triggers
decisive consequences must never be wrong, and require a corresponding
semantics.
For the application in rigorous algorithms one just needs to be sure
that the above relations, when queried with result True, really hold
with certainty.
Indeed, one is going to draw conclusions from the result True,
namely nonexistence in case of disjointness, existence in case of
containment or interiorness (if also other conditions like continuity
etc. hold).
On the other hand, from a False, one just draws the conclusion that
one lacks information and therefore continues the usual procedure
(iteration, branching, bounding, etc.).
This is the usual situation since interval arithmetic is conservative
and may lose _some_ information about ranges on the way.
This is both the blessing and the curse of intervals. It allows to
gain global information through it, but this information is less than
perfect.
4.3. Thus assumptions in theorems must never have false positives
(evaluated to true because of overestimation of A although being false
for the exact range A).
But they are insensitive to false negatives, since nothing follows
from a violation of an assumption of a theorem.
On the other hand, since in the cases of interest, the conclusions of
the theorems cannot be checked algorithmically except by invoking these
theorems, they are indifferent to algorithmic issues.
4.4. Example: Under typical circumstances, as soon as one has
N(X) interior X,
where X is a Newton operator, one knows that X contains a solution.
In this situation, X is an arbitrary domain, independent of the history
how it was created, whereas N(X) is a computed (and possibly
overestimated) interval extension of the Newton operator kind.
Thus in an interval Newton iteration,
X_{i+1} = N(X_i) intersect X_i
once you know X_{i+1} interior X_i without false positive
with respect to overestimation in X_{i+1}, one can be sure that X_i
(no matter how it was computed) contains an interior solution.
4.5. Thus, false negatives are harmless in equations (1)-(5), while to
be safe, false positives must be avoided by any specification of the
standard in case of (3) or (4) when A is overestimated but B is exact.
((1) and (5) are never tested directly since x is not a datum,
and (2) involves only chosen, hence exactly represented data.)
This is the case for undecorated intervals when the standard
topological textbook definition of the above relations is used.
5. Behavior for decorations
5.1. To ensure safety also for decorated intervals and bare decorations,
the standard shall uptimately contain appropriate specifications.
There are various possibilities, of which the simplest seems to be the
following ''simple mode''.
5.2. In the simple mode, the result is always false whenever one of
the arguments is a bare decoration.
Otherwise, the result is that obtained by ignoring the decorations.
5.3. The simple mode matches the interpretation of all bare decorations
as NaI's, as discussed in Motion 8.
It also accounts for the fact that in the applications, the predicates
are usually evaluated at the beginning or end of interval calculations,
invoking a mathematical theorem where the decorations must be inspected
separately anyway. Thus separating the functionality is appropriate.
5.3. Other reasonable choices exist but are less simple, and unlikely
to be more useful. For example, one could treat bare decorations with
the interpretation of Empty or Entire differently, and require that
the result for bare decorations is False if some interval consistent
with the decoration leads to a False, and True otherwise.
6. Result type
6.1. Predicates shall return a Boolean, since this is what users
expect. Nothing more is needed, because of the reasons stated in the
previous sections.
6.2. In particular, there is no need for a multi-valued logic (trits
or tetrits).
Having trits or tetrits makes the algorithm for deciding the value more
complex. It also causes overhead for users, since they need to retrieve
the Boolean from the tetrit by means of some additional operation, and
the compiler must undo all the commplexity added by the trit/tetrit.
7. Other binary predicates
7.1. The use of other binary predicates is minor, and their importance
was not convincingly demonstrated.
7.2. Unlike for reals, where there is a widely used general practice
employing all of
=, ~=, <, <=, >, >=,
and in finite precision even different versions of these, there is no
such record of actual use for most of the predicates that were discussed
in this forum.
7.3. The purpose of a standard is to promote good, well-established use
with a consistent semantics, and select these uses from all proposed
or possible uses. Predicates that haven't found significant use in
past or current programming code have nothing to do in a standard.
Adding to a standard any functionality without practical use is only a
burden, both to users (who must take extra care that they catch the
right fish among many similar possibilities with slightly different
meaning) and to implementors (who must write the implementations and
provide ingenious mnemonic for differentiating the cases).
7.4. Moreover, the more predicates with similar but distinct meanings
are available, the more confusing may it be for users to select the
right predicate matching their intention.
As Kahan said on a similar occasion, such additions would therefore
fill a much needed gap (-;).