Module

for

Powell Search Method for a Minimum

 

Background - The Taxi Cab Method

    Let  
[Graphics:Images/PowellMethodMod_gr_1.gif]  be an initial guess at the location of the minimum of the function  [Graphics:Images/PowellMethodMod_gr_2.gif].   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  [Graphics:Images/PowellMethodMod_gr_3.gif]  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  

        
[Graphics:Images/PowellMethodMod_gr_4.gif].  

Along each standard base vector  [Graphics:Images/PowellMethodMod_gr_5.gif]  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  [Graphics:Images/PowellMethodMod_gr_6.gif].  Unfortunately, the method is, in general, inefficient due to the geometry of multivariable functions.  But the construction [Graphics:Images/PowellMethodMod_gr_7.gif] 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.

                [Graphics:../Images/PowellMethodMod_gr_240.gif]
    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  [Graphics:Images/PowellMethodMod_gr_8.gif],  where  f  is a continuous function of  n  real variables and  [Graphics:Images/PowellMethodMod_gr_9.gif]  by starting with one point  [Graphics:Images/PowellMethodMod_gr_10.gif]  and using the "taxi-cab" search along the directions of the standard base vectors [Graphics:Images/PowellMethodMod_gr_11.gif].

Computer Programs  Powell's Method  Powell's Method  

Mathematica Subroutine (Taxi Cab Method for Finding a Minimum). To numerically approximate a local minimum of [Graphics:Images/PowellMethodMod_gr_12.gif],  start with [Graphics:Images/PowellMethodMod_gr_13.gif] 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 [Graphics:Images/PowellMethodMod_gr_14.gif].  In practice alternate methods could be employed.  

[Graphics:Images/PowellMethodMod_gr_15.gif]

Example 1.  Use the taxi-cab method to find the minimum of   [Graphics:Images/PowellMethodMod_gr_16.gif].  
Solution 1.

 

Example 2.  Use the taxi-cab method to find the minimum of   [Graphics:Images/PowellMethodMod_gr_30.gif].  
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  
[Graphics:Images/PowellMethodMod_gr_40.gif]  represents, in some sense, the average direction moved over the  n intermediate steps  [Graphics:Images/PowellMethodMod_gr_41.gif]  in an iteration.  Thus the point  [Graphics:Images/PowellMethodMod_gr_42.gif]  is determined to be the point at which the minimum of the function  f  occurs along the vector  [Graphics:Images/PowellMethodMod_gr_43.gif].  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  [Graphics:Images/PowellMethodMod_gr_44.gif]  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  [Graphics:Images/PowellMethodMod_gr_45.gif].  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  [Graphics:Images/PowellMethodMod_gr_46.gif]  be an initial guess at the location of the minimum of the function  

        
[Graphics:Images/PowellMethodMod_gr_47.gif].

Let  
[Graphics:Images/PowellMethodMod_gr_48.gif]   for   [Graphics:Images/PowellMethodMod_gr_49.gif]  be the set of standard base vectors.
Initialize the vectors  
[Graphics:Images/PowellMethodMod_gr_50.gif]  for  [Graphics:Images/PowellMethodMod_gr_51.gif]  and use their transpose  [Graphics:Images/PowellMethodMod_gr_52.gif]  to form the columns of the matrix  U  as follows:  

        
[Graphics:Images/PowellMethodMod_gr_53.gif].  

Initialize the counter  
[Graphics:Images/PowellMethodMod_gr_54.gif].   

(i)    Set  [Graphics:Images/PowellMethodMod_gr_55.gif].  

(ii)    For   [Graphics:Images/PowellMethodMod_gr_56.gif],   
    find the value of  
[Graphics:Images/PowellMethodMod_gr_57.gif]  that minimizes  [Graphics:Images/PowellMethodMod_gr_58.gif],  
    and set  
[Graphics:Images/PowellMethodMod_gr_59.gif].   

(iii)    Set  [Graphics:Images/PowellMethodMod_gr_60.gif]  for  [Graphics:Images/PowellMethodMod_gr_61.gif]  and
    set  
[Graphics:Images/PowellMethodMod_gr_62.gif].  

(iv)    Increment the counter  [Graphics:Images/PowellMethodMod_gr_63.gif].   

(v)    Find the value of  [Graphics:Images/PowellMethodMod_gr_64.gif]  that minimizes  [Graphics:Images/PowellMethodMod_gr_65.gif],  
    and set  [Graphics:Images/PowellMethodMod_gr_66.gif].   

