Pattern search

From Glossary

Jump to: navigation, 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.


Views
Personal tools