Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Another proposal for a "split" function to complement "mid"

On 03/18/2012 05:02 PM, John Pryce wrote:


But I see the need for a split(xx) function for those who do Branch&  Bound and similar work.

Arnold proposed a "median" idea based on finding a value xmed such that there are about as many FP numbers between xlo and xmed as between xmed and xhi, but has dropped it for the present. Dan is thinking along similar lines, but his method seems to be parameterized by the FP radix, which doesn't appeal to me much.

Can I propose a more mathematically based "median"? It's parameterized by a single number L>0, a "length scale", which the user chooses to suit the application. Like the other proposals, it is symmetric round 0, and:
- If |xlo|, |xhi| are somewhat<  L, it is almost
   the same as arithmetic mean.
- If xlo somewhat>  L, or xhi somewhat<  -L, it
   is almost the same as geometric mean.

The idea is to use the asinh(x) function, which is like x for |x| small, like log(x) for x somewhat>  1, and like -log(-x) for x somewhat<  -1. You transform from the x variable to a y variable by
   Divide by L to fit the length scale,
   Take asinh.
You take the arithmetic mean in the y variable and transform back to the x variable by
   Take sinh,
   Multiply by L.
L can be fixed at 1, as a sensible branch and bound algorithm will scale the problem anyway for good numerical performance of other auxiliary routines. Thus the extra parameter is gone.
But a split routine worthy of standardization must return NaN if one cannot split the interval, i.e., when it contains <=2 machine numbers (this also covers the empty set), and must treat infinity sensibly. I don't know whether there is an elegant way to do the latter in a way agreeable for everyone.
In 2004, my proposal for splitting was the safeguarded geometric mean, as defined in Section 12 of my optimization survey 
   http://www.mat.univie.ac.at/~neum/papers.html#glopt03
(p. 34 of the local copy). It has two parameters q and mu (of which mu is taken 1 in our implementations).