Pattern Search Terminology

Patterns

A pattern is a set of vectors {v_i} that the pattern search algorithm uses to determine which points to search at each iteration. The set {v_i} is defined by the number of independent variables in the objective function, N, and the positive basis set. Two commonly used positive basis sets in pattern search algorithms are the maximal basis, with 2N vectors, and the minimal basis, with N+1 vectors.

With GPS, the collection of vectors that form the pattern are fixed-direction vectors. For example, if there are three independent variables in the optimization problem, the default for a 2N positive basis consists of the following pattern vectors:

$\begin{matrix} v_{1} = [\begin{matrix} 1 & 0 & 0 \end{matrix}] & v_{2} = [\begin{matrix} 0 & 1 & 0 \end{matrix}] & v_{3} = [\begin{matrix} 0 & 0 & 1 \end{matrix}] \\ v_{4} = [\begin{matrix} - 1 & 0 & 0 \end{matrix}] & v_{5} = [\begin{matrix} 0 & - 1 & 0 \end{matrix}] & v_{6} = [\begin{matrix} 0 & 0 & - 1 \end{matrix}] \end{matrix}$

An N+1 positive basis consists of the following default pattern vectors.

With GSS, the pattern is identical to the GPS pattern, except when there are linear constraints and the current point is near a constraint boundary. For a description of the way in which GSS forms a pattern with linear constraints, see Kolda, Lewis, and Torczon [1]. The GSS algorithm is more efficient than the GPS algorithm when you have linear constraints. For an example showing the efficiency gain, see Compare the Efficiency of Poll Options.

With MADS, the collection of vectors that form the pattern are randomly selected by the algorithm. Depending on the poll method choice, the number of vectors selected will be 2N or N+1. As in GPS, 2N vectors consist of N vectors and their N negatives, while N+1 vectors consist of N vectors and one that is the negative of the sum of the others.

References

[1] Kolda, Tamara G., Robert Michael Lewis, and Virginia Torczon. “A generating set direct search augmented Lagrangian algorithm for optimization with a combination of general and linear constraints.” Technical Report SAND2006-5315, Sandia National Laboratories, August 2006.

Meshes

At each step, patternsearch searches a set of points, called a mesh, for a point that improves the objective function. patternsearch forms the mesh by

Generating a set of vectors {d_i} by multiplying each pattern vector v_i by a scalar Δ^m. Δ^m is called the mesh size.
Adding the ${d_{i}}$ to the current point—the point with the best objective function value found at the previous step.

For example, using the GPS algorithm. suppose that:

The current point is [1.6 3.4].
The pattern consists of the vectors
$\begin{array}{l} v_{1} = [\begin{matrix} 1 & 0 \end{matrix}] \\ v_{2} = [\begin{matrix} 0 & 1 \end{matrix}] \\ v_{3} = [\begin{matrix} - 1 & 0 \end{matrix}] \\ v_{4} = [\begin{matrix} 0 & - 1 \end{matrix}] \end{array}$
The current mesh size Δ^m is 4.

The algorithm multiplies the pattern vectors by 4 and adds them to the current point to obtain the following mesh.

[1.6 3.4] + 4*[1 0] = [5.6 3.4] 
[1.6 3.4] + 4*[0 1] = [1.6 7.4] 
[1.6 3.4] + 4*[-1 0] = [-2.4 3.4] 
[1.6 3.4] + 4*[0 -1] = [1.6 -0.6]

The pattern vector that produces a mesh point is called its direction.

Polling

At each step, the algorithm polls the points in the current mesh by computing their objective function values. When the Complete poll option has the (default) setting Off, the algorithm stops polling the mesh points as soon as it finds a point whose objective function value is less than that of the current point. If this occurs, the poll is called successful and the point it finds becomes the current point at the next iteration.

The algorithm only computes the mesh points and their objective function values up to the point at which it stops the poll. If the algorithm fails to find a point that improves the objective function, the poll is called unsuccessful and the current point stays the same at the next iteration.

When the Complete poll option has the setting On, the algorithm computes the objective function values at all mesh points. The algorithm then compares the mesh point with the smallest objective function value to the current point. If that mesh point has a smaller value than the current point, the poll is successful.

Expanding and Contracting

After polling, the algorithm changes the value of the mesh size Δ^m. The default is to multiply Δ^m by 2 after a successful poll, and by 0.5 after an unsuccessful poll.