2
$\begingroup$

Is there any algorithm (or tricks) for rootfinding to take advantages of automatic differentiation (AD)?

Rootfinding algorithms typically solve $$ \mathbf{f}(\mathbf{y}) = \mathbf{0} $$ where $\mathbf{f}:\mathbb{R}^n\rightarrow\mathbb{R}^n$ and $\mathbf{y}:\mathbb{R}^n$.

Newton's method is not applicable in my case because the whole Jacobian does not fit in my memory while Broyden's method (one of the most popular method) usually doesn't converge.

I wonder if there's any way to take advantage of automatic differentiation in making root finder algorithm more stable or faster to converge (e.g. initializing the inverse of Jacobian with AD maybe?).

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ How large is $n$? Is the Jacobian sparse or dense? $\endgroup$
    – Brian Borchers
    Commented Sep 28, 2020 at 14:46
  • 1
    $\begingroup$ $n$ is typically 10^4-10^5 and constructing the full Jacobian is expensive. I'm not sure if it's sparse or dense, but the AD engine can provide the vector-Jacobian and Jacobian-vector product automatically. $\endgroup$
    – Firman
    Commented Sep 28, 2020 at 14:55
  • $\begingroup$ I haven't used AD, but it sounds like you can form the entries of the Jacobian on the fly as they are needed. If this is true, you could use this to express the Jacobian as an operator on a vector, which would let you use "matrix-free" iterative solver methods that rely on matrix-vector products (conjugate gradient, GMRES, etc). Not sure if this is what @BrianBorchers meant by "interactive methods" $\endgroup$
    – Charlie S
    Commented Sep 28, 2020 at 17:55
  • $\begingroup$ Sorry for the typo. "interactive" should have been "iterative" in my answer. $\endgroup$
    – Brian Borchers
    Commented Sep 28, 2020 at 18:01
  • 2
    $\begingroup$ @BrianBorchers Didn't mean to be snooty, I actually googled "interactive methods" as I assumed it was some state of the art concept! $\endgroup$
    – Charlie S
    Commented Sep 28, 2020 at 19:28

1 Answer 1

Reset to default
1
$\begingroup$

There's a good discussion of globalization strategies for Newton's method root finding in Numerical Methods for Unconstrained Optimization and Nonlinear Equations by J. E. Dennis, Jr. and Robert B. Schnabel. See section 6.5 in particular.

Dennis and Schnabel advocate treating the problem of finding a root of $f(p)=0$ as a nonlinear least squares problem:

$\min \sum_{i=1}^{n} f_{i}(p)^{2}$

You can apply Newton's method for minimization of this least squares problem with a globalization strategy (line search, trust region, Levenberg-Marquardt, etc.) These globalization strategies make sense when the problem is converted to least squares form. You could solve the Newton's method equations in each iteration using an iterative method based on the Jacobian-vector multiplications provided by your AD tool. For example, the Newton-Krylov method uses a Krylov subspace method to solve the equations.

Another approach would be to directly solve the nonlinear least-squares problem using an iterative method for unconstrained nonlinear minimization such as conjugate gradients, limited memory BFGS, etc. All of these require gradient computations, which in turn boil down to multiplying the Jacobian times $f(p)$. Your AD tool should be able to help with that.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.