Gradient and Newton's Methods

    Now we turn to the minimization of a function of  n  variables, where    and the partial derivatives of are accessible.  

Steepest Descent or Gradient Method

Definition (Gradient).  Let be a function of such that    exists for  .  The gradient of , denoted by  ,  is the vector  

(1)        .  

Illustrations

    Recall that the gradient vector in (1) points locally in the direction of the greatest rate of increase of .  Hence    points locally in the direction of greatest decrease .  Start at the point    and search along the line through   in the direction  .  You will arrive at a point  ,  where a local minimum occurs when the point   is constrained to lie on the line  .  Since partial derivatives are accessible, the minimization process can be executed using either the quadratic or cubic approximation method.

    Next we compute    and move in the search direction  .  You will come to  ,  where a local minimum occurs when   is constrained to lie on the line  .  Iteration will produce a sequence,  ,  of points with the property

        

If    then   will be a local minimum .  

Outline of the Gradient Method

    Suppose that    has been obtained.  
    
(i)    Evaluate the gradient vector  .  

(ii)    Compute the search direction  .  

(iii)    Perform a single parameter minimization of    on the interval  ,  where b is large.  
    This will produce a value    where a local minimum for  .  The relation    
    shows that this is a minimum for    along the search line  .
                            
(iv)    Construct the next point  .

(v)    Perform the termination test for minimization, i.e.
    are the function values    and    sufficiently close and the distancesmall enough ?

Repeat the process.

Proof  Gradient Search  Gradient Search  

Algorithm (Steepest Descent  or Gradient Method).  To numerically approximate a local minimum of  ,  where  f  is a continuous function of  n  real variables and    by starting with one point    and using the gradient method.

Computer Programs  Gradient Search  Gradient Search  

Program (Steepest Descent  or Gradient Method).  To numerically approximate a local minimum of  ,  where  f  is a continuous function of  n  real variables and    by starting with one point    and using the gradient method.  If partial derivatives are accessible, the minimization process can be executed using either the quadratic or cubic approximation method.  For illustration purposes we use the quadratic approximation method for finding a minimum.  

Example 1.  Use the gradient search method to find the minimum of   .  
Solution 1.

Example 2.  Use the gradient method to find the minimum of      
Rosenbrock's parabolic valley, circa 1960.
Solution 2.

Exercise 3.  Use the gradient method to find the minimum of  .  
Looking at your graphs, estimate the location of the local minima.  
Solution 3.

Example 4.  Use the gradient search method to find the minimum of   .  
Solution 4.

Various Scenarios and Animations for the Gradient Search Method.

Program (Steepest Descent  or Gradient Method).  To numerically approximate a local minimum of  f(X),  where  f  is a continuous function of  n  real variables and    by starting with one point    and using the gradient method.  Including graphics commands to draw the iterations used in finding the solution.

Example 5.  Use the gradient search method to find the minimum of   .  
Solution 5.

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

Research Experience for Undergraduates

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

Download this Mathematica Notebook Gradient Search

(c) John H. Mathews 2004