This is the mail archive of the
gsl-discuss@sources.redhat.com
mailing list for the GSL project.
Re: looking for algorithm
- From: Ed Hill <ed at eh3 dot com>
- To: "Charles P. Reese" <creese at engineering dot ucsb dot edu>, gsl-discuss at sources dot redhat dot com
- Date: 26 Aug 2002 17:07:55 -0600
- Subject: Re: looking for algorithm
- References: <1030400769.4912.3.camel@localhost>
On Mon, 2002-08-26 at 16:26, Charles P. Reese wrote:
> Hi,
>
> I didn't see this in the GSL manual, but I thought I would ask anyway.
> I'm looking for a multidimensional minimization algorithm that does not
> require evaluation of the gradient. I would like something compatible
> with the GPL because I want to release code under that license, but at
> this point I will take anything that works.
Hi Charles,
Why no gradients? Is it because your objective function has some
fundamental "noise" to it (so that local gradients are misleading) or is
it just because you don't have them handy?
In the former case, good approaches include the Nelder-Mead ("amoeba"),
IFFCO, and related algorithms [0]. Nelder-Mead is relatively easy to
code and does remarkably well on a wide variety of "noisy" optimization
problems (it does "implicit filtering" [1]). I have a version of it
coded in C++ thats part of one of my pet projects [2] and I've been
meaning to implement a version of it within the GSL framework. Let me
know if you'd like to take this approach and I'll try to get it coded
soon...
If the objective function is relatively smooth, then you probably should
compute and use the gradients as it will tend to speed up convergence.
You can compute gradients using finite difference methods. In fact,
many commercial optimization programs have an option that tell them to
compute the gradients for you automatically. I'm not very familiar with
the GSL optimization code, but perhaps automatic gradient calculations
could be (or already have been?) implemented.
hth,
Ed
[0] http://mathworld.wolfram.com/Nelder-MeadMethod.html
[1] http://www4.ncsu.edu/~ctk/iffco.html
[2] http://qaxa.sourceforge.net
--
Edward H. Hill III, PhD
Post-Doctoral Researcher | Email: ed@eh3.com, ehill@mines.edu
Division of ESE | URLs: http://www.eh3.com
Colorado School of Mines | http://cesep.mines.edu/people/edhill.php
Golden, CO 80401 | Phone: 303-273-3483 Fax: 303-273-3311