This is a rewrite of large-scale nonlinear equation solvers in scipy.optimize.

This is a rewrite of large-scale nonlinear equation solvers in scipy.optimize.

Git branch is here:

    http://github.com/pv/scipy-work/commits/ticket/791-optimize-nonlin-rewrite

You may want to try out the examples in the docstring of nonlin.py

The following new features are added

    - Proper termination conditions
    - Generic framework for tolerance-controlled inexact Newton methods
    - Backtracking and line searches
    - Limited-memory Broyden methods, including SVD rank reduction
      in addition to more basic options
    - Newton-Krylov solver, using any of the solvers from scipy.sparse.linalg

The new code API is mostly backward-compatible to the old one. Some
methods that were not very useful are deprecated. All of the code is
rewritten and refactored, aiming for easier maintenance.

The API may need some tuning still; should the method_name wrappers be
discarded, and the nonlin_solve(..., jacobian='foo') be the preferred
interface?

Note that this patchset includes some work in other parts of Scipy; these
are in review separately (so don't comment on those in this ticket):

    - LGMRES sparse solver
      http://codereview.appspot.com/53096/show
      http://github.com/pv/scipy-work/commits/lgmres

    - Line search refactoring
      http://codereview.appspot.com/52096
      http://github.com/pv/scipy-work/commits/linesearch-refactor

[pav, 2009-05-11 21:19:01]

Added small notes to myself.

http://codereview.appspot.com/62059/diff/1/8
File scipy/optimize/nonlin.py (right):

http://codereview.appspot.com/62059/diff/1/8#newcode351
Line 351: 
Maybe the memoization should be implemented in linesearch.py?

http://codereview.appspot.com/62059/diff/1/8#newcode389
Line 389: """
This termination condition should be checked against some good optimization
book: eg. how good termination criteria looking at the size of the Newton step
is? Is comparing the residual norm to the initial value OK?

I guess all of this is OK, but it doesn't hurt to check carefully.

Also, the docstring here is a bit misleading: `dx` is the estimated Newton step
what's being compared, and does not include the line search prefactor.

http://codereview.appspot.com/62059/diff/1/8#newcode460
Line 460: Returns A * V, where V is a dense matrix with dimensions (N,K).
I'm not sure, but maybe I should tone it down a bit with completeness in all
these `matvec` etc. methods. Basically, usually only `solve` is necessary, and
the rest can be useful only when the Jacobian approximations are used as
preconditioners.

Also, at least for the above example problem, the Broyden*/Anderson are not very
good preconditioners for the Krylov method...

http://codereview.appspot.com/62059/diff/1/8#newcode526
Line 526: """
Better docstring here.

http://codereview.appspot.com/62059/diff/1/8#newcode1123
Line 1123: class Vackar(GenericBroyden):
Is `Vackar` a good name for this method. I gather he was Ondrej's advisor...

[I wonder if we should include the umlauts and other Czech letter-wonders in the
name ;-]

http://codereview.appspot.com/62059/diff/1/8#newcode1292
Line 1292: >>> kjac = KrylovJacobian(inner_M=jac.inverse).
Should say here that the preconditioner can have the `update` and `setup`
methods, similarly as in a Jacobian. These are called for making the nonlinear
steps.

And the example and type descriptions are wrong.

http://codereview.appspot.com/62059/diff/1/8#newcode1472
Line 1472: 
Here I wonder if the API would be nicer with only one entry point function...

[pav, 2009-05-11 21:35:20]

And notes about missing tests.

http://codereview.appspot.com/62059/diff/1/8
File scipy/optimize/nonlin.py (right):

http://codereview.appspot.com/62059/diff/1/8#newcode219
Line 219: """
Maybe need at least one test without the line search?

Also, the termination criteria, `callback`and `iter` and `maxiter` have no
tests.

http://codereview.appspot.com/62059/diff/1/8#newcode765
Line 765: def svd_reduce(self, max_rank, to_retain=None):
These various reduction methods have no tests. Ditto for max_rank.

http://codereview.appspot.com/62059/diff/1/8#newcode1170
Line 1170: class LinearMixing(GenericBroyden):
No real tests for this...

http://codereview.appspot.com/62059/diff/1/8#newcode1210
Line 1210: class ExcitingMixing(GenericBroyden):
No real tests for this either

http://codereview.appspot.com/62059/diff/1/8#newcode1296
Line 1296: outer_k : int, optional
Maybe outer_k shouldn't be a kwarg for KrylovJacobian; use inner_* like the rest
of us...