(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.

                [Graphics:../Images/PowellMethodMod_gr_272.gif]
    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  [Graphics:Images/PowellMethodMod_gr_67.gif],  where  f  is a continuous function of  n  real variables and  [Graphics:Images/PowellMethodMod_gr_68.gif]  by starting with one point  [Graphics:Images/PowellMethodMod_gr_69.gif]  and using the "dog-leg" search along the directions of the direction vectors [Graphics:Images/PowellMethodMod_gr_70.gif].

Computer Programs  Powell's Method  Powell's Method  

Mathematica Subroutine (Powell's Method for Finding a Minimum).  To numerically approximate a local minimum of [Graphics:Images/PowellMethodMod_gr_71.gif],  start with [Graphics:Images/PowellMethodMod_gr_72.gif] 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 [Graphics:Images/PowellMethodMod_gr_73.gif].  In practice alternate methods could be employed.  

[Graphics:Images/PowellMethodMod_gr_74.gif]

Example 3.  Use Powell's method to find the minimum of   [Graphics:Images/PowellMethodMod_gr_75.gif].  
Solution 3.

 

Example 4.  Use Powell's method to find the minimum of   [Graphics:Images/PowellMethodMod_gr_86.gif],
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  [Graphics:Images/PowellMethodMod_gr_105.gif].  
Looking at your graphs, estimate the location of the local minima.  
Solution 5.

 

Example 6.  Use Powell's Method to find  [Graphics:Images/PowellMethodMod_gr_135.gif]  and  [Graphics:Images/PowellMethodMod_gr_136.gif]  for the function  [Graphics:Images/PowellMethodMod_gr_137.gif].   Use the initial point  [Graphics:Images/PowellMethodMod_gr_138.gif].
Solution 6.

 

Enhanced Powell's Method

    In step
(iii) of Powell's method the first vector  [Graphics:Images/PowellMethodMod_gr_181.gif]  was discarded and the average direction vector  [Graphics:Images/PowellMethodMod_gr_182.gif]  was added to the list of direction vectors.   In fact, it would be better to discard the vector  [Graphics:Images/PowellMethodMod_gr_183.gif]  along which the greatest decrease in  f  occurred.  It seems reasonable that the vector  [Graphics:Images/PowellMethodMod_gr_184.gif]  is a large component of the average direction vector  [Graphics:Images/PowellMethodMod_gr_185.gif].  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  [Graphics:Images/PowellMethodMod_gr_186.gif]  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  [Graphics:Images/PowellMethodMod_gr_187.gif].  

(ii)    For   [Graphics:Images/PowellMethodMod_gr_188.gif],   
    find the value of  
[Graphics:Images/PowellMethodMod_gr_189.gif]  that minimizes  [Graphics:Images/PowellMethodMod_gr_190.gif],  
    and set  
[Graphics:Images/PowellMethodMod_gr_191.gif].   

(iii)    Let [Graphics:Images/PowellMethodMod_gr_192.gif] for  [Graphics:Images/PowellMethodMod_gr_193.gif].   Find the subscript  r  
    so that  
[Graphics:Images/PowellMethodMod_gr_194.gif] is the magnitude of the maximum decrease  f ,  
    and  
[Graphics:Images/PowellMethodMod_gr_195.gif]  the direction of the maximum decrease over all the direction vectors in step (ii).

(iv)    Increment the counter  [Graphics:Images/PowellMethodMod_gr_196.gif].   

(iv)    Let  [Graphics:Images/PowellMethodMod_gr_197.gif] for  [Graphics:Images/PowellMethodMod_gr_198.gif].  
    Let  
[Graphics:Images/PowellMethodMod_gr_199.gif] be the function value in the extended direction [Graphics:Images/PowellMethodMod_gr_200.gif] from  [Graphics:Images/PowellMethodMod_gr_201.gif].  
    If   [Graphics:Images/PowellMethodMod_gr_202.gif]   set [Graphics:Images/PowellMethodMod_gr_203.gif] and go to step (i), or  
    i
f   [Graphics:Images/PowellMethodMod_gr_204.gif]  set [Graphics:Images/PowellMethodMod_gr_205.gif] and go to step (i).  
    Otherwise, continue to step
(vi).  

(vi)    Set  [Graphics:Images/PowellMethodMod_gr_206.gif], where the subscript  r  is given in step (iii).    

(vii)    Find the value of  [Graphics:Images/PowellMethodMod_gr_207.gif]  that minimizes  [Graphics:Images/PowellMethodMod_gr_208.gif],  
    and set  [Graphics:Images/PowellMethodMod_gr_209.gif].   
    
(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  [Graphics:Images/PowellMethodMod_gr_210.gif].  The second inequality indicates that the decrease in the function f in the direction of greatest decrease  [Graphics:Images/PowellMethodMod_gr_211.gif]  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  [Graphics:Images/PowellMethodMod_gr_212.gif]  is replaced with the average direction from step (ii);  [Graphics:Images/PowellMethodMod_gr_213.gif]. In step (vii) the function is minimized in this direction.  Stopping criteria based on the magnitudes  [Graphics:Images/PowellMethodMod_gr_214.gif]  or  [Graphics:Images/PowellMethodMod_gr_215.gif]  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).

[Graphics:Images/PowellMethodMod_gr_216.gif]

Example 7.  Use the Taxi-Cab method to find the minimum of   [Graphics:Images/PowellMethodMod_gr_217.gif].  
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).

[Graphics:Images/PowellMethodMod_gr_242.gif]

Example 8.  Use Powell's method to find the minimum of   [Graphics:Images/PowellMethodMod_gr_243.gif].  
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