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.  

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.

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 .

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.