Quadratic Interpolative Search

Background for Search Methods

    An approach for finding the minimum of    in a given interval is to evaluate the function many times and search for a local minimum.  To reduce the number of function evaluations it is important to have a good strategy for determining where    is to be evaluated.  Two efficient bracketing methods are the golden ratio and Fibonacci searches.  To use either bracketing method for finding the minimum of  ,  a special condition must be met to ensure that there is a proper minimum in the given interval.

Definition (Unimodal Function)  The function    is unimodal on  ,  if there exists a unique number   such that  
    
          is decreasing on  ,  
    and
          is increasing on  .  

Minimization Using Derivatives

    Suppose that    is unimodal over    and has a unique minimum at  .  Also,  assume that    is defined at all points in  .   Let the starting value    lie in  .   If     ,  then the minimum point  p  lies to the right of  .  If     ,  then the minimum point  p  lies to the left of  .  

Background for Bracketing the Minimum

    Our first task is to obtain three test values,  
    
(1)            ,
    so that
(2)            .

Suppose that  ;  then    and the step size  h  should be chosen positive.  It is an easy task to find a value of  h  so that the three points in (1) satisfy (2).  Start with    in formula (1) (provided that  );  if not, take  ,  and so on.

Case (i)      If (2) is satisfied we are done.  

Case (ii)      If  , then  .  
        We need to check points that lie farther to the right.  Double the step size and repeat the process.  

Case (iii)      If  , we have jumped over  p  and  h  is too large.  
        We need to check values closer to  .  Reduce the step size by a factor of    and repeat the process.  

When  ,  the step size  h  should be chosen negative and then cases similar to (i), (ii), and (iii) can be used.  

Quadratic Approximation to Find  p

Finally, we have three points (1) that satisfy (2).  We will use quadratic interpolation to find  ,  which is an approximation to  p.  The Lagrange polynomial based on the nodes in (1) is

(3)        ,  

where  .  

The derivative of    is  

(4)        .  

Solving    in the form    yields  

(5)        .  

Multiply each term in (5) by    and collect terms involving   :

      

      

      

    

This last quantity is easily solved for  :

        .  

    The value    is a better approximation to  p  than  .  Hence we can replace    with    and repeat the two processes outlined above to determine a new  h  and a new  .   Continue the iteration until the desired accuracy is achieved.  In this algorithm the derivative of the objective function    was used implicitly in (4) to locate the minimum of the interpolatory quadratic.  The reader should note that the subroutine makes no explicit use of the derivative.  

Cubic Approximation to Find  p

    We now consider an approach that utilizes functional evaluations of both    and  .  An alternative approach that uses both functional and derivative evaluations explicitly is to find the minimum of a third-degree polynomial that interpolates the objective function    at two points.  Assume that    is unimodal and differentiable on  ,  and has a unique minimum at  .  Let  .  Any good step size  h  can be used to start the iteration.  The Mean Value Theorem could be used to obtain    and if    was just to the right of the minimum, then the slope might be twice which would mean that   we do not know how much further to the right lies, so we can imagine that is close to and estimate h with the formula:    

        .