[scilab-Users] Re: Simplex Algorithm

[Sébastien Bihorel]

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>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>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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.scilab.org/pipermail/users/attachments/20091016/6f0f97f1/attachment.htm>