Steepest Descent - Gradient Search

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.

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.

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.