Re: A simple interval challenge
The attachment contains the
Third intermediate report (December 4, 2008)
to my simple interval challenge from November 26, 2008.
The current best public algorithm achieves 112.5% of the optimal width.
Please report even now suboptimal solutions if they are within 150%
of the optimal width and make use of ideas not yet present!
Main changes compared to the second report:
- algorithms by John Pryce and myself
- symmetries: I had forgotten the continuous scaling symmetry
- new comments on the problem of minimizing the coefficient of c
that make it an interesting test problem for global optimization
Arnold Neumaier
A simple interval challenge (November 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.
Third intermediate report (December 4, 2008)
-------------------------
The current best public algorithm achieves 112.5% of the optimal width.
Please report even now suboptimal solutions if they are within 150%
of the optimal width and make use of ideas not yet present!
Main changes compared to the second report:
- algorithms by John Pryce and myself
- symmetries: I had forgotten the continuous scaling symmetry
- new comments on the problem of minimizing the coefficient of c
that make it an interesting test problem for global optimization
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.
(But they 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.)
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.
- Changing a sign and checking for a sign is not counted.
- Switches of rounding modes are not counted.
- 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 is isomorphic to the direct product
of R^x (Z/2Z)^4, and is generated by the scalings
(w,x,y,z) to (tw,tx,ty,tz) for nonzero t
and the transposition products
(wx)(bc)(z-z),
(yz)(bc)(w-w),
(wy)(xz)(a-a)(b-b),
(w-w)(x-x)(b-b)(c-c) or (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.)
Public solutions to the challenge
---------------------------------
1. 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)
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.
3. My first algorithm uses the representation
u=w^2+x^2;v=y^2+z^2;
B=b*(x*y-w*z)+c*(x*z+w*y);
f=(a*(u-v)+2*B)/(u+v)
Since B is multilinear, hence monotone in each argument,
we can compute an enclosure for B by specializing x and z to
their four endpoint combinations and taking the hull of the
results.
Similarly, since f is rational linear and hence monotone in
u and v, we can compute an enclosure for f by specializing
u and v to their four endpoint combinations and taking the
hull of the results.
Taking care of common subexpressions in the resulting formulas,
this leads to 54 interval operations and 12 real operations,
hence 60 effective interval operations, giving the enclosure
[-3.6517,9.2223], which is 117.4% of optimal width and has
excess cost 1.7e-3.
4. 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
good 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)
which reduce 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 bounds obtained are [-3.4000,8.9575], which is 112.7% of the optimal
width. He reports a count of <=68 effective interval operations,
giving an excess cost of 2.8e-4.
By the way, the innocent-looking subproblem
min s = 2*(xz+wy)/(w^2+x^2+y^2+z^2)
s.t. w in [-0.9,-0.6]
x in [-0.1,0.2]
y in [0.3,0.7]
z in [-0.2,0.1]
for getting the optimal lower bound for s has a continuum of global
minimizers with minimum -1, attained at any point with
z=-x in [-0.2,0.1], y=-w in [0.6,0.7].
This makes standard branch and bound codes extremely slow.
The recipe
q=(x^2+z^2)/(y^2+w^2);
s=linearInt(ratsin(x/z),ratsin(y/w),1/(1+q));
of Pryce gives the optimal lower bound, without any branching.
Nonpublic solutions
-------------------
5. Nate Hayes has an improved confidential algorithm which computes
the bounds [-3.2747,8.8322] (110.4% of optimal width) with 48
effective interval operations, using modal interval arithmetic,
giving an excess cost of 6.1e-5. [I have no way of checking
this result.]
6. I also found an improved algorithm, based on an ancient Egyptian
secret from 1650 BC or even earlier,
http://en.wikipedia.org/wiki/Sqrt#History
that gives the enclosure [-3.1073,8.1089] (102.3% of the optimal width)
with 7 interval operations and 27 real operations = 20.5 effective
interval operations - cheaper than the ordinary interval evaluation! -,
leading to an excess cost of 2.9e-9. [The algorithm and the result
were checked for correctness by Mihaly Markot from our Vienna team.]
This enclosure uses very specific properties of the particular
expression and will be very difficult to surpass. But the hints
given might be enough for someone else to match it!
I don't want to spoil your fun by revealing the solution.
I'll write up the whole challenge story including some context,
for publication in Reliable Computing; the solution will be in the
published version...
Work in progress
----------------
Lubomir Kolev obtained the bound [-3.8080,9.3655], which is 120.1% of
the optimal width, using 13 standard interval operations and
9 G-interval operations (affine arithmetic). At present, I neither
know how this translates into effective interval operations, nor the
details of the algorithm.
John Pryce noticed that f can be represented as the Rayleigh quotient
of a complex Hermitian matrix:
f = k^*Mk/k^*k where, in Matlab notation with i=sqrt(-1),
k = [w+i*x ; y+i*z];
M = [a c+i*b ; c-i*b -a];
The eigenvalues of M are -+sqrt(a^2+b^2+c^2); hence
|k^*Mk| <= sqrt((a^2+b^2+c^2)*(w^2+x^2+y^2+z^2)),
|f| <= sqrt((a^2+b^2+c^2)/(w^2+x^2+y^2+z^2)),
which gives the poor enclosure [-13.5810,13.5810].
But perhaps the idea can be better exploited in another way.