Question about the fminsearch Algorithm

Hallo Community,

the documentation

https://de.mathworks.com/help/matlab/math/optimizing-nonlinear-functions.html#bsgpq6p-11

states the following:

"fminsearch uses the Nelder-Mead simplex algorithm as described in Lagarias et al. [1]. This algorithm uses a simplex of n + 1 points for n-dimensional vectors x. The algorithm first makes a simplex around the initial guess x0 by adding 5% of each component x0(i) to x0. The algorithm uses these n vectors as elements of the simplex in addition to x0. (The algorithm uses 0.00025 as component i if x0(i) = 0.) Then, the algorithm modifies the simplex repeatedly according to the following procedure."

So now I wanted to know if I get this right:

Let's say my objective function looks like this

So the simplex consists of 2+1 points. These 3 points are

These 3 vectors make up the simplex, in this case the triangle.

So, first I wanted to know if my thoughts are correct?

If my description is correct, I wonder about two things:

1. Intuitively I would say that it would be more effective if the simplex is actually build AROUND x0. Because in this algorithm the simplex isn't really build around x0 but rather includes x0 to make up the simplex.

2. Is there a way for me to actually set up the starting simplex by myself? So that instead of giving the fminsearch-solver an initial guess x0, I create the starting simplex with the 3 Vectors

and I get to choose how the components of the vectors look like.

Answer 1

[Walter Roberson]

"So, first I wanted to know if my thoughts are correct?"

Yes.

"Intuitively I would say that it would be more effective if the simplex is actually build AROUND x0."

Not really. If the surrounding points are higher than x0 then you will immediately project backwards.

The ability to provide coordinates for the initial simplex would matter most in the case that x0 is close to a constraint boundary, in which case you would need more details about what happens if the initial generated coordinates are outside of the boundary.

[Steven Lord]

The ability to provide coordinates for the initial simplex would matter most in the case that x0 is close to a constraint boundary

And since fminsearch is intended to "Find minimum of unconstrained multivariable function using derivative-free method" (emphasis added) that doesn't seem to apply.

To @Florian, there's a picture at the end of that documentation page to which you linked that shows some of the points computed during the algorithm. Does that picture help clarify what each of those operations are doing?

If there is additional information (or additional pictures) that you think would help you or others better understand what fminsearch does please vote for a number of stars at the end of the page, below the "How useful was this information?" question. Once you've done that a text box will appear where you can write feedback on the page that will be sent to the documentation staff responsible for that page.

[Florian]

@Steven Lord The picture does help but I think it does not answer any of my questions, or am I wrong?

Yes there are some small things I would change in that documentation page which I have linked.

Since you are one of the Staff members of MathWorks, could you answer my questions in the original post please?

[Steven Lord]

I am a MathWorks staff member, but I don't work on the fminsearch function directly. As far as I'm aware fminsearch does not allow you to control the initial simplex; if it did, likely that would be done by specifying one or more options using optimset and I see no options that appear relevant in that section of the documentation page.

If you provide feedback on that page it will go directly to the members of the documentation staff responsible for that page. Or if you have questions about how the function works and want an "official" response you could create a service request which would be routed to the appropriate Technical Support staff, and they can contact the developers responsible for fminsearch if necessary.

[Florian]

@Steven Lord when I try to submit the service request I get an error message saying:

"Die Webseite unter https://servicerequest.mathworks.com/mysr/cp_case_new_ts_opt21 ist eventuell vorübergehend nicht verfügbar oder wurde dauerhaft an eine neue Webadresse verschoben."

Thats german (I am from germany) and it means:

"The website https://servicerequest.mathworks.com/mysr/cp_case_new_ts_opt21 may be temporarily unavailable or may have been permanently moved to a new web address."

Do you have any suggestions? 😅😅

[Steven Lord]

I've reported this to the staff responsible for the Service Request submission page for investigation.

Answer 2

[Matt J]

Is there a way for me to actually set up the starting simplex by myself? So that instead of giving the fminsearch-solver an initial guess x0, I create the starting simplex with the 3 Vectors

You might be able to something approximately like this by formulating as a 6D problem:

objective=@(z) norm(z).^2;

