Simplex Algorithm

[Jerome PICARD]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.scilab.org/pipermail/users/attachments/20091014/ff066d0c/attachment.htm>