Question about the fminsearch Algorithm
Show older comments
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
on 10 Aug 2022
0 votes
"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
on 10 Aug 2022
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.
Steven Lord
on 10 Aug 2022
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.
Steven Lord
on 10 Aug 2022
I've reported this to the staff responsible for the Service Request submission page for investigation.
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
opts=optimset('Display','iter');
[x6,fval6]=fminsearch(FUN,initialSimplex,opts)
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)
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
Categories
Find more on Programming in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
