Re: A simple interval challenge
Jean-Pierre Merlet wrote:
Arnold Neumaier wrote:
So this contest is not about testing the performance of existing
software but about testing (and making public) the bag of tricks
experts have to squeeze the best out of a very limited budget for
one range enclosure.
I am not interested in enclosures that need more than 200 effective
interval operations; this probably eliminates most branch and bound
packages (quite apart from the fact that it is difficult to count
there the number of operations).
Ok, fine by me. But what will also be useful is a full description of
the manipulation that led to the various bounds. This may be indeed
interesting to see if we can somewhat automatize the process
Yes. This is the ultimate purpose of the challenge.
I'll provide as much detail as I can get from those submitting
answers to the challenge. In particular, I'll try to reprogram
the recipes in Intlab (if they are not yet in this format,
which would be a significant help; see below for a template)
to check the results before putting them online.
It is likely that all tricks can be automatized to work not only
for this example but in more general situations, though it may
not always be easy to decide which trick should be applied when.
So these choices should probably be made in a semi-automatic way
based on statistics on trial inputs and perhaps also guided
by interventions from a graphical user interface.
The results will also show those not so familiar with interval
methods but more concerned about low level implementations which
issues really matter for efficiency in user applications.
The standard should help expert programmers to exploit the
potential of interval methods to the fullest, while not
significantly degrading ease of use for non-experts.
Arnold Neumaier
=====================================================================
% optimal width = width of true range
rangewidth = 10.9654483432912
% define input box
a=infsup(7,9);b=infsup(-1,1);c=infsup(-1,1);
w=infsup(-0.9,-0.6);x=infsup(-0.1,0.2);
y=infsup(0.3,0.7);z=infsup(-0.2,0.1);
% display input box
infsup(a),infsup(b),infsup(c)
infsup(w),infsup(x),infsup(y),infsup(z)
% compute intermediate results % work count
u=w^2+x^2;v=y^2+z^2; % 2 x (1+,2 sqr)
infsup(u),infsup(v)
A=a;
B=b*(x*y-w*z)+c*(x*z+w*y); % 3+,6*
C=2*B; % 1 *
infsup(C)
% naive result with 21 ops (8+,4 sqr,8*,1/)
ff=(A*(u-v)+C)/(u+v); % 3+,1*,1/
fnaive=infsup(ff)
wnaive=sup(ff)-inf(ff)
qnaive=wnaive/rangewidth
enaive=(qnaive-1)^6*21
% Moore's recipe with 24 ops (9+,4 sqr,8*,3/)
ff=a*(1-2/(u/v + 1)) + C/(u+v); % 4+,1*,3/
fmoore=infsup(ff)
wmoore=sup(ff)-inf(ff)
qmoore=wmoore/rangewidth
emoore=(qmoore-1)^6*24