search

JuliaNLSolvers / NLsolve.jl

Julia solvers for systems of nonlinear equations and mixed complementarity problems
Other
332 stars 66 forks source link

autodiff? #5

Closed mlubin closed 10 years ago

mlubin commented 10 years ago

In Optim, we've implemented forward-mode automatic differentiation for computing exact numerical gradients. It seems like this would be helpful for computing Jacobians here. If you're interested in incorporating this functionality into NLsolve, I'm happy to help out.

svillemot commented 10 years ago

@mlubin That sounds like a great idea. Does that completely supersede finite-differencing, or is there a reason for keeping both?

mlubin commented 10 years ago

Finite differences should still be kept as a fallback, but I think for most use cases, AD will work. The user function needs to satisfy two conditions:

  1. It must be written in pure Julia (it cannot call external C code)
  2. It must be written to take a generic Vector{T<:Number} input instead of Vector{Float64}.

The first condition has actually held back the use of AD in python, because it's very common to call C functions from python. In Julia, on the other hand, it's very reasonable to write everything in Julia.

Some extra background: To compute the Jacobian of a function R^n => R^m, forward mode AD needs O(n) function evaluations, while reverse-mode AD needs O(m) evaluations. Reverse-mode is more ideal for optimization, but it's trickier to implement (there's some work in progress, but no stable package yet).

Forward-mode is implemented by the DualNumbers package and is reasonably stable and integrated into Optim. The logic to compute a gradient is at https://github.com/JuliaOpt/Optim.jl/blob/master/src/autodiff.jl.