[Matrix-SIG] Some optimization routines.

[Andrey Kaliazin]

Hi  Travis,
you are doing a great job!

I've spent some time on these problems with many variables.
From 1 to ~200 (I'd like more, but my PC became too slow :)

When number of variables exceed 10-20, depending on a problem,
there is NO one best subroutine, definitely, and powerful second-order ones,
like BFGS, Newton-Raphson, etc, became less and less useful.
They are only good near the local extremum but you have to find it first.
Modern techniques for many-variables optimization are
1. Simulated Annealing (SA)
ASA <http://www.ingber.com/#ASA-INFO>
or SIMANN - both are in the OPT pack from NETLIB,
2. Genetic Algorithms (GA) - look for example at
<http://www-xdiv.lanl.gov/XCM/research/genalg/ga.html>
3. Of course general and specific N-dimensional Monte-Carlo methods.

Andy


----- Original Message -----
From: Ryszard Czerminski <ryszard@moldyn.com>
To: Travis Oliphant <Oliphant.Travis@mayo.edu>
Cc: <matrix-sig@python.org>


>
> As you pointed out performance and applicability of
> various optimization routines is very much problem
> dependent, therefore you need to look for "best" algorithms
> (and implementations!) in different categories.
>
> I comment here only on unconstrained, local minimization
> problems:
>
> general non-linear functions:
>
> (1) derivatives not available - SIMPLEX and conjugate
>     direction methods (but I do not know about their relative merit)
> (2) first derivatives available - conjugate gradient
>     (Polak-Ribiere variant)
> (3) first and second derivatives available - Newton-Raphson
>
> for least-square problems methods which exploit explicitly
> structure of the objective function are more effective
> e.g. Levenberg-Marquardt method
>
> Above list is probably not very complete - even only
> for unconstrained, local minimization problems.
>
> There is a very nice overview in
> http://www-fp.mcs.anl.gov/otc/Guide/OptWeb.
>
> Ryszard Czerminski         phone : (617)354-3124 x 10
> Moldyn, Inc.               fax   : (617)491-4522
> 955 Massachusetts Avenue   e-mail: ryszard@moldyn.com
> Cambridge MA, 02139-3180   http://www.moldyn.com
>
> On Wed, 14 Apr 1999, Travis Oliphant wrote:
>
> >
> > A while back there was talk about optimization routines.  I just
> > downloaded a lot of them from the subdirectory /opt on netlib
> > (constrained, unconstrained, nonlinear ...) I would like to include an
> > appropriate set of these (eventually) in the multipack module that I'm
> > constructing.
> >
> > I'd like to start with one that minimizes a function of N variables and
> > am interested to hear what people on this list have to say about the
> > appropriateness of one algorithm versus another.  I know that's a hard
> > question given that optimization is so problem-dependent.  That's why I
> > eventually want to add a number of them.  So, what are the "good" ones.
> >
> > Regards,
> >
> > Travis
> >
> >
> >
> > _______________________________________________
> > Matrix-SIG maillist  -  Matrix-SIG@python.org
> > http://www.python.org/mailman/listinfo/matrix-sig
> >
>
>
> _______________________________________________
> Matrix-SIG maillist  -  Matrix-SIG@python.org
> http://www.python.org/mailman/listinfo/matrix-sig
>