5 Local and Global Optimization

Topographical Global Optimization

Topographical Global Optimization (TGO) is clustering type algorithm where actually no clusters are formed but instead points that are better than a prespecified number k of their nearest neighbours are determined. These are called topograph minima and are candidate starting points for local optimization. A number N of points are initially uniformly sampled in the region of interest A and from this set the topograph minima are directly determined.

   TGO
     1. Sample i=1..N points xi in A, fx(i)=f(xi)
     2. Compute the distance matrix dd(i,j) = distance2(xi,xj)
                               (Observe that dd(i,j)=dd(j,i))
     3. For each point find out if it is a topograph minimum
        if k > N-1 then k=N-1
        for i=1..N do
           for j=1..N do
              d(j) = dd(i,j)
           d(i) = maxreal    ! Distance to itself a big number
           for kk=1..k do   ! Find k nearest neighboors
              min = maxreal; ! Min dist initially a big number
              for j=1..N do ! Find next neighboor
                  if min > d(j)
                  then IDmin = j; min = d(j);
              d(IDmin) = maxreal 
              if fx(i) > fx(IDmin) then next i ! Not t-min
           Add point i to the topograph minima TM
                           
      4. Use the points in TM as starting points for  
                                  local optimization

An iterative version of TGO, ITGO, can be obtained by performing TGO iteratively. In this case the m minima of iteration i are saved and used in the next iteration i+1 by sampling N-m new points. After a number of iterations the resulting minima are displayed. In this way we can use a large number of points and still have a moderately sized distance matrx.

One could also include as step 1.5 into the iterative algorithm some device to concentrate the points around local minima either by discarding "bad" points (using N' > N in step 1) or by executing some steps of a local procedure.

A. Törn, S. Viitanen: Topographical Global Optimization,
    in: C.A. Floudas and P.M. Pardalos (eds.), Recent Advances 
    in Global Optimization, Princeton University Press, 384-398,
    1992.
A. Törn, S. Viitanen: Topographical Global Optimization Using
    Pre-Sampled Points,  Journal of Global Optimization 5:
    267-276, 1994.
A. Törn, S. Viitanen: Iterative Topographical Global Optimization,
    in: C.A. Floudas and P.M. Pardalos (eds.), State of the Art in
    Global Optimization, Kluwer Academic Publishers, 353-363, 1996.