`patternsearch`

finds a sequence of points, `x0`

, `x1`

, `x2`

,
... , that approach an optimal point. The value of the objective function
either decreases or remains the same from each point in the sequence
to the next. This section explains how pattern search works for the
function described in Optimize Using the GPS Algorithm.

To simplify the explanation, this section describes how the
generalized pattern search (GPS) works using a maximal positive basis
of 2*N*, with **Scale** set to `Off`

in **Mesh** options.

This section does not show how the `patternsearch`

algorithm
works with bounds or linear constraints. For bounds and linear constraints, `patternsearch`

modifies
poll points to be feasible, meaning to satisfy all bounds and linear
constraints.

This section does not encompass nonlinear constraints. To understand
how `patternsearch`

works with nonlinear constraints,
see Nonlinear Constraint Solver Algorithm.

The problem setup:

The pattern search begins at the initial point `x0`

that
you provide. In this example, `x0 = [2.1 1.7]`

.

At the first iteration, the mesh size is 1 and the GPS algorithm
adds the pattern vectors to the initial point `x0 = [2.1 1.7]`

to compute the following mesh points:

[1 0] + x0 = [3.1 1.7] [0 1] + x0 = [2.1 2.7] [-1 0] + x0 = [1.1 1.7] [0 -1] + x0 = [2.1 0.7]

The algorithm computes the objective function at the mesh points
in the order shown above. The following figure shows the value of `ps_example`

at
the initial point and mesh points.

The algorithm polls the mesh points by computing their objective
function values until it finds one whose value is smaller than 4.6347,
the value at `x0`

. In this case, the first such point
it finds is `[1.1 1.7]`

, at which
the value of the objective function is `4.5146`

,
so the poll at iteration 1 is *successful*. The
algorithm sets the next point in the sequence equal to

x1 = [1.1 1.7]

By default, the GPS pattern search algorithm stops the current
iteration as soon as it finds a mesh point whose fitness value is
smaller than that of the current point. Consequently, the algorithm
might not poll all the mesh points. You can make the algorithm poll
all the mesh points by setting **Complete poll** to `On`

.

After a successful poll, the algorithm multiplies the current
mesh size by 2, the default value of **Expansion factor** in
the **Mesh** options pane. Because the initial mesh
size is 1, at the second iteration the mesh size is 2. The mesh at
iteration 2 contains the following points:

2*[1 0] + x1 = [3.1 1.7] 2*[0 1] + x1 = [1.1 3.7] 2*[-1 0] + x1 = [-0.9 1.7] 2*[0 -1] + x1 = [1.1 -0.3]

The following figure shows the point `x1`

and
the mesh points, together with the corresponding values of `ps_example`

.

The algorithm polls the mesh points until it finds one whose
value is smaller than 4.5146, the value at `x1`

.
The first such point it finds is `[-0.9 1.7]`

,
at which the value of the objective function is `3.25`

,
so the poll at iteration 2 is again successful. The algorithm sets
the second point in the sequence equal to

x2 = [-0.9 1.7]

Because the poll is successful, the algorithm multiplies the current mesh size by 2 to get a mesh size of 4 at the third iteration.

By the fourth iteration, the current point is

x3 = [-4.9 1.7]

and the mesh size is 8, so the mesh consists of the points

8*[1 0] + x3 = [3.1 1.7] 8*[0 1] + x3 = [-4.9 9.7] 8*[-1 0] + x3 = [-12.9 1.7] 8*[0 -1] + x3 = [-4.9 -1.3]

The following figure shows the mesh points and their objective function values.

At this iteration, none of the mesh points has a smaller objective
function value than the value at `x3`

, so the poll
is *unsuccessful*. In this case, the algorithm
does not change the current point at the next iteration. That is,

x4 = x3;

At the next iteration, the algorithm multiplies the current
mesh size by 0.5, the default value of **Contraction factor** in
the **Mesh** options pane, so that the mesh size
at the next iteration is 4. The algorithm then polls with a smaller
mesh size.

Setting the `PollMethod`

option to `'MADSPositiveBasis2N'`

or `'MADSPositiveBasisNp1'`

causes `patternsearch`

to
use both a different poll type and to react to polling differently
than the other polling algorithms.

A MADS poll uses newly generated pseudorandom mesh vectors at each iteration. The vectors are randomly shuffled components from the columns of a random lower-triangular matrix. The components of the matrix have integer sizes up to 1/$$\sqrt{\text{meshsize}}$$. In the poll, the mesh vectors are multiplied by the mesh size, so the poll points can be up to $$\sqrt{\text{meshsize}}$$ from the current point.

Unsuccessful polls contract the mesh by a factor of `4`

,
ignoring the `MeshContractionFactor`

option. Similarly,
successful polls expand the mesh by a factor of `4`

,
ignoring the `MeshExpansionFactor`

option. The maximum
mesh size is `1`

, despite any setting of the `MaxMeshSize`

option.

In addition, when there is a successful poll, `patternsearch`

starts
at the successful point and polls again. This extra poll uses the
same mesh vectors, expanded by a factor of `4`

while
staying below size `1`

. The extra poll looks again
along the same directions that were just successful.

You can display the results of the pattern search at each iteration
by setting **Level of display** to `Iterative`

in
the **Display to command window** options. This enables
you to evaluate the progress of the pattern search and to make changes
to `options`

if necessary.

With this setting, the pattern search displays information about each iteration at the command line. The first four iterations are

Iter f-count f(x) MeshSize Method 0 1 4.63474 1 1 4 4.51464 2 Successful Poll 2 7 3.25 4 Successful Poll 3 10 -0.264905 8 Successful Poll 4 14 -0.264905 4 Refine Mesh

