## Polling Types

### Using a Complete Poll in a Generalized Pattern Search

As an example, consider the following function.

The following figure shows a plot of the function. 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 to run the pattern search with Complete poll set to `Off`, its default value.

Alternatively, to run this problem using command-line functions:

```options = optimoptions('patternsearch','Display','iter'); [x,fval] = patternsearch(@poll_example,[0,5],... [],[],[],[],[],[],[],options);```

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 . Alternatively, at the command line:

```options.UseCompletePoll = true; [x,fval] = patternsearch(@poll_example,[0,5],... [],[],[],[],[],[],[],options);```

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`. ### Compare the Efficiency of Poll Options

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.

#### Problem setup

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:

1. 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];```
2. Open the Optimization app by entering `optimtool` at the command line.

3. Choose the `patternsearch` solver.

4. Enter the problem and constraints as pictured. 5. Ensure that the Poll method is ```GPS Positive basis 2N```. #### Generate the Results

1. Run the optimization. 2. Choose File > Export to Workspace. 3. Export the results and name them `gps2noff`. 4. Set Options > Poll > Complete poll to `on`. 5. Run the optimization.

6. Export the result and name it `gps2non`.

7. Set Options > Poll > Poll method to ```GPS Positive basis Np1``` and set Complete poll to `off`.

8. Run the optimization.

9. Export the result and name it `gpsnp1off`.

10. Set Complete poll to `on`.

11. Run the optimization.

12. Export the result and name it `gpsnp1on`.

13. 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`.

#### Generate the Results at the Command Line

Alternatively, you can generate the results described in Generate the Results at the command line.

1. Set the initial options and objective function.

```options = optimoptions('patternsearch',... 'PollMethod','GPSPositiveBasis2N',... 'PollOrderAlgorithm','consecutive',... 'UseCompletePoll',false); fun = @lincontest7;```
2. Run the optimization, naming the `output` structure `outputgps2noff`.

```[x,fval,exitflag,outputgps2noff] = patternsearch(fun,x0,... Aineq,bineq,Aeq,beq,[],[],[],options);```
3. Set options to use a complete poll.

`options.UseCompletePoll = true;`
4. Run the optimization, naming the `output` structure `outputgps2non`.

```[x,fval,exitflag,outputgps2non] = patternsearch(fun,x0,... Aineq,bineq,Aeq,beq,[],[],[],options);```
5. Set options to use the `'GPSPositiveBasisNp1'` poll method and not to use a complete poll.

```options.PollMethod = 'GPSPositiveBasisNp1'; options.UseCompletePoll = false;```
6. Run the optimization, naming the `output` structure `outputgps2np1off`.

```[x,fval,exitflag,outputgps2np1off] = patternsearch(fun,x0,... Aineq,bineq,Aeq,beq,[],[],[],options);```
7. Continue in a like manner to create output structures for the other poll methods with `UseCompletePoll` set `true` and `false`: `outputgss2noff`, `outputgss2non`, `outputgssnp1off`, `outputgssnp1on`, `outputmads2noff`, `outputmads2non`, `outputmadsnp1off`, and `outputmadsnp1on`.

#### Examine the Results

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.

AlgorithmFunction CountIterations
GPS2N, complete poll off1462136
GPS2N, complete poll on139696
GPSNp1, complete poll off864118
GPSNp1, complete poll on1007104
GSS2N, complete poll off75884
GSS2N, complete poll on88974
GSSNp1, complete poll off53394
GSSNp1, complete poll on49170

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.   Alternatively, if you ran the problems at the command line, you can access the data from the output structures.

`[outputgps2noff.funccount,outputgps2noff.iterations]`
```ans = 1462 136```

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:

1. `GSS Positive basis Np1` with Complete poll set to `on` (function count 491)

2. `GSS Positive basis Np1` with Complete poll set to `off` (function count 533)

3. `GSS Positive basis 2N` with Complete poll set to `off` (function count 758)

4. `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.

Watch now