Learn more about Genetic Algorithm and Direct Search Toolbox

How Pattern Search Works

On this page…
Context Successful Polls An Unsuccessful Poll Displaying the Results at Each Iteration More Iterations Stopping Conditions for the Pattern Search

Context

The pattern search algorithms find a sequence of points, x0, x1, x2, ... , that approaches 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 Example — Finding the Minimum of a Function Using the GPS Algorithm.

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

Back to Top

Successful Polls

The pattern search begins at the initial point x0 that you provide. In this example, x0 = [2.1 1.7].

Iteration 1

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]

Note   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.

Iteration 2

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.

Back to Top

An Unsuccessful Poll

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.

Back to Top

Displaying the Results at Each Iteration

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 lines of the display 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 

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 3, the entry Refine Mesh below Method 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.

Back to Top

More Iterations

The pattern search performs 88 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.

Back to Top

Stopping Conditions for the Pattern Search

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

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.

• The distance between the point found in two consecutive iterations and the mesh size are both less than X tolerance.

• The change in the objective function in two consecutive iterations and the mesh size are both less than Function tolerance.

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

The MADS algorithm uses the relationship between the mesh size, Δ^m, and an additional parameter, called the poll parameter, Δ^p, to determine the stopping criteria. For positive basis N+1, the poll parameter is , and for positive basis 2N, the poll parameter is . The relationship for MADS stopping criteria is Δ^m ≤ Mesh tolerance.

Back to Top

Pattern Search Terminology

Description of the Nonlinear Constraint Solver

© 1984-2009- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS