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  :

        .  

Proof  Quadratic and Cubic Search  Quadratic and Cubic Search  

    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:    

        .

Thus  .  The cubic approximating polynomial   is expanded in a Taylor series about   (which is the abscissa of the minimum).  At the minimum we have  , and we write   in the form:    

(6)        ,  
    and
(7)        .  

The introduction of    in the denominators of (6) and (7) will make further calculations less tiresome.  It is required that  ,  ,  ,  and  .  To find   we define:  

(8)        ,   

and we must go through several intermediate calculations before we end up with .  

Use use (6) to obtain    

          
        
Then use (8) to get  

          

Then substitute   and we have  

(9)          

Use use (7) to obtain    

          

          

Then use (8) to get  

          

Then substitute   and we have  

(10)          

Finally, use (7) and write  

        

Then use (8) to get  

(11)        

Now we will use the three nonlinear equations (9), 10), (11) listed below in (12).  The order of determining the variables will be    (the variable will be eliminated).

                  
(12)           
                

First, we will find    which is accomplished by combining the equation in (12) as follows:  

       

Straightforward simplification yields  ,  therefore    is given by  

(13)        .   

Second, we will eliminate    by combining the equation in (12) as follows, multiply the first equation by    and add it to the third equation    

          
          
        
          

which can be rearranged in the form  

          

Now the quadratic equation can be used to solve for    

          

It will take a bit of effort to simplify this equation into its computationally preferred form.

          
        
          
        
        
Hence,  

(14)        

Therefore, the value of    is found by substituting the calculated value of    in (14) into the formula  .  To continue the iteration process, let    and replace and with and , respectively, in formulas (12), (13), and (14).  The algorithm outlined above is not a bracketing method.  Thus determining stopping criteria becomes more problematic.  One technique would be to require that ,  since  .

Proof  Quadratic and Cubic Search  Quadratic and Cubic Search  

Algorithm (Quadratic Search for a Minimum).  To numerically approximate the minimum of    on the interval    by using a "quadratic interpolative" search.  Proceed with the method only if    is a unimodal function on the interval  .   The initial step size is chosen to be

Computer Programs  Quadratic and Cubic Search  Quadratic and Cubic Search  

Mathematica Subroutine (Quadratic Search for a Minimum).

Example 1.  Find the minimum of the function    on the interval    using the quadratic search method.
Solution 1.

Algorithm (Cubic Search for a Minimum).  To numerically approximate the minimum of    on the interval    by using a "cubic interpolative" search.  Proceed with the method only if    is a unimodal function on the interval  .   

Start with  ,  ,  and    and use the following sequence steps in the iteration:

          

          

          

          

          

          
        
        for   .  

Computer Programs  Quadratic and Cubic Search  Quadratic and Cubic Search  

Mathematica Subroutine (Cubic Search for a Minimum).

Example 2.  Find the minimum of the function    on the interval    using the cubic search method.
Solution 2.

Various Scenarios and Animations for the Quadrat and Cubic Search Methods.

Example 3. Find the minimum of    on the interval    using the quadratic search method.
Solution 3.

Animations (Quadratic Search  Quadratic Search).  Internet hyperlinks to animations.

Example 4. Find the minimum of    on the interval    using the cubic search method.
Solution 4.

Animations (Cubic Search  Cubic Search).  Internet hyperlinks to animations.

Research Experience for Undergraduates

Quadratic and Cubic Search  Quadratic and Cubic Search  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Quadratic and Cubic Search

(c) John H. Mathews 2004