Date: Wed, 28 Feb 96 14:33:23 +0100
From: rump@tu-harburg.d400.de ( Prof.Dr.S.M. Rump)
subject:  back to the roots


In the discussion about global optimization methods it has been
mentioned that recently developed and very effective methods are

     i) the combination of local search methods with
        branch-and-bound techniques together with interval methods,
and ii) the use of the so-called expansion principle.

The second method proves existence and uniqueness of a stationary
point first in a small interval, and then expands this interval
again proving that there is one and only one stationary point in
the larger interval. Therefore the difference between both sets
cannot contain a stationary point and can be discarded.

If something proves to be useful and one has used it frequently
enough, it seems to be natural to forget about the roots.

Therefore I would like to mention that to all of my knowledge
in this case Dr. Christian Jansson is the origin. He developed
many interesting algorithms for the one- and n-dimensional case
and gave a number of talks about this starting in 1990.

To my knowledge he was the first who combined local search
algorithms with validation algorithms, and he invented the
expansion principle. There is a written report on both techniques
dated November 1991. The reference is

     C. Jansson: A Global Minimization Method: The One-Dimensional
       Case, Technical Report 91.2, Forschungsschwerpunkt
       Informations- und Kommunikationstechnik, Technical
       University Hamburg-Harburg, 1991.

In this report Jansson showed that on well-known examples from
the literature his method with verified bounds for the global
optimum is comparable in speed with purely numerical methods
(without any verification). In fact, sometimes his methods with
verification was even faster. He compared to the well-known
algorithms by Zilinskas, Brent, Batishev, Strongin and others.

A large collection of numerical results is contained in

     C. Jansson and O. Kn
ppel: A Global Minimization Method: The
       Multi-Dimensional Case, Technical Report 92.1,
       Forschungsschwerpunkt Informations- und
       Kommunikationstechnik, Technical University
       Hamburg-Harburg, 1992.

     C. Jansson and O. Kn
ppel: Numerical results for a
       Self-Validating Global Optimization Method, Technical
       Report 94.1, Forschungsschwerpunkt Informations- und
       Kommunikationstechnik, Technical University
       Hamburg-Harburg, 1994.

The reports contain numerical results of about 50 test problems,
including the test set of Hansen. Jansson achieves a remarkable
speed up compared to existing algorithms. Even the global optimum
of the Griewank function for dimension 50 (!) is calculated with
verification (!) in less than 3 minutes on a SUN Sparc Station 1
with accuracy better than 15 decimal places. There is only one
reference of a pure floating point algorithm in the literature
being able to provide a solution for that problem for dimension
10 .

Further references include

     C. Jansson: On Self-Validating Methods for Optimization
       Problems, in J. Herzberger (ed.): Topics in Validated
       Computations, Elsevier Science B.V., pp. 381-438, 1994.

     C. Jansson and O. Kn
ppel: A Branch and Bound Algorithm for
       Bound Constrained Optimization Problems without
       Derivatives, Journal of Global Optimization 7, pp.
       297-333, 1995.



Regards,   S.M. Rump