Background - The Taxi Cab Method

    Let    be an initial guess at the location of the minimum of the function  .   Assume that the partial derivatives of the function are not available.  An intuitively appealing approach to approximating a minimum of the function  f  is to generate the next approximation    by proceeding successively to a minimum of  f  along each of the  n  standard base vectors.  This process can be called the taxi-cab method and generates the sequence of points  

        .  

Along each standard base vector    the function  f  is a function of one variable, and the minimization of  f  might be accomplished by the application of either the golden ratio or Fibonacci searches if  f  is unimodal in this search direction. The iteration is then repeated to generate a sequence of points  .  Unfortunately, the method is, in general, inefficient due to the geometry of multivariable functions.  But the construction is involved in the first step of Powell's method, and it is worthwhile to see how it works.  A typical sequence of points generated by the taxi-cab method is shown in Figure 1 below.

                
    Figure 1.  A sequence of points in 2D generated by the taxi-cab method.

Algorithm (Taxi Cab Method for Finding a Minimum).  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 "taxi-cab" search along the directions of the standard base vectors .

Computer Programs  Powell's Method  Powell's Method  

Mathematica Subroutine (Taxi Cab Method for Finding a Minimum). To numerically approximate a local minimum of ,  start with and using the "taxi-cab" search.  
Notice.  To streamline the algorithm we use Mathematica's built in procedure FindMinimum to perform the line searches along the base vectors .  In practice alternate methods could be employed.  

Example 1.  Use the taxi-cab method to find the minimum of   .  
Solution 1.

Example 2.  Use the taxi-cab method to find the minimum of   .  
Solution 2.

Powell's Method

    The essence of Powell's method is to add two steps to the process described in the preceding paragraph.  The vector    represents, in some sense, the average direction moved over the  n intermediate steps    in an iteration.  Thus the point    is determined to be the point at which the minimum of the function  f  occurs along the vector  .  As before,  f  is a function of one variable along this vector and the minimization could be accomplished with an application of the golden ratio or Fibonacci searches.  Finally, since the vector    was such a good direction, it replaces one of the direction vectors for the next iteration.  The iteration is then repeated using the new set of direction vectors to generate a sequence of points  .  In one step of the iteration instead of a zig-zag path the iteration follows a "dog-leg" path.  The process is outlined below.

    Let    be an initial guess at the location of the minimum of the function  

        .

Let     for     be the set of standard base vectors.
Initialize the vectors    for    and use their transpose    to form the columns of the matrix  U  as follows:  

        .  

Initialize the counter  .   

(i)    Set  .  

(ii)    For   ,   
    find the value of    that minimizes  ,  
    and set  .   

(iii)    Set    for    and
    set  .  

(iv)    Increment the counter  .   

(v)    Find the value of    that minimizes  ,  
    and set  .   

(vi)    Repeat steps (i) through (v) until convergence is achieved.  

    A typical sequence of points generated by Powell's method is shown in Figure 2 below.

                
    Figure 2.  A sequence of points in 2D generated by Powell's method.

Proof  Powell's Method  Powell's Method  

Algorithm (Powell's Method for Finding a Minimum).  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 "dog-leg" search along the directions of the direction vectors .

Computer Programs  Powell's Method  Powell's Method  

Mathematica Subroutine (Powell's Method for Finding a Minimum).  To numerically approximate a local minimum of ,  start with and using the "taxi-cab" search.  
Notice.  To streamline the algorithm we use Mathematica's built in procedure FindMinimum to perform the line searches along the direction vectors .  In practice alternate methods could be employed.  

Example 3.  Use Powell's method to find the minimum of   .  
Solution 3.

Example 4.  Use Powell's method to find the minimum of   ,
This example is referred to as Rosenbrock's parabolic valley, circa 1960.
Solution 4.

Exercise 5.  Use the Powell's method to find the minimum of  .  
Looking at your graphs, estimate the location of the local minima.  
Solution 5.

Example 6.  Use Powell's Method to find    and    for the function  .   Use the initial point  .
Solution 6.

Enhanced Powell's Method

    In step (iii) of Powell's method the first vector    was discarded and the average direction vector    was added to the list of direction vectors.   In fact, it would be better to discard the vector    along which the greatest decrease in  f  occurred.  It seems reasonable that the vector    is a large component of the average direction vector  .  Thus, as the number of iterations increase, the set of direction vectors will tend to become linearly dependent.  When the set becomes linearly dependent one or more of the directions will be lost and it is likely that the set of points    will not converge to the point at which the local minimum occurs.  Furthermore, in step (iii) it was assumed that the average direction vector represented a good direction in which to continue the search.  But that may not be the case.

Outline of the Enhanced Powell's Method

(i)    Set  .  

(ii)    For   ,   
    find the value of    that minimizes  ,  
    and set  .   

(iii)    Let for  .   Find the subscript  r  
    so that   is the magnitude of the maximum decrease  f ,  
    and    the direction of the maximum decrease over all the direction vectors in step (ii).

(iv)    Increment the counter  .   

(iv)    Let   for  .  
    Let   be the function value in the extended direction from  .  
    If      set and go to step (i), or  
    if     set and go to step (i).  
    Otherwise, continue to step (vi).  

(vi)    Set  , where the subscript  r  is given in step (iii).    

(vii)    Find the value of    that minimizes  ,  
    and set  .   
    
(vii)    Repeat steps (i) through (vii).

    If the conditions in step (v) are satisfied, then the set of direction vectors is left unchanged. The first inequality in step (v) indicates that there is no further decrease in the value of  f  in the average direction  .  The second inequality indicates that the decrease in the function f in the direction of greatest decrease    was not a major part of the total decrease in  f  in step (ii).   If the conditions in step (v) are not satisfied, then the direction of greatest decrease    is replaced with the average direction from step (ii);  . In step (vii) the function is minimized in this direction.  Stopping criteria based on the magnitudes    or    are typically found in steps (v) and (vii).  We leave it for the reader to investigate these enhancements.  

Various Scenarios and Animations for the Taxi-Cab Method and Powell's Method.

Mathematica Subroutine (Taxi-Cab Method for Finding a Minimum).

Example 7.  Use the Taxi-Cab method to find the minimum of   .  
Use the modified program listed above that includes graphics commands to draw the vertices and edges used in finding the solution.
Solution 7.

Mathematica Subroutine (Powell's Method for Finding a Minimum).

Example 8.  Use Powell's method to find the minimum of   .  
Use the modified program listed above that includes graphics commands to draw the vertices and edges used in finding the solution.
Solution 8.

Animations (Powell's Method Powell's Method).  Internet hyperlinks to animations.  

Research Experience for Undergraduates

Powell's Method  Powell's Method  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Powell's Method

(c) John H. Mathews 2004