Question about the fminsearch Algorithm

6 views (last 30 days)
Florian
Florian on 10 Aug 2022
Edited: Florian on 10 Aug 2022
Hallo Community,
the documentation
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.

Answers (3)

Walter Roberson
Walter Roberson on 10 Aug 2022
"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.
  5 Comments
Steven Lord
Steven Lord on 10 Aug 2022
I've reported this to the staff responsible for the Service Request submission page for investigation.

Sign in to comment.


Matt J
Matt J on 10 Aug 2022
Edited: Matt J on 10 Aug 2022
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

Bruno Luong
Bruno Luong on 10 Aug 2022
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

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!