Pattern Search Methods

“Science is simply the word to describe a method of organizing our curiosity. — Tim Minchin” penguine

  • Cyclic Coordinate Search: an algorithm that iteratively updates each variable one at a time. It starts by updating the first variable, then the second variable and so on, until all variables have been updated. Once all variables have been updated, the process repeats again with the first variable, second variable and so on. This process continues until the optimal solution is found or the maximum number of iterations is reached. The algorithm is simple to implement, but it can be slow to converge if the problem is complex or the number of variables is large

  • Powell’s Method: starting with an initial point and a set of initial search vectors, carry out bi-directional line search. The new position can then be expressed as initial point + linear combination of the search vectors. The new displacement vector becomes a new search vector, and is added to the end of the search vector list. Meanwhile, the search vector which contributed most to the new direction, i.e. the one which was most successful, is deleted from the search vector list. The algorithm is relatively simple to implement, but it can be slow to converge if the problem is complex.

  • Hooke-Jeeves (Pattern search) Method: uses the previous step’s search pattern to update the current search. The algorithm starts by defining a search pattern, which is a set of steps in different directions. The algorithm then takes a step in each direction and records the best point. It then updates the search pattern based on the best point and takes another step in each direction. This process continues until the optimal solution is found or the maximum number of iterations is reached. The algorithm is relatively simple to implement, but it can be slow to converge if the problem is complex.

  • Nelder-Mead Simplex Search: (default method in R’s Optim() function) flipping of triangles (for 2D optimization), with the performance of vertex being evaluated and ranked, and the worst performing vertex being replaced with its opposite in a complex way.

  • Tabu search: improves on local search by relaxing its basic rule. First, at each step worsening moves can be accepted if no improving move is available (like when the search is stuck at a strict local minimum). In addition, prohibitions (henceforth the term tabu) are introduced to discourage the search from coming back to previously-visited solutions.