 # Pattern search

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

1. Exploration move. Set $LaTeX: y=x$ and do for $LaTeX: \textstyle j=1,\dots,n:$
If $LaTeX: \textstyle f(y + w_j e_j) > f(y),$ replace $LaTeX: y$ with $LaTeX: y + w_j e_j.$
If $LaTeX: f(y - w_j e_j) > f(y),$ replace $LaTeX: y$ with $LaTeX: y - w_j e_j.$
If $LaTeX: x=y$ at the end of this, go perform a pattern move. Otherwise, set $LaTeX: v = y-x$ (the change) and $LaTeX: x = y$ (move to better point).
2. Pattern move. If $LaTeX: f(x + v) > f(x),$ replace $LaTeX: x$ with $LaTeX: 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 $LaTeX: (v)$ when it was successful, this is used to advance $LaTeX: x$ if it is an improvement, giving a new base point $LaTeX: (x)$ for the next series of exploration moves. Termination occurs when the widths become too small.