## 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*} is defined by the number of independent variables in the objective function,

_{i}*N*, and the positive basis set. Two commonly used positive basis sets in pattern search algorithms are the maximal basis, with 2

*N*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 2*N* positive
basis consists of the following pattern vectors:

$$\begin{array}{ccc}{v}_{1}=[\begin{array}{ccc}1& 0& 0\end{array}]& {v}_{2}=[\begin{array}{ccc}0& 1& 0\end{array}]& {v}_{3}=[\begin{array}{ccc}0& 0& 1\end{array}]\\ {v}_{4}=[\begin{array}{ccc}-1& 0& 0\end{array}]& {v}_{5}=[\begin{array}{ccc}0& -1& 0\end{array}]& {v}_{6}=[\begin{array}{ccc}0& 0& -1\end{array}]\end{array}$$

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

$$\begin{array}{ccc}{v}_{1}=[\begin{array}{ccc}1& 0& 0\end{array}]& {v}_{2}=[\begin{array}{ccc}0& 1& 0\end{array}]& {v}_{3}=[\begin{array}{ccc}0& 0& 1\end{array}]\\ {v}_{4}=[\begin{array}{ccc}-1& -1& -1\end{array}]& & \end{array}$$

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 2*N* or *N*+1.
As in GPS, 2*N* 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*} by multiplying each pattern vector_{i}*v*by a scalar Δ_{i}. Δ^{m}is called the^{m}*mesh size*.Adding the $$\left\{{d}_{i}\right\}$$ 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}=\left[\begin{array}{cc}1& 0\end{array}\right]\\ {v}_{2}=\left[\begin{array}{cc}0& 1\end{array}\right]\\ {v}_{3}=\left[\begin{array}{cc}-1& 0\end{array}\right]\\ {v}_{4}=\left[\begin{array}{cc}0& -1\end{array}\right]\end{array}$$

The current mesh size Δ

is^{m}`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 Δ

*by 2 after a successful poll, and by 0.5 after an unsuccessful poll.*

^{m}