Re: A simple interval challenge
The attachment contains the
Second intermediate report (December 1, 2008)
Based on requests, I made the rules a bit more precise;
see the items <new> in the challenge formulation.
The current record is
[-3.274656,8.832152] (110% of optimal width)
by Nate Hayes, with an unknown algorithm.
Arnold Neumaier
A simple interval challenge (Nov. 26, 2008)
---------------------------
In discussions with Nate Hayes, he mentioned the following test problem
(arising from a problem in computer vision) as an example for the
potential efficiency of modal interval arithmetic. With his permission,
I make the problem public, adding performance evaluation criteria
for a public contest.
Second intermediate report (December 1, 2008)
Based on requests, I made the rules a bit more precise;
see the items <new> in the challenge formulation below.
Challenge (based on a problem posed by Nate Hayes)
---------
Find a cheap and good enclosure for
f := (a(w^2+x^2-y^2-z^2)+2b(xy-wz)+2c(xz+wy))/(w^2+x^2+y^2+z^2)
given the following bounds on the variables a,b,c,w,x,y,z:
a in [7,9]
b in [-1,1]
c in [-1,1]
w in [-0.9,-0.6]
x in [-0.1,0.2]
y in [0.3,0.7]
z in [-0.2,0.1]
Please send results directly to me at <Arnold.Neumaier@xxxxxxxxxxxx>,
preferably with the computation encoded in Intlab, the Matlab interval
toolbox available from
http://www.ti3.tu-harburg.de/rump/intlab/
For the sake of simplicity, rounding error issues may be ignored.
(Butthey would have to be addressed in a good implementation.)
I'll post summaries when something interesting happens.
To expose insights and tools are the final objectives in the contest.
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.
The computation together with general theoretical results must
constitute a proof that the result is a rigorously valid enclosure
of the range. (Thus, the relevant cost is that of checking that
some data provided are a certificate for the range enclosure found.)
<new>
The algorithm used should be valid for all boxes whose bounds have
the same sign distribution as the bounds shown, irrespective of the
values of the bounds. But accuracy is tested only for this particular
data set.
The operation count (= cost) is in terms of effective interval
operations, defined for simplicity (and in view of potential
hardware realizations) as follows:
- Any unary or binary operation involving an (ordinary or modal)
interval, including taking the hull or the intersection of two
intervals, is counted as an interval operation.
- A purely real operation and a real compare (used in a branching
statement) are counted each as half an interval operation.
- <new>
Changing a sign and checking for a sign is not counted.
- Switches of rounding modes are not counted.
- <new>
Algortihms using more than 200 effective interval operations
do not qualify.
A suitable cumulative criterion to be minimized could be
excess_cost:=(width/rangewidth-1)^(dof-1)*cost,
where dof=7 is the number of degrees of freedom and rangewidth
(approx. 10.965, see below) is the width of the range.
This formula comes from the asymptotic behavior of a very simple
branch and bound scheme using simple interval evaluation, and
prefers algorithms providing sharper bounds.
Background information (updated)
----------------------
Symmetries
----------
This problem has a lot of structural symmetry, broken only by the
bound constrained specified.
The symmetry group of the problem has order 32 and isomorphism type
(Z/2Z)^5, and is generated by the following transposition products:
(wx)(bc)(z-z)
(yz)(bc)(w-w)
(wy)(xz)(a-a)(b-b)
(w-w)(x-x)(b-b)(c-c)
(y-y)(z-z)(b-b)(c-c)
Here (wx) swaps w and x, while (z-z) is a sign change of z, etc..
Exact solution
--------------
For comparison, we give the exact solution, due to computations
of Mihaly Markot and Dan Zuras).
The minimum is attained at
a=9;b=1;c=1;w=-0.6;x=(531-sqrt(284186))/50;y=0.7;z=-0.2;
fmin = (270-sqrt(284186))/89
= -2.9560785011851257870357909731159456912301156279187038495?u1
The maximum is attained at
a=9;b=1;c=-1;w=-0.9;x=0.2;y=0.3;z=(sqrt(13090)-114)/10;
fmax = (7*sqrt(13090)-48)/94
= 8.0093698421059609250021007563731486914427953942424830543?u1
The optimal width (width of true range) is
rangewidth = fmax-fmin
= 10.96544834329108671203789172948909438267291102216118690390?u1
(By Section 6.4 of ViennaProposal-v3.0, the ending ?u1 denotes the
fact that the true result is between the stated result and the number
one ulp larger in absolute value, i.e., that it is a correctly
truncated result.)
Previous solutions to the challenge
-----------------------------------
Simple interval evaluation gives the poor enclosure [-7.4889,19.2889]
(244% of optimal width) with 21 interval operations, using savings
due to precomputing u = w2+x2 and v = y2+z2 and evaluating
f = (a*(u-v)+2*(b*(x*y-w*z)+c*(x*z+w*y)))/(u+v).
(excess cost = 1.89e+2)
Raymon Moore provided a pure rearrangement evaluation
u=w^2+x^2;v=y^2+z^2;
s=b*(x*y-w*z)+c*(x*z+w*y);
f=a*(1-2/(u/v + 1)) + 2*s/(u+v);
with 24 operations, giving the enclosure [-5.8080,11.3655],
which is 157% of optimal width, and has excess cost 0.79.
Note that the rearrangements
s=(b*x+c*w)*y+(c*x-b*w)*z
s=(b*y+c*z)*x+(c*y-b*z)*w
of s lead to inferior results.
My enclosure (to be made public after it has been matched or
superseded by an algorithm that I can check))
is [-3.6517,9.2223] using 12 real and 54 interval operations,
hence 60 effective operations. This is 117% of optimal width,
and has excess cost 1.7e-3.
Nate Hayes has an improved confidential algorithm which computes
the bounds [-3.274656,8.832152] (110% of optimal width) with 48
effective interval operations, using modal intervals.
(excess cost = 6.1e-05)
Work in progress
----------------
Lubomir Kolev obtained the bound [-3.8080, 9.3655] using
13 standard interval operations and 9 G-interval operations
(affine arithmetic). I neither know how this translates into
effective interval operations, nor the details of the algorithm.
John Pryce reports the rearrangement
w2=w^2;x2=x^2;y2=y^2;z2=z^2;
p=(w2+x2-y2-z2)/(w2+x2+y2+z2)
r=2*(x*y-w*z)/(w2+x2+y2+z2)
s=2*(x*z+w*y)/(w2+x2+y2+z2)
f=a*p+b*r+c*s.
The (expensive) optimal enclosure of p,r,s gives (no outward rounding)
p in [-0.1910,0.8085]
r in [-0.6000,0.4913]
s in [-1.0000,-0.5263]
from which (even when the upper bounds on r,s are somewhat worse),
f in [-3.319,8.877].
(111% of optimal range). So the subchallenge is to find cheap and
sharp bounds on p, r and s.
Moore's recipe gives optimal bounds for p:
p=1-2/(1+q), where q=(w2+x2)/(y2+z2)
For r,s, John Pryce suggested the formulas
r=linearInt(ratsin(x/y),ratsin(-z/w),1/(1+q)), where q=(x2+y2)/(z2+w2)
s=linearInt(ratsin(x/z),ratsin(y/w),1/(1+q)), where q=(x2+z2)/(y2+w2)
This reduces the enclosure to linear interpolation
linearInt(x,y,t)=(1-t)*x+t*y
(for an optimal enclosure, see Section 5.8 of ViennaProposal-v3.0)
and the optimal interval enclosure of the special function ratsin,
where
ratsin(t):=2t/(t^2+1), ratcos(t):= (t^2-1)/(t^2+1)
provide a rational parameterization of the circle since
ratsin(t)^2 + ratcos(t)^2 = 1.
The implementation of ratsin(tt) for intervals tt is not quite trivial.
He is still in the debugging stage, and I don't know how close to
optimal the resulting bounds are.