[SciPy-User] Optimisation of a rough function

[David Baddeley]

Thanks everyone! Implicit filtering definitely sounds like it might be a step in 
the right direction.

To address some of the previous comments, the goal function is normally quite 
costly, making the brute force type of method somewhat impractical. To give you 
a bit more insight, I'm transforming a set of (x,y) points, calculating a 
triangularisation of the transformed point set, and calculating the product of 
all the edge lengths in that triangularisation. I'm trying to find parameters 
for the transformation which minimise this product. The goal surface I plotted 
was for a simplified case - 100 points and a simple linear transformation (ie 2 
parameters). In normal applications I'll be looking at ~100k points, and a 
non-linear transformation (~10 parameters). 

cheers,
David


----- Original Message ----
From: Dominique Orban <dominique.orban at gmail.com>
To: scipy-user at scipy.org
Sent: Sun, 3 April, 2011 4:25:43 AM
Subject: Re: [SciPy-User] Optimisation of a rough function

> Date: Sat, 2 Apr 2011 11:41:17 +0200
> Subject: Re: [SciPy-User] Optimisation of a rough function
> On Fri, Apr 01, 2011 at 11:04:15PM -0700, David Baddeley wrote:
>> there are enough optimisation gurus here that hopefully someone might
>> have some ideas. I'm trying to optimise a goal function that has a well
>> defined minimum, but also a certain amount of roughness (see attached
>> figure for an example). Most of the time (80%) optimize.fmin seems to
>> work, but it sometimes gets stuck in the roughness. optimise.anneal
>> works, but needs many more function evaluations, making it a bit
>> impractical (the goal is to be semi-interactive & the fmin
>> implementation already struggles). The goal function is quite complex
>> and already written in c. I'm really after some form of solver which
>> will skip over all the little bumps, but still benefits from using the
>> gradient information. Should probably also mention that it will usually
>> have ~ 10 parameters, rather than the 2 parameter case shown, but that
>> the same features should be present.

You have a noisy optimization problem. Not sure if it will solve your
problem but you want to look into implicit filtering:
http://www4.ncsu.edu/~ctk/imfil.html

(don't know if there's a Python version of this).

The method is described in Tim Kelley's book:

http://www.siam.org/books/kelley/fr18/index.php

-- 
Dominique
_______________________________________________
SciPy-User mailing list
SciPy-User at scipy.org
http://mail.scipy.org/mailman/listinfo/scipy-user