Polling Types

Using a Complete Poll in a Generalized Pattern Search

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

[X,Y] = meshgrid(-6:.1:6,-6:.1:14);
Z = zeros(size(X));
for i = 1:size(X,1)
for j=1:size(X,2)
Z(i,j) = poll_example([X(i,j),Y(i,j)]);
end;end;
surf(X,Y,Z,'LineStyle','none');
view([-60,30])
annotation('textarrow',[0.24 0.38],...
    [0.11 0.47],'String',{'Local minimum at [0,9]'});
annotation('textarrow',[0.68 0.6],...
    [0.15 0.26],'String',{'Global minimum at [0,0]'});

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

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.

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

MATLAB returns a table of iterations and the solution.

x =

     0     9


fval =

   -16

The algorithm begins by a=evaluating the function at the initial point, f(0, 5) = 0. The poll evaluates the following during its first iterations.

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 UseCompletePoll to true and rerun the optimization.

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

This time, the pattern search finds the global minimum at (0, 0). The difference between this run and the previous one is that with UseCompletePoll set to true, 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.

 Code for generating the figure

function graph_poll_example

[X,Y] = meshgrid(-6:.1:14,-6:.1:14);
Z = zeros(size(X));
for i = 1:size(X,1)
    for j=1:size(X,2)
        Z(i,j) = poll_example([X(i,j),Y(i,j)]);
    end;
end;
contour(X,Y,Z);
hold on

h = plot(0,5,'ko');

opts = optimoptions('patternsearch','OutputFcn',@plotpnt,'UseCompletePoll',false);
[thex,thefv] = patternsearch(@poll_example,[0,5],...
    [],[],[],[],[],[],[],opts);

opts = optimoptions('patternsearch','OutputFcn',@plotpnt,'UseCompletePoll',true);
[thex,thefv] = patternsearch(@poll_example,[0,5],...
    [],[],[],[],[],[],[],opts);
hold off

legend([h,ff,tt],'Initial point','Complete poll off','Complete poll on')

line([0,6],[9,6],'Color','k','LineStyle','--')
line([0,6],[0,3],'Color','k','LineStyle','--')

text(6,6,'Local minimum')
text(6,3,'Global minimum')

function [stop,opts,optchanged] = plotpnt(optimvalues,opts,flag)
    if strcmp(flag,'iter')
        if isequal(opts.UseCompletePoll,true)
            tt = plot(optimvalues.x(1),optimvalues.x(2),'r+');
        else
            ff = plot(optimvalues.x(1),optimvalues.x(2),'b*');
        end
    end
stop = false;
optchanged = false;
end

end

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 Solve Using patternsearch in Optimize Live Editor Task. This linearly constrained problem has a quadratic objective function.

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];
   H = [36 17 19 12  8 15; 
        17 33 18 11  7 14; 
        19 18 43 13  8 16;
        12 11 13 18  6 11; 
         8  7  8  6  9  8; 
        15 14 16 11  8 29];
   
   f = [ 20 15 21 18 29 24 ]';
    
   fun = @(x)0.5*x'*H*x + f'*x;

2. Set the initial options and objective function.

   options = optimoptions('patternsearch',...
       'PollMethod','GPSPositiveBasis2N',...
       'PollOrderAlgorithm','consecutive',...
       'UseCompletePoll',false);

3. Run the optimization, naming the output structure outputgps2noff.

   [x,fval,exitflag,outputgps2noff] = patternsearch(fun,x0,...
       Aineq,bineq,Aeq,beq,[],[],[],options);

4. Set options to use a complete poll.

   options.UseCompletePoll = true;

5. Run the optimization, naming the output structure outputgps2non.

   [x,fval,exitflag,outputgps2non] = patternsearch(fun,x0,...
       Aineq,bineq,Aeq,beq,[],[],[],options);

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

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.

Alternatively, 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 UseCompletePoll to true generally lowers the number of iterations for GPS and GSS, but the change in number of function evaluations is unpredictable.

• Setting UseCompletePoll to true 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. 'GSSPositiveBasisNp1' with UseCompletePoll set to true (function count 491)

  2. 'GSSPositiveBasisNp1' with UseCompletePoll set to false (function count 533)

  3. 'GSSPositiveBasis2N' with UseCompletePoll set to false (function count 758)

  4. 'GSSPositiveBasis2N' with UseCompletePoll set to true (function count 889)

  The other poll methods had function counts exceeding 900.

• For this problem, the most efficient poll is 'GSSPositiveBasisNp1' with UseCompletePoll set to true, although the UseCompletePoll setting makes only a small difference. The least efficient poll is 'MADSPositiveBasis2N' with UseCompletePoll set to true. In this case, the UseCompletePoll setting makes a substantial difference.

Related Topics

• How Pattern Search Polling Works
• Searching and Polling
• Search and Poll