[SciPy-dev] Proposal for more generic optimizers (posted before on scipy-user)
Tue Apr 17 00:26:34 CDT 2007
I'll check them today, thanks for the tests too
2007/4/16, Ondrej Certik <email@example.com>:
> 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.
> On 4/16/07, Michael McNeil Forbes <firstname.lastname@example.org> 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
> > Scipyemail@example.com
> > http://projects.scipy.org/mailman/listinfo/scipy-dev
> Scipy-dev mailing list
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Scipy-dev