Re: How do I bisect unbounded intervals?
Nick et al,
Although this not directly focused on our standardization process,
I find it very interesting. In particular, I am leery of
arguments concerning "happens with probability 1." For example,
in homotopy methods for solving polynomial systems, a popular
topic of research in the 1980's, arguments were used stating
that, if you chose the starting coefficients randomly, the paths
ended at all of the solutions to the desired system "with probability 1."
In fact, most polynomial systems occurring in applications have
some kind of special structure, that, in the spaces originally
set up, occur "with probability 0."
Also, "with probability 1," a random matrix is non-singular. In the
appropriate measure space, a continuous function has non-isolated
minima "with probability 0," but, again, the models people design
are often the exceptional cases. Even with toy problems, it seems
that the "probability 0" cases are hard to avoid. For example,
a simple test problem might be to minimize (x_1 - x_2)^2.
Nonetheless, the above may not apply when choosing the point
for bisection (or trisection, or whatever).
Another consideration with probability arguments is predictability
of the algorithm behavior (or "behaviour," as might occur in our
P-1788 standard). I grant you that this is a bit of a problem
in branch and bound algorithms for optimization, even without randomization,
but the reasons for excessive computation time can be traced in
particular cases when the algorithm is deterministic, provided one
is sufficiently persistent in examining the execution process.
Best regards,
Baker
On 01/12/2012 04:45 AM, N.M. Maclaren wrote:
On Jan 12 2012, Arnold Neumaier wrote:
On 01/12/2012 09:56 AM, N.M. Maclaren wrote:
On Jan 12 2012, Jean-Pierre Merlet wrote:
What we are doing in that case in ALIAS for system solving is to
choose a random number in the unbounded interval and to bisect the
interval at that point (for bounded intervals we have tried methods to
determine a bisection point that may be better than the mid-point but
have found none that were better on a significant number of examples
of our benchmarks, hence we are using the mid-point). ...
Something that might interest people is that, subject to reasonable
constraints, using random points is within a constant factor of optimal
even for bounded intervals. I suspect that you already know that :-)
According to which measure of optimality?
Performance, accuracy, what you will. The only thing that you are
sacrificing is deterministic measures of those in favour of with
probability one. Most computer scientists seem to think that is a
major theoretical or practical issue, but that's because they don't
understand probability.
Regards,
Nick Maclaren.