As an example, consider the following function.
$$f\left({x}_{1},{x}_{2}\right)=\{\begin{array}{ll}{x}_{1}^{2}+{x}_{2}^{2}-25\hfill & \text{for}{x}_{1}^{2}+{x}_{2}^{2}\le 25\hfill \\ {x}_{1}^{2}+{\left({x}_{2}-9\right)}^{2}-16\hfill & \text{for}{x}_{1}^{2}+{\left({x}_{2}-9\right)}^{2}\le 16\hfill \\ 0\hfill & \text{otherwise}\text{.}\hfill \end{array}$$
The following figure shows a plot of the function.
Code for generating the figure
The global minimum of the function occurs at (0, 0), where its value is -25. However, the function also has a local minimum at (0, 9), where its value is -16.
To create a file that computes the function, copy and paste the following code into a new file in the MATLAB^{®} Editor.
function z = poll_example(x) if x(1)^2 + x(2)^2 <= 25 z = x(1)^2 + x(2)^2 - 25; elseif x(1)^2 + (x(2) - 9)^2 <= 16 z = x(1)^2 + (x(2) - 9)^2 - 16; else z = 0; end
Then save the file as poll_example.m
in a
folder on the MATLAB path.
To run a pattern search on the function, enter the following in the Optimization app:
Set Solver to patternsearch
.
Set Objective function to @poll_example
.
Set Start point to [0
5]
.
Set Level of display to Iterative
in
the Display to command window options.
Click Start to run the pattern search
with Complete poll set to Off
,
its default value. The Optimization app displays the results in the Run
solver and view results pane, as shown in the following
figure.
The pattern search returns the local minimum at (0, 9). At the initial point, (0, 5), the objective function value is 0. At the first iteration, the search polls the following mesh points.
f((0, 5) + (1, 0)) = f(1, 5) = 0
f((0, 5) + (0, 1)) = f(0, 6) = -7
As soon as the search polls the mesh point (0, 6), at which the objective function value is less than at the initial point, it stops polling the current mesh and sets the current point at the next iteration to (0, 6). Consequently, the search moves toward the local minimum at (0, 9) at the first iteration. You see this by looking at the first two lines of the command line display.
Iter f-count f(x) MeshSize Method 0 1 0 1 1 3 -7 2 Successful Poll
Note that the pattern search performs only two evaluations of the objective function at the first iteration, increasing the total function count from 1 to 3.
Next, set Complete poll to On
and
click Start. The Run solver and
view results pane displays the following results.
This time, the pattern search finds
the global minimum at (0, 0). The difference between this run and
the previous one is that with Complete poll set
to On
, at the first iteration the pattern search
polls all four mesh points.
f((0, 5) + (1, 0)) = f(1, 5) = 0
f((0, 5) + (0, 1)) = f(0, 6) = -6
f((0, 5) + (-1, 0)) = f(-1, 5) = 0
f((0, 5) + (0, -1)) = f(0, 4) = -9
Because the last mesh point has the lowest objective function value, the pattern search selects it as the current point at the next iteration. The first two lines of the command-line display show this.
Iter f-count f(x) MeshSize Method 0 1 0 1 1 5 -9 2 Successful Poll
In this case, the objective function is evaluated four times at the first iteration. As a result, the pattern search moves toward the global minimum at (0, 0).
The following figure compares the sequence of points returned
when Complete poll is set to Off
with
the sequence when Complete poll is On
.
This example shows how several poll options interact in terms of iterations and total function evaluations. The main results are:
GSS is more efficient than GPS or MADS for linearly constrained problems.
Whether setting UseCompletePoll
to true
increases
efficiency or decreases efficiency is unclear, although it affects
the number of iterations.
Similarly, whether having a 2N
poll
is more or less efficient than having an Np1
poll
is also unclear. The most efficient poll is GSS Positive
Basis Np1
with Complete poll set
to on
. The least efficient is MADS
Positive Basis Np1
with Complete poll set
to on
.
Note: The efficiency of an algorithm depends on the problem. GSS is efficient for linearly constrained problems. However, predicting the efficiency implications of the other poll options is difficult, as is knowing which poll type works best with other constraints. |
The problem is the same as in Performing a Pattern Search on the Example. This linearly
constrained problem uses the lincontest7
file that
comes with the toolbox:
Enter the following into your MATLAB workspace:
x0 = [2 1 0 9 1 0]; Aineq = [-8 7 3 -4 9 0]; bineq = 7; Aeq = [7 1 8 3 3 3; 5 0 -5 1 -5 8; -2 -6 7 1 1 9; 1 -1 2 -2 3 -3]; beq = [84 62 65 1];
Open the Optimization app by entering optimtool
at
the command line.
Choose the patternsearch
solver.
Enter the problem and constraints as pictured.
Ensure that the Poll method is GPS
Positive basis 2N
.
Run the optimization.
Choose File > Export to Workspace.
Export the results and name them gps2noff
.
Set Options > Poll > Complete poll to on
.
Run the optimization.
Export the result and name it gps2non
.
Set Options > Poll > Poll method to GPS
Positive basis Np1
and set Complete poll to off
.
Run the optimization.
Export the result and name it gpsnp1off
.
Set Complete poll to on
.
Run the optimization.
Export the result and name it gpsnp1on
.
Continue in a like manner to create solution structures
for the other poll methods with Complete poll set on
and off
: gss2noff
, gss2non
, gssnp1off
, gssnp1on
, mads2noff
, mads2non
, madsnp1off
,
and madsnp1on
.
You have the results of 12 optimization runs. The following table shows the efficiency of the runs, measured in total function counts and in iterations. Your MADS results could differ, since MADS is a stochastic algorithm.
Algorithm | Function Count | Iterations |
---|---|---|
GPS2N, complete poll off | 1462 | 136 |
GPS2N, complete poll on | 1396 | 96 |
GPSNp1, complete poll off | 864 | 118 |
GPSNp1, complete poll on | 1007 | 104 |
GSS2N, complete poll off | 758 | 84 |
GSS2N, complete poll on | 889 | 74 |
GSSNp1, complete poll off | 533 | 94 |
GSSNp1, complete poll on | 491 | 70 |
MADS2N, complete poll off | 922 | 162 |
MADS2N, complete poll on | 2285 | 273 |
MADSNp1, complete poll off | 1155 | 201 |
MADSNp1, complete poll on | 1651 | 201 |
To obtain, say, the first row in the table, enter gps2noff.output.funccount
and gps2noff.output.iterations
.
You can also examine options in the Variables editor by double-clicking
the options in the Workspace Browser, and then double-clicking the output
structure.
The main results gleaned from the table are:
Setting Complete poll to on
generally
lowers the number of iterations for GPS and GSS, but the change in
number of function evaluations is unpredictable.
Setting Complete poll to on
does
not necessarily change the number of iterations for MADS, but substantially
increases the number of function evaluations.
The most efficient algorithm/options settings, with efficiency meaning lowest function count:
GSS Positive basis Np1
with Complete
poll set to on
(function count
491)
GSS Positive basis Np1
with Complete
poll set to off
(function count
533)
GSS Positive basis 2N
with Complete poll set to off
(function
count 758)
GSS Positive basis 2N
with Complete poll set to on
(function
count 889)
The other poll methods had function counts exceeding 900.
For this problem, the most efficient poll is GSS
Positive Basis Np1
with Complete poll set
to on
, although the Complete
poll setting makes only a small difference. The least efficient
poll is MADS Positive Basis 2N
with Complete
poll set to on
. In this case,
the Complete poll setting makes a substantial
difference.