FUN=@(x) min(  [ objective(x(1:2)),  objective(x(3:4)),  objective(x(5:6))]  );

initialSimplex=[0,0,  0,1,  1,0]-0.5

initialSimplex = 1×6

-0.5000 -0.5000 -0.5000 0.5000 0.5000 -0.5000

opts=optimset('Display','iter');

[x6,fval6]=fminsearch(FUN,initialSimplex,opts)

 
 Iteration   Func-count     min f(x)         Procedure
     0            1              0.5         
     1            7              0.5         initial simplex
     2            9         0.465156         expand
     3           11         0.433789         expand
     4           12         0.433789         reflect
     5           13         0.433789         reflect
     6           14         0.433789         reflect
     7           16         0.383347         expand
     8           17         0.383347         reflect
     9           18         0.383347         reflect
    10           20         0.320026         expand
    11           21         0.320026         reflect
    12           23         0.252827         expand
    13           24         0.252827         reflect
    14           25         0.252827         reflect
    15           27         0.162245         expand
    16           29         0.090087         expand
    17           30         0.090087         reflect
    18           32        0.0234379         expand
    19           33        0.0234379         reflect
    20           35         0.012961         expand
    21           37        0.0129221         reflect
    22           38        0.0129221         reflect
    23           39        0.0129221         reflect
    24           41        0.0129221         contract inside
    25           43        0.0129221         contract inside
    26           45        0.0129221         contract inside
    27           47        0.0108882         contract inside
    28           49       0.00628487         contract inside
    29           51       0.00628487         contract inside
    30           53       0.00628487         contract outside
    31           55       0.00628487         contract inside
    32           57       0.00628487         contract inside
    33           59       0.00628487         contract inside
    34           60       0.00628487         reflect
    35           62       0.00580298         reflect
    36           64       0.00580298         contract inside
    37           66       0.00202129         expand
    38           68      0.000742635         expand
    39           69      0.000742635         reflect
    40           71      0.000742635         contract outside
    41           72      0.000742635         reflect
    42           74      0.000124584         reflect
    43           76      0.000124584         contract inside
    44           77      0.000124584         reflect
    45           79      0.000124584         contract inside
    46           80      0.000124584         reflect
    47           81      0.000124584         reflect
    48           82      0.000124584         reflect
    49           84      0.000124584         contract inside
    50           86      2.16758e-05         reflect
    51           87      2.16758e-05         reflect
    52           88      2.16758e-05         reflect
    53           90      2.16758e-05         contract inside
    54           92      2.16758e-05         contract inside
    55           94      2.16758e-05         contract inside
    56           96      2.16758e-05         contract inside
    57           98      2.16758e-05         contract inside
    58          100      2.16758e-05         contract inside
    59          102      2.16758e-05         contract inside
    60          104      2.16758e-05         contract inside
    61          106      2.16758e-05         contract inside
    62          108      1.28725e-05         contract inside
    63          110      7.21568e-06         contract inside
    64          112      7.21568e-06         contract inside
    65          114      7.21568e-06         contract inside
    66          116      7.21568e-06         contract inside
    67          118      4.88674e-06         contract inside
    68          120      3.76706e-06         contract inside
    69          122      1.62205e-06         contract inside
    70          124      1.62205e-06         contract inside
    71          125      1.62205e-06         reflect
    72          127      1.32195e-06         contract inside
    73          129      1.03481e-06         contract inside
    74          131      1.03481e-06         contract outside
    75          133      1.03481e-06         contract outside
    76          135      8.17236e-07         contract inside
    77          137      3.99212e-07         contract inside
    78          139      3.50704e-07         contract inside
    79          141      2.10119e-07         contract inside
    80          143      1.99695e-07         contract inside
    81          144      1.99695e-07         reflect
    82          146      1.99695e-07         contract inside
    83          148      1.16567e-07         contract inside
    84          150      1.16567e-07         contract outside
    85          152      5.57791e-08         contract inside
    86          154      5.57791e-08         contract inside
    87          156      3.89366e-08         contract inside
    88          157      3.89366e-08         reflect
    89          159      3.41839e-08         contract inside
    90          161      3.28176e-08         contract inside
    91          163      2.44977e-08         contract inside
    92          165      1.94222e-08         contract inside
    93          167      1.43425e-08         contract inside
    94          169      1.18402e-08         contract inside
    95          171      7.59637e-09         contract inside
    96          173      5.49746e-09         contract inside
    97          175      5.49746e-09         contract inside
    98          177      5.33845e-09         contract inside
    99          179      4.09103e-09         contract inside
   100          181      2.65686e-09         contract inside
   101          183      2.42941e-09         contract inside
   102          185      1.34257e-09         contract inside
   103          187      1.34257e-09         contract inside
   104          189      8.62749e-10         contract inside
   105          191      8.62749e-10         contract inside
 
