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

Matthieu Brucher matthieu.brucher@gmail....
Tue Apr 17 00:26:34 CDT 2007


I'll check them today, thanks for the tests too

Matthieu

2007/4/16, Ondrej Certik <ondrej@certik.cz>:
>
> You might want to check my email (couple of days ago) about the
> broyden methods together with a python code and tests. I didn't have
> time to implement it in scipy yet, but you can already use it.
>
> Ondrej
>
> On 4/16/07, Michael McNeil Forbes <mforbes@physics.ubc.ca> wrote:
> > On 16 Apr 2007, at 12:27 PM, Matthieu Brucher wrote:
> >
> > > Basically, and approximated Jacobian is used to determine the step
> > > direction and/or size (depending on the "step" module etc.)
> > >
> > > The key to the Broyden approach is that the information about F(x+dx)
> > > is used to update the approximate Jacobian (think multidimensional
> > > secant method) in a clever way without any additional function
> > > evaluations (there is not a unique way to do this and some choices
> > > work better than others).
> > >
> > > Thus, think of Broyden methods as a Quasi-Newton methods but with a
> > > cheap and very approximate Jacobian (hence, one usually uses a robust
> > > line search method to make sure that one is always descending).
> > >
> > >
> > > I read some doc, it seems Broyden is a class of different steps, am
> > > I wrong ? and it tries to approximate the Hessian of the function.
> >
> > I am thinking of root finding G(x) = 0 right now rather than
> > optimization (I have not thought about the optimization problem
> > yet).  The way the Broyden root finder works is that you start with
> > an approximate Jacobian J0 (you could start with the identity for
> > example).
> >
> > So, start with an approximate J0 at position x0.
> >
> > G0 = G(x0)
> > dx = -inv(J0)*G0 # This is a Quasi-Newton step.  Use your favourite
> > step method here...
> > x1 = x0 + dx
> > G1 = G(x1)
> >
> > Now the Broyden part comes in.  It computes a new approximate
> > Jacobian J1 at position x1 using J0, dG and dX such that
> >
> > J1*dx = dG
> >
> > This is the secant condition.  There are many ways to do this in
> > multiple dimensions and the various Broyden methods choose one of
> > these.  The most common is the BFGS choice, but there are other
> > choices with different convergence properties.
> >
> > Now start over with J0 = J1 and x0 = x1 and repeat until convergence
> > is met.
> >
> > Michael.
> >
> > P.S. More comments to follow.
> > _______________________________________________
> > Scipy-dev mailing list
> > Scipy-dev@scipy.org
> > http://projects.scipy.org/mailman/listinfo/scipy-dev
> >
> _______________________________________________
> Scipy-dev mailing list
> Scipy-dev@scipy.org
> http://projects.scipy.org/mailman/listinfo/scipy-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://projects.scipy.org/pipermail/scipy-dev/attachments/20070417/29d8c286/attachment.html 


More information about the Scipy-dev mailing list