PATTERN SEARCH

Pattern search - This is a heuristic (in the sense of not guaranteeing convergence) for unconstrained optimization . It consists of two basic steps, where x is a current point and w is a vector of widths (both having been initialized).

1. Exploration move. Set y=x and do for j=1,...,n:

   If f(y + w_j e_j) > f(y), replace y with y + w_j e_j.

   If f(y - w_j e_j) > f(y), replace y with y - w_j e_j.

   
   If x=y at the end of this, go perform a pattern move. Otherwise, set v = y-x (the change) and x = y (move to better point).
2. Pattern move. If f(x + v) > f(x), replace x with x+v. Otherwise, reduce widths and return to exploration move.

The idea is to perform exploration moves as long as they are successful. Then, saving the last direction (v) when it was successful, this is used to advance x if it is an improvement, giving a new base point (x) for the next series of exploration moves. Termination occurs when the widths become too small.