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

Ondrej Certik ondrej@certik...
Mon Apr 16 16:29:54 CDT 2007


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
>


More information about the Scipy-dev mailing list