High-dimensional Minimization without analytical derivatives

[Ivo Alxneit]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday 04 September 2004 10:33 am, Joakim Hove wrote:
> "Anatoliy Belaygorod" <belaygorod@wustl.edu> writes:
> > My understanding is that 'in general' in high-dimensional cases with
> > rough surface, the Simulated Annealing (SA) method is better tuned
> > for finding a GLOBAL maximum , than Gradient-based methods, because
> > the latter are better tuned for 'zeroing in' the local maximums.  In
> > that regard, is Simplex Method closer to SA, or Gradient-based
> > methods?
>
> Well, excuse me if I am completely off base, but as far as I am aware
> the simplex method is restricted to *linear* problems - where it is
> 'guaranteed' to find the optimial solution. Gradient based methods and
> SA can be used for more general (nonlinear) problems, but can really
> not be compared to the two.
>
> JH

i think you refer to the simplex algorithm of linear programming. the 
algorithm of nelder and mead is something quite different (i am, however, not 
sure whether the same name was really chosen by coincidence). nelder mead 
does work to find minimas of a multidimensional (non-linear) surface.

with regard to the original question: both, nelder mead simplex or a gradient 
based method, will never guarantee that the minimum found (IF one is found) 
is a global one. you can easyly see that both do not even find the nearest by 
minimum (just construct a surface that has the same function values and maybe 
gradients at the points evaluated and then insert a local minimum somewhere 
between these point. both algorithms will just skip over it if the same 
starting point is used again) . you can become "quite" sure if you try a lot 
of different starting points and try to find other minimas. but this is 
expensive. the only methode i know of that is quite reliable to find a global 
minimum is simulated annealing which is really expensive. even in simulated 
annealing it can be tricky (or time consuming) to set up a reliable cooling 
strategy that produces the global minimum. 
- -- 
Dr. Ivo Alxneit
Laboratory for Solar Technology   phone: +41 56 310 4092
CH-5232 Villigen                    fax: +41 56 310 2624
Paul Scherrer Institute          http://solar.web.psi.ch
Switzerland                        gnupg key: 0x515E30C7
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQFBOgbPAd7CE1FeMMcRAioFAKDL43oL3+FsjWYVHb+f9jPGQduiXgCfZu22
xV72TKidWOh6KFB1cxNx/pA=
=0BXv
-----END PGP SIGNATURE-----