[SciPy-dev] Proposal for more generic optimizers (posted before on scipy-user)
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.
On 4/16/07, Michael McNeil Forbes <email@example.com> 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
> 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.
> P.S. More comments to follow.
> Scipy-dev mailing list
More information about the Scipy-dev