[scilab-Users] Re: Simplex Algorithm
Yann Collette
yann.collette at scilab.org
Fri Oct 16 15:56:20 CEST 2009
Hello,
I got this algorithm on an old paper. I don't remember if it was the one
of nelder and mead or keeney.
If you are interested in using a "pure" fminseach equivalent, you can
try to use the scilab nightly build. Such a method has been added in the
optimization module.
But I will have a look at my code. I think I use only 2 points either
you are in 3 dims or not. I should use the n-1 points to compute the
centroid.
Once I will find the mistake, I will send you an email.
YC
Sébastien Bihorel a écrit :
> Thank you Jerome for you reply,
>
> With your explanation, Yann's, and after looking at the
> optim_nelder_mead code, I believe I have a fairly good idea of what is
> going on with this algorithm. One thing that I noticed in particular
> is that the reflexion in the optim_nelder_mead function is performed
> used the two best points and not the 'n other' points (like it is done
> in the Matlab fminsearch). Are you aware if this is an improvement to
> a older form of the algorithm as implemented in the fminsearch
> function, or if this is just a variant of the same algorithm?
>
> They are additional differences within the main algorithm (like how
> the expansion, shrink and contraction are done) that I don't quite
> grasp right now... still working on that.
>
> Sebastien
>
> On Wed, Oct 14, 2009 at 3:42 AM, Jerome PICARD
> <jerome.picard at scilab.org <mailto:jerome.picard at scilab.org>> wrote:
>
>
> Hi,
>
> Here are some explainations about simplex algorithm.
>
> At each iteration, the simplex algorithm evaluates the cost
> function at every vertex of a simplex. A simplex is the smallest
> convex set created with
> n + 1 points in a space of dimension n. At each iteration of the
> algorithm, a new simplex is created with the obtained simplex at
> the previous iteration.
>
> So, if you funcion is defined in a n-dimensional space, the
> algorithm needs at each iteration n + 1 points, which are the
> vertices given by the previous iteration. In your exemple, the
> cost function has 2 real variables, then the algorithm need at
> every iteration 3 points.
>
>
> Your second question is how the new simplex is calcutated?
>
> At every iteration, the cost function is calculated at every
> vertex of the simplex. Let's imagine we want to minimize the cost
> funtion. At every iteration, the algorithm eliminates the worst
> value of the cost function, i.e. in this case the greatest value
> of the n + 1 values calculated at every vertex. This eliminated
> point is now to replace with an other. The simplext way to create
> a new point is to take the simmetric point of the eliminated point
> by the affine space generated with the n other points.
>
> Therefore, the simplex algorithm is a quite simple algorithm, so
> it is a robust algorithm. We just have to compare n + 1 values at
> each iteration. Any derivative of the cost function (like for
> example in fmincon) need to be calculated. The simplex algorithm
> will just explore the definition space of the cost function with
> simplexes.
>
>
> Best regards
>
> Jérôme
>
>
> Sébastien Bihorel wrote:
>> Hi Yann,
>>
>> The installation worked just fine. I thank you again for your
>> explanations.
>>
>> Now, I would like to ask you a couple of more theoretical
>> questions on the algorithm implemented in the nm_init,
>> step_nelder_mead or optim_nelder_mead. I am not a mathematician
>> and don't know much about the theories, and the nuts and bolts of
>> the Nelder-Mead algorithm (this is probably a mistake!). My only
>> concern, until recently, was only to know how to use it in Matlab
>> using the fminsearch function... This function is nice for lay
>> users because one doesn't have to care about dealing with simplex
>> objects.
>> The simplex toolbox seem to require such objects to be created
>> and passed from one iteration to the other. From your
>> documentation and examples, it is my understanding that the
>> simplex contain realizations of the objective function at
>> different places of the search space. Am I correct here?
>>
>> Another thing I am not clear about is whether or not the
>> dimensions of the simplex should be adapted to a specific
>> problem. In the examples you provide, the simplex f_init and
>> f_current have a 3x1 dimension for optimizing 2 parameters. Is
>> that 3x1 dimension independent of the number of parameters to
>> optimize? Let's say my objective function is a 'maximum
>> likelihood function' of observations (n states observed at t
>> times) given a model dependent on m parameters and a residual
>> variability dependent on v parameters, what should be the size of
>> the simplex and how should it be calculated?
>>
>> Thanks in advance for your time and help.
>>
>> Sebastien
>>
>>
>>
>> On Tue, Oct 13, 2009 at 10:11 AM, Yann Collette
>> <yann.collette at scilab.org <mailto:yann.collette at scilab.org>> wrote:
>>
>> I will try to update the licence of simplex. I forgot to fill
>> this one. The licence will be GPL.
>>
>>
>> YC
>>
>> Sébastien Bihorel a écrit :
>>
>> Thank a lot for all this info... I will try that tonight
>> when I go back home.
>>
>>
>> One last question though about re-distribution of
>> simplex-2.0. I had look at the license.txt file but it
>> did not seem to contain any licensing terms related to
>> simplex-2.0. In case I would like to include this toolbox
>> in the distribution of one of my code/application, what
>> would be the requirements in terms of licensing? I intend
>> to distribute my piece of software under a GPL license...
>> would this be compatible with your license terms?
>>
>> Sebastien
>>
>>
>>
>>
>> --
>> -----------------------------
>> Yann COLLETTE
>> Software Development Engineer
>> -----------------------------
>> The Scilab Consortium
>> Digiteo Foundation
>> Domaine de Voluceau
>> Rocquencourt - B.P. 105
>> 78153 Le Chesnay France
>> Phone: +33.1.39.63.57.82
>>
>>
>
>
> --
> Jérôme Picard
> Ingénieur de développement
> -------------------------
> Consortium Scilab
> Digiteo
> Domaine de Voluceau
> Rocquencourt - B.P. 105
> 78153 Le Chesnay Cedex
> Tél. : 01.39.63.55.91
>
>
>
--
-----------------------------
Yann COLLETTE
Software Development Engineer
-----------------------------
The Scilab Consortium
Digiteo Foundation
Domaine de Voluceau
Rocquencourt - B.P. 105
78153 Le Chesnay France
Phone: +33.1.39.63.57.82
More information about the users
mailing list