looking for algorithm

looking for algorithm

[Charles P. Reese]

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.

Thanks,

-- 
Charles Reese
Electrical and Computer Engineering Department
University of California
Santa Barbara, CA 93106
Voice: 805/893-4353
Fax:    805/893-3262
E-mail: creese@engr.ucsb.edu

Re: looking for algorithm

[Ed Hill]

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

Re: looking for algorithm

[Jacek Pliszka]

On 26 Aug 2002, Charles P. Reese wrote:

> I'm looking for a multidimensional minimization algorithm that does not
> require evaluation of the gradient.  I would like something compatible

My favorite is Brent's Praxis.

I even started writing one for GSL but I have two other projects I am
paid for which have to be finished first.

However I do have 2 or 3 implementations of this algorithm which I can
send you. Some are in C some in Fortran.

If you know how to pick the best one and you are not afraid to play with 
the code - get them here:

http://phyun0.ucr.edu/~pliszka/praxis.tar.bz2

It contains: praxis.orig - original versions.
praxis - my working copies together with my version - does not
work yet though I think I wrote the whole algorithm already.

Good luck,

Jacek