M.Sc. Molecular Modelling, Department of Crystallography, Birkbeck College

Molecular Interactions Unit: Energy Minimization

file last modified Fri 02 Feb 1996

n.b., need modern version of netscape to read this document correctly.

Lecture 2 (a) -Univariant Minimization

• Idea: Have a function of 1 variable f(x) - find the local minimum.

• In practice it is unusual to need to do this - normally when looking at a 1D function would explore by plotting a graph.

• But can be used to perform a line search for a multivariant function:
  minimize f() = f(X₀ + D)
  Here we minimize f() by varying , infact the minimization is along a line direction D from original point X₀ in the multivariant space.

• Bracketing a minimum

  Idea:
  • know function value at 3 points a, b & c where b is in between a and c,
  • also f(b) < f(c) and f(b) < f(a):
    
  • Provided that f() is well behaved (no discontinuties in the range) it is certain that there is at least one minimum in the section a, c.

  • If we take an additional point y and work out the function value can home in on the minimum. Result either:
    1. if f(y) < f(b) then new interval (a, y , b)
       
    2. or otherwise when f(y) > f(b) then new interval (y, b , c)
       
    Can see that in either case the new interval is smaller than original. By repeating the process the minimum can be localized to a smaller and smaller region until found to "sufficient" accuracy (there is a limit caused by machine precision of ^1/2 see Numerical Recipies).

    Establishing the initial bracket: We normally start a line search from a point with an idea that the function should decrease along the line. Numerical recipies gives a sensible routine for arriving at a third higher point (Chapter 10 mnbrak).

  • How do we choose where in the bracket to take the new point?

  • The pessimistic view: The Golden Section Method

    • This method makes no assumptions about the function's behaviour
    • divide the interval in the ratio 1: where is the number (> 1) which ensures the best reduction in bracket length per step:

    • Suppose interval (X₁,X₂,X₃) has already been divided in this way:
      
    • Place new point X₄ in larger interval:
      
      The new interval will either be (X₁,X₂,X₄) or (X₂,X₄,X₃) so get best reduction of length if X₄ to X₃ is longer than X₂ to X₄:
      
    • Now the interval has been reduced to (X₁,X₂,X₄) or (X₂,X₄,X₃) if this is the best reduction possible then the length X₁ to X₄ must equal X₂ to X₃:
      
    • So you can see that:
      
    • We have used the principle of scale similarity in that the divide the interval in the same manner at each stage. The number =1.618 is the golden section which is the way of diving a line of that the ratio of the larger part to the total is the same as the ratio of the smaller to larger. This number is meant to have special aesthetic properties.

      Summary

      The golden section search:
      1. Start with interval (a, b, c)
      2. Divide the large part of the interval in the ratio 1 to to get d
         
      3. Find f(d)
      4. If f(d) > f(b) new interval is (a, b, d), otherwise new interval is (b, d, c)
      5. Have we found the minimum sufficiently accurately? Yes- stop, No goto 2.
    • A very robust method - makes no assumptions about function provided there are no discontinuities it is guaranteed to work. However, it only reduces the size of the interval by a factor of each step. It has linear convergence properties - to reduce interval by factor of 10 needs (1/log[]) = 5 steps.

  • The optimistic view: Parabolic Interpolation

    In the golden section search we made no assumptions about the function we are working with. Instead lets assume that the function behaves reasonably. We have three points so lets fit a parabola to them:
    

    We will fit the functional form for a parabola:

    p(X) = q(X - r)² + t
    to the points a, b, c, which have function values f_a, f_b and f_c. The new testpoint is the minimum of the function r. As an exercise show that r is given by:
    

    The routine in practice would be indentical to the summary set out for the golden section method, except that step 2. is replaced by this choice.

    We may expect that this choice will be good as we get close to the minimum. This is because as we have seen near a minimum any function behaves like a quadratic. We can expect that in the final stages the routine will exhibit supralinear convergence properties.

    

    In life you never get something for nothing so these great convergence properties have a cost. Quadratic interpolation can fail consider the example below:

    

    As can be seen point 2 is at the minimum of the fitted parabola so the new test point will be at exactly the same place and the routine will get stuck. Another potential problem is if the interpolation routine starts to osscilate between two solutions. How can these problems be addressed?

    The answer is combine quadratic interpolation with the robust but plodding method of golden section search. When things are proceeding well quadratic interpolation is used but if things prove difficult a golden section move is made. Numerical Recipies gives such a routine.

We shall now look how these line search methods can be used to tackle optimization on multidimensional surfaces.

On to next section: Descents Methods