The entry `Successful Poll`

below `Method`

indicates
that the current iteration was successful. For example, the poll at
iteration 2 is successful. As a result, the objective function value
of the point computed at iteration 2, displayed below `f(x)`

,
is less than the value at iteration 1.

At iteration 4, the entry `Refine Mesh`

tells
you that the poll is unsuccessful. As a result, the function value
at iteration 4 remains unchanged from iteration 3.

By default, the pattern search doubles the mesh size after each successful poll and halves it after each unsuccessful poll.

The pattern search performs 60 iterations before stopping. The following plot shows the points in the sequence computed in the first 13 iterations of the pattern search.

The numbers below the points indicate the first iteration at which the algorithm finds the point. The plot only shows iteration numbers corresponding to successful polls, because the best point doesn't change after an unsuccessful poll. For example, the best point at iterations 4 and 5 is the same as at iteration 3.

At each iteration, the pattern search polls the points in the
current mesh—that is, it computes the objective function at
the mesh points to see if there is one whose function value is less
than the function value at the current point. How Pattern Search Polling Works provides an example of polling.
You can specify the pattern that defines the mesh by the **Poll
method** option. The default pattern, ```
GPS Positive
basis 2N
```

, consists of the following 2*N* directions,
where *N* is the number of independent variables
for the objective function.

[1 0 0...0]

[0 1 0...0]

...

[0 0 0...1]

[–1 0 0...0]

[0 –1 0...0]

[0 0 0...–1].

For example, if the objective function has three independent
variables, the `GPS Positive basis 2N`

, consists
of the following six vectors.

[1 0 0]

[0 1 0]

[0 0 1]

[–1 0 0]

[0 –1 0]

[0
0 –1].

Alternatively, you can set **Poll method** to ```
GPS
Positive basis NP1
```

, the pattern consisting of the following *N* +
1 directions.

[1 0 0...0]

[0 1 0...0]

...

[0 0 0...1]

[–1 –1
–1...–1].

For example, if objective function has three independent variables,
the `GPS Positive basis Np1`

, consists of the following
four vectors.

[1 0 0]

[0 1 0]

[0 0 1]

[–1 –1 –1].

A pattern search will sometimes run faster using ```
GPS
Positive basis Np1
```

rather than the ```
GPS Positive
basis 2N
```

as the **Poll method**, because
the algorithm searches fewer points at each iteration. Although not
being addressed in this example, the same is true when using the ```
MADS
Positive basis Np1
```

over the ```
MADS Positive basis
2N
```

, and similarly for GSS. For example, if you run a pattern
search on the example described in Linearly Constrained Problem, the algorithm
performs 1588 function evaluations with ```
GPS Positive basis
2N
```

, the default **Poll method**, but only
877 function evaluations using `GPS Positive basis Np1`

.
For more detail, see Compare the Efficiency of Poll Options.

However, if the objective function has many local minima, using ```
GPS
Positive basis 2N
```

as the **Poll method** might
avoid finding a local minimum that is not the global minimum, because
the search explores more points around the current point at each iteration.

By default, if the pattern search finds a mesh point that improves the value of the objective function, it stops the poll and sets that point as the current point for the next iteration. When this occurs, some mesh points might not get polled. Some of these unpolled points might have an objective function value that is even lower than the first one the pattern search finds.

For problems in which there are several local minima, it is
sometimes preferable to make the pattern search poll *all* the
mesh points at each iteration and choose the one with the best objective
function value. This enables the pattern search to explore more points
at each iteration and thereby potentially avoid a local minimum that
is not the global minimum. In the Optimization app you can make the
pattern search poll the entire mesh setting **Complete poll** to `On`

in **Poll** options.
At the command line, use `optimoptions`

to set
the `UseCompletePoll`

option to `true`

.

The criteria for stopping the pattern search algorithm are listed
in the **Stopping criteria** section of the
Optimization app:

The algorithm stops when any of the following conditions occurs:

The mesh size is less than

**Mesh tolerance**.The number of iterations performed by the algorithm reaches the value of

**Max iteration**.The total number of objective function evaluations performed by the algorithm reaches the value of

**Max function evaluations**.The time, in seconds, the algorithm runs until it reaches the value of

**Time limit**.After a successful poll, the distance between the point found in the previous two iterations and the mesh size are both less than

**X tolerance**.After a successful poll, the change in the objective function in the previous two iterations is less than

**Function tolerance**and the mesh size is less than**X tolerance**.

**Nonlinear constraint tolerance** is not used
as stopping criterion. It determines the feasibility with respect
to nonlinear constraints.

The MADS algorithm uses an additional parameter called the poll
parameter, Δ_{p}, in
the mesh size stopping criterion:

$${\Delta}_{p}=\{\begin{array}{ll}N\sqrt{{\Delta}_{m}}\hfill & \text{forpositivebasis}N+1\text{poll}\hfill \\ \sqrt{{\Delta}_{m}}\hfill & \text{forpositivebasis2}N\text{poll,}\hfill \end{array}$$

where Δ_{m} is
the mesh size. The MADS stopping criterion is:

Δ_{p} ≤ **Mesh tolerance**.

The pattern search algorithm is robust in relation to objective
function failures. This means `patternsearch`

tolerates
function evaluations resulting in `NaN`

, `Inf`

,
or complex values. When the objective function at the initial point `x0`

is
a real, finite value, `patternsearch`

treats poll
point failures as if the objective function values are large, and
ignores them.

For example, if all points in a poll evaluate to `NaN`

, `patternsearch`

considers
the poll unsuccessful, shrinks the mesh, and reevaluates. If even
one point in a poll evaluates to a smaller value than any seen yet, `patternsearch`

considers
the poll successful, and expands the mesh.