[SciPy-dev] Proposal for more generic optimizers (posted before on scipy-user)

[Matthieu Brucher]

>
> And one can easily make convenience functions which take standard
> arguments and package them internally.  I think that the interface
> should be flexible enough to allow users to just call the optimizers
> with a few standard arguments like they are used to, but allow users
> to "build" more complicated/more customized optimizers as they need.
> Also, it would be nice if an optimizer could be "tuned" to a
> particular problem (i.e. have a piece of code that tries several
> algorithms and parameter values to see which is fastest.)



Exactly.


> My immediate goal is to try and get the interface and module
> structure well defined so that I know where to put the pieces of my
> Broyden code when I rip it apart.


I can help you with it :)


One question about coupling: Useful criteria for globally convergent
> algorithms include testing the gradients and/or curvature of the
> function.


Simple, the criterion takes, for the moment, the current iteration number,
the former value, the current value, same for the parameters. It can be
modified to add the gradient if needed - I think the step would be a better
choice ? -


  In the Broyden algorithm, for example, these would be
> maintained by the "step" object,



but the criteria object would need
> to access these.



Access what exactly ?


  Likewise, if a "function" object can compute its
> own derivatives, then the "ceriterion" object should access it from
> there.



I don't think that the criterion need to access this, because it would mean
it knows more than it should, from an object-oriented point of view, but
this can be discussed :)


Any ideas on how to deal with these couplings?  Perhaps the
> "function" object should maintain all the state (approximate
> jacobians etc.).



I don't think so, the function provides methods to compute gradient,
hessian, ... but only the step object knows what to do with it : approximate
a hessian, what was already approximated, ... A step object is associated
with one optimizer, a function object can be optimized several times. If it
has a state, it couldn't be used with several optimizers without
reinitializing it, and it is not intuitive enough.

I've thinking about a correct architecture for several months now, and that
is what I think is a good one :
- a function to optimize that provides some method to compute the cost, the
gradient, hessian, ... only basic stuff
- an object that is responsible for the optimization, the glue between all
modules -> optimizer
- an object that tells if the optimization has converged. It needs the
current iteration number, several last values, parameters, perhaps other
things, but these things should be discussed
- an object that computes a new step, takes a function to optimize, can have
a state - to compute approximate hessian or inverse hessian
- a line search that can find a new candidate - section method, damped
method, no method at all, with a state (Marquardt), ...

With these five objects, I _think_ every unconstrained method can be
expressed. For the constraints, I suppose the step and the line search
should be adapted, but no other module needs to be touched.

I implemented the golden and fibonacci section, it's pretty straightforward
to add other line searches or steps, I'll try to add some before I submit it
on TRAC.

Matthieu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20070414/e4bd0f87/attachment.html>