Optimization terminated:
 the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-04 
 and F(X) satisfies the convergence criteria using OPTIONS.TolFun of 1.000000e-04 

x6 = 1×6

-0.4728 -0.7862 -0.6902 0.6904 0.0000 -0.0000

fval6 = 8.6275e-10

Is this better than formulating as a 2D problem? Not sure. We got to almost the same cost value in fewer iterations, each one less costly than the corresponding 6D iteration.

[x2,fval2]=fminsearch(objective,initialSimplex(1:2),opts)

 
 Iteration   Func-count     min f(x)         Procedure
     0            1              0.5         
     1            3              0.5         initial simplex
     2            4              0.5         reflect
     3            6         0.451562         expand
     4            7         0.451562         reflect
     5            9          0.36125         expand
     6           10          0.36125         reflect
     7           12         0.211562         expand
     8           13         0.211562         reflect
     9           15          0.03125         expand
    10           16          0.03125         reflect
    11           18        0.0115625         reflect
    12           19        0.0115625         reflect
    13           21          0.00125         contract inside
    14           22          0.00125         reflect
    15           24          0.00125         contract inside
    16           26      0.000332031         contract outside
    17           28      0.000235596         contract inside
    18           30      9.95636e-05         contract inside
    19           32      9.34649e-05         contract inside
    20           34       5.7607e-05         contract outside
    21           36      1.83647e-05         contract inside
    22           38      5.17057e-06         contract inside
    23           40       3.4768e-06         contract outside
    24           42      1.47622e-06         contract inside
    25           44      8.47243e-07         contract outside
    26           46      3.56663e-07         contract inside
    27           48      3.56663e-07         contract inside
    28           50      1.95547e-07         reflect
    29           52      2.43523e-08         contract inside
    30           54      2.43523e-08         contract outside
    31           56      2.43523e-08         contract inside
    32           58      1.59256e-08         contract inside
    33           60      8.71229e-09         contract inside
    34           62      9.22393e-10         contract inside
    35           63      9.22393e-10         reflect
    36           65      9.22393e-10         contract inside
 
Optimization terminated:
 the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-04 
 and F(X) satisfies the convergence criteria using OPTIONS.TolFun of 1.000000e-04 

x2 = 1×2

1.0e-04 * -0.2852 -0.1043

fval2 = 9.2239e-10

Answer 3

[Bruno Luong]

fminsearch is an mfile, you can copy it then mofify these lines #196 (R2022a)

% Set up a simplex near the initial guess.
% PUT HERE X == YOUR INITIAL GUESS #1
xin = x(:); % Force xin to be a column vector
v = zeros(n,n+1); fv = zeros(1,n+1);
v(:,1) = xin;    % Place input guess in the simplex! (credit L.Pfeffer at Stanford)
x(:) = xin;    % Change x to the form expected by funfcn
fv(:,1) = funfcn(x,varargin{:});

and #259 (R2022a)

% Continue setting up the initial simplex.
% Following improvement suggested by L.Pfeffer
 at Stanford
usual_delta = 0.05;             % 5 percent deltas for non-zero terms
zero_term_delta = 0.00025;      % Even smaller delta for zero elements of x
for j = 1:n
    y = xin;
    if y(j) ~= 0
        y(j) = (1 + usual_delta)*y(j);
    else
        y(j) = zero_term_delta;
    end
    % PUT HERE Y == YOUR INITIAL GUESS #2 3
    v(:,j+1) = y;
    x(:) = y; f = funfcn(x,varargin{:});
    fv(1,j+1) = f;
end